<jupyter_start><jupyter_text>This notenook is to compare the performance among different implementation of intervaltrees.<jupyter_code>to_build=[]
to_search=[] 
def genData(to_build_size=1000000,search_size=1000000):
    for i in range(0, 17*to_build_size, 17):
        to_build.append((i, random.randrange(i + 1, i + 100), i))
        
    for i in range(0, 34*search_size, 34):
        to_search.append((i, random.randrange(i + 1, i + 100), i))
        
genData()
tree=None<jupyter_output><empty_output><jupyter_text>intervaltree<jupyter_code>%%time
from intervaltree import IntervalTree
tree = IntervalTree()
for tup in to_build:
    tree.addi(tup[0], tup[1], tup[2])

%%time
for tar in to_search:
    tree.overlap(tar[0],tar[1])
    
print(tree.overlap(20,30))<jupyter_output>{Interval(0, 81, 0)}
CPU times: user 1min 49s, sys: 231 ms, total: 1min 50s
Wall time: 1min 59s<jupyter_text>quicksetx<jupyter_code>%%time
from quicksect import IntervalNode, Interval, IntervalTree
tree = IntervalTree()
for tup in to_build:
    tree.insert(Interval(tup[0], tup[1], tup[2]))    
%%time
from quicksectx import IntervalNode, Interval, IntervalTree
tree = IntervalTree()
for tup in to_build:
    tree.insert(Interval(tup[0], tup[1], tup[2]))    
%%time
for tar in to_search:
    tree.search(tar[0],tar[1])
    
print(tree.search(20,30))<jupyter_output>[Inv(17, 25, d=17)]
CPU times: user 532 ms, sys: 0 ns, total: 532 ms
Wall time: 542 ms<jupyter_text>kerneltree<jupyter_code>%%time
from kerneltree import IntervalTree
tree = IntervalTree()
for tup in to_build:
    tree.add(tup[0], tup[1], tup[2])


%%time
for tar in to_search:
    tree.search(tar[0],tar[1])    
print(tree.search(20,30))<jupyter_output>[(17, 25, 17)]
CPU times: user 528 ms, sys: 7.66 ms, total: 536 ms
Wall time: 546 ms
{'fraction_non_alphanumeric': 0.13853056646102074, 'fraction_numerical': 0.0628154795288839, 'mean_word_length': 5.151724137931034, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '628208', 'license': 'Apache-2.0', 'n_tokens_mistral': 772, 'n_tokens_neox': 692, 'n_words': 170, 'path': 'notebooks/benchmark.ipynb', 'repo_name': 'jianlins/PyFastNER', 'size': '1783'}