Finger Trees: A Simple General-Purpose Data Structure (2006)
staff.city.ac.uk
Finger Trees: A Simple General-Purpose Data Structure (2006)
1–10 of 79 posts
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#2Finger trees are an example of a truly elegant functional data structure that can be used for just about everything. The problem is they don't match the memory model of real hardware so for all of their elegance and theoretical performance in reality they're too slow to be useful.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#3Could someone give an example where this data structure would be useful?
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#4Finger trees are an example of a truly elegant functional data structure that can be used for just about everything. The problem is they don't match the memory model of real hardware so for all of their elegance and theoretical performance in reality they're too slow to be useful.
Is this true? How is this more true for finger trees than for red-black trees, etc?
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#5Finger trees are an example of a truly elegant functional data structure that can be used for just about everything. The problem is they don't match the memory model of real hardware so for all of their elegance and theoretical performance in reality they're too slow to be useful.
It's true that they have a high constant factor, but I think it's too harsh to say they are not useful.
One could also say that linked-lists don't match the memory model of real hardware.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#6Could someone give an example where this data structure would be useful?
You can create a persistent ordered container that has both prepend and append in amortised constant time; and concatenate in log time.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#7Finger trees are an example of a truly elegant functional data structure that can be used for just about everything. The problem is they don't match the memory model of real hardware so for all of their elegance and theoretical performance in reality they're too slow to be useful.
It's true that they have a high constant factor, but I think it's too harsh to say they are not useful. One could also say that linked-lists don't match the memory model of real hardware.
> One could also say that linked-lists don't match the memory model of real hardware.
They don't, and they almost always perform (much) worse.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#8Earlier quoted context omitted.
It's true that they have a high constant factor, but I think it's too harsh to say they are not useful. One could also say that linked-lists don't match the memory model of real hardware.
> One could also say that linked-lists don't match the memory model of real hardware. They don't, and they almost always perform (much) worse.
The context here is of course persistent data structures. Linked-lists permit very efficient structural sharing.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#9Could someone give an example where this data structure would be useful?
They can be used to implement an immutable deque.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#10Earlier quoted context omitted.
It's true that they have a high constant factor, but I think it's too harsh to say they are not useful. One could also say that linked-lists don't match the memory model of real hardware.
> One could also say that linked-lists don't match the memory model of real hardware. They don't, and they almost always perform (much) worse.
>they almost always perform (much) worse.
'Much worse' relative to what exactly?