Package it.unimi.dsi.law.util

Class ExchangeCounter

java.lang.Object

it.unimi.dsi.law.util.ExchangeCounter

public class ExchangeCounter
extends Object

Computes the number of discordances between two score vectors using Knight's O(n log n) MergeSort-based algorithm.

The number of discordances between two score vectors is the number of unordered pairs whose mutual relationship is opposite in the two orders (ties in either side are not counted).

The computation of the number of discordances is the most onerous step in the computation of Kendall's τ It is possible to compute the number of discordances trivially using BubbleSort and counting the exchanges that are necessary to turn from the ranking induced by the first score vector into the ranking induced by the second score vector, but Knight noted that the same can be done in time O(n log n) using a stable sorting algorithm [William R. Knight, &lduo;A Computer Method for Calculating Kendall's Tau with Ungrouped Data”, J. Amer. Statist. Assoc., 61(314):436−439, 1966].

This class makes it possible to count the number of exchanges that will change a given ranking, specified by an array of integers, into another order, specified by a score vector. You must create an exchange counter first, and then invoke count(). You are welcome to use a one-liner (e.g., new ExchangeCounter(v, c).count()), so that the large support array allocated by an instance of this class is collected quickly. Optionally, you can pass a support array explicitly.

The slightly awkward structure is due to the necessity (in the computation of Kendall's τ) of computing the first order externally, and to avoid passing around several additional parameters in recursive calls.

Constructor Summary

Constructors

Constructor	Description
ExchangeCounter(int[] perm, double[] v)	Creates a new exchange counter.
ExchangeCounter(int[] perm, double[] v, int[] support)	Creates a new exchange counter with a provided support array.

Method Summary

Modifier and Type	Method	Description
long	count()	Computes the number of exchanges.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

ExchangeCounter

public ExchangeCounter(int[] perm,
double[] v,
int[] support)

Creates a new exchange counter with a provided support array.

This constructor avoids the need to allocate a support array, in case one is already available.

Parameters:

perm - the array to be sorted.

v - the score vector used to compare the element of perm.

support - an array that will be used as temporary storage during the computation (its content will be erased); must be at least as long as a.

ExchangeCounter

public ExchangeCounter(int[] perm,
double[] v)

Creates a new exchange counter.

Parameters:

perm - the array to be sorted.

v - the score vector used to compare the element of perm.

Method Details

count

public long count()

Computes the number of exchanges.

Note that a call to this method will actually sort the permutation at creation time.

Returns:

the number of exchanges that will order the permutation provided at creation time using the score vector provided at creation time.