Smalltalk › Squeak › Squeak - Dev

About MappedCollection

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

24 messages Options

Damien Cassou-3

About MappedCollection

Hi,

does any of you use MappedCollection? Would it be a problem to remove
it from the image?

Bye

--
Damien Cassou

Lukas Renggli

Re: About MappedCollection

> does any of you use MappedCollection? Would it be a problem to remove
> it from the image?

No, I never used MappedCollection, but I wondered several times about
all the ugly extension this collection class creates throughout the
object hierarchy. Please remove, or unload into a separate package.

Cheers,
Lukas

--
Lukas Renggli
http://www.lukas-renggli.ch

Nicolas Cellier-3

Re: About MappedCollection

In reply to this post by Damien Cassou-3

Damien Cassou a écrit :
> Hi,
>
> does any of you use MappedCollection? Would it be a problem to remove
> it from the image?
>
> Bye
>

I used them once upon a time in st-80 ages. Never since.
I would not miss them.

They disappeared quite early from Parplace images (objectworks i think).

Using Smalltalk living organism metaphor, I think they are still here
simply because they are not competing. Thus, they do not enter in the
selection process. Unless we put selective rules on dead code like
you're proposing.
How many % of our DNA is really used? You can answer this question at
the scale of an individual life, or at the scale of hundreds of
generations. Maybe they could make an advantage in a future mutation.
They could as well disappear, or be frozen in a data bank. It's not easy
to play god.

Are Stack and SkipList more used?

Even Bag is rarely used.
LinkedList (Process only).
Heap (WorldState, Zip).

Are there metrics to measure success of a class?
Number of references?
Number of senders of factory messages?
Number of instances in images?
Number of instances garbage collected?

Nicolas

Nicolas Cellier-3

Re: About MappedCollection

In reply to this post by Lukas Renggli

Lukas Renggli a écrit :

>> does any of you use MappedCollection? Would it be a problem to remove
>> it from the image?
>
> No, I never used MappedCollection, but I wondered several times about
> all the ugly extension this collection class creates throughout the
> object hierarchy. Please remove, or unload into a separate package.
>
> Cheers,
> Lukas
>

which extension?

Nicolas

Damien Pollet

Re: About MappedCollection

In reply to this post by Nicolas Cellier-3

On 24/05/07, nicolas cellier <[hidden email]> wrote:
> Are Stack and SkipList more used?
>
> Even Bag is rarely used.

I did use it

> LinkedList (Process only).
> Heap (WorldState, Zip).

We were discussing that squeak lacks some base data structures like
hash tables or balancing trees... not useful that often, but needed
for algorithmic code and difficult to write properly.

--
Damien Pollet
type less, do more [ | ] http://typo.cdlm.fasmz.org

J J-6

Re: About MappedCollection

SkipLists sound cool as well. One of those things that you see moving
around in the image and try to remember it for later. Because it doesn't
come up much, but if it does it could really save some time.

>From: "Damien Pollet" <[hidden email]>
>Reply-To: The general-purpose Squeak developers
>list<[hidden email]>
>To: "The general-purpose Squeak developers
>list"<[hidden email]>
>Subject: Re: About MappedCollection
>Date: Thu, 24 May 2007 22:02:23 +0200
>
>On 24/05/07, nicolas cellier <[hidden email]> wrote:
>>Are Stack and SkipList more used?
>>
>>Even Bag is rarely used.
>
>I did use it
>
>>LinkedList (Process only).
>>Heap (WorldState, Zip).
>
>We were discussing that squeak lacks some base data structures like
>hash tables or balancing trees... not useful that often, but needed
>for algorithmic code and difficult to write properly.
>
>--
>Damien Pollet
>type less, do more [ | ] http://typo.cdlm.fasmz.org
>

_________________________________________________________________
More photos, more messages, more storageget 2GB with Windows Live Hotmail.
http://imagine-windowslive.com/hotmail/?locale=en-us&ocid=TXT_TAGHM_migration_HM_mini_2G_0507

Lukas Renggli

Re: About MappedCollection

In reply to this post by Nicolas Cellier-3

> > No, I never used MappedCollection, but I wondered several times about
> > all the ugly extension this collection class creates throughout the
> > object hierarchy. Please remove, or unload into a separate package.
>
> which extension?

Sorry, I confused something.

Lukas

--
Lukas Renggli
http://www.lukas-renggli.ch

Lukas Renggli

Re: About MappedCollection

In reply to this post by Damien Pollet

> We were discussing that squeak lacks some base data structures like
> hash tables or balancing trees... not useful that often, but needed
> for algorithmic code and difficult to write properly.

There are special collection implementations available on
SqueakSource. The following BTree implementation is especially useful
in the context of OODBs:

http://www.squeaksource.com/BTree.html

Lukas

--
Lukas Renggli
http://www.lukas-renggli.ch

Chris Muller-3

Re: About MappedCollection

I'll add, BTree's useful outside of OODB's too.

On 5/24/07, Lukas Renggli <[hidden email]> wrote:

> > We were discussing that squeak lacks some base data structures like
> > hash tables or balancing trees... not useful that often, but needed
> > for algorithmic code and difficult to write properly.
>
> There are special collection implementations available on
> SqueakSource. The following BTree implementation is especially useful
> in the context of OODBs:
>
> http://www.squeaksource.com/BTree.html
>
> Lukas
>
> --
> Lukas Renggli
> http://www.lukas-renggli.ch
>
>

Lukas Renggli

Re: About MappedCollection

In reply to this post by Lukas Renggli

> > > No, I never used MappedCollection, but I wondered several times about
> > > all the ugly extension this collection class creates throughout the
> > > object hierarchy. Please remove, or unload into a separate package.
> >
> > which extension?
>
> Sorry, I confused something.

Now I found it again:

#hashMappedBy: and #identityHashMappedBy:

The names made me think it has something to do with MappedCollection,
but that's probably not the case. Either-way, there are no real
senders of these methods. I would suggest removing them, unless
somebody objects ...

Lukas

--
Lukas Renggli
http://www.lukas-renggli.ch

Lukas Renggli

Re: About MappedCollection

In reply to this post by J J-6

> SkipLists sound cool as well. One of those things that you see moving
> around in the image and try to remember it for later. Because it doesn't
> come up much, but if it does it could really save some time.

SkipLists are cool as an implementation exercise for students, but I
doubt they have much practical use. Also their efficiency (memory and
space wise) is disputed:
http://resnet.uoregon.edu/~gurney_j/jmpc/skiplist.html. I would remove
them, I know of nobody that ever used a SkipList.

> Even Bag is rarely used.
> LinkedList (Process only).
> Heap (WorldState, Zip)

Bag is useful. LinkedList and Heap are not generic collections, they
are targeted at specific problems like scheduling and data
compression.

Lukas

--
Lukas Renggli
http://www.lukas-renggli.ch

Avi Bryant-2

Re: About MappedCollection

In reply to this post by Chris Muller-3

On 5/24/07, Chris Muller <[hidden email]> wrote:
> I'll add, BTree's useful outside of OODB's too.

Yes, to be specific: it's useful any time you need a Dictionary-like
collection where the keys are Magnitudes (ie, implement #<=).

What you get: efficient sorted iteration through the keys, possibly
limited to a given range. For example, if you store a list of people
keyed by their birthdate, and then want to find everyone born in a
certain year, in order of birth, you can do that very fast.

Also in the BTree package is a TSTree, which has similar properties
for String keys. So as well as keeping them sorted, you can do
efficient lookups of all the keys with a given prefix. One other neat
trick TSTree can do is a certain amount of fuzzy matching (eg find all
keys with an edit distance of 3 from 'foo') which makes it especially
useful for spell checking and similar applications.

Avi

Damien Cassou-3

Re: About MappedCollection

In reply to this post by Lukas Renggli

2007/5/25, Lukas Renggli <[hidden email]>:
> Bag is useful. LinkedList and Heap are not generic collections, they
> are targeted at specific problems like scheduling and data
> compression.

To me, LinkedLists are useful when you want a sequenceable collection
with removal and insertion functionalities.

--
Damien Cassou

Nicolas Cellier-3

Re: About MappedCollection

In reply to this post by Lukas Renggli

Lukas Renggli a écrit :

>> > > No, I never used MappedCollection, but I wondered several times about
>> > > all the ugly extension this collection class creates throughout the
>> > > object hierarchy. Please remove, or unload into a separate package.
>> >
>> > which extension?
>>
>> Sorry, I confused something.
>
> Now I found it again:
>
> #hashMappedBy: and #identityHashMappedBy:
>
> The names made me think it has something to do with MappedCollection,
> but that's probably not the case. Either-way, there are no real
> senders of these methods. I would suggest removing them, unless
> somebody objects ...
>
> Lukas
>

Also, they are not maintained and not in sync with hash.
I wonder what they were used for.
I vote with roman thumb down for these too (kill).

Nicolas

Nicolas Cellier-3

Re: About MappedCollection

In reply to this post by Damien Cassou-3

Damien Cassou a écrit :
> 2007/5/25, Lukas Renggli <[hidden email]>:
>> Bag is useful. LinkedList and Heap are not generic collections, they
>> are targeted at specific problems like scheduling and data
>> compression.
>
> To me, LinkedLists are useful when you want a sequenceable collection
> with removal and insertion functionalities.
>

Yes, it transforms cost from O(N) to O(1).
That was some provocation.
Though, i tried using them once, they are not generic.
Only a specific thing tailored for Process List.
I should be ashamed to say that, but C++ std::list are really easier to
use than current LinkedList (I mean i cannot replace OrderedCollection
with LinkedList transparently).

Nicolas

Avi Bryant-2

Re: About MappedCollection

On 5/25/07, nicolas cellier <[hidden email]> wrote:

> Yes, it transforms cost from O(N) to O(1).
> That was some provocation.
> Though, i tried using them once, they are not generic.
> Only a specific thing tailored for Process List.
> I should be ashamed to say that, but C++ std::list are really easier to
> use than current LinkedList (I mean i cannot replace OrderedCollection
> with LinkedList transparently).

Either you can have transparency, or you can have O(1)
insertion/removal, but I don't see how you can have both. To get
O(1), you have to have a reference to the link you want to remove or
insert after, which isn't transparent; if you just had a regular
object like you would put in an OrderedCollection, you would have to
do a linear scan through the list to find the right link, and you're
back to O(n). No?

Avi

Damien Cassou-3

Re: About MappedCollection

2007/5/25, Avi Bryant <[hidden email]>:

> On 5/25/07, nicolas cellier <[hidden email]> wrote:
>
> > Yes, it transforms cost from O(N) to O(1).
> > That was some provocation.
> > Though, i tried using them once, they are not generic.
> > Only a specific thing tailored for Process List.
> > I should be ashamed to say that, but C++ std::list are really easier to
> > use than current LinkedList (I mean i cannot replace OrderedCollection
> > with LinkedList transparently).
>
> Either you can have transparency, or you can have O(1)
> insertion/removal, but I don't see how you can have both. To get
> O(1), you have to have a reference to the link you want to remove or
> insert after, which isn't transparent; if you just had a regular
> object like you would put in an OrderedCollection, you would have to
> do a linear scan through the list to find the right link, and you're
> back to O(n). No?

I think the LinkedList should create Links when adding elements. And
answer the value in the link when accessing the LinkedList. This
should be transparent.

--
Damien Cassou

Nicolas Cellier-3

Re: About MappedCollection

In reply to this post by Avi Bryant-2

Avi Bryant a écrit :

> On 5/25/07, nicolas cellier <[hidden email]> wrote:
>
>> Yes, it transforms cost from O(N) to O(1).
>> That was some provocation.
>> Though, i tried using them once, they are not generic.
>> Only a specific thing tailored for Process List.
>> I should be ashamed to say that, but C++ std::list are really easier to
>> use than current LinkedList (I mean i cannot replace OrderedCollection
>> with LinkedList transparently).
>
> Either you can have transparency, or you can have O(1)
> insertion/removal, but I don't see how you can have both. To get
> O(1), you have to have a reference to the link you want to remove or
> insert after, which isn't transparent; if you just had a regular
> object like you would put in an OrderedCollection, you would have to
> do a linear scan through the list to find the right link, and you're
> back to O(n). No?
>
> Avi
>
>

Right.
If you want 0(1) in C++ you have to deal with iterators.
And iterators are transparent because used on all other containers
(collection). You just ignore underlying links (a special species of
iterator).

Nicolas

Avi Bryant-2

Re: About MappedCollection

In reply to this post by Damien Cassou-3

On 5/25/07, Damien Cassou <[hidden email]> wrote:

> I think the LinkedList should create Links when adding elements. And
> answer the value in the link when accessing the LinkedList. This
> should be transparent.

I understand what you mean by transparent, but with that kind of an
interface, you have the same algorithmic complexity as an
OrderedCollection, so what's the point?

The only way to get O(1) insertion/deletion is to pass around Link
objects, which is exactly what you're trying to avoid.

Avi

stephane ducasse

Re: About MappedCollection

In reply to this post by J J-6

but tests are missing for skiplist so you cannot easily learn how to
use them.

I think that for collection it would be easy to have tests and good
tests and have them in separate packages.

Stef

On 24 mai 07, at 22:05, J J wrote:

>
> SkipLists sound cool as well. One of those things that you see
> moving around in the image and try to remember it for later.
> Because it doesn't come up much, but if it does it could really
> save some time.
>
>> From: "Damien Pollet" <[hidden email]>
>> Reply-To: The general-purpose Squeak developers list<squeak-
>> [hidden email]>
>> To: "The general-purpose Squeak developers list"<squeak-
>> [hidden email]>
>> Subject: Re: About MappedCollection
>> Date: Thu, 24 May 2007 22:02:23 +0200
>>
>> On 24/05/07, nicolas cellier <[hidden email]> wrote:
>>> Are Stack and SkipList more used?
>>>
>>> Even Bag is rarely used.
>>
>> I did use it
>>
>>> LinkedList (Process only).
>>> Heap (WorldState, Zip).
>>
>> We were discussing that squeak lacks some base data structures like
>> hash tables or balancing trees... not useful that often, but needed
>> for algorithmic code and difficult to write properly.
>>
>> --
>> Damien Pollet
>> type less, do more [ | ] http://typo.cdlm.fasmz.org
>>
>
> _________________________________________________________________
> More photos, more messages, more storage—get 2GB with Windows Live
> Hotmail. http://imagine-windowslive.com/hotmail/?locale=en-
> us&ocid=TXT_TAGHM_migration_HM_mini_2G_0507
>
>
>