Как отфильтровать массив от всех элементов другого массива

Как отфильтровать массив от всех элементов другого массива

Все вышеперечисленные решения «работают», но они менее чем оптимальны для производительности, и все они решают проблему одинаково, а именно линейный поиск всех записей в каждой точке с использованием Array.prototype.indexOf или Array.prototype.include . Гораздо более быстрое решение (в большинстве случаев даже более быстрое, чем бинарный поиск) заключалось бы в сортировке массивов и переходе к следующему шагу, как показано ниже. Однако одним недостатком является то, что для этого необходимо, чтобы все записи в массиве были числами или строками. Однако в некоторых редких случаях двоичный поиск может быть быстрее, чем прогрессивный линейный поиск. Эти случаи возникают из-за того, что мой прогрессивный линейный поиск имеет сложность O (2n 1 n 2 ) (только O (n 1 n 2 ) в более быстрой версии C / C ) (где n 1 — искомый массив и n 2 является массивом фильтров), тогда как двоичный поиск имеет сложность O (n 1 ceil (log 2 n 2 )) (ceil = округление вверх — до потолка ), и, наконец, поиск indexOf имеет сильно изменяющаяся сложность между O (n 1 ) и O (n 1 n 2 ) , усредняя до O (n 1 ceil (n 2 ÷ 2)) . Таким образом, indexOf будет самым быстрым в среднем только в случаях, когда (n 1 , n 2 ) равно {1,2} , {1,3} или {x, 1 | x∈N} . Тем не менее, это все еще не идеальное представление современного оборудования. IndexOf изначально оптимизирован в максимально возможной степени в большинстве современных браузеров, что делает его очень зависимым от законов предсказания ветвлений . Таким образом, если мы сделаем для indexOf то же предположение, что и для прогрессивного линейного и двоичного поиска — что массив предварительно отсортирован, — тогда, согласно статистике, указанной в ссылке, мы можем ожидать примерно 6-кратного ускорения для IndexOf, сдвигая его сложность между O (n 1 ÷ 6) и O (n 1 n 2 ) , усредняя к O (n 1 ceil (n 2 7 ÷ 12)) . Наконец, обратите внимание, что приведенное ниже решение никогда не будет работать с объектами, потому что невозможно получить внутренний указатель объекта (для числового сравнения) в javascript. Если бы только Javascript мог быть

 function sortAnyArray(a,b) { return a{amp}gt;b ? 1 : (a===b ? 0 : -1); } function sortIntArray(a,b) { return (a|0) - (b|0) |0; } const Math_clz32 = Math.clz32 || (function(log, LN2){ return function(x) { return 31 - log(x {amp}gt;{amp}gt;{amp}gt; 0) / LN2 | 0; // the "| 0" acts like math.floor }; })(Math.log, Math.LN2); function filterArrayByAnotherArray(searchArray, filterArray) { if ( // NOTE: This does not check the whole array. But, if you know // that there are only strings or numbers (not a mix of // both) in the array, then this is a safe assumption. // Always use `==` with `typeof` because browsers can optimize // the `==` into `===` (ONLY IN THIS CIRCUMSTANCE) typeof searchArray[0] == "number" {amp}amp;{amp}amp; typeof filterArray[0] == "number" {amp}amp;{amp}amp; (searchArray[0]|0) === searchArray[0] {amp}amp;{amp}amp; (filterArray[0]|0) === filterArray[0] ) {filterArray // 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{amp}lt;{amp}lt;1)   filterArrayLen){amp}gt;{amp}gt;{amp}gt;0 var binarySearchComplexity= (searchArrayLen * (32-Math_clz32(filterArrayLen-1))){amp}gt;{amp}gt;{amp}gt;0; // After computing the complexity, we can predict which algorithm will be the fastest var i = 0; if (progressiveLinearComplexity {amp}lt; binarySearchComplexity) { // Progressive Linear Search return searchArray.filter(function(currentValue){ while (filterArray[i] {amp}lt; currentValue) i=i 1|0; //  undefined = NaN, which is always false for {amp}lt;, avoiding an infinite loop return filterArray[i] !== currentValue; }); } else { // Binary Search return searchArray.filter( fastestBinarySearch(filterArray) ); } } // see https://stackoverflow.com/a/44981570/5601591 for implementation // details about this binary search algorithim function fastestBinarySearch(array){ var initLen = (array.length|0) - 1 |0; const compGoto = Math_clz32(initLen) {amp}amp; 31; return function(ARG_sValue) { var sValue = ARG_sValue |0; var len = initLen |0; switch (compGoto) { case 0: if (len {amp}amp; 0x80000000) { const nCB = len {amp}amp; 0x80000000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 1: if (len {amp}amp; 0x40000000) { const nCB = len {amp}amp; 0xc0000000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 2: if (len {amp}amp; 0x20000000) { const nCB = len {amp}amp; 0xe0000000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 3: if (len {amp}amp; 0x10000000) { const nCB = len {amp}amp; 0xf0000000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 4: if (len {amp}amp; 0x8000000) { const nCB = len {amp}amp; 0xf8000000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 5: if (len {amp}amp; 0x4000000) { const nCB = len {amp}amp; 0xfc000000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 6: if (len {amp}amp; 0x2000000) { const nCB = len {amp}amp; 0xfe000000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 7: if (len {amp}amp; 0x1000000) { const nCB = len {amp}amp; 0xff000000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 8: if (len {amp}amp; 0x800000) { const nCB = len {amp}amp; 0xff800000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 9: if (len {amp}amp; 0x400000) { const nCB = len {amp}amp; 0xffc00000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 10: if (len {amp}amp; 0x200000) { const nCB = len {amp}amp; 0xffe00000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 11: if (len {amp}amp; 0x100000) { const nCB = len {amp}amp; 0xfff00000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 12: if (len {amp}amp; 0x80000) { const nCB = len {amp}amp; 0xfff80000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 13: if (len {amp}amp; 0x40000) { const nCB = len {amp}amp; 0xfffc0000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 14: if (len {amp}amp; 0x20000) { const nCB = len {amp}amp; 0xfffe0000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 15: if (len {amp}amp; 0x10000) { const nCB = len {amp}amp; 0xffff0000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 16: if (len {amp}amp; 0x8000) { const nCB = len {amp}amp; 0xffff8000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 17: if (len {amp}amp; 0x4000) { const nCB = len {amp}amp; 0xffffc000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 18: if (len {amp}amp; 0x2000) { const nCB = len {amp}amp; 0xffffe000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 19: if (len {amp}amp; 0x1000) { const nCB = len {amp}amp; 0xfffff000; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 20: if (len {amp}amp; 0x800) { const nCB = len {amp}amp; 0xfffff800; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 21: if (len {amp}amp; 0x400) { const nCB = len {amp}amp; 0xfffffc00; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 22: if (len {amp}amp; 0x200) { const nCB = len {amp}amp; 0xfffffe00; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 23: if (len {amp}amp; 0x100) { const nCB = len {amp}amp; 0xffffff00; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 24: if (len {amp}amp; 0x80) { const nCB = len {amp}amp; 0xffffff80; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 25: if (len {amp}amp; 0x40) { const nCB = len {amp}amp; 0xffffffc0; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 26: if (len {amp}amp; 0x20) { const nCB = len {amp}amp; 0xffffffe0; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 27: if (len {amp}amp; 0x10) { const nCB = len {amp}amp; 0xfffffff0; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 28: if (len {amp}amp; 0x8) { const nCB = len {amp}amp; 0xfffffff8; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 29: if (len {amp}amp; 0x4) { const nCB = len {amp}amp; 0xfffffffc; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 30: if (len {amp}amp; 0x2) { const nCB = len {amp}amp; 0xfffffffe; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } case 31: if (len {amp}amp; 0x1) { const nCB = len {amp}amp; 0xffffffff; len ^= (len ^ (nCB-1)) {amp}amp; ((array[nCB] {amp}lt;= sValue |0) - 1 {amp}gt;{amp}gt;{amp}gt;0); } } // MODIFICATION: Instead of returning the index, this binary search // instead returns whether something was found or not. if (array[len|0] !== sValue) { return true; // preserve the value at this index } else { return false; // eliminate the value at this index } }; } 

Пожалуйста, смотрите мой другой пост здесь для более подробной информации об используемом алгоритме двоичного поиска.

Если вам не нравится размер файла, как у меня, вы можете пожертвовать некоторой производительностью, чтобы значительно уменьшить размер файла и повысить удобство обслуживания.

 function sortAnyArray(a,b) { return a{amp}gt;b ? 1 : (a===b ? 0 : -1); } function sortIntArray(a,b) { return (a|0) - (b|0) |0; } function filterArrayByAnotherArray(searchArray, filterArray) { if ( // NOTE: This does not check the whole array. But, if you know // that there are only strings or numbers (not a mix of // both) in the array, then this is a safe assumption. typeof searchArray[0] == "number" {amp}amp;{amp}amp; typeof filterArray[0] == "number" {amp}amp;{amp}amp; (searchArray[0]|0) === searchArray[0] {amp}amp;{amp}amp; (filterArray[0]|0) === filterArray[0] ) { // if all entries in both arrays are integers searchArray.sort(sortIntArray); filterArray.sort(sortIntArray); } else { searchArray.sort(sortAnyArray); filterArray.sort(sortAnyArray); } // Progressive Linear Search var i = 0; return searchArray.filter(function(currentValue){ while (filterArray[i] {amp}lt; currentValue) i=i 1|0; //  undefined = NaN, which is always false for {amp}lt;, avoiding an infinite loop return filterArray[i] !== currentValue; }); } 

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

Понравилась статья? Поделиться с друзьями:
JavaScript & TypeScript
Adblock
detector