Traditional two-array leaf node for comparison.
| 72 | |
| 73 | |
| 74 | class TwoArrayLeafNode: |
| 75 | """Traditional two-array leaf node for comparison.""" |
| 76 | |
| 77 | def __init__(self, capacity: int = 128): |
| 78 | self.capacity = capacity |
| 79 | self.keys = array("q") # Empty array |
| 80 | self.values = array("q") # Empty array |
| 81 | self.next = None |
| 82 | |
| 83 | def find_position(self, key: int) -> int: |
| 84 | """Binary search for key position.""" |
| 85 | left, right = 0, len(self.keys) |
| 86 | while left < right: |
| 87 | mid = (left + right) // 2 |
| 88 | if self.keys[mid] < key: |
| 89 | left = mid + 1 |
| 90 | else: |
| 91 | right = mid |
| 92 | return left |
| 93 | |
| 94 | def insert(self, key: int, value: int) -> bool: |
| 95 | """Insert key-value pair. Returns True if successful.""" |
| 96 | pos = self.find_position(key) |
| 97 | |
| 98 | # Check if key exists |
| 99 | if pos < len(self.keys) and self.keys[pos] == key: |
| 100 | self.values[pos] = value |
| 101 | return True |
| 102 | |
| 103 | # Check capacity |
| 104 | if len(self.keys) >= self.capacity: |
| 105 | return False |
| 106 | |
| 107 | # Insert |
| 108 | self.keys.insert(pos, key) |
| 109 | self.values.insert(pos, value) |
| 110 | return True |
| 111 | |
| 112 | def lookup(self, key: int) -> int: |
| 113 | """Lookup value for key. Returns -1 if not found.""" |
| 114 | pos = self.find_position(key) |
| 115 | if pos < len(self.keys) and self.keys[pos] == key: |
| 116 | return self.values[pos] |
| 117 | return -1 |
| 118 | |
| 119 | |
| 120 | def benchmark_int_arrays(size: int = 64, iterations: int = 10000): |
no outgoing calls