1.0.2 • Published 4 years ago

@bemoje/arr-sort v1.0.2

Weekly downloads
1
License
MIT
Repository
github
Last release
4 years ago

@bemoje/arr-sort

Sort an array considerably faster than the native Array.prototype.sort as a drop-in replacement. Fork of of the famous timsort module, but this module allows for passing comparator-builder options instead of a comparator function. In short, advanced comparators made easy. Timsort: https://www.npmjs.com/package/timsort

Version

Travis CI

Dependencies

Stats

Donate

Installation

npm install @bemoje/arr-sort
npm install --save @bemoje/arr-sort
npm install --save-dev @bemoje/arr-sort

Usage

import arrSort from '@bemoje/arr-sort'

/**
 * OPTIONAL: REPLACE native Array.prototype.sort
 *
 * instead of calling sort(arr, options), you can also use arr.sort(options).
 *
 * It's generally not recommended to replace native class prototype methods, but since timsort is sturdy, tested and tried and proven to be considerably faster and IS truly a drop-in replacement, this might be a case where it could be considered a viable option.
 *
 * To activate this, do:
 */

arrSort.replaceNative()

/**
 * DATA: STRINGS
 * --------------
 */

let arr = ['5', '2', '4', '30', '1', '3']

/**
 * SORT ALPHABETICALLY BY DEFAULT
 * ------------------------------
 */

arrSort(arr)
//=> ['1', '2', '3', '30', '4', '5']

// OR
arr.sort()
//=> ['1', '2', '3', '30', '4', '5']

/**
 * DATA: NUMERIC VALUES
 * ----------------------
 */

arr = [5, 2, 4, 30, 1, 3]

/**
 * SORT NUMERICALLY
 * ----------------
 */

arrSort(arr, {
  numeric: true,
})
//=> [1, 2, 3, 4, 5, 30]

/**
 * SORT DESCENDING
 * ---------------
 */

arrSort(arr, {
  numeric: true,
  descending: true,
})
//=> [30, 5, 4, 3, 2, 1]

/**
 * DATA: PERSON OBJECTS
 * --------------------
 */

arr = [
  { name: 'john', age: 4 },
  { name: 'bill', age: 8 },
]

/**
 * SORT OBJECTS BY PROPERTY
 * ------------------------
 */

arrSort(arr, {
  by: 'name',
})

/* =>
  [
    { name: 'bill', age: 8 },
    { name: 'john', age: 4 },
  ]
*/

arrSort(arr, {
  numeric: true,
  by: 'age',
})

/* =>
  [
    { name: 'john', age: 4 },
    { name: 'bill', age: 8 },
  ]
*/

/**
 * DATA: PERSON OBJECTS WITH NESTED NAME OBJECTS
 * ---------------------------------------------
 */

arr = [
  { id: 0, name: { first: 'snoop', last: 'doggy' } },
  { id: 1, name: { first: 'kurt', last: 'qobain' } },
]

/**
 * SORT OBJECTS BY NESTED PROPERTY WITH DOT NOTATION
 * -------------------------------------------------
 */

arrSort(arr, {
  by: 'name.first',
})

/* =>
  [
    { id: 1, name: { first: 'kurt', last: 'qobain' } },
    { id: 0, name: { first: 'snoop', last: 'doggy' } },
  ]
*/

arrSort(arr, {
  by: 'name.last',
})

/* =>
  [
    { id: 0, name: { first: 'snoop', last: 'doggy' } },
    { id: 1, name: { first: 'kurt', last: 'qobain' } },
  ]
*/

/**
 * DATA: STRING DIRECTORY PATHS SPLIT IN ARRAYS
 * --------------------------------------------
 */

arr = [
  ['repo', 'src', 'compare.js'],
  ['repo', 'docs', 'index.html'],
]

/**
 * SORT BY ARRAY INDEX
 * -------------------
 */

arrSort(arr, {
  by: 2,
})

/* =>
  [
    ['repo', 'src', 'compare.js'],
    ['repo', 'docs', 'index.html'],
  ]
*/

arrSort(arr, {
  by: 1,
})

/* =>
  [
    ['repo', 'docs', 'index.html' ],
    ['repo', 'src', 'compare.js'],
  ]
*/

/**
 * DATA: DIRECTORY PATHS ARRAYS WITH SUB-ARRAYS
 * --------------------------------------------
 */

arr = [
  ['repo', 'src', ['compare', 'json']],
  ['repo', 'src', ['compare', 'ts']],
  ['repo', 'src', ['compare', 'js']],
]

/**
 * SORT ARRAYS AND SUB-ARRAYS RECURSIVELY
 * ------------------------------------
 */

arrSort(arr, {
  arrays: true,
})

/* =>
  [
    ['repo', 'src', ['compare', 'js']],
    ['repo', 'src', ['compare', 'json']],
    ['repo', 'src', ['compare', 'ts']],
  ]
*/

/**
 * DATA: IP ADDRESSES AS ARRAYS
 * ----------------------------
 */

arr = [
  [192, 168, 0, 1],
  [192, 168, 0, 101],
  [172, 0, 0, 1],
]

/**
 * SORT NUMERIC IP-ADDRESSES AS ARRAYS
 * -----------------------------------
 */

arrSort(arr, {
  numeric: true,
  arrays: true,
})

/* =>
  [
    [172, 0, 0, 1],
    [192, 168, 0, 1],
    [192, 168, 0, 101],
  ]
*/

/**
 * DATA: USER CLASS INSTANCES
 * --------------------------
 */

class User {
  constructor(firstName, lastName) {
    this.firstName = firstName
    this.lastName = lastName
  }
  get fullName() {
    return this.firstName + ' ' + this.lastName
  }
}

arr = [
  new User('john', 'doe'),
  new User('peter', 'wick'),
  new User('peter', 'johnson'),
  new User('les', 'paul'),
]

/**
 * SORT BY GETTER-FUNCTION
 * ------------------------
 */

arrSort(arr, {
  by: (user) => {
    return user.fullName
  },
})

/* =>
  [
    { firstName: 'john', lastName: 'doe'},
    { firstName: 'les', lastName: 'paul'},
    { firstName: 'peter', lastName: 'johnson'},
    { firstName: 'peter', lastName: 'wick'},
  ]
*/

Benchmark

Note: For short arrays, the speedup is insignificant or about the same. The more data there is, the faster the algorithms of timsort become, proportionally. Although timsort is a bit slower for short arrays, we're talking about a few milliseconds. So the overall improvement from Array.prototype.sort is quite unquestionable, imo.

ArrayTypeLengtharrSortArray.prototype.sortTimes faster
randomInt107159541.33
randomInt1006878140342.04
randomInt10001045972109922.02
randomInt10000156095528049031.80
descendingInt105713890.68
descendingInt100112219711.76
descendingInt10004946171833.47
descendingInt10000433191709263.95
ascendingInt105343690.69
ascendingInt100102218421.80
ascendingInt10004460164853.70
ascendingInt10000366011579124.31
ascending3RandomExchangesInt106495410.83
ascending3RandomExchangesInt100175738172.17
ascending3RandomExchangesInt10006584181152.75
ascending3RandomExchangesInt10000461941722143.73
ascending10RandomEndInt107927500.95
ascending10RandomEndInt100243035781.47
ascending10RandomEndInt10008165198852.44
ascending10RandomEndInt10000503571767973.51
allEqualInt105263970.75
allEqualInt100104819491.86
allEqualInt10004400167893.82
allEqualInt10000359761628574.53
manyDuplicateInt108337700.92
manyDuplicateInt1007806117051.50
manyDuplicateInt10001109681735391.56
manyDuplicateInt10000149147322559931.51
someDuplicateInt107977470.94
someDuplicateInt1007797117121.50
someDuplicateInt10001121891749731.56
someDuplicateInt10000152683923011871.51

Tests

Uses Jest to test module functionality. Run tests to get coverage details.

npm run test

API

Table of Contents

arrSort

Sort an array considerably faster than the native Array.prototype.sort as a drop-in replacement. Fork of of the famous timsort module, but this module allows for passing comparator-builder options instead of a comparator function. In short, advanced comparators made easy. Timsort: https://www.npmjs.com/package/timsort

Parameters
  • arr Array The array to sort.

  • compare (function | object)? Comparator function or comparator-builder options. Defaults to alphabetical compararison.

    • compare.numeric boolean Sort numerically. Defaults to lexicographic/alphabetic sort. (optional, default false)

    • compare.descending boolean Sort in descending order. Defaults to ascending order. (optional, default false)

    • compare.array boolean Sort arrays. Nested arrays are also compared recursively. (optional, default false)

    • compare.by (number | string | getter) Sort by either array index, a callback(element): any - or by object keys with dot-notation support. (optional, default undefined)

  • lo number? First element in the range (inclusive).

  • hi number? Last element in the range.

Returns Array The sorted array

replaceNative

Replace the native Array.prototype.sort method with arrSort.

Returns void

getter

Callback type definition.

Type: Function

Parameters
  • a any The value

Returns any The value to be compared