Рубрика «Алгоритмы»

На Хабре было несколько статей по решению японских кроссвордов, где авторы придумывали различные способы как такие кроссворды решать. В комментарии к статье Решение цветных японских кроссвордов со скоростью света я высказал мысль, что, поскольку, решение японских кроссвордов является NP-полной задачей, то и решать их надо с использованием соответствующего инструмента, а именно SAT солвером. Поскольку моя идея была встречена весьма скептически, я решил попробовать ее реализовать и сравнить результаты с другими подходами. Что из этого получилось можно узнать под катом.
Читать полностью »

Здравствуй!

Недавно я решил протестировать производительность Javascript на примере создания несложного WEB-приложения, умеющего строить сводные таблицы, вычислять агрегаты и подтягивать атрибуты из справочников, используя слабо-структурированные данные в качестве источника. Повторить весь функционал Excel или взрослых OLAP-систем не предполагалось, но хотелось протестировать производительность Javascript вообще и IndexedDB в частности на различных десктопных и мобильных браузерах. Забегая вперед, скажу, что выполнив первый этап работы — построение сводной таблицы однопроходным алготитмом по хранилищу фактов (индексирование часто-используемых разрезов и кэширование вычисленных агрегатов отложено на будущее) — я был разочарован производительностью чтения из IndexedDB, удивлен тем, что мобильные браузеры практически не отстают от десктопных, и озадачен эпическим провалом моего любимого Firefox в одном из тестов. Всего было 2 теста с различными вариациями:

  • формирование сводной таблицы, где основа алгоритма — единственный цикл по курсору IndexedDB, работа с объектами Object, Array, Set, Map (извлечение по ключу, вставка, итерация), конкатенация строк и простая арифметика;
  • расшифровка (drillthrough) строки сводной таблицы с выводом результата в DOM, где основа алгоритма — многократное (в цикле) извлечение одной записи из IndexedDB по ключу, и последующий вывод результатов в таблицу html группами по 100 строк методом insertAdjacentHTML('beforeEnd', html)).

Тестирование проводилось на файле JSON, содержащем 20 тыс. фактов, из которых 9 записей представляли собой справочник продуктов, остальные изображали операции купли/продажи. Табличка с результатами тестирования на нетбуке и телефоне (время в секундах), а также подробности реализации и выводы — под катом.
Читать полностью »

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

Если первый опыт окажется успешным, то в будущем вас могут ожидать и другие 15-минутные "зарисовки" по тематике компиляторов.

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

Сбалансированное слияние сверху-вниз и снизу-вверх - 1


В прошлой статье мы ознакомились с реликтовыми сортировками слияния (вызывающих прежде всего исторический интерес). А что в тренде сегодня?Читать полностью »

AI в игре Hase und Igel: minimax на троих - 1


После настоящего бума настольных игр конца 00-х в семье осталась несколько коробок с играми. Одна из них — игра “Заяц и Ёж” в оригинальной немецкой версии. Игра для нескольких игроков, в которой элемент случайности сведен к минимуму, а побеждает трезвый расчет и способность играющего “заглядывать” вперед на несколько шагов.

Мои частые поражения в игре привели меня к мысли написать компьютерный “интеллект” для выбора наилучшего хода. Интеллект, в идеале, способный сразиться с гроссмейстером Зайца и Ежа (а что, чай, не шахматы, игра попроще будет). Далее в статье идет описание процесса разработки, логики AI и ссылка на исходники.
Читать полностью »

Разработка ИИ на примере игры Dicey Dungeons - 1

Примерно в течение месяца я решал одну из самых сложных технических проблем моей новой игры Dicey Dungeons — совершенствол ИИ для финального релиза игры. Это была довольно интересная работа, и многое в ней стало для меня новым, поэтому я решил немного о ней написать.

Для начала объясню: я не специалист в теории вычислительных машин, а просто один из тех, кто достаточно изучил программирование, чтобы создавать видеоигры, после чего закончил обучение, ухватив только то, что мне было необходимо. Обычно я могу решать свои задачи самостоятельно, но настоящий программист скорее всего не одобрил бы мои решения.

Я постарался написать статью на достаточно высоком уровне абстракции, чтобы основные идеи были понятны даже непрограммистам. Но я не эксперт в таких вещах, поэтому мои объяснения теории могут быть ошибочными. Напишите мне об этом в комментариях к оригиналу, я с радостью внесу изменения!

Ну, давайте начнём с объяснения задачи!
Читать полностью »

Chain replication: построение эффективного KV-хранилища (часть 2-2) - 1

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

Deep Mind научила свой ИИ предсказывать структуру белков - 1
«Предком» AlphaFold является алгоритм AlphaGo, который стал играть в го лучше любого человека. Источник: DeepMind

Разработчики из Deep Mind за последние пару лет стали известны благодаря многим своим проектам. В частности, они научили искусственный интеллект (слабую его форму) играть в Go, классические Atari-тайтлы и некоторые другие игры, сложные для «понимания» машиной. Сейчас наступил черед более серьезных занятий — Deep Mind постепенно меняет специализацию ИИ на молекулярную биологию.

Если точнее, то искусственный интеллект учат прогнозировать структуру белка на основе фрагмента последовательности аминокислот — этих кирпичиков белковой жизни. Проект, о котором идет речь, получил название AlphaFold. ИИ научили работать быстрее и точнее, чем люди благодаря обучению по базе последовательностей, собранных генетиками за несколько лет.
Читать полностью »

Сортировка «Ханойская башня» - 1

Ханойские башни
Про знаменитую игру Эдуарда Люка́ на Хабре не писа́л только ленивый. Кажется, все покровы сорваны и что-то ещё по поводу алгоритма добавить уже невозможно. Но нет, у данной темы есть ещё скрытые ресурсы. Сегодня, в частности, мы переделаем алгоритм решения этой головоломки в полноценную сортировку. (Зачем? Just for fun. В пятницу можно.) Читать полностью »

Резервуарная выборка (eng. «reservoir sampling») — это простой и эффективный алгоритм случайной выборки некоторого количества элементов из имеющегося вектора большого и/или неизвестного заранее размера. Я не нашел об этом алгоритме ни одной статьи на Хабре и поэтому решил написать её сам.

Итак, о чём же идёт речь. Выбрать один случайный элемент из вектора — это элементарная задача:

auto result = vect[rand() % vect.size()]; // С++

Задача «вернуть K случайных элементов из вектора размером N» уже хитрее. Здесь уже можно ошибиться — например, взять K первых элементов (это нарушит требование случайности) или взять каждый из элементов с вероятностью K/N (это нарушит требование взять ровно K элементов). Кроме того, можно реализовать и формально корректное, но крайне неэффективное решение «перемешать случайно все элементы и взять K первых». И всё становится ещё интереснее, если добавить условие того, что N — число очень большое (нам не хватит памяти сохранить все N элементов) и/или не известно заранее. Для примера представим себе, что у нас есть какой-то внешний сервис, присылающий нам элементы по одному. Мы не знаем сколько их придёт всего и не можем сохранить их все, но хотим в любой момент времени иметь набор из ровно K случайно выбранных элементов из уже полученных.

Алгоритм резервуарной выборки позволяет решить эту задачу за O(N) шагов и O(K) памяти. При этом не требуется знать N заранее, а условие случайности выборки ровно K элементов будет чётко соблюдено.
Читать полностью »