3 ms·

The log-time concatenation may be the real win. Still though, why 4? Why not 2, or 8? Is this covered in some of the research?

by wrl 12y ago

asynchrony 12y ago
My understanding is that 4 is a relatively sweet spot for allowing efficient consing/deconsing of the finger nodes. I became fascinated by fingertrees a few years ago and created several toy implementations. I recall that the size of the fingers did impact the performance of various operations though I no longer remember. Sadly I do recall that the constant factors were prohibitively high which made finger trees rather unsuited as an every day list/array data structure for most applications. It would certainly simplify programming to have one sequential collection type that is adequately performant at everything.
- jules 12y ago
  > My understanding is that 4 is a relatively sweet spot for allowing efficient consing/deconsing of the finger nodes. I doubt it. For the persistent data structures I've implemented a branching factor of 32 or 64 worked best (persistent hash maps, vectors, and b+ trees). A high branching factor keeps the depth of the tree very small. Copying a block of memory a few times is cheaper than copying a little memory block a lot of times.
  - asynchrony 12y ago
    Copying the fingers is the most common operation. Every cons/decons requires copying one of the fingers. Operations that propagate deeper into the tree are lazy, so the primary factor affecting performance of common operations is time required to copy one of the fingers. The result of using a higher branching factor would be copying a larger memory block many times.
    - jules 12y ago
      Nice in theory, but my benchmarks show otherwise :) Copying a 32 words of memory doesn't take much more time than copying 1 word of memory.
jbapple 12y ago
Scott Huddleston and Kurt Mehlhorn's 1982 paper "A New Data Structure for Representing Sorted Lists" addresses this question. http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Huddleston-Mehlhorn-ActaInformatica.pdf http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Huddleston-Mehlho... The answer is that each modification costs O(1) amortized time when you have a 4. It even gives a little anecdote in the acknowledgements on the last page: "On October 29, 1979, Mehlhorn presented the results of [4] in Zurich. Ed McCreight was in the audience and asked, 'Is a similar result true for 2-3 trees?' The counterexample shown in Fig. 3 was described. He then asked, 'How about 10-50 trees?'" (Ed McCreight co-invented the B-tree) ([4] is Blum, N., Mehlhorn, K.: On the average number of rebalancing steps in weight-balanced trees. Theor. Comput. Sci. 11, 303-320 (1980)) However, you don't actually have to understand all of this to get the gist of why 2-3 trees don't have constant-amortized-time modifications. You can see that from a simple little experiment on binary numbers. Imagine that you had to implement binary arithmetic on your own. The first thing you implement is a binary counter with only increment. It starts at 0, you can add 1 as many times as you like. That's it. Note that a counter with n bits may require n bit flips to increment 11111...1. However, by assigning a binary number a potential of the number of 1 bits, you can see that incrementing takes O(1) amortized bit flips using the physicist's method. This doesn't work when you can also subtract one from your counter, since subtracting one can turn a lot of 0s into 1s. Adding one again turns them back, and you're back where you started, having spent no potential yet requiring a bunch of bit flips in each operation. However, if you allow each digit to be 0, 1, or 2, you can assign a positive potential to the 0 and 2 digits and zero potential to the 1 bits to show that both increment and decrement use O(1) amortized bit flips. The same thing happens with 2-3 trees vs. 2-3-4 trees. I believe 2-3 trees have amortized O(1) insert if deletion is not permitted, but 2-3-4 trees permit both. Number systems have some deep connections to data structure design like this. One place you can read more is in Okasaki's book, "Purely Functional Data Structures", through plenty of free resources exist on the topic as well - Amr Elmasry tends to publish about it a lot. Once you get it, you start to see the pattern in many other places.
- jbapple 12y ago
  Clarification: In the example with 0, 1, and 2 as allowed digits, I still intended for the number to be "binary" in the sense that the ith digit has weight 2^i. Thus, 12 in this system is 12^1 + 22^0 = 4, in decimal, and, in this system, 12 = 20 = 100.

The log-time concatenation may be the real win. Still though, why 4? Why not 2, or 8? Is this covered in some of the research?

by wrl 12y ago

The log-time concatenation may be the real win. Still though, why 4? Why not 2, or 8? Is this covered in some of the research?

asynchrony 12y ago

My understanding is that 4 is a relatively sweet spot for allowing efficient consing/deconsing of the finger nodes. I became fascinated by fingertrees a few years ago and created several toy implementations. I recall that the size of the fingers did impact the performance of various operations though I no longer remember. Sadly I do recall that the constant factors were prohibitively high which made finger trees rather unsuited as an every day list/array data structure for most applications. It would certainly simplify programming to have one sequential collection type that is adequately performant at everything.

jules 12y ago
> My understanding is that 4 is a relatively sweet spot for allowing efficient consing/deconsing of the finger nodes. I doubt it. For the persistent data structures I've implemented a branching factor of 32 or 64 worked best (persistent hash maps, vectors, and b+ trees). A high branching factor keeps the depth of the tree very small. Copying a block of memory a few times is cheaper than copying a little memory block a lot of times.
- asynchrony 12y ago
  Copying the fingers is the most common operation. Every cons/decons requires copying one of the fingers. Operations that propagate deeper into the tree are lazy, so the primary factor affecting performance of common operations is time required to copy one of the fingers. The result of using a higher branching factor would be copying a larger memory block many times.
  - jules 12y ago
    Nice in theory, but my benchmarks show otherwise :) Copying a 32 words of memory doesn't take much more time than copying 1 word of memory.

jbapple 12y ago

Scott Huddleston and Kurt Mehlhorn's 1982 paper "A New Data Structure for Representing Sorted Lists" addresses this question. http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Huddleston-Mehlhorn-ActaInformatica.pdf http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Huddleston-Mehlho... The answer is that each modification costs O(1) amortized time when you have a 4. It even gives a little anecdote in the acknowledgements on the last page: "On October 29, 1979, Mehlhorn presented the results of [4] in Zurich. Ed McCreight was in the audience and asked, 'Is a similar result true for 2-3 trees?' The counterexample shown in Fig. 3 was described. He then asked, 'How about 10-50 trees?'" (Ed McCreight co-invented the B-tree) ([4] is Blum, N., Mehlhorn, K.: On the average number of rebalancing steps in weight-balanced trees. Theor. Comput. Sci. 11, 303-320 (1980)) However, you don't actually have to understand all of this to get the gist of why 2-3 trees don't have constant-amortized-time modifications. You can see that from a simple little experiment on binary numbers. Imagine that you had to implement binary arithmetic on your own. The first thing you implement is a binary counter with only increment. It starts at 0, you can add 1 as many times as you like. That's it. Note that a counter with n bits may require n bit flips to increment 11111...1. However, by assigning a binary number a potential of the number of 1 bits, you can see that incrementing takes O(1) amortized bit flips using the physicist's method. This doesn't work when you can also subtract one from your counter, since subtracting one can turn a lot of 0s into 1s. Adding one again turns them back, and you're back where you started, having spent no potential yet requiring a bunch of bit flips in each operation. However, if you allow each digit to be 0, 1, or 2, you can assign a positive potential to the 0 and 2 digits and zero potential to the 1 bits to show that both increment and decrement use O(1) amortized bit flips. The same thing happens with 2-3 trees vs. 2-3-4 trees. I believe 2-3 trees have amortized O(1) insert if deletion is not permitted, but 2-3-4 trees permit both. Number systems have some deep connections to data structure design like this. One place you can read more is in Okasaki's book, "Purely Functional Data Structures", through plenty of free resources exist on the topic as well - Amr Elmasry tends to publish about it a lot. Once you get it, you start to see the pattern in many other places.

jbapple 12y ago
Clarification: In the example with 0, 1, and 2 as allowed digits, I still intended for the number to be "binary" in the sense that the ith digit has weight 2^i. Thus, 12 in this system is 12^1 + 22^0 = 4, in decimal, and, in this system, 12 = 20 = 100.