Двоичный поиск или как найти то, чего нет. Скучнопост. — ПИПМАЙ: Лучшее со всей сети

Двоичный поиск или как найти то, чего нет. Скучнопост.

Неочевидная штука: Москва не резиновая Вместимость переменных конечна. Это значит, что (в нынешней данности - когда в одном байте, обычно, 8 бит) - в этот самый байт (BYTE) "влезет" 256 значений (при счёте с нуля это число [0,255]), в слово (WORD) влезет 65536 значений, в двойное слово (DWORD) 4294967296 и в счетверённое "слово" (на дворе "прогресс", 64 бита есть 64 бита) - дохуя, но не более 18446744073709551616 значений.

А ещё это значит, что разного рода числовые идентификаторы (от номера по-порядку, до Боец00000000000000000001 - Боец18446744073709551616) - конечны. И если в этом списке кого-то выпилили, образуется "дырка", которую можно и нужно использовать повторно.

Если числа невелики - поиск "в лоб" оправдан.

А если нет?

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

Как ищут известное? Сначала берём отсортированный список значений, затем - берут середину. Нашли? Да, победа, нашли. Нет? А искомое больше? Допустим, что да - берём правую часть от половины, ищем точно также там (повторяем). Нет? Не беда, берём левую (аналогично). И так - до победы до момента нахождения. Настолько просто, что нынче это стандартный алгоритм (тыкабельно) во всех уважающих себя библиотеках, прилагающихся к языкам программирования.

Но вот закавыка. А как быстро найти то, чего нет - отсутствующий элемент (ну, уж всяко быстрее, чем "в лоб", прямым перебором)?

И тут вот такой вот велосипед (если порвёт строки, я неуиноватый, филиал хабра здесь никто не обещал, формата для исходного кода не предусмотрено):

 

//Поиск пропуска в нумерации в последовательном списке с выработкой нового номера

//TList *ls - Сортированный список номеров int (правильно, а не лексикографически, т.е. 1,2,3...10,11)

//delta - первый минимальный номер, например 1 или 100001

int SearchGapId(TList *ls, const int delta)
{
        int L  = 0; //лево
        int R = ls->Count - 1; //право
        int M, MVal; //индекс середины и номер значения из середины

 

if(ls->Count == 0)  //случай раз, список пуст - идём в конец, там получим номер
 goto mRet;

if( (int(ls->Items[R]) - delta ) == R) //случай два, в списке нет "дырок" - идём в конец, там получим номер
 {
  L = R + 1;
  goto mRet;
 }

//список не пуст, "дырки" есть, ищем

//или "двоичный поиск дырки" - "найти то, чего нет"

 while (L <= R)  //крутимся в цикле, пока "слева" не переехало "справа"
 {
     M = (L + R)/2; //берём середину, можно было быстрее, но так нагляднее
     MVal = int(ls->Items[M]) - delta; //берём значение, лежащее в списке под этим индексом
     if (MVal > M) //магия :))))
      R = M - 1;
     else
      L = M + 1;
 }

mRet:
 return (L + delta);
}

 

Как-то так :))))

P.S. А совсем "старая школа" - в уме представляет себе не "лево/право", а "верх/низ"... Удивительно.

 


Раскрыть
Admin
3 месяца назад

А че почалось то? если надо для коду — мы добавим жеж:

Изображение

+3
2 Нырнуть
FilCattish
3 месяца назад

Естественно, надо!!

+1
FilCattish
3 месяца назад

А можно помедленнее и с картинками, пожалуйста?

+1
2 Нырнуть
3 месяца назад

Ну давай «на пальцах». Главное условие — список сортирован по возрастанию значений, т.е. 1,2,3....10,11… 100,101,… и т.п.

(допустим, что счёт с единицы)

Выдаём номер:

1. Список пуст. Выдаём минимальный номер. Возвращаем 0+1

2. Список не пуст. Последний элемент списка равен его «идеальному» порядковому номеру (т.е., грубо говоря, элемент с номером 100 содержит значение 100)? Нет. Значит дырок нет.  возвращаем 100+1

3. Дырки есть, начинаем поиск. Лезем в середину. Элемент списка с номером 50 содержит 50? Да, дырка левее, нет, правее, повторяем, взяв нужную половину… В итоге мы найдём отсутствующий номер.

Хоть код и дан на c++ 98, но он вполне понятно читается, если читать :)

+2
3 Нырнуть
3 месяца назад

Блин, с «нет» и «да» заигрался. Перечитал — спохватился.

Было:

2. Список не пуст. Последний элемент списка равен его «идеальному» порядковому номеру (т.е., грубо говоря, элемент с номером 100 содержит значение 100)? Нет. Значит дырок нет.  возвращаем 100+1

По смыслу понятно, но...

Читать так:

2. Список не пуст. Последний элемент списка равен его «идеальному» порядковому номеру (т.е., грубо говоря, элемент с номером 100 содержит значение 100)? Если совпадают, значит дырок нет, возвращаем 100+1

Разница колоссальна, от таких легкомысленных опечаток — не всегда просто ржач, иногда и на голову может упасть, извиняюсь за невнимательность, постараюсь расти над собой :)

+2
4 Нырнуть
Originalnoe
3 месяца назад

А можно для самых маленьких вариант? 

5 Нырнуть
3 месяца назад

Вот есть у тебя список, содержащий номера 1,2,3,4,5 

И вдруг №4 потребовалось удалить
Удалил… Образовался промежуток-«дырка», в списке остались такие номера 1,2,3,5
Причём «схлопнуть» эту дырку (особенно, когда список достаточно большой и следом за удалённым элементом ещё много других) — колоссальный труд, все «живые» элементы, которые остались в списке — уже пронумерованы, их нужно перенумеровывать, а это время и накладные расходы.

А теперь в этот список понадобилось новый элемент добавить. 
И стало 1,2,3,5,6...
И если так делать слишком часто — никакой номерной ёмкости не хватит, да и всяческие ведомости странно выглядят, типа 1й, 3030й и Итого :)

Хорошо. Решил ты это дело как-то упорядочить. Хотя бы, чтобы если появится кто-то новенький — не назначать ему порядковый номер +1 от максимального, а запихнуть его в свободную «дырку».
Достичь этого просто. Нужно найти пустое место (и, если у нас всё по порядку, ближайшее к началу) и присвоить новенькому номер, как-то связанный с этим пустым местом.


Существует три основных способа:

1. Прямой перебор «в лоб». Берём каждую запись списка, узнаём номер который в ней содержится и, если следующая запись отличается от предыдущей больше, чем на единицу, то новенькому присваивается номер из предыдущей+1. Но это долго.
2. Вести ещё один список. При удалении любого элемента основного списка — в этот второй список записывать освободившийся номер. Но это не всегда нужные расходы
3. Двоичный поиск свободного промежутка. Т.к. мы каждый раз будем делить отрезок пополам — это будет достаточно быстро (лучше чем в 1, но хуже, чем в 2 случаях)  и не требует места под хранение второго списка (лучше чем в 2 и также, как и в 1 случаях). Получается золотая середина.

Реализуем двоичный поиск.

Сначала нужно понять, как связаны индекс элемента (порядковый номер элемента в списке) и номер элемента (значение, номер, внутренний номер или идентификатор — ниже буду именовать как-то так).
Поскольку в сях (C, C++) нумерацию ведут с нуля, то пять элементов списка имеют индексы 0,1,2,3,4
Легко видеть, что между номерами и индексами есть прямая взаимосвязь.
0 = 1-1
1 = 2-1
2 = 3-1
3 = 4-1
4 = 5-1
Иначе говоря Индекс = Номер — Дельта
В данном случае, Дельта = 1

Также, у нас ситуация — мы удалили №4 (индекс 3), после чего список 
Элемент 0 содержит №1
Элемент 1 содержит №2
Элемент 2 содержит №3
Элемент 3 содержит №5

И нам нужно выдать новый номер.


Как работает двоичный поиск дырки/промежутка.

Стоит понять заранее, нужно ли ли искать «дырку», когда нам понадобилось выдать новый номер?

Делаем две простых проверки:
1) Список совсем пуст. Тогда просто вернём дельту=1
2) Индекс последнего элемента списка совпадает с его номером (когда список был полон, то 4 = 5-1). Это значит, что можно сразу вернуть следующий номер, т.е. (4+1)+1

Не повезло, ищем.

Возьмём весь текущий отрезок значений L = 0 (индекс самого левого элемента списка), R = 3 (индекс самого последнего)

Повторяем блок действий:
Проверим, а действительно ли текущий левый индекс L не превышает текущий правый индекс R? 0<=3
Если нет — заканчиваем повторять.
Если да, работаем:
Возьмём середину на этом текущем отрезке отрезке M = (0+3)/2 = 1 (индекс элемента посредине)
/*единица, т.к. у нас целочисленное деление, тут даже округления нет, т.е. берётся целая часть*/
Возьмём значение, хранящееся в элементе с этим индексом MVal = Элемент[M] = Элемент[1] = 2
И приведём значение MVal в соответствие с индексом, чтобы можно было что-то с чем-то сравнить:
MVal = MVal — Дельта = 2 — 1 = 1

Получившееся MVal БОЛЬШЕ индекса M? (1>1? Нет)                                                     

Если да, это значит, что искомый промежуток-дырка находится в левой половине отрезка LR, Тогда выкидываем правую половину и сужаем наш отрезок справа, R = M — 1
Если нет, значит то, что мы ищем — находится в правой половине отрезка LR. Выкидываем левую половину и сужаем наш отрезок слева, L = M + 1

Повтор блока действий (L=2, 2<=3).
Возьмём середину на этом текущем отрезке отрезке M = (2+3)/2 = 2 (индекс элемента посредине)
Возьмём значение, хранящееся в элементе с этим индексом  MVal = Элемент[M] = Элемент[2] = 3
И приведём значение MVal в соответствие с индексом, чтобы можно было что-то с чем-то сравнить:
MVal = MVal — Дельта = 3 — 1 = 2

Получившееся MVal БОЛЬШЕ индекса M? (2>2? нет)                                                     
Если да, это значит, что искомый промежуток-дырка находится в левой половине отрезка LR, Тогда выкидываем правую половину и сужаем наш отрезок справа, R = M — 1
Если нет, значит то, что мы ищем — находится в правой половине отрезка LR. Выкидываем левую половину и сужаем наш отрезок слева, L = M + 1

Повтор блока действий (L=3, 3<=3).
M = 3
MVal = 5 
MVal-1 = 4
Получившееся MVal БОЛЬШЕ индекса M? (4>3? Да)                                                     
Если да, это значит, что искомый промежуток-дырка находится в левой половине отрезка LR, Тогда выкидываем правую половину и сужаем наш отрезок справа, R = M — 1
Если нет, значит то, что мы ищем — находится в правой половине отрезка LR. Выкидываем левую половину и сужаем наш отрезок слева, L = M + 1

Прекращение повтора блока действий (L=3, R=2, 3<=2? Нет)
 
Возвращаем L+Delta (3+1=4)

Примечание, на маленьких списках, скорее всего лучше будет перебор «в лоб».

Примечание2, пример специально так подобран, чтобы поиск работал подольше.

+1
6 Нырнуть
Originalnoe
3 месяца назад

Большое вам спасибо за ваш полуночный немалый труд! Только сейчас допёр. А что затратнее внедрения подобного механизма или увеличение числа (в разумных пределах)?

+2
7 Нырнуть
3 месяца назад

Всё зависит от необходимости. Уже DWORD — переполнить «простым смертным» очень сложно. В принципе, задача повторного использования идентификаторов — штука специфическая. Ну так, если прикинуть, — на ум сходу приходят айпишники (особенно IPV4) и телефонные номера, где величины переменных увеличить сложновато :)

Иначе говоря, под каждую задачу — свой инструмент. Иногда решение «в лоб» — самое оправданное, а иногда может аукнуться спустя много лет, что приводит к написанию костылей. Короче, лучше пользоваться принципами разумной необходимости и не усложнять то, что усложнения не требует. Начинять задачу многоэтажными конструкциями «чтобы было» или «потому что могу» — уж точно не стоит :)

+1

Новые комментарии