…Продолжение предыдущей статьи про waiting time paradox: на этот раз разберемся, почему успешный поиск в хэш-таблице обычно дольше, чем не-успешный
Возьмем классическую хэш-таблицу с разрешением коллизий цепочками: K пар ключ-значение, B корзинок со связными списками для разрешения коллизий, вот это все. Мы ищем в этой таблице разные ключи (а зачем еще нужна хэш-таблица?). Для каких-то ключей в таблице находится соответствие, для каких-то – нет.
Вопрос: что больше – среднее количество сравнений при успешном поиске, или среднее количество сравнений при неуспешном поиске?
Интуитивный ответ: среднее количество ключей в корзинке K/B, для успешного поиска нужно перебрать, в среднем, половину из них, а для неуспешного поиска – все.
Конечно, если бы интуитивный ответ был верен – я бы не стал об этом писать (это само по себе можно считать примером sampling bias). Дело в том, что вероятность найти/не найти ключ в корзинке – коррелирует с количеством ключей в корзинке. Где более вероятно найти заданный ключ: в корзинке, где лежит только 1 ключ, или в корзинке, где лежит 10 ключей? Как правило, чем больше ключей в корзинке – тем больше вероятность, что искомый ключ среди них все-таки есть, и наоборот.
А значит если в какой-то корзинке мы нашли ключ – вероятно, что эта корзинка была более заполнена, по сравнению с типичной ("средней"). И наоборот: если мы знаем, что в какой-то корзинке мы ключ искали, но не нашли – вероятно, что та корзинка была менее заполнена, чем типичная.
Похоже, мы снова имеем дело с чем-то вроде (обобщенного) парадокса времен ожидания, aka size-biased sampling: в хэш-таблице обычно лишь небольшое количество корзинок содержат много ключей, но именно в этих корзинках мы будем чаще всего находить нужный нам ключ – просто потому, что в таких корзинках больше кандидатов! И значит именно эти размеры корзинок будут с бОльшим весом входить в сумму для "среднего размера корзинки где мы нашли ключ". И наоборот – для в сумму для "среднего размера корзинки, где мы не нашли искомый ключ" будут с бОльшим весом входить корзинки с нетипично малым количеством ключей (например, пустые).
А велика ли разница?
Хорошо, пусть среднее количество ключей в корзинке и больше для успешного поиска – но что той разницы? Ведь в "успешном" сценарии перебирать-то приходится (в среднем) только половину из них. Все равно же успешный поиск получится короче (=меньше сравнений), чем неуспешный?
Оказывается, и это под вопросом. Однозначного ответа тут нет – в общем случае результат может быть и такой и эдакий. Но утверждается, что как раз для типичного (практически важного) случая хэш-таблицы с небольшим количеством коллизий (низким load factor-ом) эффект от inspection/waiting time paradox оказывается достаточно велик, и средние размеры "успешных"/"не успешных" корзинок различаются более чем в два раза:
…In both models, numerical calculations show that, if the chain is not too long, the average length of an unsuccessful search, which is defined to be the number of accesses required to reach the end of the chain, is less than the average length of successful search, which goes only to the "middle" of the chain
(та самая статья)
То есть "if the chain is not too long", то эффект от "парадокса времен ожидания" перебивает двухкратную разницу в средней длине поиска – и оказывается, что успешный поиск требует больше сравнений (в среднем), чем неуспешный, даже несмотря на то, что успешный поиск перебирает (в среднем) лишь половину ключей в корзинке
Но в статье не приводятся конкретные цифры, просто констатируется факт, так что разбираться подробнее придется самому
Во-первых, почему "if the chain is not too long" – почему важно, чтобы цепочки (=размеры корзинок) не были слишком большими? Можно порассуждать, почему. Неизвестно, как выглядит формула для size-biased sampling в этом случае, но логично предположить, что все упирается в вариабельность (коэффициент вариации) – как и для обычного парадокса времен ожидания. То есть чем больше вариабельность – отношение стандартного отклонения к среднему – тем больше эффект. Но чем больше в среднем ключей на корзинку в хэш-таблице, тем меньше вариабельность их количества – это центральная предельная теорема. Тогда все звучит логично: условие "не очень длинных цепочек" означает, что эффект size-biased sampling оказывается достаточно велик только тогда, когда размер корзинок имеет большую вариабельность, а это случается когда корзинки еле-еле заполнены – то есть когда у хэш-таблицы низкий load factor.
Во-вторых – а есть ли мальчик? Прежде чем разбираться, как возникает этот эффект, надо проверить, а есть ли он вообще (мало ли, что там пишут, может я все неправильно понял). Благо несложно симулировать поиск в хэш-таблице, и записывать размер корзинки, где он происходил. На графике ниже результаты такой симуляции для хэш-таблицы из 128 корзинок, и разного числа ключей/load factor-а:
Действительно: пока загрузка (load factor) таблицы меньше примерно 1.8-2.2 – успешный поиск дороже, чем не успешный, а по мере роста загрузки таблицы соотношение между ними приближается к 1/2.
Судя по этому графику, рассуждения выше хотя бы качественно похожи на правду: чем больше загрузка таблицы, тем больше ключей на корзинку, тем меньше вариабельность числа ключей в корзинке, тем меньше искажающий эффект от size-biasing sampling, тем ближе результат к интуитивному – что успешный поиск вдвое дешевле неуспешного, потому что ему приходится проверять только половину ключей.
Можно это описать математически? (beware!)
Давайте попробуем. У нас есть хэш-таблица с B корзинками, и мы кладем в нее K ключей. При этом ключи как-то распределятся по корзинкам. Как?
Попробуем оценить распределение приближенно: если ключи случайные, и хэш-функция достаточно хорошая, то вероятность попадания каждого конкретного ключа в конкретную корзинку это просто 1/(кол-во корзинок) = 1/B.
Значит (в первом приближении) вероятность того, что в корзинке окажется b ключей это вероятность, что из K попыток с вероятностью успеха 1/B мы получим b успехов – т.е. биномиальное распределение: $$bin(K, 1/B) = C^b_K \big(\frac{1}{B}\big)^b\big(1-\frac{1}{B}\big)^{K-b}$$
Биномиальное распределение удобно тем, что про него мы много знаем можем посмотреть в википедии. А именно: среднее значение для него $$\mathbb{E}[b]=\frac{K}{B}$$ (ну, это и так очевидно), а еще я сердцем чую, что нам понадобится дисперсия, так она равна $$\mathbb{D}[b]=\frac{K}{B}(1-\frac{1}{B})$$
Теперь попробуем посчитать среднюю длину успешных и неуспешных поисков.
Я начну с неуспешных, потому что они проще. Если мы ищем произвольный ключ, которого нет в таблице, то чтобы убедиться, что его там нет, нужно перебрать все ключи в той корзинке, в которую нас закинула хэш-функция. Но раз мы предполагаем, что хэш-функция у нас хорошая, а ключ – произвольный, то мы будем равновероятно попадать в корзинки всех существующих в хэш-таблице размеров. А значит среднее количество сравнений, которое потребуется, чтобы не-найти ключ – это просто средний размер корзинки, $$\mathbb{E}[L_u]=\mathbb{E}[b]=\frac{K}{B}$$
Теперь об успешных поисках – это только чуть посложнее. Возьмем случайный ключ из тех, что присутствуют в хэш-таблице. Какова вероятность, что такой ключ окажется из корзинки i? Эта вероятность равна доле всех ключей, которая хэшируется в эту корзинку. Но мы знаем, какие ключи хэшируются в эту корзинку – это те ключи, которые сейчас там лежат. То есть случайно выбранный ключ, из тех, что присутствуют в хэш-таблице, найдется в корзинке i с вероятностью (количество ключей в корзинке i)/(общее количество ключей) = $$\frac{b_i}{K}$$
А сколько сравнений нужно, чтобы найти ключ уже внутри корзинки? В среднем $$\frac{1+2+3+..+b_i}{b_i} = \frac{b_i+1}{2}$$.
Так что среднее количество сравнений по всем ключам получается такое:
$$E[L_s]= \sum_{i=0}^B \frac{b_i}{K}\frac{b_i+1}{2} = \frac{1}{2}\Big(\frac{\sum_{i=0}^Bb_i^2}{K} + \frac{\sum_{i=0}^Bb_i}{K}\Big) = \frac{1}{2}\Big(\frac{B}{K}\frac{\sum_{i=0}^Bb_i^2}{B} + 1\Big) = \frac{1}{2}(\frac{\mathbb{E}[b^2]}{\mathbb{E}[b]}+1) = \frac{1}{2}(\mathbb{E}[b]+\frac{\mathbb{D}[b]}{\mathbb{E}[b]}+1)$$
(Вот ведь не зря сердце чуяло – пригодится, пригодится дисперсия!)
Формула хоть и не идентична формуле из предыдущего поста, но очень похожа. Ключевой элемент "среднее плюс дисперсия деленная на среднее" есть, но еще затесалась лишняя единица. (Я бы хотел сказать, что эта единица тут не важна, но это будет неправдой: как раз здесь она играет свою роль)
Осталось немного позаниматься алгеброй: подставить среднее и дисперсию для биномиального распределения, посчитать отношение $$\frac{\mathbb{E}[L_s]}{\mathbb{E}[L_u]}$$, и сравнить его с единицей:
$$\frac{\mathbb{E}[L_s]}{\mathbb{E}[L_u]}=\frac{\frac{1}{2}(\mathbb{E}[b]+\frac{\mathbb{D}[b]}{\mathbb{E}[b]}+1)}{\mathbb{E}[b]} = \frac{B}{K}+\frac{K+1}{2K} \overset{K \gg 1}{\approx} \frac{B}{K}+\frac{1}{2}$$
(количество ключей K обычно >>1, так что (K+1)/K ~ 1)
Чтобы эта штука была больше единицы, достаточно, чтобы K/B было больше 2. Теперь уже можно ответить на исходный вопрос: если K/B (=load factor) < 2, то успешный поиск в среднем дольше неуспешного, и наоборот
Напомню, что java.util.HashMap
по-умолчанию имеет load factor=0.75 – гораздо ниже порога. То есть все описанное выше применимо к абсолютному большинству хэш-таблиц в любой джава-программе.
Можно прикинуть и во сколько раз больше сравнений нужно будет, в среднем, для успешного поиска при load factor=0.75: 1/0.75+1/2 ~ 1.85, почти в 2 раза
Это гарантированное сравнение, которое присутствует в каждом успешном поиске – это та самая единица в формуле, которая играет свою роль. Если бы ее не было, то эффект все равно проявлялся бы, но только при load factor < 1, и был бы заметно слабее
Насколько теория похожа на симуляцию, видно на вот этом графике. (Мне пришлось построить обратное отношение: не-успешных поисков к успешным – потому что иначе в нуле получается вертикальная асимптота, и такой график неудобно смотреть)
Честно говоря, даже слишком хорошо. На физпрактикум мне такое было бы неловко сдавать – обвинили бы в подгонке :)
Все вышесказанное, конечно, применимо не только к поиску: и обновление, и удаление существующего ключа так же будет (как правило) дольше, чем вставка нового, или попытка удаления не существующего
Если временно оставить в стороне дурацкие шутки про то, что быстрее всего искать в пустой таблице, то окажется, что не очень понятно, что с этим знанием делать. Все выводы получаются если не дурацкие, то точно не практичные. Это только у меня так?
ОтветитьУдалитьНе, у многих так. Математика -- она ж как секс. Хоть иногда и дает практические результаты, но любим мы ее не за это
УдалитьНу а если серьезно, то простых и непосредственных практических выводов из этого я и правда не вижу. Это та информация, которую, как мне кажется, полезно иметь в голове, потому что она может оказаться кирпичиком для понимания более сложных ситуаций.
УдалитьСкажем, JIT при отборе методов для агрессивной оптимизации опирается на частоту вызовов. Когда .equals() будет вызываться чаще (и более вероятно соптимизируется) -- если вы ищете в хэш-таблице ключи, которые там есть, или которые там отсутствуют?
У меня была серия постов и несколько докладов про escape-анализ и скаляризацию, и я разбирал сценарии, где один и тот же код демонстрирует существенно разные показатели производительности, в зависимости от данных, на которых JIT собирал профиль. Вот, например, про хэш-таблицу: https://dev.cheremin.info/2016/10/mapgetnew-compositekeykey1-key2.html -- там как раз результат зависит от вероятности попадания/не попадания в корзинку.
В случае equals() все проще - он вызвается ~1 раз, для любого load factor, для любого успешного поиска, и ~0 раз - для любого неуспешного. Потому что сравнение Node.hash практически исключает вызовы equals() на объектах которые на самом деле не эквивалентны.
Удалитьда, ты прав, я совсем забыл про эту ветку
Удалить