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];

Seed для CRC32?

По поводу CRC32. Это очень примитивная функция. Она создавалась в 20-м веке
в эпоху 16 и 32х битных процессоров. И в основе ее лежит один раунд ХОРь ,
сдвиг и отображение из массива заранее расчетных констант.

У нее есть некоторые интересные совйства. Кажется она идеально хеширует int32
целое число. Вот. Но если-бы я хотел повторить такие свойства то я мог-бы
создать функцию к примеру которая-бы ... меняла левые 16 бит и правые.
Вот тоже самое свойство. Идеально отображает одно в другое.

Но что говорить о прочих свойствах?

Seed для CRC32?

floppa322, я-ж про потребление памяти спрашиваю.