Qiskit / qiskit-addon-sqd-hpc / 38313384097

78%

Build Type

push

github

Committed by web-flow

Commit Message

Sample without replacement with a Fenwick tree (#61)

* Sample without replacement with a Fenwick tree

NoReplacementSampler drew from a std::discrete_distribution and rejected
already-drawn indices, rebuilding the distribution when collisions piled
up. The rejection cost grows as the number of draws k approaches the pool
size n.

Replace the internals with a Fenwick tree (binary indexed tree) over the
weights. Each draw locates the index for a uniform target in [0, total)
by descending the tree and then removes that index, both O(log n), with no
rejection and no rebuilding. The public interface and the sequential-scheme
semantics are unchanged (test/test_sample_without_replacement.cpp passes).

The exact per-index weight is stored alongside the tree so that removing a
drawn index subtracts its original value; recovering it from a difference
of Fenwick prefix sums would be subject to floating-point cancellation.

Benchmarked 1.1x-1.7x faster than the previous sampler across pool sizes
n=20..1000 and draw fractions k/n=0.02..0.90 -- faster in every regime,
unlike an Efraimidis-Spirakis approach which only helps near k/n>0.5. Add
benchmark/benchmark_sample_without_replacement.cpp exercising the sampler
directly across those (n, k) pairs.

Assisted-by: Claude Opus 4.8 (1M context)

* Add failing tests for out-of-range draws from spread weights

The Fenwick descent in NoReplacementSampler locates a leaf by comparing a
uniform target against cumulative node sums.  When those sums are smaller
than the target, every step of the descent is taken and `pos` runs past the
last leaf, so the sampler returns an index equal to the pool size.

Floating-point cancellation gets it there.  Accumulating a widely spread
weight array rounds the small weights away (1e-12 + 1e12 == 1e12), so once
the dominant weight is drawn and subtracted, the node sums and
total_weight_ collapse to exactly zero while a genuinely nonzero weight
remains.  remaining_nonzero_weights still repo... (continued)

Coverage Stats

1536 of 2164 branches covered (70.98%)

Branch coverage included in aggregate %.

94 of 99 new or added lines in 4 files covered. (94.95%)

1 existing line in 1 file now uncovered.

1246 of 1400 relevant lines covered (89.0%)

492614.08 hits per line