Counting

A switch that reads the long runs

The two-ended selection sort's record of adjacent order pays on long runs and costs on short ones, and a switch on the mean run the pass between neighbours reads could not tell an input of even short runs from one whose keys are half in short runs and half in long. The proposal counted something chosen for what the record is worth: the share of keys the pass finds in runs of at least eight, keeping the record when it reaches a tenth. At three word reads a comparison that switch chooses right on all seventeen inputs measured, including five new ones built to defeat it, where the mean's best threshold leaves up to 0.18%. But the prediction said it would be right at every rate, and it is right only at three: at one word read a comparison it costs 1.2% on runs of eight, at four it drops the record on one run of 64 among single keys, which at that rate pays. One number from the pass is enough to decide. Which number depends on the price of a word.

The two-ended selection sort finds the smallest and largest of its unsorted part on every scan, and a run of essays has taught it to remember. Its record holds two bits for each neighbouring pair — unknown, or known in one direction — which a run answers what nobody asked introduced, and a question whose keys lie at the two ends of a stretch of pairs pointing one way can be answered from the record instead of by comparing. What it costs to consult two bits a pair priced reading it, and a run end kept in a register and a register dropped by what it already knew made the reading short. A register kept through a confirmation made consulting the record cheap, a few register words a question. What it saves is comparisons, and on long runs it saves many; on short runs it saves too few to pay for the reading.

A record switched off by its runs let the sort decide. The pass between neighbours, which the sort makes before its first scan, counts the runs, and a switch kept the record only when the mean run, nn over the runs, reached a threshold. Comparisons and word reads were charged together at an exchange rate ρ\rho, word reads a comparison is worth. On even runs at ρ=3\rho = 3 the best threshold was a mean of six, as predicted, and what it saved there was three thousandths of a sort. The larger result was the risk. On inputs whose keys are half in runs of two and half in runs of 64, the pass reads a mean of 4.4, under six, while the long half saves the record 10,052 comparisons; with runs of 512 for the long half, 74,000, and switching the record off there cost 31%. Over every input the best mean threshold was three: keep the record for everything but runs of two.

That essay’s closing section said why. The record’s value on an input lives in its long runs, and a mean is a count of runs, which short runs dominate. It proposed counting the long runs directly: let the pass count the keys that lie in runs of at least L∗L^\ast, and keep the record when that share is at least ss. The prediction: at ρ=3\rho = 3, L∗=8L^\ast = 8 and ss of a tenth keep the record on every uneven input and drop it on even runs of two and four, bringing the worst cost over every input from 0.2% to under 0.05%, at every rate. The named risk: long runs that are long but few, one run of 64 among a thousand runs of one.

Five inputs made for the risk

Each input is sorted twice, once with the record kept and consulted through quiet registers and once without it, both after the pass and with the chains, as before; the cost of a sort at rate ρ\rho is its comparisons times ρ\rho plus, if the record is kept, the register words it reads. The better choice on an input is whichever of the two costs less, and a switch’s cost on an input is measured as a share above that better choice. The inputs are the earlier essay’s twelve — even runs of 2, 4, 8, 16, 32, 64 and 256 keys, and five inputs of two halves — and five new ones aimed at the risk: three runs of 32 among runs of two, a tenth of the keys; four runs of 64 among runs of two, a quarter; two runs of 64 among runs of four, an eighth; one run of 256 among runs of four, a quarter; and one run of 64 among single keys, a sixteenth.

The pass sees runs as they lie, not as they were built — the same pass a pass repaid by the scans after it gave the sort, now read for more than its count. Adjacent pieces join when the last key of one is below the first of the next, so on even runs of four 2.3% of the keys sit in runs of eight or more, and on the input built from single keys the random order makes its own runs of about two. The share the switch reads is the share of keys in runs the pass actually finds, which is all a sort could know before its first scan.

The hero plate is that share against what the record saves, at ρ=3\rho = 3. Every input where the record is worth keeping has at least 15% of its keys in runs of eight or more; every input where it is not has at most 9%. A switch at a tenth falls in the gap between them and chooses right on all seventeen.

What the mean could not separate

The mean run the pass reads mixes the two kinds of input: at three word reads a comparison the record loses on inputs with a mean of up to 4.05 keys and gains on some with means as low as 3.16, so the mean's best threshold, 3, chooses wrong on 1 of 1717 inputs of 1,024 keys sorted by the two-ended selection sort with and without its record, at 3 word reads a comparison: for each, the pass's mean run and the record's saving as a share of the cost without it (negative where the record costs more than it saves). runs of 2: 2.40, -0.31%; runs of 4: 4.05, -0.17%; runs of 8: 8.00, 0.23%; runs of 16: 16.00, 1.01%; runs of 32: 32.00, 2.52%; runs of 64: 64.00, 5.22%; runs of 256: 256.00, 21.11%; half runs of 2, half of 64: 4.41, 2.86%; half runs of 4, half of 256: 8.00, 11.50%; half runs of 2, half of 512: 4.90, 23.59%; half runs of 8, half of 128: 15.06, 5.74%; half runs of 4, half of 32: 7.16, 1.11%; three runs of 32 among runs of 2: 2.63, -0.07%; four runs of 64 among runs of 2: 3.16, 1.42%; two runs of 64 among runs of 4: 4.59, 0.58%; one run of 256 among runs of 4: 5.39, 5.59%; one run of 64 among single keys: 2.17, -0.02%.00.1000.200mean run the pass reads (log scale)record's saving, share of the cost without it2481664256best mean threshold, 3filled: the record pays · hollow: it does not3 word reads a comparison17 inputs
Fig. 1 The same seventeen inputs at three word reads a comparison, the record’s saving against the mean run the pass reads, with the mean’s best threshold, three, marked. Losses run to a mean of 4.05 keys; gains begin at 3.16.

The mean run mixes the two kinds of input: at three word reads a comparison the record loses on inputs with a mean of up to 4.05 keys and gains on some with means as low as 3.16, so no threshold on the mean can choose right on all of them; the best, three, chooses wrong on one in seventeen. The plate is the earlier essay’s diagnosis drawn with the new inputs added. Four runs of 64 among runs of two read a mean of 3.16 and the record saves 1.4% there; even runs of four read 4.05 and the record loses 0.17%. A threshold between those means would have to sit both above 4.05 and below 3.16.

The mean’s best threshold copes by giving up the cheap case. At three it keeps the record on every input but runs of two, and pays on even runs of four, the one input it gets wrong, 0.18% of the sort. That is a small number, and it is the worst any input costs that switch. The earlier essay measured the price of a switch that tried for more — a threshold of six — at 31% on the uneven inputs, and the mean has no setting between giving up runs of four and giving up the uneven inputs.

The share has a setting. The record’s value grows with the keys in long runs: on an input with a quarter of its keys in runs of 64, those keys are where the record saves comparisons, and the other three quarters, in runs of two, are where it reads words for nothing. The share counts exactly the part that pays, so on the hero plate the inputs sort themselves by what the record is worth, in a way the mean does not.

Every setting at three word reads

At 3 word reads a comparison: the worst cost above the better choice, over the 17 inputs, for a switch on the share of keys in long runs at every L* and share, and for the mean run at every threshold — runs of eight at a tenth leave 0.000%, the mean's best threshold, 3, leaves 0.175%Worst regret over 17 inputs at 3 word reads a comparison. Share switch: runs of 8 or more: 0.01 0.175%, 0.02 0.175%, 0.05 0.066%, 0.1 0.000%, 0.2 0.580%, 0.3 5.920%, 0.5 5.920%; runs of 16 or more: 0.01 0.228%, 0.02 0.228%, 0.05 0.228%, 0.1 0.228%, 0.2 0.580%, 0.3 5.920%, 0.5 5.920%. Mean threshold: 2 0.311%, 3 0.175%, 4 1.437%, 6 30.871%, 8 30.871%, 12 30.871%, 16 30.871%.share of keys in long runs at which the record is kept0.010.020.050.10.20.30.5runs of 8 or more0.170.170.070.000.585.925.92runs of 16 or more0.230.230.230.230.585.925.92mean run at which the record is kept20.3130.1741.44630.87830.871230.871630.87mean run3 word reads a comparison · per centworst over 17 inputs
Fig. 2 At three word reads a comparison, the worst cost above the better choice over the seventeen inputs, in per cent, for the share switch at L∗L^\ast of 8 and 16 and shares from 0.01 to 0.5, and for the mean switch at thresholds from 2 to 16. Runs of eight at a tenth: 0.000. The mean’s best, three: 0.175.

At three word reads a comparison the share switch on runs of eight at a tenth leaves nothing — it chooses the better of on and off on every input — while the mean’s best threshold, three, leaves 0.175%; the share’s neighbours are nearly as good, and the settings that fail fail on the inputs either side of the gap. The prediction holds at its own rate and by more than it claimed: under 0.05% was predicted, and nought is measured. A share of a twentieth on runs of eight leaves 0.066%, on the input with three runs of 32 among runs of two, whose 9.4% of keys in long runs is just under a tenth and whose record loses 0.07% at this rate. A share of a fifth leaves 0.58%, on two runs of 64 among runs of four, which at 15% is just over the gap’s other side.

Runs of sixteen behave nearly the same, shifted. The input whose verdict differs is even runs of eight: every key lies in a run of eight and none in a run of sixteen, so at L∗=16L^\ast = 16 the switch drops the record there, and at three word reads a comparison the record saves 0.23% on runs of eight. That is the worst L∗=16L^\ast = 16 does at its best share, 0.23%.

The shape of the grid is the hero plate’s gap seen from the other side. Any share between 9.4% and 14.8% of keys in runs of eight separates the inputs at this rate, and a tenth is inside it with a margin of about a point on one side and five on the other. The margin is thin on the side of the input with three runs of 32. That input was built to sit near a tenth, and it does.

A different number at every rate

The right share moves with the rate: the best switch is runs of 16 at 0.2, then 16 at 0.1, then 8 at 0.1, then 8 at 0.01 at one to four word reads a comparison, leaving 0.471%, 0.000%, 0.000%, 0.000%; runs of eight at a tenth is right only at three, and the mean's best threshold leaves 1.612%, 0.534%, 0.175%, 0.127%Worst cost above the better choice over 17 inputs at each exchange rate, for the best share switch at that rate, the switch on runs of at least 8 at a share of a tenth, and the best mean-run threshold: 1: best share (16, 0.2) 0.471%, runs of 8 at a tenth 1.214%, best mean (4) 1.612%; 2: best share (16, 0.1) 0.000%, runs of 8 at a tenth 0.133%, best mean (3) 0.534%; 3: best share (8, 0.1) 0.000%, runs of 8 at a tenth 0.000%, best mean (3) 0.175%; 4: best share (8, 0.01) 0.000%, runs of 8 at a tenth 0.163%, best mean (always) 0.127%.worst cost above the better choice, over 17 inputs1 word read0.471% · best share: 16, 0.21.214% · runs of 8 at a tenth1.612% · best mean: 42 word reads0.000% · best share: 16, 0.10.133% · runs of 8 at a tenth0.534% · best mean: 33 word reads0.000% · best share: 8, 0.10.000% · runs of 8 at a tenth0.175% · best mean: 34 word reads0.000% · best share: 8, 0.010.163% · runs of 8 at a tenth0.127% · best mean: alwaysper comparisonworst regret
Fig. 3 At each exchange rate, the worst cost above the better choice for the best share switch at that rate, for runs of eight at a tenth, and for the mean’s best threshold. One word read: 0.471%, 1.214% and 1.612%. Four: 0.000%, 0.163% and 0.127%.

The right share moves with the rate: the best switch is runs of 16 at a fifth, then 16 at a tenth, then 8 at a tenth, then 8 at a hundredth, at one to four word reads a comparison; runs of eight at a tenth is right only at three, and at one word read a comparison it leaves 1.2% on runs of eight. The prediction’s last clause — right at every rate — fails. At a cheaper word the record pays on more inputs and the bar for keeping it falls; at a dearer word it pays on fewer and the bar rises. A share chosen at three is in the gap at three, and the gap moves.

At one word read a comparison no share switch measured decides every input. The best, runs of sixteen at a fifth, leaves 0.47% on an input of half runs of four and half of 32, where 50% of keys are in runs of sixteen or more and the record still loses at that rate, because the reading on the short half outweighs the comparisons saved on the long. At two, three and four word reads a comparison some setting is exactly right. The mean’s best threshold is worse than the best share at every rate, by 1.1 points at one word read and by 0.13 at four.

The stakes are small at every rate, and the plate should be read with that in mind. The largest cost any of the three switches on the plate leaves on any input is under two per cent of a sort. What the switch is for is the large cost it avoids: on the input with half its keys in runs of 512 the record saves 23.6% of the sort at three word reads, and a switch that drops it there — the mean’s at six — gives that back.

The few long runs

On inputs whose long runs are few the record's value changes sign with the rate: one run of 64 among single keys costs the record 1.49% at one word read a comparison and saves 0.16% at four, and runs of eight turn from loss to gain between two and three — no share threshold fixed in advance can follow bothThe record's saving as a share of the cost without it at exchange rates of one to four word reads a comparison, on the inputs with few or short long runs: one run of 64 among single keys: 1 -1.49%, 2 -0.39%, 3 -0.02%, 4 0.16%; three runs of 32 among runs of 2: 1 -1.54%, 2 -0.44%, 3 -0.07%, 4 0.12%; runs of 4: 1 -1.61%, 2 -0.53%, 3 -0.17%, 4 0.00%; runs of 8: 1 -1.21%, 2 -0.13%, 3 0.23%, 4 0.41%; two runs of 64 among runs of 4: 1 -0.96%, 2 0.19%, 3 0.58%, 4 0.77%; half runs of 4, half of 32: 1 -0.47%, 2 0.72%, 3 1.11%, 4 1.31%.-0.020-0.01000.0101234word reads a comparison is worthrecord's saving, share of the cost without it½ 4 · ½ 32two runs of 64 in 4runs of 8one run of 64 in singlesthree runs of 32 in 2runs of 41,024 keyssaving by rate
Fig. 4 The record’s saving against the exchange rate on the inputs with few or short long runs: one run of 64 among single keys, three runs of 32 among runs of two, even runs of four and of eight, two runs of 64 among runs of four, and half runs of four and half of 32. One run of 64 among single keys: −1.49% at one word read a comparison, +0.16% at four.

On inputs whose long runs are few the record’s value changes sign with the rate: one run of 64 among single keys costs the record 1.49% at one word read a comparison and saves 0.16% at four, and even runs of eight turn from loss to gain between two and three — no share threshold fixed in advance can follow both. The risk the proposal named is real, and it is a fact about rates rather than about the share. One run of 64 among single keys puts 6.3% of the keys in a run of eight or more; at three word reads a comparison the record loses 0.02% there and the switch, below a tenth, rightly drops it. At four, the record gains 0.16% and the switch still drops it. A share set low enough to keep it at four would keep the record at one word read a comparison on that input, where it loses 1.49%, and on every input with more of its keys in long runs, five of which lose at that rate too.

The plate also shows why these inputs are the hard ones. Each line crosses zero somewhere in the range of rates, because on each the record’s saving and its reading are of the same size. On inputs with many keys in long runs the line is far above zero at every rate and any switch keeps the record; on even runs of two it is below zero at every rate and any switch drops it. The decision is only ever difficult on inputs where it is worth little.

Of the five inputs built to defeat the share, none is decided wrong at three word reads a comparison; four are decided wrong by runs of eight at a tenth at some other rate, and one — four runs of 64 among runs of two — is decided wrong at one word read even by the best share for that rate. The risk was that a share would be fooled by structure. What it is fooled by is price.

Every verdict

Whether the record pays, input by input and rate by rate: it pays on 8, 12, 13, 16 of the 17 inputs at one to four word reads a comparison, and the switch on runs of eight at a tenth disagrees with the better choice on 5, 1, 0, 3 of themFor each input and each exchange rate, whether keeping the record costs less than dropping it, and what the switch on runs of at least eight at a share of a tenth chooses: runs of 2: 1 off, 2 off, 3 off, 4 off; runs of 4: 1 off, 2 off, 3 off, 4 on (switch wrong); runs of 8: 1 off (switch wrong), 2 off (switch wrong), 3 on, 4 on; runs of 16: 1 off (switch wrong), 2 on, 3 on, 4 on; runs of 32: 1 on, 2 on, 3 on, 4 on; runs of 64: 1 on, 2 on, 3 on, 4 on; runs of 256: 1 on, 2 on, 3 on, 4 on; half runs of 2, half of 64: 1 on, 2 on, 3 on, 4 on; half runs of 4, half of 256: 1 on, 2 on, 3 on, 4 on; half runs of 2, half of 512: 1 on, 2 on, 3 on, 4 on; half runs of 8, half of 128: 1 on, 2 on, 3 on, 4 on; half runs of 4, half of 32: 1 off (switch wrong), 2 on, 3 on, 4 on; three runs of 32 among runs of 2: 1 off, 2 off, 3 off, 4 on (switch wrong); four runs of 64 among runs of 2: 1 off (switch wrong), 2 on, 3 on, 4 on; two runs of 64 among runs of 4: 1 off (switch wrong), 2 on, 3 on, 4 on; one run of 256 among runs of 4: 1 on, 2 on, 3 on, 4 on; one run of 64 among single keys: 1 off, 2 off, 3 off, 4 on (switch wrong).1 read2 reads3 reads4 readsfilled: the record pays · ring: the switch chooses wrongruns of 2runs of 4runs of 8runs of 16runs of 32runs of 64runs of 256half runs of 2, half of 64half runs of 4, half of 256half runs of 2, half of 512half runs of 8, half of 128half runs of 4, half of 32three runs of 32 among runs of 2four runs of 64 among runs of 2two runs of 64 among runs of 4one run of 256 among runs of 4one run of 64 among single keys17 inputs, 1,024 keyson or off
Fig. 5 For each of the seventeen inputs and each exchange rate, whether keeping the record costs less than dropping it, and where the switch on runs of eight at a tenth disagrees. The record pays on 8, 12, 13 and 16 of the inputs at one to four word reads a comparison; the switch is wrong on 5, 1, 0 and 3 of them.

The record pays on 8, 12, 13 and 16 of the seventeen inputs at one to four word reads a comparison, and the switch on runs of eight at a tenth disagrees with the better choice on 5, 1, 0 and 3 of them. The table is the whole result in one place. Reading down a column, the inputs where the record pays are a set that grows as words get dearer — not in the sense of the record getting better, but of the comparisons it saves being worth more words each. Reading across a row, nine inputs never change their verdict; the eight that do are the inputs with few long runs and the even runs of four, eight and sixteen.

The switch’s mistakes are where the verdicts move. At one word read a comparison it keeps the record on runs of eight and sixteen and on three of the uneven inputs, where at that rate the record does not pay; at four it drops it on runs of four and on two of the few-long-runs inputs, where it now does. At three it makes none. A switch that wanted to be right at every rate would have to read the rate as well as the runs, which is to say it would have to be told the price of a word.

What the pass knows and what it is not told

The question the proposal closed on was whether one more number from the pass, chosen for what the record is worth, is enough to decide, or whether the decision belongs to each run. On these inputs one number is enough — the share of keys in runs of at least eight — but only for a given rate, and the threshold on that number is a statement about the rate. That is not a failure of the share. It is the same thing the price of remembering an answer found from the other end: the record is worth keeping when a comparison costs more than the words it takes to avoid one, and no property of the input alone can say which that is.

The per-run alternative the proposal mentioned is still open in principle. The runs too short to drop found that forgetting short runs inside the record made it dearer, not cheaper, because the record’s bookkeeping is shared across runs; a decision per run would face the same sharing. The share switch avoids it by making one decision for the input, and the measurement says that one decision, made from the right number, is enough at any single rate.

What changes the decision is the machine, and the machine is the one input the pass never reads. A sort deployed where a word read is cheap relative to a comparison — keys that are long strings, compared character by character — sits at a low rate; one comparing machine integers in registers sits at a high one. A table of the best share at each rate, measured once, would let the sort choose its threshold from the type of its keys.

What the measurement leaves out

One size, 1,024 keys. The record’s saving and the registers’ reading both scale with nn, but not in the same way on every input; a larger array would move the gap.

Four rates, all integers. The best share is measured at one, two, three and four word reads a comparison; between them it was not.

Seventeen inputs, five of them built for this question. A real input’s runs are not pieces of a random permutation each sorted; inputs drawn from real data, such as logs appended in near-order, were not measured.

Still open: a threshold that reads the price

The share switch is right at three word reads a comparison and wrong at the others, and the plates say why: the inputs near the gap are those whose record saves about as much as it reads, and where that balance falls depends on the rate. The pass could compute that balance directly instead of a proxy for it. It knows, as it goes, the runs it finds; the essays on this record have measured what a run of each length saves in comparisons and costs in register words. A switch could sum, over the runs the pass finds, a predicted saving and a predicted reading for each — a small table indexed by run length — and keep the record when the predicted saving times the rate exceeds the predicted reading.

The measurement that follows builds that table from even runs, where saving and reading are measured exactly, applies it to every input here at every rate, and charges the switch’s own arithmetic as word reads. The prediction is that it is right on all seventeen inputs at all four rates, and that its worst cost anywhere is under 0.05%, because it reads the one quantity the share stands in for. It could fail on the halves: the saving on a run depends on the runs around it, since the two-ended sort’s scans cross run boundaries, and a table built from even runs may misprice a long run among short ones. The question is whether the record’s value on an input is a sum of what its runs are worth one at a time, or whether the runs interact enough that only sorting the input tells.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

The objects this essay names

Each one links to every other essay that touches it.

Bit vectorComparison countNatural runPredictionSelection sortSpace time trade