Автор много гундосил про поиск. Но это реально просто и ничего не значит без эффективной сортировки, про что автор не сказал ни слова. Весь ролик ждал что проскочит хотя бы раз "сортировка методом бинарного дерева"
Бинарный поиск был крайне популярен в стародавние воемена, когда гирлянды делали из большого количества последовательно включённых лампочек. Рано или поздно происходила потеря контакта или сгорала лампочка. Вот и делили пополам, потом прозванивали произвольно выбранную часть. Каждая итерация позволяла очень быстро найти неисправность. Дошёл до этого своими мозгами еще в детстве.
Я как программист скажу, что не все так однозначно. ) Двоичный поиск обычно работает с массивами. Т.е. все значения расположены в памяти подряд. Добавление нового элемента в такой массив это дорогая и долгая операция. Если нужно не только искать, но и часто изменять данные, то программисты используют красно-черное дерево или b+ дерево. Причем, алгоритм красно-черного дерева напишут без подсказки меньше 1% программистов. Потому что мало кто задумывался, как оно вообще работает. Это прямо магия какая то.
Ну какая ж магия… деревья - структуры как раз использующие встроенный логарифм прохода для ускорения вставки поиска etc… в различных видах типа самобалансир и тд… поправьте ежели шо🥴
@@КириллЧе-я5ы магия, в том, что при добавлении новых значений в любое место дерева, длинна всех ветвей остается одинаковой. Это балансировка дерева, алгоритм которой мало кто объяснит. Помнят только, что какие то узлы красные, а какие то чёрные.
@@Alemorfда и это не магия, это правило построения дерева. Просто учёный, разработавший алгоритм именно кчд, просчитал каким образом отбалансировать дерево… 72й год кажся…
.бинарный поиск, анекдот: Начальник принес стопку анкет помощнику, чтоб он выбрал 10 кандидатов. Ушёл. Пришёл через час, помощник ещё возится с анкетами. Говорит, давай, я сам. Большую часть анкет убрал в сторону, не глядя, из оставшихся 15 выбрал 10 анкет. Помощник спросил, а как же стопка анкет, просмотреть, выбрать лучших. Начальник ответил, зачем нам неудачники... 😂😢
С малолетства засиживался в библиотеках и поражался, как библиотекари ищут книгу. У одних сортировка по авторам, у других по названию, по жанру и тд. Потом узнал, что на каждую книгу десятка два карточек по критерию книги. Отсюда вывод - если есть возможность массив сортируй по мере наполнения, чтобы не было мучительно больно.
Было бы неплохо так ясно и понятно (этого не отнять) послушать по "магию" помехоустойчивого кодирования - коды Рида-Соломона. Отличный стык математики и IT и тоже классика еще из 60х. Но это чуть посложнее чем "детишки, просто делите все пополам"
Неа, сначала начинаем с розетки, потом проверяем выход блока питания, потом нагрев, потом входные и выходные элементы, потом электролиты. А вот потом уже поблочно, покаскадно, поканально, поэлементно.
Метод половинного деления, неосознанно применялся еще в школе, особенно когда пошли толстые учебники. И на слова учителя " открываем учебник на 68 странице", что-то не припомню, что бы листали подряд страницы. Тупо делили пополам, пополам и т.д.
Ага, ага. "Открайте учебник на 10 странице" - так, середина это 120 страница, четвертина 60, ещё пополам 30, 15, 8, 13, 11, 10, ура! Любой здравомыслящий школьник по наитию применит метод второго порядка: на глазок пропорционально откроет с нужного края и линейно поищет в окрестности. Ньютон рулит над Коши.
Обычно в программировании используют именно хэш-таблицы за счёт поиска за O(1) и добавления элемента за амортизированное O(1). Если только не нужно выполнить нестрогий поиск слева/справа или не используются иммутабельные структуры данных.
По-моему, самый простой способ написать бп - это использовать полуинтервалы, то есть: Индексы элементов массива это числа от 0 до n-1(n - длина массива, пусть l=0 - указатель на начало, r=n - указатель на конец(не включает последний элемент массива), если r - l == 1, то такой полуинтервал включает в себя один элемент - искомый(если он есть в массиве) while r > l + 1: m = (r + l) / 2 if array[m] > value: r = m else: l = m if array[l] == value: return l else: return -1 Никаких +-1, и проверка на равенство необязательна
Когда то давно я изобрел этот метод. Но потом оказалось, что кто-то уже давно изобрел его до меня. 😅😢😂 сейчас у меня есть изобретение в области ии, которое позволит ии понимать динамические образы, надеюсь хоть тут успею быть первым😊
Ну да, легко искать, когда всё уже отсортировано, а вот когда всё вразброс, вот тут уже начинаются серьезные проблемы. Универсального алгоритма сортировки до сих пор не изобрели.
@@alex-vl7ls Быстрая сортировка использует рекурсию и требует большого объема оперативной памяти, из-за чего её, например, невозможно применить на микроконтроллере, с 1кб ОЗУ.
@@PsevdoAI Ее можно реализовать нерекурсивно. Но вы правы, она действительно требует дополнительную память. Но, допустим на таком микроконтроллере, невозможно записать большой массив, на котором выигрыш от быстрой сортировки в скорости был бы значим (килобайт ОЗУ это 8192 бита, или же всего 256 int'ов), а значит можно взять условный пузырек (или сортировку Шелла, она не требует дополнительной памяти и у нее лучше асимптотика)
@@Dmitriy-rc5bi Все алгоритмы по своему магические, но они разработаны для решения конкретных задач и вне не имеют смысла. Например, нет никакого смысла 5ти значные числа перемножать алгоритмом Карацубы (или любым другим "продвинутым" алгоритмом умножения). Это все равно что винить самолет в том, что ему нужна взлетная полоса
Помню, в детстве писал на ассемблере код для функций умножения и деления целых чисел. Умножение реализовал как цикл суммирования. Деление - как поиск значения обратной функции от умножения, как раз методом дихотомии...
А что, деление и умножение в столбик не объясняли в школе? В двоичной системе счисления как и в любой другой работает одинаково. выровнял делитель по делимому по старшему биту если делитель меньше делимого или равен, на один разряд дальше вниз если больше, и отнимаешь. Умножение так же только выравнивать нужно по младшему разряду. конечно там есть пару оптимизаций простеньких, но в целом процессоры так и делают.
@@sergc9068 Потому-что цель была, как можно быстрее заполучить искомые функции, а не тратить время на создание более сложных алгоритмов. Быстродействие также было несущественно.
Быстрая сортировка Хоара, по сути, модификация метода бинарного поиска. А быстрое преобразование Фурье, благодаря которому работает сжатие картинок/видео/звука - это модифицированная быстрая сортировка.
На самом деле, лексикографическое упорядочение - это древесная структура данных: первый знак #х, второй знак #у и т.д. Соответственно и момент выяснения, в каком месте находится "середина диапазона" по отношению к искомому номеру - это тоже сравнение внутри дерева. Тогда нафига проверять в дальнейшем те ветви, которые уже заведомо отвергнуты на предыдущей проверке??? То есть - древесная структура данных однозначно диктует древесный поиск в качесве бвстрейшего!☝️ Бинарный алгоритм хорош при поиске в линейно упорядоченном массиве - например на этапе выяснения, какая из N букв стоит на следующей позиции. И тогда возникает вопрос: скольки буквенным алфавитом следует пользоваться, чтобы в итоге быстрее найти нужный объект из N? Боюсь соврать, но по-моему ответ "е" 😊
На Python: import numpy as np import time # Генерация массива из 100 тыс. чисел без повторений data = np.random.choice(np.arange(1, 10000000), size=999999, replace=False) # Вывод массива #print(data) def binary_search(arr, target): left, right = 0, len(arr) - 1 start_time = time.time()
while left target: right = mid - 1
# Если искомый элемент больше значения в середине, # продолжаем поиск в правой половине списка else: left = mid + 1
# Если элемент не найден, возвращаем -1 end_time = time.time() print(f"Время поиска: {end_time - start_time} секунд") return -1 # Искомый элемент, например target = 69248 # Вызов функции бинарного поиска index = binary_search(data, target) if index != -1: print(f"Элемент {target} найден в позиции {index}.") else: print(f"Элемент {target} не найден.") Но увеличьте размерность массива data еще на 2 разряда, и ваша ОЗУ компьютера скажет вам до свидания.
Проблема про переполнение сумм индексов в Java высосана из пальца. Так можно повысасывать из пальца и другие edge cases, где и Питон сломается. Передали неотсортированный массив, или передали в поиск пустой массив, но при этом стартовые индексы указали и сразу вылезли за пределы массива.
Если говорить об алфавитной расстановке ключей поиска, то по сути это поиск по словарю. В старые аналоговые времена, когда нас учили технике перевода, для быстрого поиска в англо-русском словаре полезно было помнить волшебное слово DILOS. Вот и весь дихотомический алгоритм. Не 12 строк, а 5 символов.
держи, может придется где то + или -1 поставить, а может и нет....))) не оптимизировано типа i++ и тд для понимания, да и компилятор оптимизирует сам, главное писать понятно...))) =================================================================== xx = искомое значение. dd = length(mas); //начальная длина массива. =================================================================== // для ориентации // int bg =0; //начало массива. // для ориентации // int en = dd; //конец массива. int sm = 0; //смещение в массиве. while (zz != xx ) //выполнять до тех пор пока не равенство. { ii = dd div 2; //половина целое, край.
zz = mas[ ii + sm ] ;//беру крайнее значение у первой половины. sm=ii+sm; if (sm == 1) { std::cout
Гениально. Сначала мы долго и мучительно отсортируем миллиард записей, а потом быстро найдём нужную :) Дело не в методе поиска, а в отсортированности данных.
2 года назад пытался написать бинарное дерево на С++. Только когда закончил понял, что криво всё сделал, и этим неудобно пользоваться. Потом стало лень исправлять. Так, что не буду это безобразие никому отправлять. Ради ваших нервных клеток)
Еще не досмотрел. 0:45. Понятно, что это пример, но в случае с книгами я бы предпочел алгоритм, который выбирал бы полки с краю, если книга, например, начинается на А. Как мы обычно ищем слово в словаре? Мы хотим найти слово на букву И (10-я), например. Мы понимаем, что это ближе к началу и открываем примерно в первой трети словаря. Пусть там К (12-я). Значит И левее, но не намного. Примерно 0,8. Переходим туда и видим Е. Значит И где-то посередине. Делим оставшиеся страницы пополам и попадаем на И. По-моему, это даже какой-то реальный алгоритм с названием, но не помню точно, как называется. Если найду, отпишу UPDATE: похоже на интерполяционный поиск
Наверное, в идеале можно было бы ещё держать хистограмму со статистикой распределения слов по буквам, с которых они начинаются. Тогда можно будет точнее определить индекс, с которого вероятнее всего стоит начинать поиск. В принципе базы данных так и делают.
Всё зависит от ситуации. Ты попадёшь в просак, если все книги в твоей библиотеке начинаются на А. Либо, когда у тебя уже есть поднабор, но там большинство букв по этом индексу одинаково. Пример: Ты ищешь слово "Рация" и у тебя уже есть твой поднабор на букву "Р". Т. к. после "Р" идёт "а", то логично искать в начале. Но на "Ра" огромнейшее число слов, та же приставка "рас" уже нехило смещает положение: "расстояние", "расположение", "рассада" и т. д. Т. е. в словаре, слово "Рация" должно быть где-то между четвертью и половиной, но никак не в начале набора слов начинающихся с "Р". В-общем, если есть какие-то данные о наборе для поиска и их можно применить в алгоритме, - это, конечно, делается. Да, он будет более специфичен, но и более быстр для конкретного типа задач.
Это работает только для равномерных распределений по мощности элементов. А алгоритмическая сложность считается по худшему варианту. У вас и в словаре буквы не равнозначны (больше всего слов на букву П, меньше всего - на Й). Вообще лучшего поиска быть не может - всё зависит от данных. Современные БД очень наглядно это реализуют - когда вы добавляете данные, в тот же самый момент собирается/обновляется аналитика и статистика по распределениям ключей, и это позволяет выбрать и оптимальную логику сохранения (не всегда упорядочивание при вставке выгодно), и при запросе на поиск выбрать самый оптимальный данным алгоритм.
Добавлю ещё что есть чуть отличающийся алгоритм - быстрого поиска. Он лежит в основе быстрой сортировки Хоара. Там вместо деления пополам берётся просто индекс на бум. Т. е. есть массив из, например, 10 элементов. Мы берём Math.random(1, 10) -> 7. Если 7й элемент больше нашего, то будем искать между (8, 10), если меньше, то (1, 6), если равен, то нам повезло)
Я щас учусь в 11 классе, в этом году прошёл на всерос по инфе. Могу смело сказать, что всех людей, косячащих в такой халяве, как бинок, надо уволить нафиг
Двадцать пять лет тому назад, я поручил бинарному поиску найти смысл жизни, а он, редиска, до сих пор ищет. При этом, он умудрился пережить двух кошек, одну собаку, три аквариума с рыбками, бесчисленное количество кактусов и тараканов, причём не только тех тараканов, которые живут за печкой, но и в разных головах. ;-) Ну это всё шутки юмора, а теперь о серьёзном: этот комментарий 227-ой, а это простое число! ;-)
1. Бинарный поиск это, конечно, хорошо. Но если есть возможность пользоваться знанием того, какое распределение, то есть более эффективные алгоритмы. В нерперывном случае для поиска нуля монотонной гладкой функции (что по сути та же задача) обычно применим метод Ньютона, который обходит дихотомию как сокол черепаху. В дискретном случае иногда также получается воспользоваться структурой набора данных. 2. 7:40. "//" в Рython для комментариев не используется (используется "#") 3. Каждый раз, когда слышу "для хеш-таблиц среднее время поиска - константа" тяжело вздыхаю. Не то чтобы это совсем неправда, но есть достаточно много случаев, когда это ломается. 4. Написать без ошибок код бинарного поиска вполне можно. Но это такой челлендж для занудных зануд - глаз должен быть намётан на подобные ошибки.
2, это код вообще не запустится, т.к. array и Array - это два разных имени в питоне. mid - туда же. Виталик видимо языки попутал, или вставил фрагмент из запроса в ЧатГПТ - они любит иногда такое подкидывать.
А чем подобный "бинарный поиск" отличается от метода последовательного приближения применяемого в АЦП, где как такового упорядочивания исходных данных нет (вернее исходные данные не извести и/или могут быть изменяемые со временем)?
а вот я бы еще такой вопрос задал: а какой смысл писать код бинарного поиска, если он уже есть? на том же Python есть bisect. крайне маловероятно, что свой код будет работать лучше, чем всеми используемые реализации, т.е. пользоваться им даже ты сам/сама не будешь. понимания принципа работы поиска едва ли станет больше. а особенности языка, распределения памяти, переполнения и пр. и так встретятся при постоянном кодинге. а если кодишь не постоянно, то с этими проблемами тем более нет смысла возиться: есть рабочий проверенный вариант - берешь его, адаптируешь для своих нужд и используешь
если это нужно впихнуть в какой-нибудь stm32f103 то ваш питон это будет минуты переваривать и засрёт там всю память, максимально вероятно что напишу это на C/C++/fpc/Rust, будет работать во много раз быстрее и не потребуется столько памяти конечно, можно оперировать что и в STL есть бинарный поиск на шаблонах, но не всегда разумно тянуть какой-нибудь std::vector со всеми его методами и полями
Можно было и про quick-sort упомянуть. Удивительно быстро сортирует массив, в котором потом ищем. Тоже делит пополам, правда там рекурсия а это чуть посложнее для понимания
@@СергейДмитриевич-р7ч , это не Паскаль. 1) Отсутствуют точки с запятой, разделяющие операторы; 2) в заголовке function используется is; 3) после else стоит двоеточие; 4) нет блоков begin ... end; 5) возвраты из тела функции производятся отсутствующей в Паскале конструкцией return значение
А как быть если элемент не найден и ты хочешь получить не -1, а индекс элемента для вставки нового(т.е. ненайденого) элемента? Это помогло бы иметь всегда отсортированную последовательность.
А любой человек, которому в пронумерованном массиве документов нужно будет найти определенный номер, сам приходит к интуитивному пониманию алгоритма. Формально просто описать его нужно, при детальном понимании и рассмотрении. Хотя формальное описание письменным языком намного лаконичнее, чем описание языками программирования. Хотя на Хаскелле можно лаконично формально описывать алгоритмы. Но и читать это взамен - сущая морока.
Если бы я был Виталиком, то я задвинул бы телегу о том, что у программистов нуль стал натуральным числом и что программисты умудряются его вполне целочисленно считать) Хотя в классическом поле вещественных, которым мы оперируем нуль не счётен. И это также отсылает нас к тому, сколько оградок у забора из заданного количества столбов.
Лучший поиск - отсутствие поиска. Лучшая сортировка - отсутствие необходимости сортировать. Если названия всех книг и название искомой книги известны заранее, то поиск по заранее созданной хештаблице занимает одну операцию.
Это не комментарий , а вопрос. Если понимать натуральный ряд как последовательность чисел, в которой два соседних числа находятся на одинаковом расстоянии, то это расстояние может быть рациональным числом , иррациональным (для нечетных оснований) и даже трансцендентных чисел (например, точки , определяемые трансцендентной функцией синус)?
У тебя тут взаимоисключающие определения. У тебя либо натуральный ряд, в котором расстояние по определению единица, либо натуральные числа, расстояние между которыми натуральное число или нуль, если ты одно и то же натуральное число в множестве чисел рассматриваешь.
Вот сортировка как раз очень длительный и утомительный процесс с многократной перестановкой элементов. Кстати, вопросик: а ошибки у программистов в программе поиска были такие стандартные, о которых рассказывал автор видоса? Типа, переполнение промежуточного значения и неверное условие границ отсева... И возврата... Или есть еще какие-то подводные камни в трех -соснах- строках кода?
Как правильно заходить в библиотеку 😅 Надо сразу подойти к библиотекарю и поздороваться. Сразу спроси есть ли долги и отдай книги которые брал ранее. Только после этого проси новые!
8:35 а как код себя поведет, если объектов в массиве нечетное число? Середина будет дробной, ее же надо к int приводить, тогда как раз серединой станет меньший элемент
А смысл? Дробная часть итак будет отброшена при делении int на int, сработает неявное приведение. Явное приведение нужно как раз в обратном случае, когда мы НЕ хотим терять дробную часть; тогда приводим делимое или делитель к double/float. Но не в этом случае, мы ведь с индексом работаем, а он должен полюбому оставаться целым числом; иначе просто код не скомпилируется (на C# или Java, например; а Пайтон просто в рантайме сам сделает обратное приведение). YAGNI если короче)
Конечно нет, тернарный поиск - это совсем другой алгоритм, хотя с такой же асимптоткой, он нужен для того, чтобы найти экстремум на выпуклой на каком-то подотрезке функции
У бинарного поиска один огромный минус - требуется предварительная сортировка массива. Редко исходный массив остается неизменным. Значит после каждого изменения требуется сортировка, а это очень наклАдная операция.
Больцано и Коши: бисекция рулит! Ньютон: алё, мы же всё ещё говорим про математику? Метод имени меня не хотите ли? Это к тому, что бинарный поиск - не лучший. Он лучший из худших, когда природа хранимых и искомых данных не позволяет ничего больше, чем ввести отношение порядка. Даже в библиотеке никто не занимается такой фигнёй, как бисектить по стеллажам (и получать гигантские кешмиссы для произвольного доступа и гигантские задержки для последовательного - бегать от стеллажа к стеллажу). Вместо этого берут индекс. И это, кстати, довольно близко по идеям к методам второго порядка.
Это всё конечно весело но где нам надо так искать в прикладных задачах? К реальному примеру, базы данных, да там всё отсортировано но часто это сортировка по айди, а то и по дате создания записи там уже бинарный поиск не затащит ибо ищем мы чаще всего по нику, почте а то и вовсе по данным из связанной таблицы.
Сортировка сравнением ограничение по временной сложности nlogn именно из-за логарифм поиска… этот самый логарифм поиска многим Математикам не давал покоя… так появились деревья
больше 18 минут говорить о бинарном поиске, и даже не затронуть cache friendly реализацию, или хотя бы перейти на унимодальный поиск - это прямо сильно... мастерство пустых разговоров.
Джентльмены, что за ор по поводу "сперва добейся(отсортируй), а потом говори". Автор же несколько раз повторил, что способ хорош для уже отсортированных данных, внимательно слушайте, что говорят.
А теперь давайте разберёмся с такой "мелочью" как сортировка 😏
Автор много гундосил про поиск. Но это реально просто и ничего не значит без эффективной сортировки, про что автор не сказал ни слова. Весь ролик ждал что проскочит хотя бы раз "сортировка методом бинарного дерева"
@@sergc9068 во, во, я тоже ждал и думал, что вся красота бинарного поиска меркнет перед изначальным отсутствием сортировки ))
@@sergc9068 Пусть лучше расскажет про R-деревья и Z-порядок.
О да, до любого поиска сперва нужна сортировка или сортировку для данных в долгосрочной памяти
.
Бинарный поиск был крайне популярен в стародавние воемена, когда гирлянды делали из большого количества последовательно включённых лампочек. Рано или поздно происходила потеря контакта или сгорала лампочка. Вот и делили пополам, потом прозванивали произвольно выбранную часть. Каждая итерация позволяла очень быстро найти неисправность. Дошёл до этого своими мозгами еще в детстве.
А как можно прозвонить произвольно заданную часть цепи, не вырезая её из всей гирлянды?
@@f.linezkij запросто, главное чтобы остальная цепь была разомкнута
Это еще древние люди придумали. Древние люди по 20 лет жили. Все в детсве придумывали, все гениальное просто.
лучший вид поиска это удалить половину,а потом всё остальное
После слов "сортировка" и "удалить" вспомнил Stalin sort
@@VL1507сххахахахахах, шаришь
Сортировка слиянием так и работает, только она не удаляет, а сортирует обе половины, а потом сливает их
Не сортировки, а поиска в отсортированном массиве. А алгоритмов сортировки куча разных.
Я как программист скажу, что не все так однозначно. ) Двоичный поиск обычно работает с массивами. Т.е. все значения расположены в памяти подряд. Добавление нового элемента в такой массив это дорогая и долгая операция. Если нужно не только искать, но и часто изменять данные, то программисты используют красно-черное дерево или b+ дерево. Причем, алгоритм красно-черного дерева напишут без подсказки меньше 1% программистов. Потому что мало кто задумывался, как оно вообще работает. Это прямо магия какая то.
Ну какая ж магия… деревья - структуры как раз использующие встроенный логарифм прохода для ускорения вставки поиска etc… в различных видах типа самобалансир и тд… поправьте ежели шо🥴
@@КириллЧе-я5ы магия, в том, что при добавлении новых значений в любое место дерева, длинна всех ветвей остается одинаковой. Это балансировка дерева, алгоритм которой мало кто объяснит. Помнят только, что какие то узлы красные, а какие то чёрные.
@@Alemorfда и это не магия, это правило построения дерева. Просто учёный, разработавший алгоритм именно кчд, просчитал каким образом отбалансировать дерево… 72й год кажся…
@@КириллЧе-я5ы ничего то вы в магии не понимаете.
@@Alemorf😂
5:50 ролик начинается отсюда
На превью число 37. После просмотра видео от веритасиума, данный факт меня прям заинтриговал 😅
+++
Любимая рубрика! Всегда эти видео оставляю на утро выходного дня, когда можно расслабленно посмотреть под чаек )
.бинарный поиск, анекдот:
Начальник принес стопку анкет помощнику, чтоб он выбрал 10 кандидатов. Ушёл. Пришёл через час, помощник ещё возится с анкетами. Говорит, давай, я сам. Большую часть анкет убрал в сторону, не глядя, из оставшихся 15 выбрал 10 анкет. Помощник спросил, а как же стопка анкет, просмотреть, выбрать лучших. Начальник ответил, зачем нам неудачники...
😂😢
😂
Жестокая правда
В нормальном варианте анекдота: "большую часть стопки выбросил в мусорную корзину".
С малолетства засиживался в библиотеках и поражался, как библиотекари ищут книгу. У одних сортировка по авторам, у других по названию, по жанру и тд. Потом узнал, что на каждую книгу десятка два карточек по критерию книги. Отсюда вывод - если есть возможность массив сортируй по мере наполнения, чтобы не было мучительно больно.
Было бы неплохо так ясно и понятно (этого не отнять) послушать по "магию" помехоустойчивого кодирования - коды Рида-Соломона. Отличный стык математики и IT и тоже классика еще из 60х. Но это чуть посложнее чем "детишки, просто делите все пополам"
Прекрасное видео. Спасибо большое, удачи Вам и успехов.
оказывается метод Коши программисты называют бинарным поиском! ))
Недавно решил разобраться с этим алгоритмом, я поражен его эффективностью. Спасибо за столь познавательный ролик!
Отличный ролик! Может, стоит задуматься о серии роликов про интересные алгоритмы?
Программисты нажали F, чтобы отдать честь
Бинарный поиск в инженерии: при поломке, делим цепь на 2, проверяем работоспособность, продолжаем пока не найдем неисправный узел
Неа, сначала начинаем с розетки, потом проверяем выход блока питания, потом нагрев, потом входные и выходные элементы, потом электролиты. А вот потом уже поблочно, покаскадно, поканально, поэлементно.
да ты шо
@@404Negative Не, а кто
Спасибо, было интересно! Лайк, подписка)
И здесь 37!
Всегда рад видеть твоё видео!
Ура, видео, в котором я хоть что-то понимаю
Метод половинного деления, неосознанно применялся еще в школе, особенно когда пошли толстые учебники.
И на слова учителя " открываем учебник на 68 странице", что-то не припомню, что бы листали подряд страницы. Тупо делили пополам, пополам и т.д.
Ага, ага. "Открайте учебник на 10 странице" - так, середина это 120 страница, четвертина 60, ещё пополам 30, 15, 8, 13, 11, 10, ура!
Любой здравомыслящий школьник по наитию применит метод второго порядка: на глазок пропорционально откроет с нужного края и линейно поищет в окрестности. Ньютон рулит над Коши.
Обычно в программировании используют именно хэш-таблицы за счёт поиска за O(1) и добавления элемента за амортизированное O(1). Если только не нужно выполнить нестрогий поиск слева/справа или не используются иммутабельные структуры данных.
Хотелось бы ещё видео про R-деревья и поиск среди пространственных данных.
По-моему, самый простой способ написать бп - это использовать полуинтервалы, то есть:
Индексы элементов массива это числа от 0 до n-1(n - длина массива, пусть l=0 - указатель на начало, r=n - указатель на конец(не включает последний элемент массива), если r - l == 1, то такой полуинтервал включает в себя один элемент - искомый(если он есть в массиве)
while r > l + 1:
m = (r + l) / 2
if array[m] > value:
r = m
else:
l = m
if array[l] == value:
return l
else:
return -1
Никаких +-1, и проверка на равенство необязательна
Когда то давно я изобрел этот метод. Но потом оказалось, что кто-то уже давно изобрел его до меня. 😅😢😂 сейчас у меня есть изобретение в области ии, которое позволит ии понимать динамические образы, надеюсь хоть тут успею быть первым😊
Ну да, легко искать, когда всё уже отсортировано, а вот когда всё вразброс, вот тут уже начинаются серьезные проблемы. Универсального алгоритма сортировки до сих пор не изобрели.
Всмысле не изобрели? Быструю сортировку взять хотя бы
@@alex-vl7ls Быстрая сортировка использует рекурсию и требует большого объема оперативной памяти, из-за чего её, например, невозможно применить на микроконтроллере, с 1кб ОЗУ.
@@PsevdoAI Ее можно реализовать нерекурсивно. Но вы правы, она действительно требует дополнительную память. Но, допустим на таком микроконтроллере, невозможно записать большой массив, на котором выигрыш от быстрой сортировки в скорости был бы значим (килобайт ОЗУ это 8192 бита, или же всего 256 int'ов), а значит можно взять условный пузырек (или сортировку Шелла, она не требует дополнительной памяти и у нее лучше асимптотика)
В том-то и дело, что вся сила и магия этого алгоритма мгновенно меркнет, как только становится известно, что весь массив должен быть отсортирован))
@@Dmitriy-rc5bi Все алгоритмы по своему магические, но они разработаны для решения конкретных задач и вне не имеют смысла. Например, нет никакого смысла 5ти значные числа перемножать алгоритмом Карацубы (или любым другим "продвинутым" алгоритмом умножения). Это все равно что винить самолет в том, что ему нужна взлетная полоса
Удобно искать обрыв провода
Помню, в детстве писал на ассемблере код для функций умножения и деления целых чисел. Умножение реализовал как цикл суммирования. Деление - как поиск значения обратной функции от умножения, как раз методом дихотомии...
В ассемблере здорво сдвигом вправо делить на 2, на 4, на 8, на 16
@@USER-ruzer2000 Да, сложил два числа и сдвинул - вот тебе и среднее!
А что, деление и умножение в столбик не объясняли в школе?
В двоичной системе счисления как и в любой другой работает одинаково.
выровнял делитель по делимому по старшему биту если делитель меньше делимого или равен, на один разряд дальше вниз если больше, и отнимаешь.
Умножение так же только выравнивать нужно по младшему разряду. конечно там есть пару оптимизаций простеньких, но в целом процессоры так и делают.
@@sergc9068 Потому-что цель была, как можно быстрее заполучить искомые функции, а не тратить время на создание более сложных алгоритмов. Быстродействие также было несущественно.
Поиск, это, конечно, хорошо, но как на счёт сортировки самих массивов перед этим?)
Один хрен, надо выбрать алгоритм индексации неиндексированного массива.
heapSort, quickSort и mergeSort за время O(n log n) к вашим услугам. В случае ограниченного диапозона значений bucketSort и вовсе за линейное время))
Быстрая сортировка Хоара, по сути, модификация метода бинарного поиска. А быстрое преобразование Фурье, благодаря которому работает сжатие картинок/видео/звука - это модифицированная быстрая сортировка.
Если тебе надо найти элемент много раз, то от 1 сортировки погода не испортится
Если надо один раз найти элемент, то линия, конечно, выигрывает
Спасибо, бро. может втолкуешь еще как работает алгоритм блюма?
На самом деле, лексикографическое упорядочение - это древесная структура данных: первый знак #х, второй знак #у и т.д.
Соответственно и момент выяснения, в каком месте находится "середина диапазона" по отношению к искомому номеру - это тоже сравнение внутри дерева.
Тогда нафига проверять в дальнейшем те ветви, которые уже заведомо отвергнуты на предыдущей проверке???
То есть - древесная структура данных однозначно диктует древесный поиск в качесве бвстрейшего!☝️
Бинарный алгоритм хорош при поиске в линейно упорядоченном массиве - например на этапе выяснения, какая из N букв стоит на следующей позиции.
И тогда возникает вопрос: скольки буквенным алфавитом следует пользоваться, чтобы в итоге быстрее найти нужный объект из N?
Боюсь соврать, но по-моему ответ "е" 😊
Ура, я так рад что у тебя реклама появилась )
На Python:
import numpy as np
import time
# Генерация массива из 100 тыс. чисел без повторений
data = np.random.choice(np.arange(1, 10000000), size=999999, replace=False)
# Вывод массива
#print(data)
def binary_search(arr, target):
left, right = 0, len(arr) - 1
start_time = time.time()
while left target:
right = mid - 1
# Если искомый элемент больше значения в середине,
# продолжаем поиск в правой половине списка
else:
left = mid + 1
# Если элемент не найден, возвращаем -1
end_time = time.time()
print(f"Время поиска: {end_time - start_time} секунд")
return -1
# Искомый элемент, например
target = 69248
# Вызов функции бинарного поиска
index = binary_search(data, target)
if index != -1:
print(f"Элемент {target} найден в позиции {index}.")
else:
print(f"Элемент {target} не найден.") Но увеличьте размерность массива data еще на 2 разряда, и ваша ОЗУ компьютера скажет вам до свидания.
Проблема про переполнение сумм индексов в Java высосана из пальца. Так можно повысасывать из пальца и другие edge cases, где и Питон сломается. Передали неотсортированный массив, или передали в поиск пустой массив, но при этом стартовые индексы указали и сразу вылезли за пределы массива.
Виталий, -> 8:20 : у тебя ошибка в 8 строчке кода (array не определена, не забываем про регистр ;-) )
Если говорить об алфавитной расстановке ключей поиска, то по сути это поиск по словарю. В старые аналоговые времена, когда нас учили технике перевода, для быстрого поиска в англо-русском словаре полезно было помнить волшебное слово DILOS. Вот и весь дихотомический алгоритм. Не 12 строк, а 5 символов.
держи, может придется где то + или -1 поставить, а может и нет....)))
не оптимизировано типа i++ и тд для понимания, да и компилятор оптимизирует сам, главное писать понятно...)))
===================================================================
xx = искомое значение.
dd = length(mas); //начальная длина массива.
===================================================================
// для ориентации // int bg =0; //начало массива.
// для ориентации // int en = dd; //конец массива.
int sm = 0; //смещение в массиве.
while (zz != xx ) //выполнять до тех пор пока не равенство.
{
ii = dd div 2; //половина целое, край.
zz = mas[ ii + sm ] ;//беру крайнее значение у первой половины.
sm=ii+sm; if (sm == 1) {
std::cout
тут с очень серьезными ошибками, но! кому надо обращайся покажу рабочий вариант.
Мне нравится как он пишет комментарии на пайтон :-))
Всего-то осталось предварительно отсортировать массив. И можно применять бинарный поиск ))
Гениально. Сначала мы долго и мучительно отсортируем миллиард записей, а потом быстро найдём нужную :)
Дело не в методе поиска, а в отсортированности данных.
Проще один раз отсортировать и потом искать за логарифм, чем каждый раз использовать линейный поиск
И сортировка миллиарда записей займет не так уж много времени
Сортировка слиянием и быстрая сортировка имеют тот же принцип
2 года назад пытался написать бинарное дерево на С++. Только когда закончил понял, что криво всё сделал, и этим неудобно пользоваться. Потом стало лень исправлять. Так, что не буду это безобразие никому отправлять. Ради ваших нервных клеток)
Точно. Так бывает, доделаешь наконец, вроде и работает, но понимаешь - "эх, ребята, всё не так"
в АЦП последовательного приближения тоже используется алгоритм бинарного поиска
Если не ошибаюсь, метод золотого сечения потребует меньше количества итераций чем метод половинного деления
Прямой доступ по указателю ещё быстрее) )
Еще не досмотрел. 0:45. Понятно, что это пример, но в случае с книгами я бы предпочел алгоритм, который выбирал бы полки с краю, если книга, например, начинается на А.
Как мы обычно ищем слово в словаре? Мы хотим найти слово на букву И (10-я), например. Мы понимаем, что это ближе к началу и открываем примерно в первой трети словаря. Пусть там К (12-я). Значит И левее, но не намного. Примерно 0,8. Переходим туда и видим Е. Значит И где-то посередине. Делим оставшиеся страницы пополам и попадаем на И.
По-моему, это даже какой-то реальный алгоритм с названием, но не помню точно, как называется. Если найду, отпишу
UPDATE: похоже на интерполяционный поиск
Имеет место быть! Но тут наверное зависит от условий задачи. Вдруг у нас 100 книг на букву А и по одной книге на все остальные буквы алфавита
Наверное, в идеале можно было бы ещё держать хистограмму со статистикой распределения слов по буквам, с которых они начинаются. Тогда можно будет точнее определить индекс, с которого вероятнее всего стоит начинать поиск. В принципе базы данных так и делают.
Всё зависит от ситуации. Ты попадёшь в просак, если все книги в твоей библиотеке начинаются на А. Либо, когда у тебя уже есть поднабор, но там большинство букв по этом индексу одинаково.
Пример: Ты ищешь слово "Рация" и у тебя уже есть твой поднабор на букву "Р". Т. к. после "Р" идёт "а", то логично искать в начале. Но на "Ра" огромнейшее число слов, та же приставка "рас" уже нехило смещает положение: "расстояние", "расположение", "рассада" и т. д. Т. е. в словаре, слово "Рация" должно быть где-то между четвертью и половиной, но никак не в начале набора слов начинающихся с "Р".
В-общем, если есть какие-то данные о наборе для поиска и их можно применить в алгоритме, - это, конечно, делается. Да, он будет более специфичен, но и более быстр для конкретного типа задач.
Это работает только для равномерных распределений по мощности элементов. А алгоритмическая сложность считается по худшему варианту. У вас и в словаре буквы не равнозначны (больше всего слов на букву П, меньше всего - на Й). Вообще лучшего поиска быть не может - всё зависит от данных. Современные БД очень наглядно это реализуют - когда вы добавляете данные, в тот же самый момент собирается/обновляется аналитика и статистика по распределениям ключей, и это позволяет выбрать и оптимальную логику сохранения (не всегда упорядочивание при вставке выгодно), и при запросе на поиск выбрать самый оптимальный данным алгоритм.
Добавлю ещё что есть чуть отличающийся алгоритм - быстрого поиска. Он лежит в основе быстрой сортировки Хоара. Там вместо деления пополам берётся просто индекс на бум. Т. е. есть массив из, например, 10 элементов. Мы берём Math.random(1, 10) -> 7. Если 7й элемент больше нашего, то будем искать между (8, 10), если меньше, то (1, 6), если равен, то нам повезло)
Я щас учусь в 11 классе, в этом году прошёл на всерос по инфе. Могу смело сказать, что всех людей, косячащих в такой халяве, как бинок, надо уволить нафиг
Обманчиво простая штука.
-Этот алгоритм легкий разберется даже ребенок
-В нем ошибаются 90% программистов
ок...
Бинарный поиск легко может как найти нужное число, так и обратная задача: добавление 1 элемента в массив.
Двадцать пять лет тому назад, я поручил бинарному поиску найти смысл жизни, а он, редиска, до сих пор ищет. При этом, он умудрился пережить двух кошек, одну собаку, три аквариума с рыбками, бесчисленное количество кактусов и тараканов, причём не только тех тараканов, которые живут за печкой, но и в разных головах. ;-)
Ну это всё шутки юмора, а теперь о серьёзном: этот комментарий 227-ой, а это простое число! ;-)
1. Бинарный поиск это, конечно, хорошо. Но если есть возможность пользоваться знанием того, какое распределение, то есть более эффективные алгоритмы. В нерперывном случае для поиска нуля монотонной гладкой функции (что по сути та же задача) обычно применим метод Ньютона, который обходит дихотомию как сокол черепаху. В дискретном случае иногда также получается воспользоваться структурой набора данных.
2. 7:40. "//" в Рython для комментариев не используется (используется "#")
3. Каждый раз, когда слышу "для хеш-таблиц среднее время поиска - константа" тяжело вздыхаю. Не то чтобы это совсем неправда, но есть достаточно много случаев, когда это ломается.
4. Написать без ошибок код бинарного поиска вполне можно. Но это такой челлендж для занудных зануд - глаз должен быть намётан на подобные ошибки.
2, это код вообще не запустится, т.к. array и Array - это два разных имени в питоне. mid - туда же. Виталик видимо языки попутал, или вставил фрагмент из запроса в ЧатГПТ - они любит иногда такое подкидывать.
Есть ещё и адаптивный поиск. Пример: если вы ищете в справочнике слово на букву Ф вы же не лезете в середину справочника. Вы лезете ближе к концу.
Это если известно, что на каждого элемента примерно одинаковое количество.
А если в списке из ста слов 70-80 на букву Ф?
А чем подобный "бинарный поиск" отличается от метода последовательного приближения применяемого в АЦП, где как такового упорядочивания исходных данных нет (вернее исходные данные не извести и/или могут быть изменяемые со временем)?
Там тоже видно, больше ли текущее значение уровня сигнала.
а вот я бы еще такой вопрос задал: а какой смысл писать код бинарного поиска, если он уже есть? на том же Python есть bisect.
крайне маловероятно, что свой код будет работать лучше, чем всеми используемые реализации, т.е. пользоваться им даже ты сам/сама не будешь. понимания принципа работы поиска едва ли станет больше.
а особенности языка, распределения памяти, переполнения и пр. и так встретятся при постоянном кодинге. а если кодишь не постоянно, то с этими проблемами тем более нет смысла возиться: есть рабочий проверенный вариант - берешь его, адаптируешь для своих нужд и используешь
если это нужно впихнуть в какой-нибудь stm32f103 то ваш питон это будет минуты переваривать и засрёт там всю память, максимально вероятно что напишу это на C/C++/fpc/Rust, будет работать во много раз быстрее и не потребуется столько памяти
конечно, можно оперировать что и в STL есть бинарный поиск на шаблонах, но не всегда разумно тянуть какой-нибудь std::vector со всеми его методами и полями
Спасибо Вам за ролик
Как всегда захватывающе. F
Можно было и про quick-sort упомянуть. Удивительно быстро сортирует массив, в котором потом ищем. Тоже делит пополам, правда там рекурсия а это чуть посложнее для понимания
Это не quick-sort, а merge-sort
В бинарном поиске тоже рекурсия
@@germansidorenko7381 зачем, если можно через while?
1:00
1) увидел код, но не успел рассмотреть
2) перемотал назад чтобы рассмотреть
3) понял что не знаешь какой это язык
4) смотришь дальше
Паскаль
@@СергейДмитриевич-р7ч , это не Паскаль. 1) Отсутствуют точки с запятой, разделяющие операторы; 2) в заголовке function используется is; 3) после else стоит двоеточие; 4) нет блоков begin ... end; 5) возвраты из тела функции производятся отсутствующей в Паскале конструкцией return значение
Питон
С кучей ошибок
А как получить отсортированный список? Вот тут и будет определяться вычислительная сложность поиска, сортировкой, а не самим алгоритмом поиска.
Интересно, а в Пайтоне есть поиск для неоднородного массива, заполненного неотсортированными данными? В Julia например есть!
А как быть если элемент не найден и ты хочешь получить не -1, а индекс элемента для вставки нового(т.е. ненайденого) элемента? Это помогло бы иметь всегда отсортированную последовательность.
Сохранять отдельно L и R - на входе в цикл это индексы
14:25 Пасхалочка :-)
Не как и откуда, но я знал этот алгоритм, дсже будто, сам его придумал. И тут узнаю что он оказывается по сути самый эффективный...
А любой человек, которому в пронумерованном массиве документов нужно будет найти определенный номер, сам приходит к интуитивному пониманию алгоритма. Формально просто описать его нужно, при детальном понимании и рассмотрении. Хотя формальное описание письменным языком намного лаконичнее, чем описание языками программирования. Хотя на Хаскелле можно лаконично формально описывать алгоритмы. Но и читать это взамен - сущая морока.
@@CraBiKun По сути так и есть и это чудо человеческого сознания
Две самые популярные ошибки - это ошибка границы (она же - ошибка плюс-минус-единицы).
Если вы понимаете, о чём я.
Если бы я был Виталиком, то я задвинул бы телегу о том, что у программистов нуль стал натуральным числом и что программисты умудряются его вполне целочисленно считать) Хотя в классическом поле вещественных, которым мы оперируем нуль не счётен. И это также отсылает нас к тому, сколько оградок у забора из заданного количества столбов.
@@CraBiKun про несчётность нуля можно дальше не продолжать. Каша в голове - страшная штука.
Где отсортированы все решения проблем, чтобы искать их с помощью бинарного поиска?
Да, бинарный поиск - это очевидное решение для упорядоченных массивов. Вот бы было что-то подобное для НЕупорядоченных!
А еще интересно, почему Виталий для примера выбрал число 37...? :)
ua-cam.com/video/d6iQrh2TK98/v-deo.html&ab_channel=Veritasium
Лучший поиск - отсутствие поиска. Лучшая сортировка - отсутствие необходимости сортировать. Если названия всех книг и название искомой книги известны заранее, то поиск по заранее созданной хештаблице занимает одну операцию.
Это не комментарий , а вопрос. Если понимать натуральный ряд как последовательность чисел, в которой два соседних числа находятся на одинаковом расстоянии, то это расстояние может быть рациональным числом , иррациональным (для нечетных оснований) и даже трансцендентных чисел (например, точки , определяемые трансцендентной функцией синус)?
У тебя тут взаимоисключающие определения. У тебя либо натуральный ряд, в котором расстояние по определению единица, либо натуральные числа, расстояние между которыми натуральное число или нуль, если ты одно и то же натуральное число в множестве чисел рассматриваешь.
Только честно, вы 37 расположили на превью после видео Veritasium?
В видео описан алгоритм для упорядаченного ряда, а задачу библиотеки, где все перепутаны этот алгоритм не позволит найти нужную книгу.
Вот сортировка как раз очень длительный и утомительный процесс с многократной перестановкой элементов.
Кстати, вопросик: а ошибки у программистов в программе поиска были такие стандартные, о которых рассказывал автор видоса? Типа, переполнение промежуточного значения и неверное условие границ отсева... И возврата... Или есть еще какие-то подводные камни в трех -соснах- строках кода?
Как правильно заходить в библиотеку 😅
Надо сразу подойти к библиотекарю и поздороваться.
Сразу спроси есть ли долги и отдай книги которые брал ранее.
Только после этого проси новые!
8:35 а как код себя поведет, если объектов в массиве нечетное число? Середина будет дробной, ее же надо к int приводить, тогда как раз серединой станет меньший элемент
А смысл? Дробная часть итак будет отброшена при делении int на int, сработает неявное приведение. Явное приведение нужно как раз в обратном случае, когда мы НЕ хотим терять дробную часть; тогда приводим делимое или делитель к double/float. Но не в этом случае, мы ведь с индексом работаем, а он должен полюбому оставаться целым числом; иначе просто код не скомпилируется (на C# или Java, например; а Пайтон просто в рантайме сам сделает обратное приведение). YAGNI если короче)
мой любимый алгоритм
Я такой алгоритм классе в 8ом как хобби в школе сам придумал написав его без ошибок, я могу считаться гением?🤣
Вот только он работает исключительно в отсортированных массивах
В коде ошибка: return mid. При этом выше в коде Mid
Аналогично с Array array в elif.
Чатгупэтэ писал)
Ну он же так и сказал) ua-cam.com/video/zWyPZUe1VcE/v-deo.html
В питоне вообще не принято переменные с прописных писать)
О! Вы еще и в проге разбираетесь))
Только алгоритм, по-моему, тернарный (где бинарность - частный случай: для четного числа элементов в массиве).
Конечно нет, тернарный поиск - это совсем другой алгоритм, хотя с такой же асимптоткой, он нужен для того, чтобы найти экстремум на выпуклой на каком-то подотрезке функции
У бинарного поиска один огромный минус - требуется предварительная сортировка массива. Редко исходный массив остается неизменным. Значит после каждого изменения требуется сортировка, а это очень наклАдная операция.
8:25
А если искомое число -1 , то при выводе -1 мы какой вывод должны сделать: что ответ -1 ,или что искомого числа нет?😂
Если такое число в массиве есть, то вернеся индекс элемента, если нет, то вернется -1
Больцано и Коши: бисекция рулит!
Ньютон: алё, мы же всё ещё говорим про математику? Метод имени меня не хотите ли?
Это к тому, что бинарный поиск - не лучший.
Он лучший из худших, когда природа хранимых и искомых данных не позволяет ничего больше, чем ввести отношение порядка.
Даже в библиотеке никто не занимается такой фигнёй, как бисектить по стеллажам (и получать гигантские кешмиссы для произвольного доступа и гигантские задержки для последовательного - бегать от стеллажа к стеллажу). Вместо этого берут индекс.
И это, кстати, довольно близко по идеям к методам второго порядка.
8:04 в python на строки делить не принято ;)
комментарии там через решетку
return -1 в пайтоне совершенно необязательно, так что это даже 11-строчный алгоритм.
тебе в пайтоне строчки 4 достаточно будет
@@borisov4028 мне?!
который даже не запустится
Не работает этот метод. Как найти одну единственную среди массива подруг? Получается только линейным методом перебора😊
Сначала сортируй.
Это всё конечно весело но где нам надо так искать в прикладных задачах? К реальному примеру, базы данных, да там всё отсортировано но часто это сортировка по айди, а то и по дате создания записи там уже бинарный поиск не затащит ибо ищем мы чаще всего по нику, почте а то и вовсе по данным из связанной таблицы.
А как в неупорядоченном массиве искать?
13:43 в 10-й строке пропущена точка с запятой, в этом ошибка?
Это опечатка, если такой код был бы написан в библиотеке, то он просто не скомпилировался
Сортировка сравнением ограничение по временной сложности nlogn именно из-за логарифм поиска… этот самый логарифм поиска многим Математикам не давал покоя… так появились деревья
Полинарный поиск круче, если использовать распараллеливание.
Я зашёл сюда только что бы поставить лайк за число 37 на превью. Слава Иваново
Старый анекдот про "как найти льва в пустыне?" =)
Построить забор через середину пустыни? Послушать, с какой стороны рычит лев?
Да, именно.
Лучше было бы тогда указать индексацию с нуля
37 не случайно?
больше 18 минут говорить о бинарном поиске, и даже не затронуть cache friendly реализацию, или хотя бы перейти на унимодальный поиск - это прямо сильно... мастерство пустых разговоров.
еще не смотрел, 20 секунд. Начинаем с середины. От середины налево, или направо, до середины этого отрезка. И так далее...
ua-cam.com/video/zWyPZUe1VcE/v-deo.html
тоже косяк
У L+R не будет на 3 цифры больше. Максимум на 1
Джентльмены, что за ор по поводу "сперва добейся(отсортируй), а потом говори". Автор же несколько раз повторил, что способ хорош для уже отсортированных данных, внимательно слушайте, что говорят.
Дональд Кнут, стрелочная нотация-это его?
его