предисловие
Сегодня будет продолжать чат алгоритм JS, следующее объяснение, мы можем понять базовую реализацию и выполнение различных реализаций алгоритма поиска, а затем обнаружили, что разница в производительности для циркуляции, Foreach, пока мы поймем, как сделать нарезку Производительность алгоритма, значительно улучшила алгоритм веб-работником.
В то же время я также кратко представлю классический двухточечный алгоритм, алгоритмы поиска хеш-таблицы, но это не является предметом этой главы, и я подробно представлю эти продвинутые алгоритмы, заинтересованные друзья могут обратить внимание на мою колонку , или вместе Обсуждение.
Для производительности алгоритма мы по-прежнему будем использовать предыдущую главу.Как сделать интерфейсный код в 60 раз быстрееФункция getFnRunTime в , вы можете проверить и изучить, если вам интересно, я не буду здесь слишком много объяснять.
в предыдущей главеКак сделать интерфейсный код в 60 раз быстрееМы смоделировали 19 000 фрагментов данных.В этой главе, чтобы сделать эффект более очевидным, я буду подделывать 1,7 миллиона фрагментов данных для проверки, но поверьте мне, это не имеет большого значения для js. . .
1. Для поиска петли
Основная идея: пройти массив через цикл for, найти индекс значения для поиска в массиве и поместить его в новый массив.
Код реализован следующим образом:
const getFnRunTime = require('./getRuntime');
/**
* 普通算法-for循环版
* @param {*} arr
* 耗时：7-9ms
*/
function searchBy(arr, value) {
let result = [];
for(let i = 0, len = arr.length; i < len; i++) {
if(arr[i] === value) {
result.push(i);
}
}
return result
}
getFnRunTime(searchBy, 6)
Результат после n раз тестирования стабилен показан на рисунке:
2.для каждого цикла
Основная идея аналогична циклу for:
/**
* 普通算法-forEach循环版
* @param {*} arr
* 耗时：21-24ms
*/
function searchByForEach(arr, value) {
let result = [];
arr.forEach((item,i) => {
if(item === value) {
result.push(i);
}
})
return result
}
Это занимает 21-24 миллисекунды, и видно, что производительность не так хороша, как у цикла for (скажем так, пока суть та же).
3. пока цикл
код показывает, как показано ниже:
/**
* 普通算法-while循环版
* @param {*} arr
* 耗时：11ms
*/
function searchByWhile(arr, value) {
let i = arr.length,
result = [];
while(i) {
if(arr[i] === value) {
result.push(i);
}
i--;
}
return result
}
Видно, что производительность циклов while и for одинаковая, и обе они отличные, но это не значит, что производительность forEach плохая, поэтому он не используется. В Foreach меньше кода, чем в цикле for, но foreach использует IEnumerable. Менее эффективен, чем цикл for во время выполнения. Однако более удобно использовать foreach при работе с циклами с неопределенным количеством циклов или когда необходимо вычислить количество циклов. А код foreach подобен циклу for после оптимизации кода системы компиляции.
4. Дихотомический поиск
Больше сценариев применения бинарного поиска в массивах с уникальными и упорядоченными значениями в массиве, поэтому я не буду здесь сравнивать его производительность с for/while/forEach.
Основная идея: начать сравнение со средней позиции последовательности, если значение текущей позиции равно искомому значению, поиск успешен, если искомое значение меньше значения текущей позиции, поиск в первая половина последовательности; если искомое значение больше Текущее значение позиции продолжает поиск во второй половине последовательности, пока не будет найдено
код показывает, как показано ниже:
/**
* 二分算法
* @param {*} arr
* @param {*} value
*/
function binarySearch(arr, value) {
let min = 0;
let max = arr.length - 1;
while (min <= max) {
const mid = Math.floor((min + max) / 2);
if (arr[mid] === value) {
return mid;
} else if (arr[mid] > value) {
max = mid - 1;
} else {
min = mid + 1;
}
}
return 'Not Found';
}
В сценариях с большим объемом данных дихотомия очень эффективна, но нестабильна, что также является небольшим недостатком в запросах к большим данным.
5. Поиск в хэш-таблице
Поиск по хеш-таблице также называется поиском по хеш-таблице. Путем поиска по ключу место хранения записи можно получить без сравнения. Он устанавливает определенное соответствие f между местом хранения записи и ее ключом, так что каждое ключевое слово ключ соответствует месту хранения f(key)
Сценарии использования поиска по хеш-таблице:
- Хеш-таблицы лучше всего подходят для решения задач, связанных с поиском записей, равных заданному значению.
- Поиск по хешу не подходит для случая, когда одно и то же ключевое слово соответствует нескольким записям.
- Не подходит для поиска по диапазону, например, для поиска одноклассников в возрасте 18–22 лет.
Здесь я сначала приведу минимальную версию hashTable, чтобы всем было проще понять хеширование:
/**
* 散列表
* 以下方法会出现数据覆盖的问题
*/
function HashTable() {
var table = [];
// 散列函数
var loseloseHashCode = function(key) {
var hash = 0;
for(var i=0; i<key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % 37
};
// put
this.put = function(key, value) {
var position = loseloseHashCode(key);
table[position] = value;
}
// get
this.get = function(key) {
return table[loseloseHashCode(key)]
}
// remove
this.remove = function(key) {
table[loseloseHashCode(key)] = undefined;
}
}
У этого метода может быть проблема с конфликтом данных, но есть решения.Поскольку здесь задействовано много знаний, я начну статью, чтобы представить ее позже:
- открытая адресация
- вторичный метод обнаружения
- случайное обнаружение
Оптимизация с помощью веб-воркеров
С помощью вышеуказанных методов мы уже знаем производительность и сценарии применения различных алгоритмов.Когда мы используем алгоритм, мы также можем оптимизировать его с помощью веб-воркеров, чтобы программа могла обрабатываться параллельно.Поток веб-воркеров помогает нам обрабатывать результаты вычислений, и, наконец, объединяет результаты и передает их в браузер через механизм событий работника.Эффект очень значителен.
Суммировать
- Для сложных запросов к массиву производительность for/while выше, чем для forEach и других методов массива.
- Метод бинарного поиска O(logn) — очень эффективный алгоритм. Однако очевидны и его недостатки: он должен быть упорядочен, и нам трудно гарантировать, что все наши массивы упорядочены. Конечно, сортировку можно выполнять и при построении массива, но это связано со вторым узким местом: это должен быть массив. Эффективность чтения массива равна O(1), а эффективность вставки и удаления элемента — O(n). В результате снижается эффективность построения отсортированных массивов.
- Базовое использование и сценарии использования поиска по хэш-таблице.
- Если позволяют условия, мы можем использовать веб-воркеры для оптимизации алгоритма и позволить ему выполняться параллельно в фоновом режиме.
Ну, хотя эта статья относительно проста, она очень важна.Я надеюсь, что у всех есть более интуитивное понимание алгоритма поиска, и я надеюсь, что у всех есть лучший способ обсуждать и общаться вместе.
В будущем будет запущено больше отличных алгоритмов, так что следите за обновлениями~
И, наконец, добро пожаловать в группу передовых технологий и вместе обсудите прелести переднего плана.