cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kobejean/cp-library

:warning: perf/bit6.py

Depends on

Code

#!/usr/bin/env python3
"""
Benchmark comparing BIT6 (6-channel BIT) vs regular BIT with 6-tuples.
Tests construction, point updates, prefix sums, range sums, and mixed operations.
"""

import random
import sys
import os
sys.path.insert(0, os.path.dirname(os.path.dirname(os.path.abspath(__file__))))

from cp_library.perf.benchmark import Benchmark, BenchmarkConfig
from cp_library.ds.tree.bit.bit6_cls import BIT6
from cp_library.ds.tree.bit.bit_monoid_cls import BITMonoid

# Configure benchmark
config = BenchmarkConfig(
    name="bit6",
    sizes=[1000000, 100000, 10000, 1000, 100],  # Reverse order to warm up JIT
    operations=['construction', 'point_updates', 'prefix_sums', 'range_sums', 'mixed_ops'],
    iterations=10,
    warmup=3,
    output_dir="./output/benchmark_results/bit6"
)

# Create benchmark instance
benchmark = Benchmark(config)

# Define operations for BIT with 6-tuples
def tuple6_add(a, b):
    """Addition operation for 6-tuples"""
    return (a[0] + b[0], a[1] + b[1], a[2] + b[2], a[3] + b[3], a[4] + b[4], a[5] + b[5])

def tuple6_sub(a, b):
    """Subtraction operation for 6-tuples"""
    return (a[0] - b[0], a[1] - b[1], a[2] - b[2], a[3] - b[3], a[4] - b[4], a[5] - b[5])

# Data generator
@benchmark.data_generator("default")
def generate_bit6_data(size: int, operation: str):
    """Generate test data for BIT6 operations"""
    # Generate random initial values
    values_a1 = [random.randint(1, 1000) for _ in range(size)]
    values_a2 = [random.randint(1, 1000) for _ in range(size)]
    values_a3 = [random.randint(1, 1000) for _ in range(size)]
    values_a4 = [random.randint(1, 1000) for _ in range(size)]
    values_a5 = [random.randint(1, 1000) for _ in range(size)]
    values_a6 = [random.randint(1, 1000) for _ in range(size)]
    
    # Create tuple values for regular BIT
    tuple_values = [(values_a1[i], values_a2[i], values_a3[i], values_a4[i], values_a5[i], values_a6[i]) 
                    for i in range(size)]
    
    # Generate update operations
    num_updates = min(1000, size // 10)
    update_indices = [random.randint(0, size - 1) for _ in range(num_updates)]
    update_values_a1 = [random.randint(1, 1000) for _ in range(num_updates)]
    update_values_a2 = [random.randint(1, 1000) for _ in range(num_updates)]
    update_values_a3 = [random.randint(1, 1000) for _ in range(num_updates)]
    update_values_a4 = [random.randint(1, 1000) for _ in range(num_updates)]
    update_values_a5 = [random.randint(1, 1000) for _ in range(num_updates)]
    update_values_a6 = [random.randint(1, 1000) for _ in range(num_updates)]
    update_tuple_values = [(update_values_a1[i], update_values_a2[i], update_values_a3[i],
                           update_values_a4[i], update_values_a5[i], update_values_a6[i]) 
                          for i in range(num_updates)]
    
    # Generate query ranges
    num_queries = min(1000, size // 10)
    query_ranges = []
    for _ in range(num_queries):
        l = random.randint(0, size - 1)
        r = random.randint(l + 1, size)
        query_ranges.append((l, r))
    
    # Generate prefix indices
    prefix_indices = [random.randint(1, size) for _ in range(num_queries)]
    
    return {
        'values_a1': values_a1,
        'values_a2': values_a2,
        'values_a3': values_a3,
        'values_a4': values_a4,
        'values_a5': values_a5,
        'values_a6': values_a6,
        'tuple_values': tuple_values,
        'update_indices': update_indices,
        'update_values_a1': update_values_a1,
        'update_values_a2': update_values_a2,
        'update_values_a3': update_values_a3,
        'update_values_a4': update_values_a4,
        'update_values_a5': update_values_a5,
        'update_values_a6': update_values_a6,
        'update_tuple_values': update_tuple_values,
        'query_ranges': query_ranges,
        'prefix_indices': prefix_indices,
        'size': size
    }

# Setup functions to prepare data and reduce overhead during timing
@benchmark.setup("default")
def setup(data):
    prepared = data.copy()
    return prepared

# Construction operation
@benchmark.implementation("bit6_sum", "construction")
def construction_bit6_sum(data):
    """Construct BIT6 with sum operation"""
    bit = BIT6(data['tuple_values'])
    return len(bit)

@benchmark.implementation("tuple6_bit_sum", "construction")
def construction_tuple6_bit_sum(data):
    """Construct BITMonoid with 6-tuple sum operation"""
    bit = BITMonoid(tuple6_add, (0, 0, 0, 0, 0, 0), data['tuple_values'])
    return len(bit)

# Point updates operation
@benchmark.implementation("bit6_sum", "point_updates")
def point_updates_bit6_sum(data):
    """Point updates on BIT6 with sum"""
    bit = BIT6(data['size'])
    checksum = 0
    indices = data['update_indices']
    updates = data['update_tuple_values']
    for j in range(len(indices)):
        i = indices[j]
        val = updates[j]
        bit.set(i, val)
        result = bit.get(i)
        checksum ^= result[0] ^ result[1] ^ result[2] ^ result[3] ^ result[4] ^ result[5]
    return checksum

@benchmark.implementation("tuple6_bit_sum", "point_updates")
def point_updates_tuple6_bit_sum(data):
    """Point updates on BITMonoid with 6-tuples"""
    bit = BITMonoid(tuple6_add, (0, 0, 0, 0, 0, 0), data['size'])
    checksum = 0
    indices = data['update_indices']
    updates = data['update_tuple_values']
    for j in range(len(indices)):
        i = indices[j]
        val = updates[j]
        # Set element: add difference between target and current
        current = tuple6_sub(bit.sum(i + 1), bit.sum(i))
        bit.add(i, tuple6_sub(val, current))
        # Get element: reconstruct from prefix sums
        result = tuple6_sub(bit.sum(i + 1), bit.sum(i))
        checksum ^= result[0] ^ result[1] ^ result[2] ^ result[3] ^ result[4] ^ result[5]
    return checksum

# Prefix sums operation
@benchmark.implementation("bit6_sum", "prefix_sums")
def prefix_sums_bit6_sum(data):
    """Prefix sums on BIT6 with sum"""
    bit = BIT6(data['tuple_values'])
    checksum = 0
    for n in data['prefix_indices']:
        result = bit.sum(n)
        checksum ^= result[0] ^ result[1] ^ result[2] ^ result[3] ^ result[4] ^ result[5]
    return checksum

@benchmark.implementation("tuple6_bit_sum", "prefix_sums")
def prefix_sums_tuple6_bit_sum(data):
    """Prefix sums on BITMonoid with 6-tuples"""
    bit = BITMonoid(tuple6_add, (0, 0, 0, 0, 0, 0), data['tuple_values'])
    checksum = 0
    for n in data['prefix_indices']:
        result = bit.sum(n)
        checksum ^= result[0] ^ result[1] ^ result[2] ^ result[3] ^ result[4] ^ result[5]
    return checksum

# Range sums operation
@benchmark.implementation("bit6_sum", "range_sums")
def range_sums_bit6_sum(data):
    """Range sums on BIT6 with sum"""
    bit = BIT6(data['tuple_values'])
    checksum = 0
    for l, r in data['query_ranges']:
        result = bit.sum_range(l, r)
        checksum ^= result[0] ^ result[1] ^ result[2] ^ result[3] ^ result[4] ^ result[5]
    return checksum

@benchmark.implementation("tuple6_bit_sum", "range_sums")
def range_sums_tuple6_bit_sum(data):
    """Range sums on BITMonoid with 6-tuples"""
    bit = BITMonoid(tuple6_add, (0, 0, 0, 0, 0, 0), data['tuple_values'])
    checksum = 0
    for l, r in data['query_ranges']:
        # Range sum: sum(r) - sum(l)
        result = tuple6_sub(bit.sum(r), bit.sum(l))
        checksum ^= result[0] ^ result[1] ^ result[2] ^ result[3] ^ result[4] ^ result[5]
    return checksum

# Mixed operations (updates + queries)
@benchmark.implementation("bit6_sum", "mixed_ops")
def mixed_ops_bit6_sum(data):
    """Mixed updates and queries on BIT6"""
    bit = BIT6(data['tuple_values'])
    checksum = 0
    
    # Interleave updates and queries
    query_ranges = data['query_ranges']
    update_indices = data['update_indices']
    update_tuple_values = data['update_tuple_values']
    min_len = min(len(query_ranges), len(update_indices))
    
    for i in range(min_len):
        if i % 2 == 0:
            # Range query
            l, r = query_ranges[i]
            result = bit.sum_range(l, r)
            checksum ^= result[0] ^ result[1] ^ result[2] ^ result[3] ^ result[4] ^ result[5]
        else:
            # Update
            idx = update_indices[i]
            val = update_tuple_values[i]
            bit.add(idx, val)
            result = bit.get(idx)
            checksum ^= result[0] ^ result[1] ^ result[2] ^ result[3] ^ result[4] ^ result[5]
    return checksum

@benchmark.implementation("tuple6_bit_sum", "mixed_ops")
def mixed_ops_tuple6_bit_sum(data):
    """Mixed updates and queries on BITMonoid"""
    bit = BITMonoid(tuple6_add, (0, 0, 0, 0, 0, 0), data['tuple_values'])
    checksum = 0
    
    # Interleave updates and queries
    query_ranges = data['query_ranges']
    update_indices = data['update_indices']
    update_tuple_values = data['update_tuple_values']
    min_len = min(len(query_ranges), len(update_indices))
    
    for i in range(min_len):
        if i % 2 == 0:
            # Range query
            l, r = query_ranges[i]
            result = tuple6_sub(bit.sum(r), bit.sum(l))
            checksum ^= result[0] ^ result[1] ^ result[2] ^ result[3] ^ result[4] ^ result[5]
        else:
            # Update
            idx = update_indices[i]
            val = update_tuple_values[i]
            bit.add(idx, val)
            result = tuple6_sub(bit.sum(idx + 1), bit.sum(idx))
            checksum ^= result[0] ^ result[1] ^ result[2] ^ result[3] ^ result[4] ^ result[5]
    return checksum

if __name__ == "__main__":
    # Parse command line args and run appropriate mode
    runner = benchmark.parse_args()
    runner.run()
Traceback (most recent call last):
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python.py", line 101, in bundle
    return bundler.update(path)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python_bundle.py", line 154, in update
    self.process_file(path)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python_bundle.py", line 24, in process_file
    self.bundled_code[file_path] = self.process_imports(tree, file_path, source, file_is_top_level)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python_bundle.py", line 102, in process_imports
    processor.visit(tree)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/ast.py", line 418, in visit
    return visitor(node)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/ast.py", line 426, in generic_visit
    self.visit(item)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/ast.py", line 418, in visit
    return visitor(node)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python_bundle.py", line 80, in visit_ImportFrom
    self.process_module(node, module_path, file_is_top_level, from_import=True, import_names=node.names)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python_bundle.py", line 92, in process_module
    imported_code = self.bundler.import_file(module_path, is_top_level)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python_bundle.py", line 31, in import_file
    self.process_file(file_path, is_top_level)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python_bundle.py", line 24, in process_file
    self.bundled_code[file_path] = self.process_imports(tree, file_path, source, file_is_top_level)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python_bundle.py", line 102, in process_imports
    processor.visit(tree)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/ast.py", line 418, in visit
    return visitor(node)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/ast.py", line 426, in generic_visit
    self.visit(item)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/ast.py", line 418, in visit
    return visitor(node)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python_bundle.py", line 80, in visit_ImportFrom
    self.process_module(node, module_path, file_is_top_level, from_import=True, import_names=node.names)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python_bundle.py", line 92, in process_module
    imported_code = self.bundler.import_file(module_path, is_top_level)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python_bundle.py", line 31, in import_file
    self.process_file(file_path, is_top_level)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python_bundle.py", line 24, in process_file
    self.bundled_code[file_path] = self.process_imports(tree, file_path, source, file_is_top_level)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python_bundle.py", line 102, in process_imports
    processor.visit(tree)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/ast.py", line 418, in visit
    return visitor(node)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/ast.py", line 426, in generic_visit
    self.visit(item)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/ast.py", line 418, in visit
    return visitor(node)
  File "/opt/hostedtoolcache/PyPy/3.10.16/x64/lib/pypy3.10/site-packages/onlinejudge_verify/languages/python_bundle.py", line 64, in visit_ImportFrom
    raise NotImplementedError("Relative imports are not supported")
NotImplementedError: Relative imports are not supported
Back to top page