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

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

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

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

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

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

Это одно из лучших выступлений, которое я встречал. Хоть про эту презентацию уже писали на Хабре и переводили 6 лет назад, я решил её красиво оформить и ещё раз обратить на неё внимание. Она того стоит.

image

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

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

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

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

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

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

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

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

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

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

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

Здесь мы будем использовать только массивы чисел (прямо как на собеседовании). Примеры на JavaScript.
Читать полностью »

в 14:30, , рубрики: ajax, ASCII, C#, c++, clang, computer, computer science, cs50, cs50 на русском, CS50 на русском языке, css, david, David J. Malan, dom, gdb, harvard, html, http, IP, java, javascript, malan, mvc, onlineuniver, php, return, rsa, science, Scratch, sql, tcp, Алгоритмы, аргументы командной строки, асимптотическая нотация, библиотеки, Бинарная нотация, бинарный поиск, Булевые выражения, быстрая сортировка, видеокурс, Гарвард, глобальные переменные, деревья, Дополнительные видео, Компиляторы, компьютерные науки, линейный поиск, массивы, методы, область видимости, обучение, основы программирования, очереди, переменные, приведение типа, приоритетность, Программирование, программист, рекурсивные деревья, рекурсия, связные списки, символьные строки, сортировка вставками, сортировка выбором, сортировка пузырьком, сортировка слиянием, стили, структуры, технологии, указатели, условия, хеш-таблицы, циклы, шифр, языки программирования

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

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

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

image

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

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

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

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

Добавлю в копилку статей Хабра о Бинарном поиске еще одну.
Речь пойдет о кастомной реализации, может быть полезно всем, кто часто использует в работе ВПР для сравнения больших списков или для поиска данных в больших массивах.

Предыстория

Все началось с того, что я открыл для себя т.н. Double-TRUE VLOOKUP trick (трюк с двойным использованием ВПР и ИСТИНА в 4-м параметре). Развернутое описание алгоритма можно найти в статье Charles Williams «Why 2 VLOOKUPS are better than 1 VLOOKUP» (в конце статьи).

Поняв принцип работы и открыв для себя, что этот подход может быть в тысячи раз быстрее обычного линейного поиска (ВПР с 4-м параметром ЛОЖЬ), я начал продумывать варианты раскрыть его возможности. В ходе реализации получилось несколько годных инструментов для контекстной рекламы, один из которых я еще продолжаю улучшать, и уже посвятил проекту пару статей на Хабре. Чтиво рекомендуется SEO-специалистам и специалистам по контекстной рекламе (сразу оговорюсь, по ссылкам в статьях уже устаревшие версии, последняя версия условно 6.0, ссылки на скачивание всех версий, включая самую свежую, будут в конце этой статьи):
Анализ больших семантических ядер, или «Робот-распознаватель»
Лемматизация в Excel, или «Робот-распознаватель 3.0

Так вот, несмотря на невероятную скорость работы этих файлов (невероятную для Excel), их создание потребовало использования таких же невероятно длинных мегаформул как одной из составляющих работы макросов (в последней из вышеуказанных статей приведен пример — формула на 3215 символов). И всему виной сложный синтаксис функции.
Если набить руку с его использованием, он перестает казаться сложным, но неискушенным пользователям, для которых предназначен такой подход, вряд ли захочется разбираться в нем.

Синтаксис выглядит так: Если(ВПР(искомое; массив;1; ИСТИНА)<искомое;""; ВПР(искомое; массив;n; ИСТИНА))
где n — порядковый номер столбца, из которого мы хотим вернуть значение напротив искомого ключа.
Вместо «ИСТИНА» в 4-м параметре можно использовать «1» для номинального сокращения длины формул, это не меняет их сути.
Если озвучить ход работы формулы, будет нижеследующее:
«Если бинарный поиск ключа по первому столбцу массива возвращает значение, меньшее, чем сам ключ, возвращаем пустую строку. Иначе — возвращаем результат бинарного поиска ключа со смещением n»
Подход используется для того, чтобы не возвращать никаких значений, если искомый ключ в массиве отсутствует, т.к. зачастую, если искомое не найдено — нам не нужно меньшее значение. Так сказать, все или ничего. Вкратце, в этом и есть суть «трюка».

Напомню, на карту поставлен прирост скорости, исчисляющийся трех-четырехзначными числами. Если подходить чисто математически — на массиве в 2^20 строк обычный бинарный поиск будет делать ~10 вычислений, формула выше — около 20, в то время, как линейный поиск — ~500.000, т.е. прирост формулы выше — в 25.000 раз. Если голые цифры не впечатляют, более красноречивое эквивалентное сравнение — 1 секунда против ~7 часов.
На практике прирост не столь существенный (в конце статьи ссылка на статью, где сравнивались разные способы). Это во многом связано с затратами процессорного времени на дополнительные процедуры, которые выполняет программа (например, запись значений в ячейки). НО прирост по-прежнему критически значимый (~4000 раз).

Но одновременно с этим мы имеем сложный, совершенно неюзабельный синтаксис. Не всем смертным дался ВПР, что говорить о комбинациях 2х ВПР с ЕСЛИ.

Вопрос со сложным синтаксисом я решил с помощью VBA — написал UDF (user-defined function, пользовательская функция), которая прячет под капот наши условные конструкции, оставляя нам привычный синтаксис всем известного ВПР.

Код UDF:
Читать полностью »

Вступление

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

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

Да, всё так и можно завершать статью, всем спасибо. было бы плюнуть на значительный оверхеад памяти на вспомогательные данные в виде ссылок на левые-правые поддеревья и флаг для балансировки (разный в зависимости от используемой техники — красно-чёрные, АВЛ и т.п. деревья). Ещё один, не то чтобы минус — это постоянная модификация дерева при вставке для балансировки (тут особенно важна сложность и запутанность методов для новичков). На этом минусы заканчиваются и сложно себе представить что-то лучше и более универсальное (хеш-таблицы, ИМХО, ещё круче, но ОХ УЖ ЭТИ КОЛЛИЗИИ).
Читать полностью »

Вопросы про индексы, которые вам не надо будет задавать - 1

После ответов на 14 вопросов об индексах, которые вы стеснялись задать, у меня возникло гораздо больше комментариев, уточнений и исправлений. Скомпилировать из всего этого статью выглядело затеей с минимумом пользы. И это заставило меня призадумался, а почему вообще мы должны «стесняться задавать» подобные вопросы? Стыдно не знать? А есть ли способ разобраться, не вгоняя себя в краску? Есть. Причем он избавит от многочисленных неточностей, которыми изобилуют многие «ответы». Вы будете чувствовать буквально каждый байт вашей базы кончиками своих пальцев.

Для этого, я предлагаю «поднять капот» у SQL Server и окунуться в сладостный мир шестнадцатеричных дампов. Может статься, что внутри все гораздо проще, чем вам казалось.

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

Рассмотрим простую задачу: есть некоторый достаточно большой неизменный набор чисел, к нему осуществляется множество запросов на наличие некоторого числа в этом наборе, необходимо максимально быстро эти запросы обрабатывать. Одно из классических решений заключается в формировании отсортированного массива и обработке запросов через бинарный поиск. Но можно ли добиться более высокой производительности, чем в классической реализации? В этой статье мне хотелось бы рассказать про Cache-Conscious Binary Search. В данном алгоритме предлагается переупорядочить элементы массива таким образом, чтобы использование кэша процессора происходило максимально эффективно.Читать полностью »

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

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

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


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