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

До 2020 года в Школу анализа данных могли попасть только те, кто очень глубоко и творчески владеет высшей математикой. Но этим качеством обладают не все способные люди, интересующиеся data science и инфраструктурой больших данных. Нередко разработчики, аналитики и молодые исследователи не помнят математику 1-2 курса вуза настолько хорошо, чтобы преодолеть наши вступительные экзамены. В этом году мы хотим дать таким людям возможность всё-таки попасть в ШАД. Мы организовали для них специальный трек поступления, о котором я расскажу ниже.

Но мало в ШАД попасть. Матанализ, линейная алгебра и теория вероятностей будут нужны дальше: без них не удастся разобраться с байесовскими методами, корректно оценить асимптотику сложности быстрой сортировки, написать хитрый метод многомерной оптимизации. Поэтому мы создаём принципиально новый адаптационный курс по математике. Все, кто поступят в ШАД по новым правилам, должны будут пройти этот курс.

Берём не только крутых математиков. Новый способ поступить в ШАД с опытом в IT - 1
Читать полностью »

1. Введение

Влияние подпрограмм (англ. subroutine) на программирование без преувеличения огромно. Введенные на заре программирования они не теряют своей актуальности и поныне. Без них практическое программирование представить просто невозможно. Хотя с формальной точки зрения они не так уж и нужны, т.к. чистую теорию интересуют больше свойства алгоритма, чем его размеры.

В теории автоматов понятие вложенных автоматов, на базе которых строилась бы практика автоматных подпрограмм (АПП), обсуждается редко. Подобная (вложенная) иерархическая организация автоматов, если и рассматривается, то весьма поверхностно. Одной из причин подобного отношения может служить сложность реализации вложенной иерархии на аппаратном уровне [1, 2].

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

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

Привет, меня зовут Вася Рубцов, я занимаюсь разработкой рекомендательных систем в Авито.

Основная цель площадки для размещения объявлений — помочь продавцам найти покупателей, а покупателям — товары, которые они ищут. В отличие от интернет-магазинов факт продажи происходит за пределами нашей платформы, и мы не можем это отследить. Поэтому ключевой метрикой у нас является «контакт» — это событие нажатия кнопки «показать телефон» на карточке товара, либо начало диалога в мессенджере с продавцом. Из этой метрики мы получаем «байеров» — количество уникальных пользователей в день, которые сделали по крайней мере один контакт.

Два основных продукта, которым занимается отдел рекомендаций в Авито, — это рекомендации для пользователя на главной странице или user2item и блок похожих объявлений на карточке товара или item2item. Треть всех просмотров объявлений и четверть всех контактов происходит с рекомендаций, поэтому рекомендательные движки играют важную роль в Авито.

В статье я расскажу, как мы улучшили наши item2item рекомендации за счёт item2vec и как это повлияло на user2item рекомендации.

Как мы используем item2vec для рекомендаций похожих товаров - 1

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

Архивы памяти: как мозг кодирует и воспроизводит воспоминания - 1

С одной стороны мозг человека достаточно понятен, с другой — полон загадок и вопросов, на которые пока нет ответов. И тут все логично, учитывая, что данная система чрезвычайно сложна как с точки зрения архитектуры, так и с точки зрения протекающих процессов и связи между ними. Если по классике сравнивать мозг с компьютером, то помимо обработки информации, он выполняет и ее хранение. Любое воспоминание изымается из архивов памяти под влиянием какого-то стимула: знакомый аромат, мелодия, слова и т.д. Однако остается вопрос — где этот архив и что способствует его открытию? Ученые из NINDS (Национальный институт неврологических расстройств и инсульта) изучили мозг пациентов, больных устойчивой к препаратам эпилепсией, чтобы выявить и попытаться объяснить механизмы извлечения воспоминаний. Так как же мы вспоминаем, что происходит в мозге в этот момент и почему исследование проводилось с участием больных эпилепсией? Об этом мы узнаем из доклада ученых. Поехали.Читать полностью »

imageФото: newsroom.intel.com

Intel и исследователи из Корнеллского университета продемонстрировали новую способность нейроморфного чипа Intel Loihi. Теперь он способен распознавать запахи десяти опасных химических веществ даже при сильных помехах, имитируя работу обонятельной системы человека. Читать полностью »

Простая хэш-таблица для GPU - 1

Я выложил на Github новый проект A Simple GPU Hash Table.

Это простая хэш-таблица для GPU, способная обрабатывать в секунду сотни миллионов вставок. На моём ноутбуке с NVIDIA GTX 1060 код вставляет 64 миллиона случайно сгенерированных пар ключ-значение примерно за 210 мс и удаляет 32 миллиона пар примерно за 64 мс.

То есть скорость на ноутбуке составляет примерно 300 млн вставок/сек и 500 млн удалений/сек.

Таблица написана на CUDA, хотя ту же методику можно применить к HLSL или GLSL. У реализации есть несколько ограничений, обеспечивающих высокую производительность на видеокарте:

  • Обрабатываются только 32-битные ключи и такие же значения.
  • Хэш-таблица имеет фиксированный размер.
  • И этот размер должен быть равен двум в степени.

Для ключей и значений нужно зарезервировать простой разграничивающий маркер (в приведённом коде это 0xffffffff).
Читать полностью »

Доброго времени суток.

В свободное время провёл небольшое исследование.

В теории графов известен жадный алгоритм поиска кликового числа. Далеко не всегда он даёт верный результат. Под катом проводится анализ результатов работы жадного алгоритма при его комбинации с частичным перебором множеств вершин на графах из «DIMACS benchmark set».

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

Пишем поиск подстроки лучше, чем в учебниках - 1

Жизнь инженера полна сюрпризов: особенно, когда приходится иметь дело с производительностью. Например, что произойдет, если попытаться запустить этот кусок Java-кода? Выглядит довольно невинно:

// Для использования String.repeat нужен JDK 11 и выше:
final var needle = "A".repeat(500000) + "B";
final var haystack = "A".repeat(1000000) + "B";
System.out.println(haystack.indexOf(needle));

Мы ждем, ждем, ждем… По крайней мере, на моем ноутбуке 2015 года c OpenJDK 13 поиск иголки в стоге сена занимает около минуты. Наша старая добрая JVM прошла сквозь десятилетия перформанс-тюнинга, в ней эффективно реализованы интринсики для String.indexOf и так далее. Что же могло пойти не так?

Это начало серии из нескольких статей, любезно предоставленных их автором, Linas Medžiūnas, и изначально опубликованых в блоге WiX Engineering.

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

Theory is when you know everything but nothing works.
Practice is when everything works but no one knows why.
In distributed systems, theory and practice are combined:
nothing works and no one knows why.

Чтобы доказать, что шутка в эпиграфе — абсолютная глупость, мы уже в третий раз проводим SPTDC (school on practice and theory of distributed computing). Об истории школы, её сооснователях Петре Кузнецове и Виталии Аксёнове, а также об участии JUG Ru Group в организации SPTDC мы уже рассказывали на Хабре. Поэтому сегодня — о школе в 2020 году, о лекциях и лекторах, а также об отличиях школы от конференции.

Школа SPTDC пройдёт с 6 по 9 июля 2020 года в Москве.

Все лекции будут на английском языке. Основные темы лекций: persistent concurrent computing, cryptographic tools for distributed systems, formal methods for verifying consensus protocols, consistency in large-scale systems, distributed machine learning.

SPTDC 2020 — третья школа о практике и теории распределённых вычислений - 1
Сразу догадались, в каком воинском звании персонажи на картинке? Я вас обожаю.
Читать полностью »

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

Получилось примерно так:

(Почти) Автогенерация цветов - 1

Под катом будет еще, берегите трафик.
Читать полностью »


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