TypedArraySort vs Array.sort for Argsorting

Benchmark created on October 7, 2023

Setup

/**
 * Return frequency of each byte value in a byte sequence.
 *
 * @param {Uint8Array} byteSequence - The input byte sequence.
 * @returns {Uint8Array | Uint16Array | Uint32Array | BigUint64Array} - An array containing the byte frequencies.
 */
function getFreqs(byteSequence) {
    // Determine the minimum data type required based on the byte sequence length.
    let dataType = Uint8Array;
    if (byteSequence.byteLength > 255) {
        dataType = Uint16Array;
    }
    if (byteSequence.byteLength > 65535) {
        dataType = Uint32Array;
    }
    if (byteSequence.byteLength > 4294967295) {
        dataType = BigUint64Array;
    }

    // Initialize an array to store byte frequencies.
    const frequencies = new dataType(256);

    // Calculate byte frequencies.
    for (let i = 0; i < byteSequence.length; i++) {
        frequencies[byteSequence[i]]++;
    }

    return frequencies;
}

/**
 * Argsort an Array-like, returning indices that would sort it.
 *
 * @param {Array | TypedArray} arr - The input array or TypedArray.
 * @param {boolean} [reversed=false] - Set to true to argsort in reverse order.
 * @returns {Uint8Array | Uint16Array | Uint32Array} - An array containing the sorted indices.
 * @throws {Error} - If the input is not an array or TypedArray.

// Example usage with arrays of different types:
const values1 = [40.5, 10.2, 30.7, 20.3];
const values2 = new Float32Array([40.5, 10.2, 30.7, 20.3]);

const sortedIndices1 = argsortTypedArray(values1);
const sortedIndices2 = argsortTypedArray(values2);

console.log(sortedIndices1); // Output: Uint8Array [ 1, 3, 2, 0 ]
console.log(sortedIndices2); // Output: Uint8Array [ 1, 3, 2, 0 ]
*/
function argsort(arr, {reversed=false}={}) {
  // Determine the smallest appropriate TypedArray based on the length of the input.
  let indices;
  if (arr.length <= 255) {
    indices = new Uint8Array(arr.length);
  } else if (arr.length <= 65535) {
    indices = new Uint16Array(arr.length);
  } else {
    indices = new Uint32Array(arr.length);
  }

  // Initialize the indices array with values [0, 1, 2, ...].
  for (let i = 0; i < arr.length; i++) {
    indices[i] = i;
  }

  // Sort the indices based on the values in the input array.
  indices.sort((a, b) => reversed ? arr[b] - arr[a] : arr[a] - arr[b]);

  return indices;
}

function argsortArray(arr, {reversed=false}={}) {
  // Determine the smallest appropriate TypedArray based on the length of the input.
  let indices = Array .from (arr .keys())

  // Sort the indices based on the values in the input array.
  indices.sort((a, b) => reversed ? arr[b] - arr[a] : arr[a] - arr[b]);

  return indices;
}

function utfEncode (s) {return (new TextEncoder()).encode(s)}

let fs = getFreqs(utfEncode("🏳️‍🌈xab yabc zabcd"))

Test runner

argsort(fs)

argsortArray(fs)

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published on October 7, 2023