Частичная сортировка в JavaScript

Есть ли встроенная функция JavaScript для выполнения частичной сортировки? Если нет, то как это можно реализовать?

Учитывая несортированный массив из N элементов, я хотел бы найти K элементов, которые являются минимальными по отношению к некоторой весовой функции. K намного меньше, чем N, поэтому было бы неэффективно отсортировать весь массив и взять первые K элементов.

Я был бы счастлив, даже если бы было что-то нестандартное, зависящее от браузера. Я все еще могу вернуться к пользовательской реализации JavaScript.

PS: Это моя текущая пользовательская реализация (без учета весовой функции, просто сортировка элементов для простоты):

function bisect(items, x, lo, hi) {
  var mid;
  if (typeof(lo) == 'undefined') lo = 0;
  if (typeof(hi) == 'undefined') hi = items.length;
  while (lo < hi) {
    mid = Math.floor((lo + hi) / 2);
    if (x < items[mid]) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

function insort(items, x) {
  items.splice(bisect(items, x), 0, x);
}

function partialSort(items, k) {
  var smallest = [];
  for (var i = 0, len = items.length; i < len; ++i) {
    var item = items[i];
    if (smallest.length < k || item < smallest[smallest.length - 1]) {
      insort(smallest, item);
      if (smallest.length > k)
        smallest.splice(k, 1);
    }
  }
  return smallest;
}

console.log(partialSort([5, 4, 3, 2, 1, 6, 7, 8, 1, 9], 3));

Алгоритм проходит по указанному массиву один раз, отслеживая отсортированный список из k самых маленьких элементов на данный момент, используя бинарный поиск для вставки новых элементов.

Пожалуйста, опубликуйте альтернативные решения, если вы думаете, что они могут быть быстрее или элегантнее. Сроки очень приветствуются.

Ответ 1

Нет. Там будет полный массив sort, поэтому вам нужно будет использовать свою собственную реализацию.

Небольшое улучшение вашего кода (я думал о том же алгоритме: -)):

function partialSort(items, k) {
    var smallest = items.slice(0, k).sort(),
        max = smallest[k-1];
    for (var i = k, len = items.length; i < len; ++i) {
        var item = items[i];
        if (item < max) {
            insort(smallest, item);
            smallest.length = k;
            max = smallest[k-1];
        }
    }
    return smallest;
}

(Даже кажется немного быстрее, я думаю, из-за кэширования переменной max)

Ответ 2

Нет никакой функции частичной частичной сортировки. Самое близкое к тому, что вы хотите, Array.filter.

function isSmallEnough(element, index, array) {
  return (element <= 10);
}
var filtered = [12, 5, 8, 130, 44].filter(isSmallEnough);
// filtered is [5, 8]

Пример был заимствован (и слегка изменен) из приведенной выше ссылки.

Ответ 3

Для сравнительно небольшого k может оказаться целесообразным реализовать Max Heap (из-за отсутствия нативного в JavaScript):

Создать максимум кучи первых k значений
Для каждого оставшегося значения:
- Если он меньше, чем корень кучи, замените корень на это значение. В противном случае игнорируйте значение. Обратите внимание, что размер кучи никогда не меняется.
Наконец, отсортируйте кучу и верните ее.

Фактически, это улучшение по сравнению с другой идеей, использующей Min Heap, но она требует кучи всего массива и поэтому не будет работать так быстро. После кучи всего массива вы просто k раз извлекаете значение из этой кучи и возвращаете эти значения.

Я добавил оба решения в тесты производительности, которые создал Берги. Для этого конкретного теста (5000 значений массива, k = 10) решение Max Heap быстрее в два раза. Но это преимущество будет уменьшаться при увеличении k.

Вот код для решения Max Heap:

// A few Heap-functions that operate on an array
function maxSiftDown(arr, i=0, value=arr[i]) {
    if (i >= arr.length) return;
    while (true) {
        var j = i*2+1;
        if (j+1 < arr.length && arr[j] < arr[j+1]) j++;
        if (j >= arr.length || value >= arr[j]) break;
        arr[i] = arr[j];
        i = j;
    }
    arr[i] = value;
}

function maxHeapify(arr) {
    for (var i = arr.length>>1; i--; ) maxSiftDown(arr, i);
    return arr;
}

// The main algorithm
function partialSortWithMaxHeap(items, k) {
    var heap = maxHeapify(items.slice(0, k));
    for (var i = k, len = items.length; i < len; ++i) {
        var item = items[i];
        if (item < heap[0]) maxSiftDown(heap, 0, item);
    }
    return heap.sort((a,b) => a-b);
}

// Sample data & call
var arr = Array.from({length:5000}, () => Math.floor(Math.random() * 1e5));
   
console.log(partialSortWithMaxHeap(arr, 10));

Ответ 4

Я сделал версию, которая работает с объектами, например Array.sort(f):

function partialSort(items, k,f) {
    function bisect(items, x, lo, hi) {
        var mid;
        if (typeof(lo) == 'undefined') lo = 0;
        if (typeof(hi) == 'undefined') hi = items.length;
        while (lo < hi) {
        mid = Math.floor((lo + hi) / 2);
        if (0>f(x,items[mid])) hi = mid;
        else lo = mid + 1;
        }
        return lo;
    }

    function insort(items, x) {
        items.splice(bisect(items, x), 0, x);
    }

    var smallest = items.slice(0, k).sort(f),
        max = smallest[k-1];
    for (var i = k, len = items.length; i < len; ++i) {
        var item = items[i];
        if (0>f(item,max)) {
            insort(smallest, item);
            smallest.length = k;
            max = smallest[k-1];
        }
    }
    return smallest;
}

// [ { e: 1 }, { e: 1 }, { e: 2 } ]
console.log(partialSort([{e:4},{e:6},{e:1},{e:8},{e:3},{e:1},{e:6},{e:2}],3,(a,b)=>a.e-b.e))
console.log()