CBQN has flags for arrays to indicate that the cells are ordered (as if sorted): one for ascending ordering and one for descending. Both flags together mean all cells are the same. These flags can be set in many cases, and allow for faster operation in many primitives, including asymptotic improvements. They're particularly important for Bins (โโ) to avoid checking that a large ๐จ is sorted in order to search a much smaller ๐ฉ.
Trivial cases of arithmetic imply flags: for the identity, flags of a are maintained, and constant results can have both flags set.
Many primitives are monotonic in each argument. For example, if aโคb, then (a<k)โฅ(b<k), that is, < is monotonically descending in ๐จ. In the table below, + indicates an ascending argument, which corresponds to maintained order, while - indicates a descending argument and swapped order. The result inherits any flags shared by ๐จ and ๐ฉ (so, a bitwise and) after swapping flags for any descending arguments. Since it's reused, a scalar argument is effectively constant and should count as having both flags set. Table โ counts as having a constant right argument.
| Prim | Bool | ๐จ |
๐ฉ |
|---|---|---|---|
+โโ |
โจโงร |
+ | + |
>โฅ-ยฌ |
+ | - | |
<โค |
- | + |
Multiplication by a constant factor with รโงรท, such as kรv or vรทk, maintains the ordering of v if k is positive, reverses it if negative, and gives a constant result if zero and v is finite.
The following scans F` have ordered results. Since F`โพโฝ applies โฝ to the result of F`, it gives the opposite ordering.
| Prim | Bool | Order |
|---|---|---|
โ |
รโง |
Descending |
โ |
+โจ |
Ascending |
Other primitives have the effects listed below.
| Prim | Monadic | Dyadic |
|---|---|---|
โ |
Sorted up | Same as ๐ฉ |
/ |
Sorted up | Same as ๐ฉ |
โ |
Sorted up | Same as ๐ฉ if no fills |
โ |
Same as ๐ฉ |
Same as ๐ฉ |
โฝ |
Swaps flags | |
โฅ |
sโฅatom is constant |
|
โ |
Same as ๐จ if ๐ฉ up, swapped if ๐ฉ down |
|
โ |
Up if ๐ฉ sorted |
|
โท |
Same as ๐ฉ |
|
โ |
Elements sorted up | Elements same as ๐ฉ |
โพยซยป |
Checkable if ๐จ and ๐ฉ both ordered |
As โพยซยป are fast operations and require a check that can be relatively expensive on short arguments, it's not clear whether they should try to maintain sortedness flags.
Ordering functions โงโจโโ can use flags in obvious ways: pre-sorted arguments make Sort and Grade trivial, and Bins should check for a sortedness flag before attempting to verify that ๐จ is sorted.
Both Bins โโ and Searches โโโโท can apply adaptive galloping methods if both arguments are sorted. There's extensive research on these techniques but I don't have much experience with them.
The minimum and maximum of an ordered list are its first and last cells (reversed if sorted down). This is useful for primitives that perform range checking, as well as folds and scans with โ or โ. In particular, the scan either returns ๐ฉ or acts as โฃ`.
Sorted arguments can be split into runs with binary searches. If the range is much smaller than the length then the runs must be long on average. Then operations such as /โผ or +ยด where a run can be processed in constant time can process runs quickly. For example, +ยด on a sorted-descending boolean list is simply the index of the first 0 as found by a binary search. Other cases include ๐ฉ for monadic /, ๐จ for / and โ, scans with + or boolean โ =, and Match (โกโข) if both arguments are sorted in the same direction.
Small-range selection can be performed with in-register shuffles. For โ with sorted ๐จ, an adaptive technique is to operate on ๐จ one vector register at a time, checking the range with the first and last element. Then either a shuffle or gather can be used as appropriate, or even a broadcast if the first and last index are equal.