А contains(k) у PerfectHashTable фактически единственный метод
если тебе нужен только contains - то посмотри в сторону Фильтра Блума. Это - probabalistic проверка но она
надежно работает для закрытие большего числа запросов.
Вобщем я выдохся. Я думаю что твой тюнинг он - очень специфичен. И его нельзя решать только теоретически.
У тебя должно быть как минмум 3 макета софта. Под open-adressing и под separate-chaining и под твой идеальный квадрат. Я напомню что самые лучшие реализации алгоритмов - обладают сильной когерентностью по памяти.
Это связано с кешами в железе. Поэтому твои теоретические обоснования могут сильно ошибаться в практике.
Вот. И результатом этих трех макетов должны быть 3 бенчмарка где ты показываешь практически
время инициализации структуры и среднее время доступа.
floppa322, я все таки хочу понять мотивацию. Тебе нужна вспомогательная стуктура для алгоритма. Если ты уже дошел до такой ситуации что тебе нужна мемоизация расчетов (max(id)) то будь добр - потрать время на подготовку.
Основной алгоритм отработает быстро. Если хочешь идеальное хешировние - то по ссылке которую ты приводишь все равно нет гарантий что идеальная генерация закончится в 1 итерацию. Тоесть полюбому построение таблицы у тебя - слабое место. Ищи компромиссы.
floppa322, дружище если ты оптимизируешь время загрузки данных в таблицу - то ты сразу проиграл. Бери метод списков и все будет работать чудесно.
Хочешь открытая адресация с майнингом - попробуй не удваивать а умножать на 10% размер массива. Там именно массив а не бакеты. Я думаю что через 2-3 итерации все сойдется.
By the way. Я понимаю что ты - теоретик. Но мне всегда интересна практическая сторона вопроса. Какие ключи
ты хочешь хранить? Строки? Числа? Сколько из будет? Какой лимит времени ты хотел-бы потратить на
инициализацию системы? Вот меня как дата-инженера это в первую очередь беспокоит. А вовсе не нелинейность.
Данная технология применяется в различных словарях и базах данных, в алгоритмах со статической (известной заранее) информацией.
я вот как себе это понимаю. Есть справочники которые редко меняются. Страны. Валюты. Языки. Всякие там биржевые тикеры. У тебя всегда есть достаточно времени чтобы расчитать эту таблицу почти идеально.
Вариант с 2 таблицами я-бы сразу выкинул. Неэффективное использование памяти. И выигрыш - ничтожный.
Хеш таблицы (ХТ) бывают двух видов. В основном. Это метод списков и открытая адресация.
В промышленности и в бизнесе (насколько я видел) в основном используется первый тип ХТ. У них
нет проблемы которую ты нарисовал. Никакие двухуровневые таблицы им не нужны. И этот тип реализован в С++/Java/C# e.t.c. библиотеках поддержки коллекций. В некоторых современных вариантах списки могут
превращаться в красно-черные деревья. Поэтому может быть гибрид хеш+R&B.
Второй тип подходит для редких кейсов типа хранения примитивов достаточно компактно. Но надо тонко
подбирать грань keys/capacity чтоб не попасть в ситуацию 3 и 4 и 5 обращения к памяти. Там будет резкий
рост времени отклика.
Твое идеальное хеширование в принципе сводится ко 2 типу. Надо только подбирать keys/capacity до тех пор пока нет коллизий и нет повторных чтений. Учитывая что у тебя идеальное хеширование (ключи не меняются) то можно майнить такие
конфигурации. Тоесть подбирать их длительное время для достижения почти идеального результата.
Эффективность твоего метода также зависит от выбора менеджмента памяти. Допустим для Java там возможностей не очень много а для С++/C можно играть union поинтеров и самих данных и достигать каких-то более лучших
результатов. Например делая вспомогательные структуры более компактными.
Виктор, ну да бог. Тестируйте. Как оно будет. VGA здесь вобщем-то не в тему. Это стандарт 90х-2000х.
Уходящий стандарт. Аналогвый и в цифре он бы занимал самую малую полосу. У него даже разрешения
были низкие из-за электрических характеристик кабеля. Больше просто нельзя было поднять.
AntonTsiklop, наивный мальчик. При работе с базами данных ты должен где-то в коде обеспечить
проверку результата любой операций DML (insert/update). Они могут не сработать. По разным причинам.
Место в базе закончилось. Или ты вставляешь в базу строку которая вызывает primary key violation.
Да много чего может быть. Короче читай документацию по ORM Django. Там должно быть описано
как это делать.
z4_ln, каждый дополнительный монитор аллоцирует память и ресурсы видяшки.
Не думай что это совсем бесплатно.
Я не знаю как работает USB card, но главная задача которая ставилась при разработке HDMI
например - это пропускная способность и лаг. USB технически здесь не подходит. И результат
работы этого зоопарка тебе скорее всего сильно не понравиться.
Можешь зайти сюда и отписать потом по результатам.
Snoz3f, мда. С булевыми полями все базы хреново работают. Низко-кардинальные поля.
И значит индексирование не особо полезно.
Можно побить таблицу на части. Partitions. Или фасеты. Это тоже самое - только смысл - группировки
свойств по партишенам.
Я не помню поддерживаем Mongo partitions или нет. Но можно создать несколько collections.
Например если идет поиск по 4 булевым полям. То можно создать 16 коллекций где каждой
будет соотвествовать комбинация флажков.
Это если количество документов примерно одинаковое. Если будет сильный перекос - то можно
как-то мелкие коллекции слить в одну.
Ну и софт переписать чтоб был роутинг по разным коллекциям.
ElezthemDev, дружище. Твой ответ - повергает в уныние. Если тебе что-то конкретно непонятно по шагам - то ты спрашивай. Если ты вообще-вообще ничего не знаешь то я не могу тебе помогать.
И хабр не заниматеся процессом обучения а просто отвечает на конкретные вопросы.
Я тебе написал команды для командной строки Linux. Но это может работать и в Windows если ты установишь sqlite.
Тогда формула проще выходит. И вращать и отражать и гиперкубы делать.