В среднем пишу больше, но бывают периоды, когда попадается и такое:
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.
А можно подробнее про двойное хеширование? Стоит ли игра свеч? Если я правильно понял, то оно в целом ухудшает производительность. Т.е. группа нехороших элементов может загадить собой данные так, что нормальные элементы будут долго искать подходящую дырочку в массиве. Есть какие-то измерения?
А лучше ещё процессор получше core i7, например, nvme ssd неплох, хорошую видекарту добавить, и будет вообще огонь машина.
За $140 долларов машинка с экраном, клавиатурой и батареей, которая может работать и что-то выполнять — это очень круто.
Да, тоже удивился про количество. Брал на али на распродаже «комп» с подобным конфигом (только там ещё и атом до кучи), так из коробки без отключения всякого хлама где-то 1.1Гб было занято. И винда где-то 11Гб сожрала всего. Т.е. вполне реально пользоваться можно.
Да, ключи могут поменяться, могут утечь, мессенджер может сливать информацию. Гарантии никакой нет. С криптографией основные протоколы согласования давно придуманы, и не думаю, что придумают что-то ещё (кроме конкретных алгоритмов шифрования).
Поэтому я в этом плане поддерживаю политику Телеграма: удобные чаты для всех, секретные, чтобы говорили о том, что они есть, всякие забавные фишки вроде эмоджи на звонках, чтобы начать разговор со сверки смайликов.
Т.е. с маркетинговой точки зрения — абсолютно правильная политика. Большинству не нужны секретные чаты, нужны фразы о том, что они есть и специалисты довольны.
Проблема в том, что вы можете обменяться ключами безопасно по данному протоколу, но не ясно с кем. Т.е. посередине может быть человек, который будет посредником и пропускать всё через себя. Чтобы это обойти придумали сертификаты и доверие, т.е. мы начинаем доверять кому-то, кто говорит, что никого посередине нет. В мессенджерах пытаются обойти тем, что показывают секретный ключ, который можно (и нужно) сверить по отдельному каналу.
Ну обычно приложения всё-таки стараются писать так, чтобы они не падали от любого эксепшена, а креши бывают жёсткие, так что ничего пикнуть не успевает. И часто последние строчки в логах бывают очень важны. Классический пример — OOM убийство, когда по логам можно понять, где примерно всё случилось. Ну и всякие ребуты железа, убийство процессов и т.д.
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 элемента, прежде чем попадём в дырку и есть ощущение, что на реальных данных всё может быть хуже.
За $140 долларов машинка с экраном, клавиатурой и батареей, которая может работать и что-то выполнять — это очень круто.
Поэтому я в этом плане поддерживаю политику Телеграма: удобные чаты для всех, секретные, чтобы говорили о том, что они есть, всякие забавные фишки вроде эмоджи на звонках, чтобы начать разговор со сверки смайликов.
Т.е. с маркетинговой точки зрения — абсолютно правильная политика. Большинству не нужны секретные чаты, нужны фразы о том, что они есть и специалисты довольны.