Code: Megapixel99/countfn
Every empirical complexity tool I could find on either registry measures elapsed time. PyPI's big-O estimates the class from execution time, and npm's big-o-calculator times growing inputs and reports the "probable" complexity; neither can refuse to answer. countfn counts operations instead: hand it a function, a ladder of input sizes, and a builder for the inputs, and it reports how each kind of work grows, or refuses.
pip install countfn # or: npm install countfn
from countfn import measure, describe
report = measure(binary_search, sizes=[64, 128, 256, 512, 1024, 2048],
make_input=lambda n, rng: rng.sample(n * 10, n), trials=80)
print(describe(report)) # reads: log n; writes: UNDETERMINED, nothing ever wrote
The function is handed an instrumented sequence, so nothing about it changes except accepting what it is given; reads and writes through the subscript are what get counted. A count is the same number on a loaded laptop and an idle server, this year and next. That matters because the fitting machinery underneath is undetermined, covered yesterday, whose central precondition refuses an observable that is a mean over noise, and a timing is exactly that: it still has a standard error, still forms a ladder, and can still plateau, so it produces confident answers rather than wrong-looking ones. A count gives the ladder, the error bars and the three-rung plateau something real to be computed from.
Three channels are counted, because they are the three that mean the same thing in both languages: reads (element access through the subscript, including iteration), writes (element assignment, including append and push), and calls (invocations of a callable you wrapped). Comparisons are deliberately not a channel. a < b on two objects costs two protocol events in JavaScript and one dunder in Python, so you wrap the comparator instead and both halves count one call per call. Measured that way, an insertion sort's comparison count fits 0.2559 +/- 0.003006 · n², which is the n²/4 every textbook quotes, measured.
The claim a stranger can check to the integer is the cross-language parity. One seeded generator (mulberry32, specified in 32-bit arithmetic), one iteration rule (n reads, never n+1, because Python's fallback protocol would otherwise call __getitem__ until it raised), and one subscript rule are part of the contract. So the same algorithm on the same seed performs the same counted operations in both languages: insertion sort on seed 17 at n=64 is {reads: 3812, writes: 1848} in Python and in JavaScript. The parity suite runs four algorithms through both halves and compares the count tables.
The refusals are where the tool differs from a curve fit. A count that depends only on n has a standard error of exactly zero at every rung, so there is no noise to compare against and the verdict is UNDETERMINED [exact]. The mean counts are printed, since a reader can name the class off 16:16 32:32 64:64 128:128 in a second. Passing a tolerance converts that into declared error bars, and the report then states that the bars were declared rather than measured. A constant still moving is not a class. A merge sort's reads/(n log n) drifts from 2.755 to 2.861 across a 32-times ladder, and the report says so rather than naming the nearest candidate. And two classes that both settle are a refusal rather than a tie to be broken. The separation arithmetic is done for you on the nearest pair: n and n log n differing by only 1.3x across this ladder, a top rung of 2048 making that 1.8x. The committed control is one test asserting three functions produce three different answers at once: n², log n, and a refusal. A tool that always names a class and a tool that always refuses both fail it.
The instrument only sees the object it wrapped, which is the sharpest limit. An out-of-place algorithm copies its input and works where nothing is counting. A naive measurement of merge sort therefore reports n reads, which is true and is not what anyone means by the cost of a merge sort. A function may declare a second probe parameter and wrap its own working structures on the same counter, opt-in and visible in the signature. One test asserts both sides: far more than n reads with the probe, and exactly n without.
Two findings about the dependency were reported in the README rather than worked around quietly, and both paid off. The zero-error rung being dropped, with a message describing the ladder when the truth was about the observable, is the defect undetermined 0.2.0 has since fixed. And the two halves of undetermined formatted a large plateau differently, truth=1e+06 in Python against truth=1000000 in JavaScript, diverging for every integer at or above 10⁶. Its own parity suite asserted those strings agree, and had always passed, because its test ladder tops out at 512. countfn's parity suite compares the rendered report, so it caught the divergence on the first run after that comparison was added. The fix locally was not to reformat somebody else's sentence but to state the plateau in sizes, which is what a reader thinks in anyway. 4 rungs agree within 2.0 sigma, from size 128 up beats 4 rungs from truth=16777216, which is n³ at 256 and tells nobody anything.
Fifteen mutations were applied to the source and all fifteen are caught, and the two that needed better tests rather than fixes are the interesting ones. The nearest-pair mutation survived its first run because the fixture's first pair happened to be the nearest one. And half_up exists because a mean of 1966.5 printed as 1966 in one half and 1967 in the other, which every assertion comparing the numbers had passed. The halves were rounding ties in opposite directions, and only the string comparison saw it.
What it does not answer is how long anything takes. Two algorithms with the same read count can differ by an order of magnitude in cache behaviour, and this reports them identical. It answers how the work grows, which is the question a timing answers badly; it does not answer how long the work takes, which is the question a timing answers well. Use both.
Top comments (0)