Seed для CRC32?

Ну... популярность ключей это-ж краеугольный камень всего перформанс тюнинга. Это и для баз данных актуально. Для файловых систем. И для веб-приложений с Rest.

И один великий сказал дескыть всего 2 проблемы у нас. Как обозвать переменную и как инвалидировать
кеш. А все остальное - решаемо.

Seed для CRC32?

Если честно, у меня пока нет никаких мыслей, как это можно развить, чтобы было O(1) без жирных констант на contains

Если ты дойдешь до практики реализации кешей. То там окажется что оперативная память неодинаково
работает. Если делать тюнинг структур данных под L1/L2/L3 то может оказаться что такое зональное
деление ключей на популярные и непопулярные очень полезно для кеша.

Вот. Поэтому лучше остановись и сделай бенчмарк в сравнении с хешами STL, Google e.t.c.

O(1) - это чистая теория. А практика может показать что твой теоретический хороший O(1) может быть хуже например логарифма но адаптированного к железу. Бегаешь по красно-черному дереву но ближе к CPU. А пробирования хещ-таблиц будут всегда промахами для железа.

Вот мой десктоп дома (Ryzen-5) имеет на борту 8М кеша L3. И если я его прогрею полностью
(положу туда одну зону из хеш-таблицы) то я почти гарантирую очень короткий отклик
без вовлечения оперативной памяти.

Seed для CRC32?

Ну я вообще тестирую set. В нем только и будет contains. А get не имеет смысла.

Seed для CRC32?

Действительно, можно отсортировать данные по частоте заросов на них, скажем на 10% объектов приходится 90% запросов contains/get, тогда можно с обычным линейным пробированием эти 10% запихать первыми (так, чтобы distance от места вставки до реального места был не больше 1.05 скажем), а остальные 90% запихать потом. Тогда мат. ожидание кеш мисса будет близко к 1.

Да и если использовать этот пирамидальный вариант таблиц то можно пускать в population ключи
в порядке их частоты. Сначала - самые популярные. Они займут толстый слой пирамиды. А потом
уже те кто пореже будут заселены на 2 и 3 и выше уровня. Но нам - пофиг. Они - редкие посетители.

Seed для CRC32?

floppa322, я вот решил следующее посчитать. Допустим я не буду вставлять конфликтующие ключи. А просто буду вести их список. Долг типа. Вот получилось так на 5 млн.

2023-07-28 20:06:28,511 : [INFO] - Start demo
2023-07-28 20:06:29,417 : [INFO] - Populated successfully!
2023-07-28 20:06:29,417 : [INFO] - Inserted : 3160854
2023-07-28 20:06:29,419 : [INFO] - Collision list size : 1839146
2023-07-28 20:06:29,419 : [INFO] - Hash set physical size is 5000000 slots (20000000 bytes)
2023-07-28 20:06:29,419 : [INFO] - Inserted/slots ratio : 63%
2023-07-28 20:06:29,419 : [INFO] - Finish

Из 5 лямов успешно вставились порядка 3.1 млн. Долговых ключей на 1.8. Хорошая новость
их хотя-бы не так много. Далее я могу рекурсивно применить алгоритм построения этой-же
таблицы к списку долговых ключей. Но теперь мне уже не нужно 5 млн слотов. Я сразу создаю
1.8. И если эта геометрическая прогрессия работает (100% - 63% = 37%) то каждый раз
я буду получать треть от оригнального размера. Хеш функцию в данном случае можно
даже не менять. Просто меняется у нас остаток от деления. Будет пирамида таблиц.

Seed для CRC32?

Мне как базовику очень не нравится что кукушка постоянно что-то тасует в памяти. Было-бы более ясно если есть фаза генерации или популяции таблицы. И после этого мы ее фиксируем и больше ключи не вращаются.

Seed для CRC32?

Мда... От коллизий вообще не уйти. Может примем за допущение что 1 коллизия для 1 ключа это нормально?

Но глубина пробирования будет в 1 шаг. После первой коллизии мы применяем ту-же хеш-функцию типа CRC или mur-mur но с другим seed.

Если после 2 шага коллизия - то растягиваем таблицу.

Seed для CRC32?

floppa322, функция mur-mur-hash. Линейное. Пока я фикшу баги.

Но ты булки не расслабляй. Кодь дальше.

Seed для CRC32?

Короче я нашел свой старый исходник и сюда приложу а ты посмотри. Если какой-то API по Java ты не знаешь - то я могу подсказать.

UPD: Нет. Херовенько он работает. Надо подфиксить.

Seed для CRC32?

10-16n

Тоесть ты хочешь сказать что вместо 5 млн слотов тебе надо будет 16 * 5 000 000 = 80_000_000 ?

Восемдесят лямов?

Ахахаха.

Seed для CRC32?

Нормально.

Я 5 миллионов ключей записал в 5008333 слотов. Без коллизий за 2 итерации.

Как посчитать значение до прибавления к ней процента?

galliard, я написал достаточно для решения. Ты просто не мог поставить задачу в термиах алгебры.

Что делать, когда Wolfram говорит, что будет корень, а считать не хочет - a³+b³=z³?

Wataru, да эту формулу я ему и давал недавно.

Seed для CRC32?

Отписал я вариант ответа. Чего тут еще придумывать. Ну ты подумай что двухуровневая таблица - это-ж фу-фу-фу.
Ни один нормальный разработчик не захочет тащить в проект накладные расходы ни с того ни с сего 2х от нужного размера. И кукуха здесь не поможет и Робин гуд. Если уж ты такой перфекционист.

Почему результат трансформации углов эйлера таков?

А какой правильный ответ?

Как разогнать процессор AMD?

Как давно стоит эта операционка?

Драйвер на видео как называется? Какая версия? Возможно ли обновить?

Seed для CRC32?

floppa322, почитай еще про метод Робин-Гуда. Возможно тебе пригодится.

Seed для CRC32?

Давай я тебе мысль закину. А ты подумай. Вот в твоем исходнике-же нет таблицы.
Там только ключи. Сет по сути. Тогда тебе можно завести битовый массив и включай биты
где надо. У тебя 5 млн ключей?

А я тебе предлагаю аллоцировать 512 Мб битов и этого тебе хватит для любого
целого числа от 0 до 4 млрд.

Seed для CRC32?

floppa322, ты меньше слушай ребят из Кликхаус. Они всполне могли использовать
CRC32 (славо богу его и TCP использует и много чего) но не в таком юзкейсе как ты
придумал.

Seed для CRC32?

А как ты выбрал эти константы? Почему 16 и 14?

const size_t INNER_BUCKET_SIZE = 16;
    const size_t ITEM_PER_BUCKET = 14;
    bool innerBucket[INNER_BUCKET_SIZE];