CorsortGainLexi

class corsort.CorsortGainLexi(compute_history=False, record_leq=False, final_scorer=<function scorer_rho>)[source]

Corsort with lexicographic gain (information gain, difference of position estimates).

Examples

>>> np.random.seed(22)
>>> n_ = 15
>>> p = np.random.permutation(n_)
>>> corsort = CorsortGainLexi(compute_history=True)
>>> corsort(p).n_comparisons_
39
>>> entropy_bound(n_) 
40.24212...
>>> corsort.history_distances_ 
[76, 64, 76, 74, 74, 68, 64, 64, 60, 60, 46, 44, 34, 32, 30, 28, 20, 22, 22, 20, 20, 22, 20, 18, 16, 12, 12, 10,
 10, 6, 4, 2, 4, 4, 4, 2, 2, 2, 2, 0]
>>> corsort.__name__
'corsort_lexi'

apply_i_lt_j(i, j)

Assuming perm[i] < perm[j], update the poset accordingly.

Parameters:

i (int) – Index of the small item.
j (int) – Index of the big item.

Examples

>>> corsort = Corsort()
>>> corsort.n_ = 4

Assume that we know perm[0] < perm[1], and perm[2] < perm[3]:

>>> corsort.leq_ = np.array([
...     [ 1,  1,  0,  0],
...     [-1,  1,  0,  0],
...     [ 0,  0,  1,  1],
...     [ 0,  0, -1,  1],
... ])

Assume we learn that perm[1] < perm[2]:

>>> corsort.apply_i_lt_j(1, 2)
>>> corsort.leq_
array([[ 1,  1,  1,  1],
       [-1,  1,  1,  1],
       [-1, -1,  1,  1],
       [-1, -1, -1,  1]])

Now we know the full order by transitivity.

compare_and_update_poset(i, j)

Perform a comparison between perm[i] and perm[j], and update the poset accordingly.

Parameters:

i (int) – First index.
j (int) – Second index.

distance_to_sorted_array()

Distance to sorted array.

Returns:: Distance between the current estimation and the sorted array.
Return type:: int

gain(i, j)[source]

Ensured gain when comparing perm[i] and perm[j].

Parameters:

i (int) – First index.
j (int) – Second index.

Returns:

Ensured gain if i and j are compared. Cf. gain_i_lt_j().

Return type:

tuple

gain_i_lt_j(i, j)[source]

Gain if we learn that perm[i] < perm[j].

Parameters:

i (int) – Index of the small element.
j (int) – Index of the big element.

Returns:

Potential gain if we compare i and j and find that perm[i] < perm[j]. First element: number of pairs for which we will learn their comparison if it is the case. Second element: difference of position estimate between i and j (currently, i.e. before comparing them).

Return type:

tuple

property history_comparisons_values_

History of the pairwise comparisons, in terms of compared values. Tuple (x, y) means that items of values x and y were compared, and that x < y.

Type:: list of tuple

next_compare()

Iterator of pairwise comparisons to make.

Returns:: An iterator of pairwise comparisons to make.
Return type:: iterable

test_i_lt_j(i, j)

Test whether perm[i] < perm[j].

Parameters:

i (int) – First index.
j (int) – Second index.

Returns:

True if item of index i is lower than item of index j.

Return type:

bool

Notes

The history of distance is computed just before the comparison. Hence it should be computed a last time at the end of the algorithm.

update_position_estimates()

Update position estimate of each item.

Examples

>>> corsort = Corsort(final_scorer=scorer_delta)
>>> corsort.n_ = 4
>>> corsort.leq_ = np.array([
...     [ 1,  1,  1,  1],
...     [-1,  1, -1, -1],
...     [-1,  1,  1,  0],
...     [-1,  1,  0,  1],
... ])
>>> corsort.update_position_estimates()
>>> corsort.position_estimates_
array([-3,  3,  0,  0])