Выглядит как решение соседа по палате :) Надо будет попробовать. К сожалению, реализация на C# через нативный враппер. Он может быть быстрее, а может быть проблемным из-за маршаллинга. Надо посмотреть на память и скорость, может его стоит использовать в качестве основной реализации сета, а не хранилища, которое будет в него преобразовано.
А если меньше, то плохо выходит. + начало блока надо кодировать. В общем, при плотных данных это хороший вариант. Я подобный вариант описал в начале статьи, только ограничил всё числами от 0 до 255.
Для известного распределения — надо по идее использовать для информации все множества (в одном каждое число уникально и ничего мы не добьёмся). По идее тут Хаффман может подойти. Можете дать ссылку на VLQ в git? потому что попытки узнать что это, привели к коду, реализующему VLQ, опубликованному на гитхабе :)
Group varint — вариант для скорости, надо тут тестировать на C#, возможно ли получить преимущество, или невозможность делать некоторые вещи — сожрёт возможную выгоду.
RLE на мой взгляд больше для битмапов подойдёт, или для очень специфичных данных, для которых можно и другие варианты подобрать. Что-то пока не могу придумать, чем RLE тут помогло.
Про статистику я как раз писал — что всё зависит от данных, поэтому и расписал разные варианты.
В среднем пишу больше, но бывают периоды, когда попадается и такое:
1. Ревью, ревью и ревью.
2. Документация (чтение, написание)
3. Обсуждения (что, как и кому делать)
4. Оптимизация, да во время процесса может быть написано и удалено несколько тысяч строк кода, сделана куча бенчмарков, а потом может оказаться добавление одной строчки или указание что сделать
5. Вдумчивое чтение логов (стрельнула бага у клиента, понять причину, решить как её обойти в будущем, и стоит ли вообще обходить, может бага из-за того что он сам что-то не то сделал)
6. Настройка инфраструктуры/базы/билдов/деплоя
Можно уточнить — 500 одновременных заходов на сайт, это что имеется в виду? Потому что 500 запросов к серверу одновременно, это весьма серьёзная нагрузка. И если «поделка» такое выдерживает, то не такая уж это и поделка.
Другое дело, если вы имеете в виду 500 человек постоянно что-то смотрят на сайте и раз в минуту кликают по ссылкам, это уже не особенная нагрузка, да.
Если бы я помнил ещё. Там так часто всё меняется и зависит от версии, что пример подбирать надо. Не очень хороший пример, но вот список приложений. Где справа появляется пара пунктов в развёрнутом виде. в свёрнутом — они тоже есть, но в самом низу, т.е. знать про них надо.
появляются, например, при раскрытии окна на весь экран
О да, за это отдельный котёл в аду для UX-дизайнеров Microsoft надо придумать. Где регулировка температуры варки будет доступна только если рстянуться поперёк котла и раскинуть руки.
Гуглишь, куда настройку засунули, говорят — тут находится. Всё обнюхал — нет, оказывается развернуть окно надо, тогда появится.
Ага и в каждой версии винды, которые выходят раз в полгода настройки находятся всё время в разных местах. Ну и новые, конечно же только часть функционала реализуют.
Фото бюллютеня — это мелочи. Можно найти фотку из интернета, можно сказать, что забыл или не умеешь, можно подделать фотку. А вот если ты приходишь в понедельник утром и обязан отдать секретный ключ с флешки — и там будет «неправильный» голос. То это уже весьма плохо. При этом, в отличие от фоточек — тут всё достаточно хорошо систематизируется. Т.е. Отдел А приходит в 10 утра к специально выделенному человеку и отдаёт ключи. Кто не отдал — заносим в список.
Да понял условия. Степень двойки недолюбливаю, т.к. повышенный расход памяти. И если с простым числом можно порость хеш ужаться (типа мы добавили всё и сейчас будем только проверять, то со степенью двойки это не получится). Но в целом проще да, и, возможно, меньше коллизий.
Асимптотика — да. Но математиков к программированию допускать всё-таки не стоит. Ибо асимптотически у них всё идеально, а в реальности…
В общем, чуть поигрался — вариант с цепочками в худших случаях значительно опережает данный. Но памяти жрёт гораздо больше, т.е. можно компенсировать проблемы уменьшением FillFactor.
Если дойдут руки, попробую заюзать на реальной задаче, где огромное количество сетов используется, посмотрю на использование памяти и скорость.
Спасибо что подтолкнули меня заняться задачей, которую откладываю уже несколько месяцев :)
А если размер не степень двойки? Мне сейчас тяжело продумывать пример, но это очень неправильное поведение полностью полагаться на значения хеша. Может тут и прокатит, но шаг влево, шаг вправо и хеш станет 0, и мы будем бегать по одному элементу. Обычно в статьях рекомендуют код вида 1 + (hash % (size — 1)).
Т.е. явно добавляют единичку
Чуть поигрался с хешами, результаты стали лучше. На 1000 с заполнением .75 худшее попадание за 25 попыток, в среднем — 3.2
С заполнением .5 — уже 15/1.8
Какое у вас заполнение по факту было? Сомневаюсь, что с таким заполнением вы со второй попытки всё угадываете. Всё-таки терверы говорят про 4.
В общем, написал свою реализацию на потестить. Может где-то наврал, да и в качестве второго хеша заюзал xor (чтобы сбить линейность, но может не сбивается). В общем, если что, то второй хеш надо бы проверить что не 0, иначе могут быть проблемы.
Так вот, на рандомных данных, среднее плохое, но жить можно, но есть очень длинный хвост мерзости. Т.е. некоторые несуществующие элементы никак не могут попать в свободную ячейку. Т.е. в хорошем, плотном сете из 1000 элементов можно получить 854 итерации на поиск.
Так что, очень аккуратно следует использовать данную схему.
Проблема в том, что при наличии коллизий, мы начинаем расскидывать в разные ячейки. Но проблема в том, что эти «другие» ячейки уже «зарезервированы» под другие значения. Т.е. упрощённый пример, пусть будет массив из 7 элементов для простоты.
пришёл элемент, первый хеш код у него 3, вставили в третью ячейку
пришёл другой элемент, неудачно, хешкод опять 3, второй 2, вставили в 5-ую ячейку
пришлёт трейтий элемент с хешкодом 5 — должны были вставить в 5-ую ячейку, но занято. Надо подбирать другую.
Чем больше занято в массиве, тем может быть тяжелее подбор и поиск.
Откуда 4 элемента — массив заполнен на 75%. Проверяем на существование какой-либо несуществующий элемент. С вероятностью 0.75 попадём в занятую ячейку. Пойдём перебирать дальше — опять попадём в занятую с вероятностью 0.75. И так далее. И тут я уже забыл тервер, чтобы прикинуть мат.ожидание количества попыток :) Может я неправ насчёт 4-х. Возможно меньше.
Метод цепочек достаточно эффективный, ценой увеличения потребления памяти, да. Вопрос в том, насколько к реальности проблемный/беспроблемный метод двойного хеширования. Пока ощущения, что в идеальных случаях он очень хорош, но в случае проблем начинает быстро деградировать (попали в коллизию, закинули в сосденюю ячейку этот элемент, приходит нормальный элемент и попадает в эту же ячейку, получается вынужденная коллизия и ищется место уже для этого элемента). Также, рехеш не быстрая операция, и хотелось бы производить её пореже.
Дальше, если я правильно понял ваш код, то размер буфера у вас изначально 8 и увеличивается в 2 раза. Т.е. определённо не простые числа. Т.е. вы половину данных (навскидку) не используете в своём массиве.
Идём дальше, заполнение таблицы на 75% — по асимптоике получается, что пустой будет только каждый 4-ый элемент, т.е. мы должны в среднем перебрать 4 элемента, прежде чем попадём в дырку и есть ощущение, что на реальных данных всё может быть хуже.
И если я ещё правильно понял код, то при сильно заполненной таблице поиск несуществующего элемента вырождается в O(n) — т.к. будем перебирать почти все элементы, пока не переберём все или случайно попадём в null.
А можно подробнее про двойное хеширование? Стоит ли игра свеч? Если я правильно понял, то оно в целом ухудшает производительность. Т.е. группа нехороших элементов может загадить собой данные так, что нормальные элементы будут долго искать подходящую дырочку в массиве. Есть какие-то измерения?
Group varint — вариант для скорости, надо тут тестировать на C#, возможно ли получить преимущество, или невозможность делать некоторые вещи — сожрёт возможную выгоду.
Про статистику я как раз писал — что всё зависит от данных, поэтому и расписал разные варианты.
1. Ревью, ревью и ревью.
2. Документация (чтение, написание)
3. Обсуждения (что, как и кому делать)
4. Оптимизация, да во время процесса может быть написано и удалено несколько тысяч строк кода, сделана куча бенчмарков, а потом может оказаться добавление одной строчки или указание что сделать
5. Вдумчивое чтение логов (стрельнула бага у клиента, понять причину, решить как её обойти в будущем, и стоит ли вообще обходить, может бага из-за того что он сам что-то не то сделал)
6. Настройка инфраструктуры/базы/билдов/деплоя
Другое дело, если вы имеете в виду 500 человек постоянно что-то смотрят на сайте и раз в минуту кликают по ссылкам, это уже не особенная нагрузка, да.
О да, за это отдельный котёл в аду для UX-дизайнеров Microsoft надо придумать. Где регулировка температуры варки будет доступна только если рстянуться поперёк котла и раскинуть руки.
Гуглишь, куда настройку засунули, говорят — тут находится. Всё обнюхал — нет, оказывается развернуть окно надо, тогда появится.
В общем, чуть поигрался — вариант с цепочками в худших случаях значительно опережает данный. Но памяти жрёт гораздо больше, т.е. можно компенсировать проблемы уменьшением FillFactor.
Если дойдут руки, попробую заюзать на реальной задаче, где огромное количество сетов используется, посмотрю на использование памяти и скорость.
Спасибо что подтолкнули меня заняться задачей, которую откладываю уже несколько месяцев :)
Т.е. явно добавляют единичку
С заполнением .5 — уже 15/1.8
Какое у вас заполнение по факту было? Сомневаюсь, что с таким заполнением вы со второй попытки всё угадываете. Всё-таки терверы говорят про 4.
Так вот, на рандомных данных, среднее плохое, но жить можно, но есть очень длинный хвост мерзости. Т.е. некоторые несуществующие элементы никак не могут попать в свободную ячейку. Т.е. в хорошем, плотном сете из 1000 элементов можно получить 854 итерации на поиск.
Так что, очень аккуратно следует использовать данную схему.
пришёл элемент, первый хеш код у него 3, вставили в третью ячейку
пришёл другой элемент, неудачно, хешкод опять 3, второй 2, вставили в 5-ую ячейку
пришлёт трейтий элемент с хешкодом 5 — должны были вставить в 5-ую ячейку, но занято. Надо подбирать другую.
Чем больше занято в массиве, тем может быть тяжелее подбор и поиск.
Откуда 4 элемента — массив заполнен на 75%. Проверяем на существование какой-либо несуществующий элемент. С вероятностью 0.75 попадём в занятую ячейку. Пойдём перебирать дальше — опять попадём в занятую с вероятностью 0.75. И так далее. И тут я уже забыл тервер, чтобы прикинуть мат.ожидание количества попыток :) Может я неправ насчёт 4-х. Возможно меньше.
Дальше, если я правильно понял ваш код, то размер буфера у вас изначально 8 и увеличивается в 2 раза. Т.е. определённо не простые числа. Т.е. вы половину данных (навскидку) не используете в своём массиве.
Идём дальше, заполнение таблицы на 75% — по асимптоике получается, что пустой будет только каждый 4-ый элемент, т.е. мы должны в среднем перебрать 4 элемента, прежде чем попадём в дырку и есть ощущение, что на реальных данных всё может быть хуже.