Рубрика «двоичный поиск»

Ускорение поиска в Have I Been Pwned до 49 микросекунд (С++) - 1

Я давно знал о сайте Have I Been Pwned (HIBP). Правда, до недавнего времени никогда там не был. Мне всегда хватало двух паролей. Один из них неоднократно использовался для мусорной почты и пары аккаунтов на странных сайтах. Но пришлось от него отказаться, потому что почту взломали. И, честно говоря, я благодарен хакеру, потому что это событие заставило меня пересмотреть свои пароли — то, как я их использую и храню.

Конечно, я поменял пароли на всех аккаунтах, где стоял скомпрометированный пароль. Затем мне стало интересно, попал ли утёкший пароль в базу HIBP. Я не хотел вводить пароль на сайте, поэтому скачал базу данных (pwned-passwords-sha1-ordered-by-count-v5). База весьма впечатляет. Это текстовый файл на 22,8 ГБ с набором хэшей SHA-1, по одному в каждой строке со счётчиком, сколько раз пароль с данным хэшем встречался в утечках. Я вычислил SHA-1 своего взломанного пароля и попытался найти его.
Читать полностью »

Двоичный поиск в графах - 1

Двоичный поиск — один из самых базовых известных мне алгоритмов. Имея отсортированный список сравнимых элементов и целевой элемент, двоичный поиск смотрит в середину списка и сравнивает значение с целевым элементом. Если цель больше, мы повторяем с меньшей половиной списка, и наоборот.

При каждом сравнении алгоритм двоичного поиска разбиваем пространство поиска пополам. Благодаря этому всегда будет не более $log(n)$ сравнений со временем выполнения $O(log n)$. Красиво, эффективно, полезно.

Но всегда можно посмотреть под другим углом.

Что, если попробовать выполнить двоичный поиск по графу? Большинство алгоритмов поиска по графам, такие как поиск в ширину или поиск в глубину, требуют линейного времени и были придуманы довольно умными людьми. Поэтому если двоичный поиск по графу будет иметь какой-то смысл, то он должен использовать больше информации, чем та, к которой имеют доступ обычные алгоритмы поиска.
Читать полностью »

Измерение пропускной способности узких мест по времени двойного прохода пакета

По всем параметрам, сегодняшний интернет не может перемещать данные так быстро, как должен. Большинство пользователей сотовой связи в мире испытывают задержки от нескольких секунд до нескольких минут: публичные точки WiFi в аэропортах и на конференциях ещё хуже. Физикам и климатологам нужно обмениваться петабайтами данных с коллегами по всему миру, но они сталкиваются с тем, что их тщательно продуманная многогигабитная инфраструктура часто выдаёт всего несколько мегабит в секунду на трансконтинентальных линиях. [6]

Эти проблемы возникли из-за выбора архитектуры, который был сделан при создании системы регулирования заторов TCP в 80-е годы — тогда потерю пакетов решили интерпретировать как «затор». [13] Эквивалентность этих понятий была справедливой для того времени, но только из-за ограничений технологии, а не по определению. Когда NIC (контроллеры сетевых интерфейсов) модернизировали с мегабитных до гигабитных скоростей, а микросхемы памяти — с килобайт до гигабайт, до связь между потерей пакетов и заторами стала менее очевидной.

В современном TCP регулирование заторов по потере пакетов — даже в наиболее совершенной технологии такого рода CUBIC [11] — основная причина этих проблем. Если буферы узких мест слишком большие, то система регулирования заторов по потере пакетов держит их полными, вызывая излишнюю сетевую буферизацию. Если буферы слишком маленькие, то система регулирования заторов по потере пакетов неверно интерпретирует потерю пакета как сигнал затора, что ведёт к снижению пропускной способности. Решение этих проблем требует альтернативы регулированию заторов по потере пакетов. Для нахождения этой альтернативы следует разобраться, где и как возникают заторы.
Читать полностью »

Привет!

Я решил продолжить серию статей про гипотезу Эйлера, написав несколько улучшенных версий программ для решения диофантова уравнения вида a5 + b5 + c5 + d5 = e5.

10 новых сказок о потерянном времени - 1

Как известно, для того, чтобы решить какую-либо сложную вычислительную задачу, нужно обратить внимание как минимум на следующие пункты:

  1. Эффективный алгоритм
  2. Быстрая реализация
  3. Мощное железо
  4. Распараллеливание

Я уделил больше всего внимания первому пункту. Давайте посмотрим, что из этого получилось.
Читать полностью »

С мая 2010 года Google Docs ввёл новый формат документов, который сохраняет подробную историю версий. Вы можете открутить действия назад, словно в замедленном фильме. Текстовый редактор сохраняет время нажатия клавиш с точностью до микросекунды.

Журналист и хакер Джеймс Сомерс сумел взломать внутренний формат Google Docs и извлечь метки времени для каждого нажатия клавиш. Таким образом, вы можете посмотреть историю создания документа от начала и до конца. Более того, кейлоггер Google Docs очень продвинутый: он присваивает уникальные идентификаторы символам, так что знает даже, откуда и куда скопирована каждая буква!

Самое главное, что для вас открыта история нажатия клавиш и чужих документов, которыми с вами поделились коллеги для совместной работы. Это можно назвать неожиданным поведением программы. Если я создаю документ, а потом открываю к нему совместный доступ, я не могу ожидать, что все коллеги увидят полную историю, как создавался этот текст, какие слова исправлялись и какие предложения удалялись, прежде чем документ выложили на всеобщее обозрение.
Читать полностью »

В данной статье речь пойдет об алгоритме HEngine и реализации решения проблемы подсчета расстояния Хэмминга на больших объемах данных.
Читать полностью »

Это перевод статьи Джошуа Блоха «Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken» 2006 года.

Я живо помню первую лекцию Джона Бентли в университете Карнеги-Меллон, на которой он попросил нас, свежеиспечённых аспирантов, написать функцию двоичного поиска. Потом он взял одно из решений и разобрал его на доске, и разумеется, в нём оказалась ошибка, как и во многих других наших попытках. Этот случай стал для меня наглядной демонстрацией к его книге «Жемчужины программирования». Мораль в том, чтобы внимательно расставлять инварианты в программе.

И вот, теперь 2006 год. Я был потрясён, узнав, что программа двоичного поиска, корректность которой Бентли доказывал формально и тестами, содержит ошибку. Не подумайте, что я придираюсь; по правде сказать, эта такая ошибка, что вполне может ускользать от тестеров десятилетиями. Более того, двоичный поиск, который я написал для JDK, тоже был багнутым лет эдак девять. И только сейчас, когда она сломала кому-то программу, о ней сообщили в Sun.
Читать полностью »

Недавно (буквально два года назад) тут пробегала статья Только 10% программистов способны написать двоичный поиск. Двоичный поиск — это классический алгоритм поиска. Мало того, это еще чрезвычайно простой алгоритм, который можно очень легко описать: берем отсортированный массив, смотрим в середину, если не нашли там число, в зависимости от того, что в середине — ищем это число этим же методом либо в левой части, либо в правой, откидывая средний элемент. Для функций также, просто берем не массив, а функцию. Все очень и очень просто, алгоритм описан почти везде, все баги словлены и описаны.

Так вот, я не могу реализовать двоичный поиск. Для меня он ни капельки не тривиален. Наверное, я ненастоящий программист. А ведь так и есть, я всего-лишь студент, но ведь это не оправдание? Если точнее, я не могу реализовать хороший корректный красивый двоичный поиск. Все время у меня вылезает проблема либо с корректностью, либо с красивостью, либо и с тем, и с другим. Так что, да, заголовок немного желтоват.
Прежде чем читать этот топик, напишите свою версию бинарного поиска — для отсортированного массива. Причем, в зависимости от параметра, поиск должен выдавать или первый элемент, или любой из дублирующих. Еще для сравнения, напишите бинарный поиск для функций

Читать полностью »

Локализация точки в выпуклом многоугольнике Листая страницы хаба «Алгоритмы», наткнулся на топик, посвященный решению задачи локализации точки в многоугольнике: задан многоугольник (замкнутая ломаная линия без самопересечений), требуется определить — находится ли заданная точка A внутри этого многоугольника или нет. В одном из последних комментариев к топику было высказано недоумение, какое отношение такая чисто математическая задача имеет к теории алгоритмов. Имеет-имеет, причем самое непосредственное. Задача локализации является классической задачей вычислительной геометрии (не путать с компьютерной графикой). В качестве разминки предлагается взглянуть на картинку справа, на которой изображен многоугольник типа кривой Пеано (источник [1]), и попытаться ответить на вопрос — красная точка ты видишь суслика? и я не вижу, а он есть! находится внутри или снаружи многоугольника? А ниже мы (исключительно в образовательных целях) рассмотрим простую вариацию данной задачи, когда заданный многоугольник является выпуклым.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js