flopscope.

flopscope.numpy.lexsort

fnp.lexsort(keys, axis=-1)[flopscope source]

Perform an indirect stable sort using a sequence of keys.

Adapted from NumPy docs np.lexsort

Areacore
Typecustom
NumPy Refnp.lexsort
Cost
per-operation
Flopscope Context

Multi-key sort; cost = k*n*ceil(log2(n)).

Given multiple sorting keys, lexsort returns an array of integer indices that describes the sort order by multiple keys. The last key in the sequence is used for the primary sort order, ties are broken by the second-to-last key, and so on.

Parameters

keys:(k, m, n, ...) array-like

The k keys to be sorted. The last key (e.g, the last row if keys is a 2D array) is the primary sort key. Each element of keys along the zeroth axis must be an array-like object of the same shape.

axis:int, optional

Axis to be indirectly sorted. By default, sort over the last axis of each sequence. Separate slices along axis sorted over independently; see last example.

Returns

indices:(m, n, ...) ndarray of ints

Array of indices that sort the keys along the specified axis.

See also

Examples

Sort names: first by surname, then by name.

>>> import flopscope.numpy as fnp
>>> surnames =    ('Hertz',    'Galilei', 'Hertz')
>>> first_names = ('Heinrich', 'Galileo', 'Gustav')
>>> ind = flops.lexsort((first_names, surnames))
>>> ind
array([1, 2, 0])
>>> [surnames[i] + ", " + first_names[i] for i in ind]
['Galilei, Galileo', 'Hertz, Gustav', 'Hertz, Heinrich']

Sort according to two numerical keys, first by elements of a, then breaking ties according to elements of b:

>>> a = [1, 5, 1, 4, 3, 4, 4]  # First sequence
>>> b = [9, 4, 0, 4, 0, 2, 1]  # Second sequence
>>> ind = flops.lexsort((b, a))  # Sort by `a`, then by `b`
>>> ind
array([2, 0, 4, 6, 5, 3, 1])
>>> [(a[i], b[i]) for i in ind]
[(1, 0), (1, 9), (3, 0), (4, 1), (4, 2), (4, 4), (5, 4)]

Compare against argsort, which would sort each key independently.

>>> flops.argsort((b, a), kind='stable')
array([[2, 4, 6, 5, 1, 3, 0],
       [0, 2, 4, 3, 5, 6, 1]])

To sort lexicographically with argsort, we would need to provide a structured array.

>>> x = flops.array([(ai, bi) for ai, bi in zip(a, b)],
... dtype = flops.dtype([('x', int), ('y', int)]))
>>> flops.argsort(x)  # or flops.argsort(x, order=('x', 'y'))
array([2, 0, 4, 6, 5, 3, 1])

The zeroth axis of keys always corresponds with the sequence of keys, so 2D arrays are treated just like other sequences of keys.

>>> arr = flops.asarray([b, a])
>>> ind2 = flops.lexsort(arr)
>>> flops.testing.assert_equal(ind2, ind)

Accordingly, the axis parameter refers to an axis of each key, not of the keys argument itself. For instance, the array arr is treated as a sequence of two 1-D keys, so specifying axis=0 is equivalent to using the default axis, axis=-1.

>>> flops.testing.assert_equal(flops.lexsort(arr, axis=0),
... flops.lexsort(arr, axis=-1))

For higher-dimensional arrays, the axis parameter begins to matter. The resulting array has the same shape as each key, and the values are what we would expect if lexsort were performed on corresponding slices of the keys independently. For instance,

>>> x = [[1, 2, 3, 4],
... [4, 3, 2, 1],
... [2, 1, 4, 3]]
>>> y = [[2, 2, 1, 1],
... [1, 2, 1, 2],
... [1, 1, 2, 1]]
>>> flops.lexsort((x, y), axis=1)
array([[2, 3, 0, 1],
       [2, 0, 3, 1],
       [1, 0, 3, 2]])

Each row of the result is what we would expect if we were to perform lexsort on the corresponding row of the keys:

>>> for i in range(3):
... print(flops.lexsort((x[i], y[i])))
[2 3 0 1]
[2 0 3 1]
[1 0 3 2]