Home

Notes

This is where I keep some notes about this project

I have another page that keeps track of preliminary experiments

General

• I tried using 2 ways searches instead of 3-way searches, they were much slower

VEB Layouts

• I tried using bit tricks instead of array lookup for the VEB layouts, they were much slower
• Even reading m0 = (2 << h0)-1 is faster than computing it.
• Replacing m1*i with i<<(1+h1) - m0 does not make things any faster (even with 1+h1 precomputed)

To Do

• Implement tests with sqrt(n) arrays of size sqrt(n)
• Implement implicit b-tree with b=64/sizeof(T)
• Implement succinct in-place construction algorithms
• Compare with teh AFJ implementation (once I get it to compile)
• Add error checking of the value of n to constructors
• Make constructors accept ForwardIterators

To Explore

• Are there in-place algorithms for transforming sorted arrays to VEB layouts of Eytzinger layouts?