Benchmark range query performance vs alternatives.
()
| 43 | |
| 44 | |
| 45 | def benchmark_range_queries(): |
| 46 | """Benchmark range query performance vs alternatives.""" |
| 47 | print("=== Range Query Performance ===\n") |
| 48 | |
| 49 | sizes = [1000, 5000, 10000] |
| 50 | range_sizes = [10, 50, 100, 500] |
| 51 | |
| 52 | for data_size in sizes: |
| 53 | print(f"Dataset size: {data_size:,} items") |
| 54 | |
| 55 | # Setup data structures |
| 56 | data = create_test_data(data_size) |
| 57 | |
| 58 | # B+ Tree |
| 59 | bplustree = BPlusTreeMap(capacity=64) |
| 60 | bplustree.update(data) |
| 61 | |
| 62 | # Regular dict |
| 63 | regular_dict = dict(data) |
| 64 | |
| 65 | # SortedDict (if available) |
| 66 | if HAS_SORTEDDICT: |
| 67 | sorted_dict = SortedDict(data) |
| 68 | |
| 69 | for range_size in range_sizes: |
| 70 | start_key = data_size // 3 # Start from 1/3 into the data |
| 71 | end_key = start_key + range_size |
| 72 | |
| 73 | print(f"\n Range query: {range_size} items (keys {start_key}-{end_key-1})") |
| 74 | |
| 75 | # B+ Tree range query |
| 76 | def bplus_range(): |
| 77 | return list(bplustree.range(start_key, end_key)) |
| 78 | |
| 79 | bplus_time, bplus_result = benchmark_function(bplus_range) |
| 80 | print( |
| 81 | f" B+ Tree: {bplus_time*1000:.3f} ms ({len(bplus_result)} items)" |
| 82 | ) |
| 83 | |
| 84 | # Dict scan approach |
| 85 | def dict_range(): |
| 86 | return [ |
| 87 | (k, v) for k, v in regular_dict.items() if start_key <= k < end_key |
| 88 | ] |
| 89 | |
| 90 | dict_time, dict_result = benchmark_function(dict_range) |
| 91 | print( |
| 92 | f" Dict scan: {dict_time*1000:.3f} ms ({len(dict_result)} items)" |
| 93 | ) |
| 94 | |
| 95 | # SortedDict range (if available) |
| 96 | if HAS_SORTEDDICT: |
| 97 | |
| 98 | def sorted_dict_range(): |
| 99 | return list(sorted_dict.irange(start_key, end_key - 1)) |
| 100 | |
| 101 | sorted_time, sorted_result = benchmark_function(sorted_dict_range) |
| 102 | print( |
no test coverage detected