Module search 

Search and sort over slices of keys. A key is an item read as a whole number (Key), or an unsigned word whose order is the order you want (RadixKey). Float::order_key gives each float such a word, as wide as the float. Positions take 32 bits inside these functions, so a slice holds at most u32::MAX items. tolerant builds its searches over floats on these functions.

index_of and classes index the first position of each key; firsts marks first occurrences directly. index_of passes over x once for each item of y when y has at most SCANNED items. The index is a table when the keys span at most twice the slice’s length, or 1024, and a hash table otherwise. numbered numbers the classes in order of first position, with each one’s size. grouped_keys numbers them the same way from a table of keys, with each one’s positions, numbered_keys with each item’s number, and class_counts gives only their sizes. counts counts the items with each key in such a table. sort_rows sorts keys that span such a table by counting them. It sorts other keys with an LSD radix sort that skips any byte that is the same in every key. view_sort_along, view_partition_along and view_quantiles_along work on each item’s SortKey, which reads back to the item exactly. A sort counts, sorts a float lane through a bitonic network on vectors, or sorts the keys by comparison or by the same radix sort. With several threads, the radix sort splits each pass of more than RADIX_PIECE keys across them, and index_of splits its lookups.

Structs

Chains

Positions grouped by a 64-bit key, such as a hash. A map gives the first and last position pushed with each key, and each position links to the next one pushed with the same key. Positions pushed in order give chains in order.

ClassNumbers

Each item’s class number below count, at any integer width: classes that a fold totals, or a scan runs, each on its own (Grouping).

Exact

A cell compared exactly: an atom, which has no shape, or an array of compact Booleans, integers or characters, with its shape. Two cells are equal when their shapes and items are equal. Booleans and integers of any width compare as numbers, and characters only with characters. A hash leaves out the shape, which equality compares. Cells order as BPL grades them: an atom before an array, arrays by rank, then item by item with numbers before characters (crate::characters::order_of_kinds), then by length and shape.

Grouped

The classes of a slice, numbered from 0 in order of their first positions, with the positions of each.

Groups

Positions group by group, ascending within each group, with the number in each group. Each buffer holds whole groups. The two classes of a slice of two keys take a buffer each, which into_buffers hands over without a copy. Other groups share one buffer. Positions are u32s.

Links

The positions in one or two of Chains’ chains, each in the order they were pushed. Keep next this small: the search loops that call it rely on it inlining.

Numbered

The classes that classes gives, numbered from 0 in order of their first positions, with the number of items in each.

Ranges

One range of positions for each group, in any order, as each one’s start and length: a segmented array’s vector items as their entries in its leaf. Each range folds by Reduction::slice and scans by Reduction::scan. An empty range folds to R::unit().

Enums

Set

Set operations retain first-occurrence order, matching as classification and membership do.

Constants

SCANNED

The number of items of y up to which index_of and tolerant::index_of pass over x once for each, in place of building an index.

Traits

Grouping

A grouping of a vector’s items that a fold totals, or a scan runs, each on its own: classes by number (ClassNumbers), or ranges of positions (Ranges), as a segmented array’s items are ranges of its leaf.

Key

An item as a whole number: a Boolean’s 0 or 1, an integer, a character’s code point, or an order key. Two items match exactly when their keys are equal. A 64-bit unsigned key wraps to a negative number, which keeps keys distinct.

RadixKey

An unsigned key that sort_rows sorts one byte at a time.

Functions

bins

For each of values, the number of boundaries at or below it, as BQN’s dyadic ⍋ and NumPy’s searchsorted with side='right' give it. boundaries must be in ascending order. When they are, and they span few enough keys for a table, a table of the count of boundaries at or below each key answers each value with one read. Otherwise each value takes a binary search, which halves its range with a select in place of a branch, so mispredicted comparisons don’t stall it. Sixteen values search together, level by level, because every search of boundaries halves the same lengths. Their loads at each level are then independent.

class_counts

The number of items in each class of x, in order of the classes’ first positions, as numbered counts them. Keys that span a table take counts, then a pass for first positions that stops once it has found every key x holds, with nothing written for each item.

classes

The first position of each item’s key in x, which represents the item’s class.

counts

The least key of x, and the number of items with each key from it to the greatest (counts_into), when table allows that range.

counts_into

Writes the number of items of x with each key into counts, whose entries are zero and stand for the keys from min on, covering every key of x. Up to 4 keys, each count but the first takes a pass that vectorizes. With fewer than 64 keys, runs of one key are common, and each count would wait for the previous one to be stored. So the items then go to four tables in turn, which are summed at the end. On the Mac, four tables made 2 keys 3 times as fast as one table, and 64 keys or more no faster.

dense_offsets

Whether offsets are dense enough to use a table over the size positions they fall below.

find_with

Marks where pattern_shape fits within shape and every pattern item matches. Shapes describe compact row-major buffers; same compares their flat positions. A lower-rank pattern has leading axes of length one.

first_classes

The first position of each item’s key in x, from one pass that records and reads each key together. Two items’ keys are equal exactly when the items match.

first_matches

For each item of y, the position of the first equal item of x, or the length of x where none is equal, from a hash map. index_of takes it for keys that span too much for a table.

firsts

Whether each item is the first with its key. Narrow key ranges mark first positions in a table; wider keys use a hash set.

grouped

The positions of groups in order of group, keeping their order within each group, with the number in each of the n groups.

grouped_by

The positions of items grouped by the group that group gives each item, keeping their order within each group, with the number in each of the n groups. grouped is the version for groups given as numbers.

grouped_keys

The classes of x as Grouped gives them, or None when its keys span too many values for a table. Each class’s positions come from one pass over x.

index_of

For each item of y, the first position of its key in x, or the length of x when it has none. A slice here holds at most u32::MAX items, so positions are u32s.

inverse_permutation

Inverts a permutation: each position’s rank in order, as a T such as a grade’s u32 or an axis order’s usize. Every position must occur exactly once.

member_layout

The layout of the major cells of an array laid out by layout, when a query laid out by query can match one of them: its shape equals theirs, and its axis names and keys agree with theirs (Layout::matches). None when it can’t. A Rank error for a rank-0 array, which isn’t a container.

numbered

Numbers the classes in classes, which gives each item the first position of its class, as classes and tolerant::classes do, and counts each class.

numbered_keys

The classes of x as Numbered gives them, numbered as grouped_keys numbers them, or None when its keys span too many values for a table. A fold of each class reads these numbers in one pass, where each class’s positions would take a pass to build and a gather to read. A pass that numbers each key as it first meets it, in place of numbered_table, measured slower: it stores to a table entry for every item, and repeated keys then wait on those stores. Each class’s count comes from one count of the class numbers (ClassNumbers::counts).

occurrences

For each offset, how many preceding offsets equal it, and the largest occurrence count. None when none repeats. Every offset must be below size.

quantiles

Linear-interpolated quantiles of x. Selection keeps the input width; f16 interpolation computes in f32. Empty inputs give NaN. A probability outside [0, 1], or NaN, gives a Domain error.

select

Places each of the sorted, distinct ranks at its sorted position, leaving the runs between them unordered. Ranks must be below x.len(). Selecting the middle requested rank first partitions disjoint runs for the remaining ranks; one rank takes linear time.

sort_rows

The rows of an n-row table in ascending order, comparing entries column by column from the first. Rows that compare equal keep their order of position. columns holds each column’s n keys, whose unsigned order is the order you want. A caller fills them from its items in a pass that vectorizes. Fewer than 256 rows take a comparison sort. One column whose keys tabled allows takes a counting sort. Other tables take the radix sort once for each column, from the last. Positions are u32s, as a slice holds at most u32::MAX items.

view_argextremes

The first minimum or maximum position of each lane, without gathering lanes or allocating a result per lane. Comparisons use sorting’s NaN-last order.

view_argpartition

Positions partitioned around rank. Equal values need not keep their original order.

view_bins

For each item of values, the number of boundaries at or below it, as bins counts them: for Booleans, integers or characters of one kind, with integers of different widths read as i64, and for floats of one width by their order keys. None for other pairs.

view_bins_below

For each item of values, the number of boundaries below it, for views of one dtype other than complex: bins of the complemented order keys, with boundaries reversed. None for other views.

view_class_counts

The size of each class of x, in order of first position, as view_classes matches them. Booleans, integers and characters that span a table count from it, as class_counts does. None for complex numbers.

view_classes

The class of each item of x, as the first position of an item that matches it: exactly for Booleans, integers and characters, through classes, and within t for floats, through tolerant::classes, which checks for an interrupt as it goes. None for complex numbers.

view_contains

Whether one of cells consecutive cells of x matches y. The caller checks cell shapes and aligns keys before searching, as view_member does.

view_find

Marks occurrences of a compact pattern in a compact target, with the shapes and geometry of find_with. Booleans, integers and characters of one kind match exactly, and floats of any widths match within t, including NaN with NaN. None for other dtype pairs.

view_firsts

Whether each item of x is the first of its class, as view_classes matches them. None for complex numbers.

view_grade

Stable positions that order a vector. Equal items keep their original positions, including signed zeros and NaNs.

view_grouped

The classes of x, as view_classes matches them, numbered in order of first position, with the positions of each. Booleans, integers and characters that span a table group straight from it, as grouped_keys does. None for complex numbers.

view_index_of

For each item of y, the first position in x of an item that matches it, or the length of x where none does: exactly for Booleans, integers or characters of one kind, with integers of different widths read as i64, and within t for floats of one width, checking for an interrupt as it goes. An integer haystack also takes f64 needles when every needle is an integer that tolerant::integer_of accepts. None for other pairs.

view_lexgrade

Stable lexicographic order of n rows, with columns in primary-first order. Each column is a compact view, its first key’s offset and the step between keys. Columns can have different dtypes; radix keys keep each column’s item width. None for complex keys.

view_lexgrade_along

Stable positions that order each lane of [outer, len, inner], as view_lexgrade orders rows, laid out as the lanes’ items are. Each column, in primary-first order, is a compact view, the offset of the first item’s key and the step between successive items’ keys: 1 where the view holds one key for every item, or a row’s width where each item is a row of a matrix. None for complex keys. An interrupt stops a run of several lanes with the interrupt hook’s error.

view_matches

Whether equal-length compact cells match. Booleans and integers match floats as f64s within t. None when their kinds need the caller’s numeric conversion.

view_member

Whether query matches one major cell of x, as ≡ matches arrays, for compact items in row-major order. The query’s layout must match a cell’s (member_layout). Its items line up with the cell’s by key. Items compare at the two views’ common dtype, as view_matches compares them, and characters never match numbers. It checks for an interrupt as the search goes. A Rank error for a rank-0 x.

view_numbered

The classes of x, as view_classes matches them, numbered in order of first position, with each item’s class number. Booleans, integers and characters that span a table number straight from it, as numbered_keys does. None for complex numbers.

view_order_keys

Each item’s order key, widened to 64 bits. Within one dtype, their unsigned order is the items’ order, with every NaN last. None for complex numbers.

view_partition_along

Partitions each lane around rank in its output buffer, comparing its items’ SortKeys, computed once. Value partitioning writes the items back from the keys, and index partitioning writes i64 positions. None for complex numbers. An interrupt stops it with the interrupt hook’s error.

view_quantiles_along

Quantiles of each lane, with a leading probability axis. Integers select exactly before converting the selected values to f64; floats keep their width. None for complex numbers, which have no order. A probability outside [0, 1], or NaN, gives a Domain error, and an interrupt the interrupt hook’s error.

view_selected

The positions of the items of x whose ranks in a stable grade, ascending or descending where down, fall in range, in rank order. Positions break ties because taking from a stable grade observes them. A run nearer the end is found in the reversed order. None for complex numbers.

view_set

Unique values of a set operation on two views of one dtype. Shared searches do all matching; gathered output has no keys or names. None for unsupported pairs.

view_sort

A sorted vector: one lane of view_sort_along.

view_sort_along

Sorts each lane into its own output. A lane of 256 items or more whose values span a small table sorts by counting, and a float lane through networked where it takes the lane’s length. Other lanes sort their items’ SortKeys, computed once, by an unstable comparison sort below value_radix_from and by the radix sort from there, then write the items back from the keys. Equal keys come from equal items, so the result doesn’t depend on how the sort orders them, and ¯0 comes before 0. Lanes run through the shared stack scheduler, which reuses each thread’s buffers. A single lane runs on the calling thread, where the radix sort can split its passes across threads. None for complex numbers. An interrupt stops a run of several lanes with the interrupt hook’s error.