Я не очень понял, Вы у меня спрашивали или нет, но постараюсь ответить.
Как мне кажется, Вы не доконца поняли алгоритм. Вернее, не сам алгоритм, а ньюансы по потреблению памяти.
Давайте посмотрим еще раз на пример, таблица из 100 битов, 2 хеш функции, и положем в нее одно значение. Допустим хеши получились разные и мы установим 2 единицы из 100. Вероятность false positive = (2 / 100) ^ 2 = 4 / 10000 = 1 / 2500.
Если я правильно понимаю, то Вы предлагаете вместо одной таблицы размера 100 использовать 2 таблицы по 50, по одной на хеш функцию. Тогда при добавлении одного элемента мы поставим по одной единичке в каждой из таблиц. Вероятность false positive = (1 / 50) ^ 2 = 1 / 2500.
Вроде бы то же самое. НО! В оригинальном алгоритме значения хешей могут совпасть (с вероятностью 1/100 в нашем случае) и мы установим в массив 1 единичку, а не 2. В этом случае вероятность false positive = (1 / 100) ^ 2 = 4 / 10000. Т.е. в среднем оригинальный алгоритм дает лучший результат, чем Ваша модификация. И это при добавлении всего одного элемента.
При добавлении большего количества элементов вероятность колизий (попаданий на уже установленую 1) будет расти и тем самым уменьшать суммарное количество единиц во всем массиве. А это уменьшает вероятность false positive.
А сколько требует? Мне даже стало интересно ваше мнение.
Разберитесь еще раз с алгоритмом и аккуратно подумайте про заполнение битового массива в случайных позициях и вероятности попадать на единички при false positive.
Если не получится придумать, то я подскажу как нагуглить в википедии.
Но, ведь, увеличение числа хэш-функций увеличит число единиц в массиве.
Верно.
Если у нас занесен в массив 1 IP, то ложных срабатываний не будет.
Не верно.
Допустим, мы выделили массив из 100 бит. Рассмотрим на пальцах случаи:
1 хеш функция. Тогда при добавлении одного элемента у нас 1 единица и 99 нулей. Вероятность ложного срабатывания = 1 / 100.
2 хеш функции. При добавлении одного элемента скорее всего они дадут разные значения и мы установим 2 единицы и 98 нулей. Ложноположительное срабатывание возможно тогда, когда обе хеш функции (независимые) у нового элемента попадут в эти единицы. Вероятность такого события = (2 / 100) ^ 2 = 4 / 10000 = 1 / 2500.
Если добавлять больше элементов, то (при одинаковом размере массива и количестве хеш функций) вероятность ложноположительного срабатывания медленно растет, но с какого-то момента начинает расти очень быстро.
Если же условно зафиксировать количество памяти и количество добавленых элементов, то при росте количества хеш функций вероятность ложноположительного срабатывания сначала падает, а потом начинает расти.
Таким образом, подбор параметров это компромис между количеством памяти и точностью. И, как я писал выше, надо следить за количеством добавленых элементов, т.к. при добавлении больше расчетного точность очень сильно падает.
У фильтра Блума есть еще одно неприятное свойство.
Если мы ожидаем определенное количество уникальных объектов и у нас есть требования к вероятности ложноположительных срабатываний, то мы можем расчитать количество требуемой памяти и количеству хеш функций. Так вот, если памяти не выделить с запасом, а уникальных объектов положить больше, чем планировали, то начиная с какого-то момента вероятность ложноположительных срабатываний растет катастрофически.
Откровенно говоря, с помощью фильтра Блума и счетчика можно сделать тоже самое.
Конечно же нет.
Во-первых, наивное решение будет давать погрешность в одну сторону, как раз из-за ложноположительных срабатываний. Для компенсации этого эффекта, наверно, есть какие-то формулы, но скорее всего они не очень простые.
А во-вторых потребляемый объем памяти разительно отличается. Как я писал ниже, фильтр блума требует O(n) памяти. Допустим у нас 1 милиард уникальных объектов, это порядка гигабайта памяти если выделить в среднем по одному байту на объект (но лучше по 2 байта).
А теперь сравниваем с HyperLogLog, на вики пишут про 1.5 килобайта при средней ошибке в 2%. В реальности при таких вводных ошибка частенько будет больше 5%. Например, чтобы почти всегда ошибка была в пределах 1% (но в большинстве случаев меньше) нужно около 20кб памяти. Против гигабайта в фильтре блума.
Самая крышесносная на мой взгляд это HyperLogLog. Позволяет посчитать количество уникальных объектов (не точно, с парой процентов погрешности) используя всего пару килобайт памяти.
Это означает, что каждый раз, когда маршрутизатор получает пакет на скорости более 100 Гбит/с, он должен обращаться к своей памяти и выполнять в лучшем случае логарифмический поиск (O(log(n)))
Это не правда, хеш таблица работает в среднем за O(n). Коллизии можно уменьшать разными методами, например так. Так что по скорости тут выигрыша особо и нет, как мне кажется.
По памяти фильтр блума, конечно, меньше (обычно в разы или даже в десятки раз), но это все еще O(n), как и в хеш таблице. Условно говоря, для фильтра блума желательно выделить хотя бы 2 байта на объект, а хеш таблицу можно ужать до 16 байт на объект.
Спасибо за отзыв, приятно что кому-то кроме меня удобно пользоваться таким способом.
Могу порекомендовать ещё 2 вещи:
Повесить на отдельный хоткей Private Browsing в Firefox, в статье есть как это сделать. Я так разделяю сайты, где я залогинен и где хочу затруднить трекинг. Это на самом деле удобно, я почти всё гуглю в приватных вкладках.
Разберитесь с кастомными назначениями, та часть в статье с showwin "CustomKey1" и showwinDetach. Это добавляет удобства при решении нестандартных задач. Например, визуально сравнивать данные из разных программ или разных окон одной программы. Можно, например, быстро перелючаться на окно с pdf или даже открыть один pdf в нескольких окнах на разных страницах и быстро перемещаться между ними.
На некоторых электрических пишуших машинках стрелка клавиши enter была в обратную сторону: вверх и вправо (или вправо и вверх, точно уже не помню), по направлению движения каретки. И еще на tab и backspace стрелки в обратную сторону. Очень странно выглядело.
Возможно. Я не пользовал отдельной клавишей для find next, может и просто переопределил и не заметил. В своем комментарии я хотел поделиться как можно сделать удобнее, кому-то такой способ не подойдет и это ок.
Лично мне сейчас такой возможности не хватает. 2 года на макбуке с тачбаром, полное г. Только звук и яркость прикольно регулировать. С радостью обменял бы тачбар на нормальные кнопки (а заодно и остальную клавиатуру на нормальные кнопки).
Как и многие, только сейчас узнал, что по Backspace можно переходить назад. Не понимаю зачем так было делать, опасная же функция. Есть ощущение, что я не раз так переходил назад, тихонько матерился и возвращался, так и не поняв, что произошло.
А теперь о решении. Можно переназначить назад/вперед на F2/F3 (надо ставить плагин), эти клавиши в браузере все равно не используются. Случайно их задеть можно, но такое бывает не чаще, чем случайно Backspace нажать. Для меня это реально удобное решение, я его подсмотрел когда активно пользовался хромбуком.
Котёл на обычном паровозе тоже опасен. Но вариантов в то время было мало. Если по каким-то причинам нельзя паровоз, то либо один из этих вариантов (сжатый воздух, пароаккумулятор), либо на лошади возить. Подобие гиробуса, но на рельсах, наверно, сложно было сделать в то время.
Меня в свое время удивило, что существовал еще такой экзотический транспорт, как электропаровоз.
Бегло просмотрел реддит. Интересная идея с дальтонизмом: Palette 1 (вроде как) различима всеми. С другой стороны, Palette 0 наихудшая в этом плане.
Но я всё-таки думаю, что причины чисто технические и сделали так, как проще и дешевле.
Если все просуммировать, то во всех палитрах:
Цвет 0 можно задать любой (обычно черный), и он же используется для заливки вне границ экрана (но, возможно, я тут выдумываю).
Канал яркости фиксирован для всех цветов палитры кроме цвета 0.
Зеленый канал совпадает с первым битом цвета, а красный со вторым битом.
Синий канал зависит от палитры. В Palette 0 он всегда 0, в Palette 1 всегда 1, а в Mode 5 равен биту 1 (зеленому каналу). Конечно, кроме цвета 0.
Если так, то можно было бы относительно легко сделать еще одну палитру, подключив синий канал к красному. Было бы green/magenta/white. Имхо, так себе палитра.
Интересно будет вывести все возможные палитры, сформированные подобным образом. Если бы не только синий канал был зависим. Мне кажется, там могли бы быть приятные палитры типа желтый/синий/белый.
Я подозревал это. Но тем не менее, адаптер и монитор, скорее всего, разрабатывали не совсем разные люди и какая-то комуникация между ними была. Но это, конечно, только мои догадки.
Как интересно, совсем забыл про этот режим. Он почему-то редко в играх использовался, хотя на мой взгляд палитра более приятная.
За ссылку спасибо, посмотрю.
Уже очень много лет для меня CGA хранит одну загадку. Может сообщество подскажет в чем дело.
Например, абсолютно понятно почему в текстовом режиме 16 цветов. 80х25 знакомест тоже логичны: страница текста помещается в 2кб + 2кб на атрибуты цвета.
В графическом режиме прямоугольные пиксели тоже оправданы, разрешение 320х200 вместо 320х240 для того, чтобы уместить видеостраницу в 16кб при 4 цветах. Отсюда же и монохромный 640х200. Увеличить в 2 раза разрешение по вертикали (а не по горизонтали) логично: так лучше отрисовывать текст.
Не понятно следующее: почему в графическом режиме такая уродская палитра? То, что ее надо было выбирать из 16 доступных цветов — ок. Захардкодили условно 4 палитры (2 разные палитры + бит яркости для всей палитры сразу) — еще можно понять. Но почему именно эти цвета?
С одной стороны можно понять: фиксируем бит яркости и синий цвет для всего экрана, а красный и зеленый доступны. Но это только часть дела, черный цвет надо обрабатывать отдельно и обычно он остается черным. Более того, насколько мне известно, вместо черного можно выбрать вообще любой цвет из 16. Неужели так сложно было сделать настраиваимыми все 4 цвета? Разработчики софта имели бы гораздо больше возможностей, а игры были бы менее вырвиглазными.
Причем, нельзя сказать, что разработчики CGA не думали о цветах. Они очень хотели уметь рисовать коричневый и сделали для этого специальный аппаратный хак и рисуют его вместо темного желтого.
We need to go deeper, существует приставка к приставке Game Cube :) https://en.wikipedia.org/wiki/Game_Boy_Player
Причем, там даже не эмуляция: Rather than emulating a Game Boy system, the Game Boy Player uses physical hardware nearly identical to that of a Game Boy Advance.
Сначала удивился почему нет Hacker's Delight, у нас Алгоритмические трюки для программистов от Генри Уоррен-мл, но, как оказалось, первое издание было в 2002г. Но я все же уверен, что эта книга стареть не будет.
Книга очень необычная и по-своему интересная, хоть и малополезная в повседневном использовании. В ней огромное количество алгоритмов с применением "битовой магии" (например, посчитать количество единичных битов или найти определенную битовую последовательность). Прочтение лично у меня несколько раз вызывало удивление "а что, так можно было?". В общем рекомендую, с книгой прияно выделить часок времени, открыть любую главу и узнать что-то новое.
Так это список правил для вымогателей почты/телефона. С ним все понятно. Я спрашивал про эти фильтры:
«Спрашивать о файлах cookie» для блокировки еще одной надоевшей уже всем вещи в виде уведомлений о том, что тот или иной сайт использует файлы cookie (причем работает!), и даже для отключения кнопок социальных сетей на сайтах, если вдруг кому-то нужно и такое.
Я не очень понял, Вы у меня спрашивали или нет, но постараюсь ответить.
Как мне кажется, Вы не доконца поняли алгоритм. Вернее, не сам алгоритм, а ньюансы по потреблению памяти.
Давайте посмотрим еще раз на пример, таблица из 100 битов, 2 хеш функции, и положем в нее одно значение. Допустим хеши получились разные и мы установим 2 единицы из 100. Вероятность false positive = (2 / 100) ^ 2 = 4 / 10000 = 1 / 2500.
Если я правильно понимаю, то Вы предлагаете вместо одной таблицы размера 100 использовать 2 таблицы по 50, по одной на хеш функцию. Тогда при добавлении одного элемента мы поставим по одной единичке в каждой из таблиц. Вероятность false positive = (1 / 50) ^ 2 = 1 / 2500.
Вроде бы то же самое. НО! В оригинальном алгоритме значения хешей могут совпасть (с вероятностью 1/100 в нашем случае) и мы установим в массив 1 единичку, а не 2. В этом случае вероятность false positive = (1 / 100) ^ 2 = 4 / 10000. Т.е. в среднем оригинальный алгоритм дает лучший результат, чем Ваша модификация. И это при добавлении всего одного элемента.
При добавлении большего количества элементов вероятность колизий (попаданий на уже установленую 1) будет расти и тем самым уменьшать суммарное количество единиц во всем массиве. А это уменьшает вероятность false positive.
А сколько требует? Мне даже стало интересно ваше мнение.
Разберитесь еще раз с алгоритмом и аккуратно подумайте про заполнение битового массива в случайных позициях и вероятности попадать на единички при false positive.
Если не получится придумать, то я подскажу как нагуглить в википедии.
Верно.
Не верно.
Допустим, мы выделили массив из 100 бит. Рассмотрим на пальцах случаи:
Если добавлять больше элементов, то (при одинаковом размере массива и количестве хеш функций) вероятность ложноположительного срабатывания медленно растет, но с какого-то момента начинает расти очень быстро.
Если же условно зафиксировать количество памяти и количество добавленых элементов, то при росте количества хеш функций вероятность ложноположительного срабатывания сначала падает, а потом начинает расти.
Таким образом, подбор параметров это компромис между количеством памяти и точностью. И, как я писал выше, надо следить за количеством добавленых элементов, т.к. при добавлении больше расчетного точность очень сильно падает.
У фильтра Блума есть еще одно неприятное свойство.
Если мы ожидаем определенное количество уникальных объектов и у нас есть требования к вероятности ложноположительных срабатываний, то мы можем расчитать количество требуемой памяти и количеству хеш функций. Так вот, если памяти не выделить с запасом, а уникальных объектов положить больше, чем планировали, то начиная с какого-то момента вероятность ложноположительных срабатываний растет катастрофически.
Конечно же нет.
Во-первых, наивное решение будет давать погрешность в одну сторону, как раз из-за ложноположительных срабатываний. Для компенсации этого эффекта, наверно, есть какие-то формулы, но скорее всего они не очень простые.
А во-вторых потребляемый объем памяти разительно отличается. Как я писал ниже, фильтр блума требует O(n) памяти. Допустим у нас 1 милиард уникальных объектов, это порядка гигабайта памяти если выделить в среднем по одному байту на объект (но лучше по 2 байта).
А теперь сравниваем с HyperLogLog, на вики пишут про 1.5 килобайта при средней ошибке в 2%. В реальности при таких вводных ошибка частенько будет больше 5%. Например, чтобы почти всегда ошибка была в пределах 1% (но в большинстве случаев меньше) нужно около 20кб памяти. Против гигабайта в фильтре блума.
Если в фильтре блума возникают коллизии, то еще не известно что хуже работать будет.
Самая крышесносная на мой взгляд это HyperLogLog. Позволяет посчитать количество уникальных объектов (не точно, с парой процентов погрешности) используя всего пару килобайт памяти.
Это не правда, хеш таблица работает в среднем за O(n). Коллизии можно уменьшать разными методами, например так. Так что по скорости тут выигрыша особо и нет, как мне кажется.
По памяти фильтр блума, конечно, меньше (обычно в разы или даже в десятки раз), но это все еще O(n), как и в хеш таблице. Условно говоря, для фильтра блума желательно выделить хотя бы 2 байта на объект, а хеш таблицу можно ужать до 16 байт на объект.
Спасибо за отзыв, приятно что кому-то кроме меня удобно пользоваться таким способом.
Могу порекомендовать ещё 2 вещи:
showwin "CustomKey1"иshowwinDetach. Это добавляет удобства при решении нестандартных задач. Например, визуально сравнивать данные из разных программ или разных окон одной программы. Можно, например, быстро перелючаться на окно с pdf или даже открыть один pdf в нескольких окнах на разных страницах и быстро перемещаться между ними.На некоторых электрических пишуших машинках стрелка клавиши enter была в обратную сторону: вверх и вправо (или вправо и вверх, точно уже не помню), по направлению движения каретки. И еще на tab и backspace стрелки в обратную сторону. Очень странно выглядело.
Возможно. Я не пользовал отдельной клавишей для find next, может и просто переопределил и не заметил. В своем комментарии я хотел поделиться как можно сделать удобнее, кому-то такой способ не подойдет и это ок.
Лично мне сейчас такой возможности не хватает. 2 года на макбуке с тачбаром, полное г. Только звук и яркость прикольно регулировать. С радостью обменял бы тачбар на нормальные кнопки (а заодно и остальную клавиатуру на нормальные кнопки).
Как и многие, только сейчас узнал, что по Backspace можно переходить назад. Не понимаю зачем так было делать, опасная же функция. Есть ощущение, что я не раз так переходил назад, тихонько матерился и возвращался, так и не поняв, что произошло.
А теперь о решении. Можно переназначить назад/вперед на F2/F3 (надо ставить плагин), эти клавиши в браузере все равно не используются. Случайно их задеть можно, но такое бывает не чаще, чем случайно Backspace нажать. Для меня это реально удобное решение, я его подсмотрел когда активно пользовался хромбуком.
Котёл на обычном паровозе тоже опасен. Но вариантов в то время было мало. Если по каким-то причинам нельзя паровоз, то либо один из этих вариантов (сжатый воздух, пароаккумулятор), либо на лошади возить. Подобие гиробуса, но на рельсах, наверно, сложно было сделать в то время.
Меня в свое время удивило, что существовал еще такой экзотический транспорт, как электропаровоз.
Бегло просмотрел реддит. Интересная идея с дальтонизмом: Palette 1 (вроде как) различима всеми. С другой стороны, Palette 0 наихудшая в этом плане.
Но я всё-таки думаю, что причины чисто технические и сделали так, как проще и дешевле.
Если все просуммировать, то во всех палитрах:
Если так, то можно было бы относительно легко сделать еще одну палитру, подключив синий канал к красному. Было бы green/magenta/white. Имхо, так себе палитра.
Интересно будет вывести все возможные палитры, сформированные подобным образом. Если бы не только синий канал был зависим. Мне кажется, там могли бы быть приятные палитры типа желтый/синий/белый.
Я подозревал это. Но тем не менее, адаптер и монитор, скорее всего, разрабатывали не совсем разные люди и какая-то комуникация между ними была. Но это, конечно, только мои догадки.
Как интересно, совсем забыл про этот режим. Он почему-то редко в играх использовался, хотя на мой взгляд палитра более приятная.
За ссылку спасибо, посмотрю.
Уже очень много лет для меня CGA хранит одну загадку. Может сообщество подскажет в чем дело.
Например, абсолютно понятно почему в текстовом режиме 16 цветов. 80х25 знакомест тоже логичны: страница текста помещается в 2кб + 2кб на атрибуты цвета.
В графическом режиме прямоугольные пиксели тоже оправданы, разрешение 320х200 вместо 320х240 для того, чтобы уместить видеостраницу в 16кб при 4 цветах. Отсюда же и монохромный 640х200. Увеличить в 2 раза разрешение по вертикали (а не по горизонтали) логично: так лучше отрисовывать текст.
Не понятно следующее: почему в графическом режиме такая уродская палитра? То, что ее надо было выбирать из 16 доступных цветов — ок. Захардкодили условно 4 палитры (2 разные палитры + бит яркости для всей палитры сразу) — еще можно понять. Но почему именно эти цвета?
С одной стороны можно понять: фиксируем бит яркости и синий цвет для всего экрана, а красный и зеленый доступны. Но это только часть дела, черный цвет надо обрабатывать отдельно и обычно он остается черным. Более того, насколько мне известно, вместо черного можно выбрать вообще любой цвет из 16. Неужели так сложно было сделать настраиваимыми все 4 цвета? Разработчики софта имели бы гораздо больше возможностей, а игры были бы менее вырвиглазными.
Причем, нельзя сказать, что разработчики CGA не думали о цветах. Они очень хотели уметь рисовать коричневый и сделали для этого специальный аппаратный хак и рисуют его вместо темного желтого.
We need to go deeper, существует приставка к приставке Game Cube :)
https://en.wikipedia.org/wiki/Game_Boy_Player
Причем, там даже не эмуляция: Rather than emulating a Game Boy system, the Game Boy Player uses physical hardware nearly identical to that of a Game Boy Advance.
Сначала удивился почему нет
Hacker's Delight, у насАлгоритмические трюки для программистовот Генри Уоррен-мл, но, как оказалось, первое издание было в 2002г. Но я все же уверен, что эта книга стареть не будет.Книга очень необычная и по-своему интересная, хоть и малополезная в повседневном использовании. В ней огромное количество алгоритмов с применением "битовой магии" (например, посчитать количество единичных битов или найти определенную битовую последовательность). Прочтение лично у меня несколько раз вызывало удивление "а что, так можно было?". В общем рекомендую, с книгой прияно выделить часок времени, открыть любую главу и узнать что-то новое.
Так это список правил для вымогателей почты/телефона. С ним все понятно. Я спрашивал про эти фильтры: