Sorry to add another issue to the pile, but just wanted to note one more odd behavior I noticed in IntervalDict - namely, the asymmetry of performance in queries at the lower end vs. upper end of its domain.
Sample benchmarks:
@pytest.mark.parametrize("size", [10, 100, 1000])
def test_get_above(self, benchmark, size):
content = [(P.closedopen(i, i+1), i) for i in range(size)]
d = P.IntervalDict(content)
query = P.closedopen(size+2, size+3)
benchmark(lambda: d.get(query))
@pytest.mark.parametrize("size", [10, 100, 1000])
def test_get_below(self, benchmark, size):
content = [(P.closedopen(i, i+1), i) for i in range(size)]
d = P.IntervalDict(content)
query = P.closedopen(-2, -1)
benchmark(lambda: d.get(query))
and local results:
------------------------------------------------------------------------------------------------- benchmark: 17 tests -------------------------------------------------------------------------------------------------
Name (time in us) Min Max Mean StdDev Median IQR Outliers OPS Rounds Iterations
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_get_below[10] 13.7500 (2.87) 60.6670 (3.35) 14.2937 (2.83) 0.9847 (5.56) 14.1250 (2.83) 0.1250 (1.51) 1968;3879 69,960.9675 (0.35) 43399 1
test_get_below[100] 13.8330 (2.89) 364.9170 (20.13) 14.8991 (2.95) 4.1035 (23.17) 14.2920 (2.86) 0.8740 (10.53) 860;1845 67,117.9769 (0.34) 44860 1
test_get_below[1000] 13.9160 (2.90) 42.2080 (2.33) 14.3391 (2.84) 0.9640 (5.44) 14.2080 (2.84) 0.1250 (1.51) 663;1174 69,739.2519 (0.35) 22836 1
test_get_above[10] 25.0000 (5.22) 7,553.1250 (416.72) 31.3991 (6.22) 86.0603 (485.96) 25.4590 (5.09) 1.7090 (20.59) 122;1632 31,848.0852 (0.16) 20169 1
test_get_above[100] 126.2080 (26.34) 1,021.7500 (56.37) 137.7285 (27.28) 53.1447 (300.09) 127.0830 (25.42) 2.9590 (35.65) 63;404 7,260.6600 (0.04) 2165 1
test_get_above[1000] 1,141.2080 (238.15) 1,234.4170 (68.11) 1,152.5858 (228.28) 13.1128 (74.04) 1,148.5420 (229.71) 4.5417 (54.73) 86;112 867.6144 (0.00) 863 1
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Note test_get_below has O(1) performance and test_get_above has O(n) performance.
This seems to be down to the storage structure used in IntervalDict - it's backed by a SortedDict sorted on key.lower, which is great for optimizing queries at the bottom of the domain (vast majority of keys can be excluded), but does nothing to help queries at the top of the domain (all keys must be searched, since the structure knows nothing about key.upper).
Not saying this necessarily has to be fixed, but out of curiosity - was an implementation ever considered using a SortedDict with atomic, disjoint interval keys instead? This would have a structure similar to Interval, with similar range-query optimization opportunities (i.e. avoid scanning subintervals both below and above query range, cost is proportional to query range size and is position-independent, etc.). To be honest, that's what I had assumed it was before I read the code.
Sorry to add another issue to the pile, but just wanted to note one more odd behavior I noticed in
IntervalDict- namely, the asymmetry of performance in queries at the lower end vs. upper end of its domain.Sample benchmarks:
and local results:
Note
test_get_belowhas O(1) performance andtest_get_abovehasO(n)performance.This seems to be down to the storage structure used in
IntervalDict- it's backed by aSortedDictsorted onkey.lower, which is great for optimizing queries at the bottom of the domain (vast majority of keys can be excluded), but does nothing to help queries at the top of the domain (all keys must be searched, since the structure knows nothing aboutkey.upper).Not saying this necessarily has to be fixed, but out of curiosity - was an implementation ever considered using a
SortedDictwith atomic, disjoint interval keys instead? This would have a structure similar toInterval, with similar range-query optimization opportunities (i.e. avoid scanning subintervals both below and above query range, cost is proportional to query range size and is position-independent, etc.). To be honest, that's what I had assumed it was before I read the code.