Implement Overlap Method that Uses Presorted Input

[endrebak]

It seems to be working fine and be as fast as the other method. It is missing contained, and First/Last options. I expect to be done tomorrow.

Implementing this will allow us to avoid sorting the input which is useful when the same set is used multiple times or is already presorted.

https://github.com/pyranges/ruranges/tree/simpler_overlap

Fixes #17

[endrebak]

Results (using presorted data is 6 times faster, seemed to be the same result for 1e6 intervals too):

presorted data 0.13289713859558105
6998166
nonsorted data 0.8254482746124268
6998166

from numpy.random import seed
import pyranges as pr
import pandas as pd

from pathlib import Path
from time import time

import ruranges

num_intervals = int(5e6)
chr1_size = 249 * int(10e6)

gr = pr.random(num_intervals, chromsizes={"chr1": chr1_size}).remove_strand().sort_ranges(use_strand=False)
gr2 = pr.random(num_intervals, chromsizes={"chr1": chr1_size}).remove_strand().sort_ranges(use_strand=False)

start = time()

x0, x1 = ruranges.overlaps_simple(
    starts=gr.Start.to_numpy(),
    ends=gr.End.to_numpy(),
    starts2=gr.Start.to_numpy(),
    ends2=gr.End.to_numpy(),
    _no_checks=True,
)

print("presorted data", time() - start)
print(len(x0))

start = time()

x0, x1 = ruranges.overlaps(
    starts=gr.Start.to_numpy(),
    ends=gr.End.to_numpy(),
    starts2=gr.Start.to_numpy(),
    ends2=gr.End.to_numpy(),
)

print("nonsorted data", time() - start)
print(len(x0))

[endrebak]

overlaps_simple should not have been the name used really. I should change to overlaps_presorted or something.

[endrebak]

@marco-mariotti I'm considering whether to make this available in PyRanges. There other considerations dominate the running time.

I'm sure people will request it though.