Class TestPerformanceComparison

python/tests/test_performance_regression.py:234–292

Compare performance against standard Python dict.

class TestPerformanceComparison:
    """Compare performance against standard Python dict."""

    def test_insertion_comparable_to_dict(self):
        """Test that insertion performance is comparable to dict."""
        size = 5000
        data = [(i, f"value_{i}") for i in range(size)]

        # Test dict
        dict_obj = {}
        with time_it() as dict_elapsed:
            for key, value in data:
                dict_obj[key] = value

        # Test B+ Tree
        tree = BPlusTreeMap()
        with time_it() as tree_elapsed:
            for key, value in data:
                tree[key] = value

        dict_time = dict_elapsed()
        tree_time = tree_elapsed()

        # B+ Tree insertion can be slower than dict, but not by too much
        # (dict has O(1) amortized, B+ Tree has O(log n))
        assert (
            tree_time < dict_time * 10
        ), f"B+ Tree insertion ({tree_time:.3f}s) is too slow compared to dict ({dict_time:.3f}s)"

    def test_ordered_iteration_faster_than_sorted_dict(self):
        """Test that ordered iteration is faster than sorting dict items."""
        size = 10000
        data = [(random.randint(0, 100000), f"value_{i}") for i in range(size)]

        # Build dict
        dict_obj = {}
        for key, value in data:
            dict_obj[key] = value

        # Build B+ Tree
        tree = BPlusTreeMap()
        for key, value in data:
            tree[key] = value

        # Test sorted dict iteration
        with time_it() as dict_elapsed:
            sorted_items = sorted(dict_obj.items())

        # Test B+ Tree iteration (already sorted)
        with time_it() as tree_elapsed:
            tree_items = list(tree.items())

        dict_time = dict_elapsed()
        tree_time = tree_elapsed()

        # B+ Tree iteration should be faster than sorting dict items
        assert (
            tree_time < dict_time