Хэш таблицы
Вот кукушкины таблички можно заставить иметь заполнение в 80% и даже более, если увеличить размер корзины - хэши адресует корзины, а потом внутри корзины заранее заданного размера мы ищем наш элемент.
Однако, у нас возникает просадка производительности из-за необходимости сканировать корзину, сколь малой она не была бы.
Второй вопрос - количество циклов, которые мы можем выполнить перед тем, как считать таблицу полной. Чем их больше, тем медленней будет работа с таблицей.
То же самое относится и к последовательному проходу - когда мы вычисляем индекс внутри хэш таблицы и потом просто идём последовательно по возрастанию (по модулю размера таблицы), сравнивая элементы. В этом случае мы вовсе можем пройти всю таблицу, прежде чем поймём, что она заполнена.
А если пытаться ограничивать количество сравнений, то у нас табличка распухнет - ведь это кукушкино размещение, только с возможностью перекрытия корзин и всего с одним адресом. Насколько она распухнет? Неизвестно.
Размер памяти, к которой мы обращаемся, влияет на оптимальность использования кеширования. Во-первых, мы чаще промахиваемся мимо кешей, во-вторых, мы чаще промахиваемся мимо запомненных нами страничек виртуальной памяти.
Поэтому мне интересно, не скрывается ли в хэш табличках какой-нибудь логарифм, который проявляется только при работе с железом, что может быть построено физически.
Иерархия размеров кешей в модели кеш-независимых алгоритмов считается следующей квадратичному закону: размер_памяти_уровняi+1 = размер_памяти_уровняi2. Время доступа к очередному уровню, вроде бы, не указано.
Надо будет посмотреть на времена доступа и попробовать как-то оценить стоимость доступа к элементу хэш-таблицы.
Ибо если у нас вылезает логарифм тем или иным боком, то структуры данных типа cache-oblivious lookahead arrays становятся весьма и весьма привлекательными. Ведь при их построении не надо заранее задавать размеры корзин или полином индексов проверки, а потом судорожно менять, когда всё работает не настолько быстро, как хотелось бы.
Однако, у нас возникает просадка производительности из-за необходимости сканировать корзину, сколь малой она не была бы.
Второй вопрос - количество циклов, которые мы можем выполнить перед тем, как считать таблицу полной. Чем их больше, тем медленней будет работа с таблицей.
То же самое относится и к последовательному проходу - когда мы вычисляем индекс внутри хэш таблицы и потом просто идём последовательно по возрастанию (по модулю размера таблицы), сравнивая элементы. В этом случае мы вовсе можем пройти всю таблицу, прежде чем поймём, что она заполнена.
А если пытаться ограничивать количество сравнений, то у нас табличка распухнет - ведь это кукушкино размещение, только с возможностью перекрытия корзин и всего с одним адресом. Насколько она распухнет? Неизвестно.
Размер памяти, к которой мы обращаемся, влияет на оптимальность использования кеширования. Во-первых, мы чаще промахиваемся мимо кешей, во-вторых, мы чаще промахиваемся мимо запомненных нами страничек виртуальной памяти.
Поэтому мне интересно, не скрывается ли в хэш табличках какой-нибудь логарифм, который проявляется только при работе с железом, что может быть построено физически.
Иерархия размеров кешей в модели кеш-независимых алгоритмов считается следующей квадратичному закону: размер_памяти_уровняi+1 = размер_памяти_уровняi2. Время доступа к очередному уровню, вроде бы, не указано.
Надо будет посмотреть на времена доступа и попробовать как-то оценить стоимость доступа к элементу хэш-таблицы.
Ибо если у нас вылезает логарифм тем или иным боком, то структуры данных типа cache-oblivious lookahead arrays становятся весьма и весьма привлекательными. Ведь при их построении не надо заранее задавать размеры корзин или полином индексов проверки, а потом судорожно менять, когда всё работает не настолько быстро, как хотелось бы.