Двоичный поиск или как найти то, чего нет. Скучнопост.
Неочевидная штука: Москва не резиновая Вместимость переменных конечна. Это значит, что (в нынешней данности - когда в одном байте, обычно, 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);
}
Как-то так :))))
Новые комментарии
BuhBuhov
1 день назад
Поиграл раз двадцать. Если не тридцать. Лучший результат 7,47 секунды.
Вот серьезно. Кто будет играть в игру, которая длится максимум семь секунд? Ну, может кто-то продержится 10-15. Да еще вдобавок, надо хвататься за мышь каждый раз, когда проиграл. А потом быстро перекидывать руку на клавиши управления курсором?
В целом задумка ничем не хуже чем змейка. Очень хорошая задумка. Но в змейку при ловкости можно несколько минут играть. А тут бац! Семь секунд и начинай сначала. Да еще и мышкой.
BuhBuhov
4 дня назад
К посту претензий нет. Плюсик поставил. Но… @Admin пост целиком выпадает в ленту. То есть кнопки «Раскрыть» снизу нет. Надо листать, пока не кончится. Бага массовой загрузки картинок?
Плюс завтра будет субботница, только что подготовил. В кнопке «Раскрыть» у меня в профиле, показывает, что картинок будет 25. Но их там тридцать. Я пересчитал.
MEGAV0LT
7 дней назад
Очень давно, это максимум 2000-й. Если у кого и осталось, то на VHS. Не оцифровано, потому и не в сети
BuhBuhov
8 дней назад
Я кстати, можно сказать жизнь уже прожил! Так что я лучше вас знаю! 
BuhBuhov
8 дней назад
Где-то я читал, что мозгу пофиг. Он продолжает строить новые нейронные связи всю жизнь. То есть, человек способен учиться всю жизнь. Но с годами и приобретением опыта, мозг (а может и не мозг, а личность в котором она живет) вдруг решает, что уже научилась всему, чему возможно. И тогда наступает период — «А че вы меня учите? Я и сам все знаю!». И это становится началом конца.
Человек решает — да нафиг надо в этом разбираться? Вон, есть сын, дочь, внук. Они мне все настроят и все.
А ведь разобраться-то не так уж сложно. Надо только немного напрячь свои мозги.
Дело не в возрасте, а в любознательности. И мысли — «Если дети понимают, что же — я не разберусь?».
Если этого нет, то ничего уже не поможет. А если есть, то такой человек будет до смерти умным и толковым.
Жаль только, что таких людей мало. В основном как раз эти — «я жизнь прожил! Я все лучше вас знаю!».
Но такова селява. :-)
А че почалось то? если надо для коду — мы добавим жеж:
Естественно, надо!!
А можно помедленнее и с картинками, пожалуйста?
Ну давай «на пальцах». Главное условие — список сортирован по возрастанию значений, т.е. 1,2,3....10,11… 100,101,… и т.п.
(допустим, что счёт с единицы)
Выдаём номер:
1. Список пуст. Выдаём минимальный номер. Возвращаем 0+1
2. Список не пуст. Последний элемент списка равен его «идеальному» порядковому номеру (т.е., грубо говоря, элемент с номером 100 содержит значение 100)? Нет. Значит дырок нет. возвращаем 100+1
3. Дырки есть, начинаем поиск. Лезем в середину. Элемент списка с номером 50 содержит 50? Да, дырка левее, нет, правее, повторяем, взяв нужную половину… В итоге мы найдём отсутствующий номер.
Хоть код и дан на c++ 98, но он вполне понятно читается, если читать :)
Блин, с «нет» и «да» заигрался. Перечитал — спохватился.
Было:
По смыслу понятно, но...
Читать так:
Разница колоссальна, от таких легкомысленных опечаток — не всегда просто ржач, иногда и на голову может упасть, извиняюсь за невнимательность, постараюсь расти над собой :)
А можно для самых маленьких вариант?
Вот есть у тебя список, содержащий номера 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, пример специально так подобран, чтобы поиск работал подольше.
Большое вам спасибо за ваш полуночный немалый труд! Только сейчас допёр. А что затратнее внедрения подобного механизма или увеличение числа (в разумных пределах)?
Всё зависит от необходимости. Уже DWORD — переполнить «простым смертным» очень сложно. В принципе, задача повторного использования идентификаторов — штука специфическая. Ну так, если прикинуть, — на ум сходу приходят айпишники (особенно IPV4) и телефонные номера, где величины переменных увеличить сложновато :)
Иначе говоря, под каждую задачу — свой инструмент. Иногда решение «в лоб» — самое оправданное, а иногда может аукнуться спустя много лет, что приводит к написанию костылей. Короче, лучше пользоваться принципами разумной необходимости и не усложнять то, что усложнения не требует. Начинять задачу многоэтажными конструкциями «чтобы было» или «потому что могу» — уж точно не стоит :)