Skip to content

Home

Jump to bottom Edit New page
Pat Morin edited this page May 1, 2015 · 6 revisions

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?
Add a custom footer
Add a custom sidebar
Clone this wiki locally