Алгоритмы поиска и их реализации
При написании кода или программного обеспечения вы неизбежно столкнетесь с ситуацией, когда вам нужно найти определенное значение в заданном наборе данных. Есть несколько разных способов провести этот поиск. Я расскажу как о линейном, так и о бинарном поиске, а также о другом методе повышения производительности линейного поиска. Что касается оптимизации, каждый метод имеет разный результат. При сравнении различий в производительности между действиями стандартно ссылаться на наихудшую ситуацию, что означает, какой была бы производительность, если бы элемент был найден при последнем выполнении функции. Для линейного и бинарного поиска мы увидим, какими будут худшие, лучшие и средние ситуации.
Линейный поиск
Линейный поиск буквально проходит каждый элемент в наборе данных по частям, пока не найдет элемент, который вы хотите найти. Чтобы найти элемент x с индексом n в упорядоченном списке, мне потребовалось бы ровно n шагов, чтобы найти этот элемент. Это называется O(n). Для небольшого списка это нормально и не представляет проблемы. Например, если у меня есть массив, который выглядит так: [1, 2, 3, 4, 5, 6, 7] и я хочу найти число 5, мне потребуется ровно 5 шагов, чтобы найти число, которое я ищу. Давайте посмотрим, как это работает в Javascript с отсортированным массивом.
let sortedArr = [ 2, 4, 5, 6, 8, 10, 16, 32 ]
function linearSearch(num){
sortedArr.forEach(function(item, index){
if(item === num){
console.log(`I found ${item} at index ${index}!`)
return
}
})
}
linearSearch(32)
Рабочий пример: https://repl.it/@r_nilon92/sortedLinearSearchExample
Таким образом, для каждого элемента sortedArr мы проверяем, равен ли элемент по каждому индексу числу (num), которое мы передали нашей функции в качестве аргумента.
Этот метод поиска идеально подходит для небольшого массива, такого как этот. Однако для большого списка данных, скажем, содержащего 4 000 000 000 элементов, это может вызвать неудобства. В худшем случае производительности (например, если число, которое вы ищете, является последним элементом в массиве или даже не существует!), потребуется 4 000 000 000 шагов или O (n), чтобы найти число, которое вы ищете. . В лучшем случае это будет ровно один шаг (если искомый элемент является первым элементом в нашем массиве) или O(1). Средний случай для этого типа поиска — O(n). Как вы можете видеть, это не самый эффективный способ для случаев, когда речь идет о больших наборах данных. И как программисты, мы всегда стремимся к большей эффективности.
Бинарный поиск
Бинарный поиск также довольно прост и понятен, хотя для его реализации требуется немного больше логики, чем для линейного поиска. Двоичный поиск, также известный как полуинтервальный поиск, логарифмический поиск и, мой личный фаворит, двоичный поиск, является гораздо более эффективным способом поиска элемента в определенном наборе данных. Единственным недостатком является то, что данные, которые вы просматриваете, необходимо сортировать.
Чтобы найти элемент в упорядоченном массиве, вы должны сначала взглянуть на среднюю точку в этом массиве. Если средняя точка больше, чем число, которое вы хотите найти, то вы ограничите поиск нижней половиной и отбросите верхнюю половину. Точно так же, если средняя точка меньше искомого числа, вы ограничите поиск верхней половиной. Число существует только в одной из половин, поэтому компьютер отбрасывает ту половину, которой не может принадлежать искомое число. Этот процесс повторяется многократно, пока число не будет найдено. В информатике эта результирующая производительность называется O(log N) . Чтобы увидеть разницу в шагах, выполняемых в линейном и двоичном режимах, возьмите логарифмическое значение количества элементов в массиве, в котором вы хотите выполнить поиск. Скажем, у нас есть массив с 8 000 000 000 элементов. Это очень много для поиска! Давайте сократим это пополам. Теперь у нас есть 2 000 000 000 элементов, в которых, как мы знаем, находится нужное нам число. Чтобы узнать, сколько шагов потребуется, чтобы найти наш элемент, мы можем вычислить двоичную логарифмическую функцию log2 8 000 000 000, что дает нам 32. Хотя 32 — это много. шагов, чтобы найти число, это значительно короче, чем 8 000 000 000 в нашем линейном поиске наихудшего случая. В худшем и среднем сценариях вы найдете элемент x за время O(log n), а в лучшем случае — за O(1).
let orderedList = [ 2, 3, 5, 7, 8, 10, 12, 15, 18, 19, 24, 87, 111 ];
function binarySearch(arr, num) {
let lowestNum = 0;
let highestNum = orderedList.length - 1;
let midPoint;
let checkMidpoint;
while(lowestNum <= highestNum) {
midPoint = Math.floor((lowestNum + highestNum) / 2),
// midPoint = arr.length/2
checkMidpoint = arr[midPoint];
if(checkMidpoint === num) {
console.log('I found the number you were looking for at index: ' + midPoint + '! The value is ' + checkMidpoint + "!");
return;
}
if(num < checkMidpoint) {
highestNum = midPoint - 1;
}
else {
lowestNum = midPoint + 1;
}
}
return `I couldn't find ${num} in the list.` ;
}
binarySearch(orderedList,10);
Рабочий пример: https://repl.it/@r_nilon92/Binary-Search-Example
Бинарный поиск отлично работает в этой конкретной ситуации. Но это работает только в ситуациях, когда ваши данные отсортированы. Что произойдет, если ваши данные не отсортированы?
Изменение набора данных для повышения эффективности линейного поиска
Часто при поиске данных мы хотим искать одни и те же данные снова и снова. Во многих случаях 80% наших поисковых запросов приходится на 20% нашей области поиска. Это называется принципом Парето, названным в честь экономиста и инженера XIX века Вильфредо Парето. Первоначально принцип Парето применялся к неравенству и распределению доходов, но он также нашел место в компьютерных науках в отношении оптимизации. Например, Microsoft обнаружила, что 20% ошибок в их программном обеспечении вызывают 80% сбоев.
Если мы примем тот принцип, что 80% наших поисков находятся в такой небольшой области, мы можем переместить эти наиболее распространенные поисковые запросы в начало нашего набора данных, тем самым сделав наш поиск во многих случаях намного короче, чем это было бы в противном случае. Давайте посмотрим на пример.
let unsortedArr = [2, 5, 3, 7, 8, 10, 15, 18, 24, 111, 12, 19, 87];
function linearSearch(num) {
unsortedArr.forEach(function(itemValue, index, array){
if(itemValue === num) {
if(index > 0) {
organizeArr(index, array, index -1);
}
}
});
return unsortedArr;
}
function organizeArr(index, array, indexSwitch) {
var tempCurrentValue = array[index];
//tempCurrentValue stays the same
array[index] = array[indexSwitch];
array[indexSwitch] = tempCurrentValue;
}
console.log("Before Organization: " + unsortedArr);
var first = linearSearch(7);
var second = linearSearch(7);
var third = linearSearch(7);
var fourth = linearSearch(7);
console.log("After Organization: " + fourth);
/*
Before Organization: 2,5,3,7,8,10,15,18,24,111,12,19,87
After Organization: 7,2,5,3,8,10,15,18,24,111,12,19,87
*/
Рабочий пример: https://repl.it/@r_nilon92/LinearSearchWIthOrganization
Изменяя наши данные с течением времени, чтобы отразить наиболее распространенные поисковые запросы, мы можем улучшить нашу среднюю производительность, чем обычно.
Резюме
Так что лучше? Линейный или двоичный? Как правило, мы хотели бы использовать алгоритмы линейного поиска, когда данные, с которыми мы работаем, не отсортированы. Мы можем сделать этот процесс более эффективным, создав функцию, которая перемещает наиболее часто искомые элементы в начало массива. Для отсортированных массивов, особенно когда массив имеет большой размер, алгоритмы бинарного поиска более желательны и значительно короче для выполнения.
