genieclust.tools#

Functions one might find useful, but not necessarily

genieclust.tools.argkmin(x, k)#

Finds the position of an order statistic

Parameters:

xndarray: A vector with n elements of type int, float, or double.
kint: An integer between 0 and n - 1, preferably small.

Returns:

int: The index where the (k-1)-th smallest value in x is located.

Notes

It holds argkmin(x, 0) == argmin(x), or, more generally, argkmin(x, k) == np.argsort(x)[k].

Run time is \(O(nk)\) and working memory is \(O(k)\). An insertion sort-like scheme is used to locate the order statistic. In practice, the function is very fast for small k and randomly ordered or almost sorted (increasingly) data.

Example timings	argkmin(x, k)	np.argsort(x)[k]
(ascending) n= 100000000, k= 1:	0.060s	4.388s
(descending)	0.168s	7.329s
(random)	0.073s	26.673s
(ascending) n= 100000000, k= 5:	0.060s	4.403s
(descending)	0.505s	7.414s
(random)	0.072s	26.447s
(ascending) n= 100000000, k= 100:	0.061s	4.390s
(descending)	8.007s	7.639s
(random)	0.075s	27.299s

Examples

>>> x = np.r_[2, 3, 6, 5, 1, 4]
>>> genieclust.tools.argkmin(x, 0) # index of the smallest value
4
>>> genieclust.tools.argkmin(x, 1) # index of the 2nd smallest value
0

genieclust.tools.cummax(x)#

Cumulative maximum

Parameters:

xndarray: A vector with n elements of type int, float, or double.

Returns:

ndarray: A vector of length n whose i-th element is equal to max(x[:i]).