image
зрештою, я повинен був до цього прийти. Коли я опублікував статтю «Я написав швидку хеш-таблицю», а потім ще одну — «Я написав ще більш швидку хеш-таблицю». Тепер я завершив роботу над самою швидкою хеш-таблицею. І під цим я розумію, що реалізував самий швидкий пошук порівняно з усіма хеш-таблиць, які мені вдалося знайти. При цьому операції вставки та видалення також працюють дуже швидко (хоча і не швидше конкурентів).
Я використовував хешування за алгоритмом Robin Hood з обмеженням максимальної кількості наборів. Якщо елемент повинен бути на відстані більше Х позицій від своєї ідеальної позиції, то збільшуємо таблицю і сподіваємося, що в цьому випадку кожен елемент зможе бути ближче до своєї бажаної позиції. Схоже, такий підхід дійсно добре працює. Величина Х може бути відносно невелика, що дозволяє реалізувати деякі оптимізації внутрішнього циклу пошуку по хеш-таблиці.
Якщо ви хочете тільки спробувати її в роботі, то можете завантажити звідси. Або прокрутіть вниз до розділу «Вихідний код і використання». Хочете подробиць — читайте далі.
Читати далі →

Лекції Технопарку. 1 семестр. Алгоритми і структури даних

Черговий пост в рамках нашого циклу лекцій Технопарку. Цього разу ми пропонуємо вашій увазі курс, присвячений алгоритмам і структурам даних. Автор курсу — Степан Мацкевич, співробітник компанії ABBYY.

Лекція 1. Основи

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


Читати далі →