Hi,
does any of you use MappedCollection? Would it be a problem to remove it from the image?
Bye
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 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
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
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 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
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
On 24/05/07, nicolas cellier ncellier@ifrance.com 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.
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" damien.pollet@gmail.com Reply-To: The general-purpose Squeak developers listsqueak-dev@lists.squeakfoundation.org To: "The general-purpose Squeak developers list"squeak-dev@lists.squeakfoundation.org Subject: Re: About MappedCollection Date: Thu, 24 May 2007 22:02:23 +0200
On 24/05/07, nicolas cellier ncellier@ifrance.com 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_migr...
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
2007/5/25, Lukas Renggli renggli@gmail.com:
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 a écrit :
2007/5/25, Lukas Renggli renggli@gmail.com:
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
On 5/25/07, nicolas cellier ncellier@ifrance.com 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
2007/5/25, Avi Bryant avi@dabbledb.com:
On 5/25/07, nicolas cellier ncellier@ifrance.com 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.
On 5/25/07, Damien Cassou damien.cassou@gmail.com 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
From: "Avi Bryant" avi@dabbledb.com Reply-To: The general-purpose Squeak developers listsqueak-dev@lists.squeakfoundation.org To: "The general-purpose Squeak developers list"squeak-dev@lists.squeakfoundation.org Subject: Re: About MappedCollection Date: Fri, 25 May 2007 12:19:43 -0700
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?
Actually OrderedCollection is analogues to the C++ STL "vector" implementation (flat space of some fixed size, if it is going to be exceeded an expensive expand and possibly copy happens). The STL also has a doubly linked list implementation called "list" which has very different characteristics (random access is much slower, insert or removal at either end is O(1)).
_________________________________________________________________ PC Magazines 2007 editors choice for best Web mailaward-winning Windows Live Hotmail. http://imagine-windowslive.com/hotmail/?locale=en-us&ocid=TXT_TAGHM_migr...
Avi Bryant a écrit :
On 5/25/07, nicolas cellier ncellier@ifrance.com 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
From: "Avi Bryant" avi@dabbledb.com Reply-To: The general-purpose Squeak developers listsqueak-dev@lists.squeakfoundation.org To: "The general-purpose Squeak developers list"squeak-dev@lists.squeakfoundation.org Subject: Re: About MappedCollection Date: Fri, 25 May 2007 11:21:16 -0700
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
Well you can have O(1) insert at either end with a plain singly linked list (so long as the interface object has a link to the head *and* the tail). It is true that removals will have to be O(n) for generic objects, but a generic linked list is still valuable for various different algorithms (e.g. LIFO, FIFO).
LinkedLists aren't (or at least shouldn't be) expected to be good at what e.g. vectors excel at.
_________________________________________________________________ PC Magazines 2007 editors choice for best Web mailaward-winning Windows Live Hotmail. http://imagine-windowslive.com/hotmail/?locale=en-us&ocid=TXT_TAGHM_migr...
From: "Damien Cassou" damien.cassou@gmail.com Reply-To: The general-purpose Squeak developers listsqueak-dev@lists.squeakfoundation.org To: "The general-purpose Squeak developers list"squeak-dev@lists.squeakfoundation.org Subject: Re: About MappedCollection Date: Fri, 25 May 2007 10:47:27 +0200
To me, LinkedLists are useful when you want a sequenceable collection with removal and insertion functionalities.
I think the problem is that Squeak (Smalltalk in general?) LinkLists are very specialized and not really usable as a normal collection.
_________________________________________________________________ Make every IM count. Download Messenger and join the im Initiative now. Its free. http://im.live.com/messenger/im/home/?source=TAGHM_MAY07
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" damien.pollet@gmail.com Reply-To: The general-purpose Squeak developers list<squeak- dev@lists.squeakfoundation.org> To: "The general-purpose Squeak developers list"<squeak- dev@lists.squeakfoundation.org> Subject: Re: About MappedCollection Date: Thu, 24 May 2007 22:02:23 +0200
On 24/05/07, nicolas cellier ncellier@ifrance.com 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
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
I'll add, BTree's useful outside of OODB's too.
On 5/24/07, Lukas Renggli renggli@gmail.com 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
On 5/24/07, Chris Muller asqueaker@gmail.com 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
thanks for the explanation.
Stef
On 25 mai 07, at 10:06, Avi Bryant wrote:
On 5/24/07, Chris Muller asqueaker@gmail.com 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
squeak-dev@lists.squeakfoundation.org