Pull to refresh

Мгновенный поиск в 75 гигабайтах

PHP *
Sandbox
Речь пойдет о том, как был реализован быстрый поиск по большим объемам данных на этой страничке. Там можно искать пароль по хешу, для игрового сервера PvPGN, и генерировать эти же хеши.
Поиск написан на чистом PHP, без использования модулей и сторонней БД. В принципе, таким образом можно наращивать объемы до многих терабайт, было бы место — скорость от этого не сильно пострадает.

Далее от начала до конца описан весь процесс, который включает в себя брутфорс, создание хеш таблицы, её сортировка и, собственно, поиск.


Читать дальше →
Total votes 143: ↑122 and ↓21 +101
Views 32K
Comments 115

Я не могу написать бинарный поиск

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

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

А в чем, собственно, проблема?
Total votes 165: ↑107 and ↓58 +49
Views 194K
Comments 156

Cache-Conscious Binary Search

Enterra corporate blog .NET *Algorithms *C# *
Рассмотрим простую задачу: есть некоторый достаточно большой неизменный набор чисел, к нему осуществляется множество запросов на наличие некоторого числа в этом наборе, необходимо максимально быстро эти запросы обрабатывать. Одно из классических решений заключается в формировании отсортированного массива и обработке запросов через бинарный поиск. Но можно ли добиться более высокой производительности, чем в классической реализации? В этой статье мне хотелось бы рассказать про Cache-Conscious Binary Search. В данном алгоритме предлагается переупорядочить элементы массива таким образом, чтобы использование кэша процессора происходило максимально эффективно.
Читать дальше →
Total votes 47: ↑46 and ↓1 +45
Views 10K
Comments 12

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Algorithms *
Sandbox

Вступление


Здравствуйте, хабравчане. Это моя первая публикация, в которой хочу поделиться структурой данных SMAS. В конце статьи будет предоставлен С++ — класс предложенной структуры данных. Реализация рекурсивная, но моя цель — донести идею. Реализацию не рекурсивной версии — дело второе. Важно «услышать» мнения.

Что не так с деревом?


Да, всё так и можно завершать статью, всем спасибо. было бы плюнуть на значительный оверхеад памяти на вспомогательные данные в виде ссылок на левые-правые поддеревья и флаг для балансировки (разный в зависимости от используемой техники — красно-чёрные, АВЛ и т.п. деревья). Ещё один, не то чтобы минус — это постоянная модификация дерева при вставке для балансировки (тут особенно важна сложность и запутанность методов для новичков). На этом минусы заканчиваются и сложно себе представить что-то лучше и более универсальное (хеш-таблицы, ИМХО, ещё круче, но ОХ УЖ ЭТИ КОЛЛИЗИИ).
Читать дальше →
Total votes 19: ↑12 and ↓7 +5
Views 5.2K
Comments 91

Упрощаем бинарный поиск в Excel — реализация Double VLOOKUP Trick с помощью UDF

High performance *Semantics *Algorithms *Development for e-commerce *
Добавлю в копилку статей Хабра о Бинарном поиске еще одну. Речь пойдет о кастомной реализации, может быть полезно всем, кто часто использует в работе ВПР для сравнения больших списков или для поиска данных в больших массивах.
Читать дальше →
Total votes 12: ↑11 and ↓1 +10
Views 9.3K
Comments 25

Усовершенствуем функцию ВПР в Excel

Programming *Algorithms *
Sandbox

Прочтение публикации Упрощаем бинарный поиск в Excel сподвигло на дополнительное усовершенствование функции ВПР по сравнению с приведенным в статье.


Что не было учтено, и что хотелось бы добавить:

Читать дальше →
Total votes 18: ↑18 and ↓0 +18
Views 14K
Comments 13

Бинарный поиск в JavaScript. Практический пример

Website development *JavaScript *Programming *
Translation
Tutorial
image

Что такое бинарный поиск?


Когда нужно выполнить поиск в массиве, простейшим способом может быть использование indexOf() или, возможно, цикла for(). Любой из этих способов будет начинать перебирать массив начиная с начала и переходить по каждому элементу массива до тех пор, пока не будет найдено нужное значение.

Теперь сравним это с бинарным поиском.

Бинарный поиск позволяет выполнять поиск в отсортированном массиве путем многократного разбиения массива пополам.
Читать дальше →
Total votes 24: ↑12 and ↓12 0
Views 39K
Comments 19

Принцип Брета Виктора: «Творцам нужна мгновенная связь с тем, что они создают»

проект «Энгельбарт» corporate blog Programming *Game development *Interfaces *Popular science
Это одно из лучших выступлений, которое я встречал. Хоть про эту презентацию уже писали на Хабре и переводили 6 лет назад, я решил её красиво оформить и ещё раз обратить на неё внимание. Она того стоит.

image

Брет Виктор: Я просто хочу рассказать вам о том, как прожить свою жизнь.

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

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

Эта презентация разбита на три части.

Вначале, я расскажу о принципе, которым я руководствуюсь в своей работе, и постараюсь показать вам, что из этого выходит. Также, я расскажу вам о некоторых людях, которые жили подобным образом. Об их принципах, о том, во что они верили и верят. Но все это будут только примеры, которые помогут Вам задуматься о том, во что верите Вы, и о том, как Вы хотите прожить свою жизнь.
Total votes 46: ↑41 and ↓5 +36
Views 20K
Comments 31

Самый полный русскоязычный перевод Гарвардского курса по программированию CS50 2015, бесплатно на YouTube

Programming *
Sandbox
В этой статье я хочу немного рассказать о самом лучшем в мире курсе по программированию.

С 2013 года наша небольшая команда занимается переводом и адаптацией англоязычных видеокурсов. За это время мы перевели и адаптировали свыше 150 часов материала. Перед тем как приступать к работе, мы анализировали материалы нескольких обучающих онлайн-школ, и выбирали, на наш педагогический взгляд, самую лучшую, которая максимально доступно, структурированно и кратко подаёт обучающий материал. В результате чего нам приходилось просматривать по несколько курсов касающихся одной и той же тематики, а после выбирать тот, который наиболее качественный и доступный для понимания новичкам.

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

image
Total votes 19: ↑18 and ↓1 +17
Views 53K
Comments 27

Big O

JavaScript *Programming *Algorithms *
Translation
Примечание. Сокращенный перевод, скорее пересказ своими словами.
UPD: как отметили в комментариях, примеры не идеальны. Автор не ищет лучшее решение задачи, его цель объяснить сложность алгоритмов «на пальцах».


Big O нотация нужна для описания сложности алгоритмов. Для этого используется понятие времени. Тема для многих пугающая, программисты избегающие разговоров о «времени порядка N» обычное дело.

Если вы способны оценить код в терминах Big O, скорее всего вас считают «умным парнем». И скорее всего вы пройдете ваше следующее собеседование. Вас не остановит вопрос можно ли уменьшить сложность какого-нибудь куска кода до n log n против n^2.

Структуры данных


Выбор структуры данных зависит от конкретной задачи: от вида данных и алгоритма их обработки. Разнообразные структуры данных (в .NET или Java или Elixir) создавались под определенные типы алгоритмов.

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

Здесь мы будем использовать только массивы чисел (прямо как на собеседовании). Примеры на JavaScript.
Читать дальше →
Total votes 39: ↑30 and ↓9 +21
Views 120K
Comments 30

Сглупил ли Ричард Хендрикс, или Линейный поиск против бинарного

JUG Ru Group corporate blog High performance *.NET *Algorithms *


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


Желая унизить главного героя Ричарда Хендрикса, его бывший начальник показывает на совещании фрагмент его старого кода. Там к уже отсортированным данным применён линейный поиск — так что задача будет выполнена, но выглядит это очень неэффективно.


Сам Ричард не спорит с тем, что код плохой. Однако среди зрителей сериала у его решения внезапно нашлись защитники, и теперь мне интересно, что об их позиции думает Хабр.

Читать дальше →
Total votes 66: ↑56 and ↓10 +46
Views 25K
Comments 54

Бинарный поиск в микроконтроллере

СпецПромДизайн corporate blog Algorithms *Programming microcontrollers *Manufacture and development of electronics *

Алгоритм бинарного поиска или поиска делением пополам известен давно. В данной статье будет рассмотрен пример его «железячной» реализации на 8-битном микроконтроллере и особенностях, которые возникают при этом.

Читать далее
Total votes 8: ↑6 and ↓2 +4
Views 4.3K
Comments 18