2-я игровая физика?

Все вышеперечисленные решения «работают», но менее оптимальны для производительности и все они подходят к проблеме таким же образом, что и линейный поиск всех записей в каждой точке с помощью Array.prototype.indexOf или Array.prototype.includes . Более быстрое решение (гораздо быстрее, чем бинарный поиск в большинстве случаев) - это сортировка массивов и проскальзывание вперед, как вы видите ниже. Однако один недостаток заключается в том, что для этого требуется, чтобы все записи в массиве были числами или строками. Однако, однако, бинарный поиск может в некоторых редких случаях быть быстрее, чем прогрессивный линейный поиск. Эти случаи возникают из-за того, что мой прогрессивный линейный поиск имеет сложность O (2n1 + n2) (только O (n1 + n2) в более быстрой версии C / C ++ ) (где n1 - искомый массив, а n2 - массив фильтров), тогда как бинарный поиск имеет сложность O (n1ceil (log2n2)) (ceil = round up - ceil ing), и, наконец, поиск indexOf имеет весьма переменную сложность между O (n1) и O (n1n2) , усредняя по O (n1ceil (n2 ÷ 2)) . Таким образом, indexOf будет только самым быстрым, в среднем, в случаях (n1, n2) , равных {1,2} , {1,3} или {x, 1 | x∈N} . Тем не менее, это все еще не идеальное представление современного оборудования. IndexOf оптимизирован в максимально возможной степени в большинстве современных браузеров, что делает его очень подверженным законам предсказания ветвей . Таким образом, если мы сделаем такое же предположение на indexOf, как и в случае с прогрессивным линейным и двоичным поиском, - чтобы массив был предварительно настроен, то, согласно статистическим данным, перечисленным в ссылке, мы можем ожидать примерно 6-кратное ускорение для IndexOf, смещение его сложности между O (n1 ÷ 6) и O (n1n2) , усреднение по O (n1ceil (n27 ÷ 12)) , Наконец, обратите внимание, что приведенное ниже решение никогда не будет работать с объектами, потому что невозможно получить внутренний указатель объекта (для численного сравнения) в javascript.

function sortAnyArray(a,b) { return a>b ? 1 : (a===b ? 0 : -1); }
function sortIntArray(a,b) { return a - b; }
var Math_clz32 = Math.clz32;
function filterArrayByAnotherArray(searchArray, filterArray, isInteger = false, i = 0) {
    if (isInteger) { // if all entries in both arrays are integers
        searchArray.sort(sortIntArray);
        filterArray.sort(sortIntArray);
    } else {
        searchArray.sort(sortAnyArray);
        filterArray.sort(sortAnyArray);
    }
    var searchArrayLen = searchArray.length, filterArrayLen = filterArray.length;
    var progressiveLinearComplexity = ((searchArrayLen<<1) + filterArrayLen)>>>0
    var binarySearchComplexity= (searchArrayLen * (32-Math_clz32(filterArrayLen-1)))>>>0;
    // After computing the complexity, we can predict which algorithm will be the fastest
    if (progressiveLinearComplexity < binarySearchComplexity) {
        // Progressive Linear Search
        return searchArray.filter(function(currentValue){
            while (filterArray[i] < currentValue) ++i;
            // +undefined = NaN, which is always false for <, avoiding an infinite loop
            return filterArray[i] !== currentValue;
        });
    } else {
        // Binary Search
        return searchArray.filter(function(currentValue) {
            var lo = -1, hi = filterArrayLen;
            while (1 + lo !== hi) {
                const mi = (hi + lo) >> 1;
                if (currentValue <= filterArray[mi]) hi = mi; else lo = mi;
            }
            return filterArray[hi] !== currentValue;
        });
    }
}

Чтобы доказать разницу в скорости, давайте рассмотрим некоторые JSPerfs. Для фильтрации массива из 16 элементов бинарный поиск примерно на 17% быстрее, чем indexOf, тогда как filterArrayByAnotherArray примерно на 93% быстрее, чем indexOf. Для фильтрации массива из 256 элементов бинарный поиск примерно на 291% быстрее, чем indexOf, тогда как filterArrayByAnotherArray примерно на 353% быстрее, чем indexOf. Для фильтрации массива из 4096 элементов бинарный поиск примерно на 2655% быстрее, чем indexOf, тогда как filterArrayByAnotherArray примерно на 4627% быстрее, чем indexOf.