Tool:New ultrafast interval tree implementation for Python: kerneltree

Question

[endrebak]

https://github.com/endrebak/kerneltree

Ultrafast interval tree implementation stolen from the kernel, modified and wrapped for Python.

Currently the nodes only store (start, end, int), so if you need to store additional data you need to create an int -> val hash.

For a sane number of intervals, the other Python and Cython implementations are going to be plenty fast enough.

Timings:

1 mill values

Python based intervaltrees took 01 minutes and 37 seconds to build the tree. 
Cython based intervaltrees took 00 minutes and 08 seconds to build the tree. 
C based intervaltrees took 00 minutes and 00 seconds to build the tree.

10 mill values

Python based intervaltrees took 16 minutes and 51 seconds to build the tree. 
Cython based intervaltrees took 02 minutes and 10 seconds to build the tree. 
C based intervaltrees took 00 minutes and 17 seconds to build the tree. 
C based intervaltrees took 00 minutes and 14 seconds to build the tree using 
the helper function build.

Bug reports and such welcome.

[endrebak]

Use https://github.com/hunt-genes/ncls instead. It is much faster :)