elizarov


Блог Романа Елизарова


Entries by tag: hash

Бизнес-логика
elizarov

Зачем оптимизировать хеш-таблицы для кэширования объектов в бизнес приложениях? Разве там на них уходит процессорное время? Это один из вопросов, который мне задали после моего выступления с докладом про быстрые структуры данных. А на что уходит время в бизнес приложениях? Ведь во многих из них нет сложных задач, где применив эффективный алгоритм с меньшей асимптотической сложностью можно было бы легко добиться ускорения в разы. Бизнес-логика редко превосходит по сложности цикл, в котором происходит суммирование чисел. Цикл, который я использовал для сравнения производительности различных хеш-таблиц является вполне репрезентативным примером бизнес-логики типичного приложения.

Разберемся на что там уходит время с числамиCollapse )


Слайды с доклада про быстрые структуры данных
elizarov

По просьбе организаторов Application Developer Days выкладываю слайды своего доклада про быстрые структуры данных на SlideShare. Смотреть cлайды по этой ссылке.

Под катом видео и планы на будущее...Collapse )


Теория на практике или хеш-таблицы часть 4
elizarov

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

Подробности с выкладками под катомCollapse )


Распределение нагрузки имеет значение или быстрый хеш часть 3
elizarov

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

Подробности с цифрами под катом...Collapse )


Пишем самый быстрый хеш для кэширования данных: Часть 2
elizarov

Сделал доклад. Получилось неожиданно больше мыслей, чем можно донести за отведенные 45 минут. Не буду пересказывать (организаторы выложат слайды и видео). Доклад был в основном посвящен именно написанию быстрого кода вообще, чем конкретно очень быстрым хеш-таблицам, которые были использованы в качестве примера и по которым, к сожалению, пришлось пробегаться уже скомкано в конце. Однако, я открою интригу из своей предыдущей заметки.

Read more...Collapse )


Пишем самый быстрый хеш для кэширования данных: Часть 1
elizarov

12 мая 2012 года я выступаю с докладом на конференции Application Developer Days. Мой доклад будет посвящен написанию высокопроизводительных структур данных и будет служить продолжением моей серии статей про производительность. Я покажу весь путь дизайна на примере конкретной задачи. Это задача кэширования данных загруженных из БД, которая очень часто возникает в бизнес приложениях. Безусловно, есть множество готовых каркасов, которые решают эту задачу совершенно прозрачно для программиста. Но что делать, если вы создаете высоконагруженное приложение, оперирующее миллионами объектов и вынужденное постоянно к мим обращаться для выполнения тех или иных стоящих перед вами задач? Например, высокопроизводительные приложения для торговли на финансовых рынках, по типу тех, которые мы создаем в Devexperts.

Продолжение под катом с конкретным кодом и результатами тестированияCollapse )


?

Log in

No account? Create an account