Всем привет.

Время от времени я, как и большинство программистов, изучаю какие-то новые структуры и алгоритмы.

В этот раз мне на глаза попались статьи по cache oblivious алгоритмам. Это такие алгоритмы, которые изначально более оптимизированы для работы с подсистемой кэширования современных процессоров.

Одним из представителей этой группы является Unrolled linked list.

Что же это такое?

Существует типичная проблема в большом классе задач, которая возникает при обработке потока сообщений:

— нельзя пропихнуть большого слона через маленькую трубу, или другими словами, обработка сообщений не успевает «проглотить» все сообщения.

При этом существуют некоторые ограничения на поток данных:

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

На диаграмме приведён пример разрешения проблемы: нагребатор(tm), работающий на нитке T₁, в то время как разгребатор(tm) работает на нитке T₂

• за время обработки события типа A успевают прийти новые события как типа B, так и A
• после обработки события типа B необходимо обработать наиболее актуальное событие типа A

Т.о. стоит задача о выполнении задач по ключу, так, что выполняется только самая актуальная из всех задач по данному ключу.

На суд публике представляется созданный нами ThrottlingExecutor.

Замечание терминологии: stream есть поток данных, тогда как thread есть нитка или нить выполнения. И не стоит путать потоки с нитками.

Замечание 1: проблема осложняется ещё тем, что может быть несколько нагребаторов(tm), при этом каждый нагребатор(tm) может порождать только события одного типа; с другой стороны есть потребность в нескольких (конечно же, для простоты можно выбрать N=1) разгребаторах(tm).

Замечание 2: мало того, что данный код должен работать в многопоточной (конкурентной) среде — т.е то самое множество нагребаторов(tm) — разгребаторов(tm), код должен работать с максимальной производительностью и низкими latency. Резонно к этим всем качествам добавить ещё и свойство garbage less.

И почти в каждом проекте так или иначе возникает эта задача, и каждый её решает по разному, но все они либо не эффективны, либо медленны, либо и то, и другое вместе взятое.

Привет, Хабр!

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

Признаюсь. Я не очень любил курс структур данных и алгоритмов в университете. Все эти стеки, очереди, кучи, деревья, графы (будь они не ладны) и прочие “остроумные” названия непонятных и сложных структур данных ни как не хотели закрепляться в моей голове. Как истинный “прагматик”, я уже на втором — третьем курсе свято верил в стандартную библиотеку классов и молился на дарованные нам (простым смертным) коллекции и контейнеры, бережно реализованные отцами и благородными донами CS. Казалось, все что можно было придумать — уже давно придумано и реализовано.

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

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

В этой статье мы расскажем о невероятно гибкой системе управления сайтом – Boolive, сочетающей в себе мощь и простоту.

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

1. При разработке даже в продвинутых IDE (системах разработки) и при выполнении приложения отсутствует какой-либо контроль за структурой и типами данных в массиве.
2. IDE ничем не может помочь при разработке, так что названия возможных ключей массивов придется вспоминать-печатать или где-то искать-копировать-вставлять, что кроме неудобства и снижения производительности повышает вероятность опечатки.
3. Сложно контролировать где-как используются отдельные элементы этого массива и соответственно сложно рефакторить, даже несмотря на мощь современных IDE.

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

Привет сообществу!

Я Юрий Кашницкий, раньше делал здесь обзор некоторых MOOC по компьютерным наукам и искал «выбросы» среди моделей Playboy.

Сейчас я преподаю Python и машинное обучение на факультете компьютерных наук НИУ ВШЭ и в онлайн-курсе сообщества по анализу данных MLClass, а также машинное обучение и анализ больших данных в школе данных одного из российских телеком-операторов.

Почему бы воскресным вечером не поделиться с сообществом материалами по Python и обзором репозиториев по машинному обучению… В первой части будет описание репозитория GitHub с тетрадками IPython по программированию на языке Python. Во второй — пример материала курса «Машинное обучение с помощью Python». В третьей части покажу один из трюков, применяемый участниками соревнований Kaggle, конкретно, Станиславом Семеновым (4 место в текущем мировом рейтинге Kaggle). Наконец, сделаю обзор попавшихся мне классных репозиториев GitHub по программированию, анализу данных и машинному обучению на Python.

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

Я хотел бы сказать большое спасибо А. Дайняк за прочитанный курс и добавить, что это лишь изложение кусочка курса, и на большее я не претендую.

Superjob приглашает на Data Science Meetup. Встречаемся 2 марта в нашем офисе на Малой Дмитровке.



Темы и спикеры:

• «Применение алгоритмов поиска нечетких дубликатов в поиске вакансий»

Дмитрий Кожокарь, старший разработчик Superjob, расскажет об опыте создания эффективного алгоритма по поиску нечетких дубликатов среди большого количества полуструктурированных текстовых записей. В докладе рассматривается использование функции из семейства locality-sensitive hashing с дополнительными оптимизациями для выявления схожих вакансий и последующего объединения их в кластеры.

Специально для тех, кто не успел зарегистрироваться на Superjob Data Science Meetup, мы организуем прямую трансляцию события на Youtube или Facebook.

Начало в 19:00 по московскому времени.

Видео, доклады и краткий отчет для тех, кто не приехал и не успел посмотреть прямую трансляцию.

В офисе Superjob состоялся Data Science Meetup. Послушать доклады пришли около ста аналитиков и разработчиков, включая специалистов из Renault, Тинькофф банк, Эльдорадо, SAP, Вымпелком, Delloite, ВТБ и тд. Около 500 человек смотрели прямую трансляцию.

Привет Всем! Я недавно запустил на GitHub проект JavaScript Algorithms and Data Structures, который содержит примеры классических алгоритмов и структур данных написанных на JavaScript с объяснениями, примерами и ссылками для дальнейшего изучения (в частности на соответствующие YouTube видео).

Основная задача проекта — помочь программистам в изучении и применении алгоритмов и сделать это на JavaScript-е.

Введение

Прошло долгих четыре месяца с момента публикации статьи о моей попытке низкоуровневой реализации префиксного дерева. Несмотря на все мои старания потолок на который оказалась способна моя прошлая реализация префиксного дерева был ~80 тыс. слов в секунду. Я потратил тогда кучу сил и времени, но полученный результат сгодился бы только как лабораторная работа по информатике.

Многие тогда мне говорили: «Не изобретай велосипед, который уже изобрели! Используй готовое решение». Сложность в том, что мне не удавалось использовать что-то, что я не понимаю хотя бы в общих очертаниях.

Префиксное дерево я кажется понял, и вот чего удалось добиться.

Краткое содержание первой части

В первой части я сделал болванку расширения, заставил ее правильно работать в IDE Clion, написал функцию-аналог my_array_fill() и проверил ее работоспособность в php.

Что теперь?

Теперь я запилю код библиотеки libtrie в наше расширение.

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

Всем привет! Недавно открыл для себя язык Rust. О своих первых впечатлениях поделился в предыдущей статье. Теперь решил копнуть немного глубже, для этого необходимо что-то посерьёзнее списка. Выбор мой пал на дерево Меркла. В этой статье я хочу:

• рассказать про эту структуру данных
• посмотреть на то, что уже есть в Rust
• предложить свою реализацию
• сравнить производительность

Hello, dear Habr users! This article is about Web 3.0 — the decentralized Internet. Web 3.0 introduces the concept of decentralization as the foundation of the modern Internet. Many computer systems and networks require security and decentralization features to meet their needs. A distributed registry using blockchain technology provides efficient solutions for decentralization.

Здравствуйте, уважаемые хабрапользователи! В этой статье речь идет о web 3.0 — интернете с децентрализацией. Web 3.0 вводит понятие децентрализации как основы для современного интернета, многие компьютерные системы и сети нуждаются в свойствах защищенности и децентрализации для своих нужд. Решение для децентрализации называется технологиями распределенного реестра или блокчейн.

Добрый день, уважаемые читатели!

Данная статья посвящена Plasma Cash Chain и проливает свет на следующие темы:

• трилемма масштабируемости и способы ее решения;
• структуры данных чайлд чейна и их отображение в рутчейне;
• реализация ввода в рутчейн;
• реализация вывода из рутчейна.

Компания Opporty использовала язык программирования Javascript для реализации чайлдчейна, а также Solidity для рутчейна. Примеры кода приводятся на этих языках.

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

Детали под катом.

Предисловие

Кто из iOS разработчиков не мечтал о работе в престижном месте вроде Yandex или Avito. К сожалению, про мечты на собеседованиях спрашивает только hr, а вот интервьюеры из числа разработчиков задают вопросы немного другого характера. Чем отличается reference type от value type или bounds от frame? Вопросы, который каждый из нас слышал не раз на собеседованиях. Если ваше интервью начинается с вопроса про отличия значимого и ссылочного типов или в духе “расскажите ка нам про SOLID”, то вы явно на пути трудоустройства в ООО “Так себе перспективы“.