Bonjour,
> It is possible to create functional arrays with O(1) access in many
> circumstances. For example, the data structure desribed in Melissa
> O'Neil's PhD thesis[1], has O(1) get/set an element on the most recent
> version of an array, and O(log n) for prior version.
>
> I wonder if anyone has tried implementing this data structure ?
Yes : Melissa O'Neill. She may still have the sml sources. They were
based on SML/NJ standard library implementation of splay trees.
> I suspect that it would outperform tree based implementations in
> many situations.
Yes : acces to the last version of the array. Slower for older
versions and a few garbage-collecting problems.
> I tried implementing it myself, but failed, so I don't actually know
> how fast it would be in practice. IIRR, I failed because I couldn't
> understand the explanation of the O(1) solution to the list order
> problem sufficiently well to implement it.
The list order problem is related to garbage collection. That is the
'hard' part.
Diego Olivier
-------------------------------------------------------
SF.Net email is sponsored by Shop4tech.com-Lowest price on Blank Media
100pk Sonic DVD-R 4x for only $29 -100pk Sonic DVD+R for only $33
Save 50% off Retail on Ink & Toner - Free Shipping and Free Gift.
http://www.shop4tech.com/z/Inkjet_Cartridges/9_108_r285
|
