Package it.unimi.dsi.law.big.util

Class ExchangeCounter

java.lang.Object
it.unimi.dsi.law.big.util.ExchangeCounter
public class ExchangeCounter
extends Object
Computes the number of discordances between two score big 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​(long[][] perm, double[][] v)
    Creates a new exchange counter.
    ExchangeCounter​(long[][] perm, double[][] v, long[][] support)
    Creates a new exchange counter with a provided support big 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​(long[][] perm, double[][] v, long[][] support)
      Creates a new exchange counter with a provided support big array.

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

      Parameters:
      perm - the big array to be sorted.
      v - the score big vector used to compare the element of perm.
      support - a big 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​(long[][] perm, double[][] v)
      Creates a new exchange counter.
      Parameters:
      perm - the big array to be sorted.
      v - the score big 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.