On Mon, 19 Jan 2015, Marcel Taeumel wrote:

> At the moment, I vote against an implementation with linked associations as
> suggested by Levente [1] because:
>
> - Naming reveals implementation detail (LinkedList resp. LinkedAssociation)
> and thus a LinkedDictionary could only be abstract like HashedCollection is

I used this name to make it loadable into an updated Trunk image.

> - LinkedAssociation instances keep references (#next, #previous), which may
> interfere with automatic garbage collection if used outside the dictionary
> (see getter #associations)
>
> We could add automatic boxing/unboxing of linked elements (like Set does
> with SetElement) but this would nullify the performance gain of linked
> structures compared to arrays.

That's not true for removal, which still takes O(n) time with the current 
implementation:

| n random array |
n := 10000.
random := Random seed: 36rSQUEAK.
array := Array new: n streamContents: [ :stream |
 		n timesRepeat: [ stream nextPut: (random nextInt: 1073741823) -> 1 ] ].
{ OrderedDictionary. LinkedDictionary } collect: [ :class |
 	Smalltalk garbageCollect.
 	[
 		| instance |
 		instance := class new.
 		instance addAll: array.
 		array do: [ :each | instance removeKey: each key ] ] timeToRun ].
"==> #(892 10)"

The current implementation can be modified to take only O(1) time average, 
by using another array, which maps the index of an association in the 
array variable to the index of the association in the order variable.

Levente

>
> Best,
> Marcel
>
> [1] http://leves.web.elte.hu/squeak/LinkedDictionary-ul.1.mcz
>
>
>
> --
> View this message in context: http://forum.world.st/The-Trunk-Collections-mt-599-mcz-tp4800299p4800301.html
> Sent from the Squeak - Dev mailing list archive at Nabble.com.
>
>