Хорошо, был виноват действительно meson. add_project_arguments("-fsanitize=address") честно не знаю, что делает, но до линкера флаг не доходит. Решением стало продублировать его в add_project_link_arguments()

Хэш-функция wyhash используется по-умолчанию в Зиге, Ниме и Го (начиная с 1.17), и считается одной из самых быстрых. И насколько же ржачная у автора почта)

На этом всё не кончается. Он просто взял и назвал презервативом🗿

При том, что он даже в описании упомянул слово protects!! Какой-то итальянец, который сделал rapidhash как эволюцию wyhash'a, тоже назвал это PROTECTED. НО КИТАЙЦУ ПОХУЙ, У КИТАЙЦА CONDOM

Чувак работает в Fudan University в Шанхае. Просто приходит, с Даниэлем Лемайром casually drops SotA хэшфункцию, даже лицензию никакую не ставит. И уходит.

Я ж сука уверен, у него есть красивенькая университетская почта. Но китайцу похуй. Китаец гоняет с godspeed_china@yeah.net.

Я им восхищаюсь.

Прекрасно. Я перепутал разделы и вхуярил образ никса в свой рут вместо флешки🗿

То-то ещё сука думаю, хули этот задохлик вдруг стал 70мб/с на запись выдавать блять

Просыпаюсь, пробуждаю эту шайтан-машину. Кеды по классике решили умереть, только теперь окончательно: даже в тту переключиться нельзя. Понимая, что чинить это можно только ребутом, а с некоторых пор я больше никогда не смогу обратно в систему бутнуться, с утрешнего нераздупля пришлось таки садиться и ставить этот никс.

Загружаюсь во флешку. Загружается, но зависает после сообщения о попытке поднять systemd-udevd. Посидев пару минут, начинаю осознавать, что мой образ битый, а старой системы больше-то и нет, чтобы залить чем-то другим.

Но вспоминаю, что, слава богу, у меня на втором м2 ссд ещё винда есть. Перезагружаюсь, тыкаю в биосе сначала на первый м2. Загружается установщик никса...

Пытаюсь ещё раз. Бутаюсь во второй м2 ссд в списке. Загружается установщик никса...

Вытаскиваю флешку, ребутаюсь. Загружается установщик никса...

Вот тут я конкретно охуел. Что бы я не делал, эта транзисторная рисоварка всё равно грузится в установщик никса. При том хорошо, если бы он ещё работал

А ответ, кстати, оказался довольно прост: вот как раз те 2.5 гига, которые я случайно на ссд заебашил, как раз и загружались. По крайней мере, хорошая новость - мне больше не нужна будет флешка

Отдельно хочу поблагодарить разработчикам balenaEtcher. Эти ребята умудрились поломать код в дистрибуции для армов. Пришлось кочегарить розетту, потому что в арме оно ныло на (0, h.requestMeta) is not a function. х86 версия, кстати, сработала без нареканий по функционалу - гуй тормозной был, правда, ну просто жуть.

Я снова буду программировать

Цитаты великих

Способы разрешения коллизий

В продолжение темы о хэшмапах, как структура данных таковые полагаются полностью на хэшфункцию - что логично. Но поскольку коллизии в общем случае неизбежны (исключения - идеальные хэш- и identity-функции), то их разрешать как-то всё равно да и приходится. И основополагающих принципа существует всего два:

1) Закрытая адресация (она же separate chaining) - способ был впервые описан во внутреннем меморандуме в IBM в 1953 году. Это как раз классическая схема, которая была использована и в старой гошной мапе. Базовый случай - хэшфункцией мы адресуем связной список из вхождений (вхождение есть пара ключ-значение), где уже линейно искомое значение и ищем. Гошная мапа просто немного уменьшила футпринт за счёт связного списка бакетов, где бакет держит сразу до 8 вхождений, и сравнения по верхушке хэша, что даёт хороший бонус для значений, у которых операция сравнения является довольно дорогой (те же строки).

2) Открытая адресация - появилась чуть позже, пускай и с разницей всего в пару лет (что неудивительно - основой послужил как раз-таки тот самый меморандум с закрытой адресацией). В ней больше не используется концепция двухмерного массива, и заместо все значения лежат в одном большом массиве (где вхождения называют слотами). Само разрешение коллизий тогда работает достаточно просто - всё так же адресуем слот в массиве по хэшу, и если он нам не подходит (для вставки - уже оккупирован, для лукапа - не совпадает ключ), тогда мы просто идём дальше и смотрим следующий слот. Правда, как именно мы выбираем следующий слот - тоже тема для отдельного разговора: есть linear probing, когда мы сдвигаем индекс слота на константу (обычно 1), есть quadratic probing, когда мы, соответственно, сдвигаем индекс уже на результат какого-нибудь квадратического уравнения. Есть совсем уж страшное double hashing, когда сдвиг разрешается второй хэш-функцией. Суть методов quadratic probing и double hashing заключается исключительно в том, чтобы снизить так званую кластеризацию - неравномерное распределение элементов, когда они скапливаются на каком-то одном промежутке (double hashing даёт наилучший результат, но по производительности самый худший, а вот quadratic probing есть золотая середина с достаточно тонко подобранными значениями). Плоха кластеризация тем, что без перебора слотов в общем случае не обойтись, а это линейная сложность - всё-таки хотелсь бы амортизированную константу, пускай качество самой хэш-функции и отыгрывает здесь гораздо большую роль - но мир, увы, не идеален.


Конечно, помимо вышеперечисленных двух способов, существуют и другие разновидности (Coalesced hashing, Cuckoo hashing, Hopscotch hashing, Robin Hood hashing), но все они, так или иначе, основываются на открытой адресации.


Фанфакт: "открытая адресация" открытая потому, что все элементы вот у нас в одном массивчике как надо лежат, и мы по ним по всем проходимся, когда как при закрытой адресации все слоты находятся в отдельной структуре данных, виртуально не имеющего ничего общего с массивом этих самых слотов. То есть, при открытой адресации мы адресуем слот со значением, а при закрытой - коробочку, по которой дальше уже как-то сам ходи ищи-свищи.

Swissmap, на которую сейчас в го переходят, кстати, тоже есть таблицей на открытой адресации. Только они добавили ещё так званую метадату - отдельный (на самом деле, не очень) массив чаров, что и обращения к памяти более локализирует (более кэш-френдли => гуд), и по которой sse инструкциями гулять можно. В общем - быстро и красиво. Но сложна.

В комментариях я сказал, что при близкой к полной заполненности операция сопоставления или вставки в открытую хэш-таблицу может никогда не завершиться. Логично, ведь если таблица полностью заполнена - мы никогда не наткнёмся на свободный слот, который и является маркером "дальше ходу нет" (куда пишем при вставке, и при котором отчитываемся об обсутствии вхождения при сопоставлении).

Это решается счётчиком просмотренных слотов. Но этот способ интересен тем, что ограничение количества попыток нахождения слота также является один из способов борьбы с кластеризацией. Если я правильно понял, то если вставка валится из-за того, что свободный слот не был найден в промежутке i..i+n (где n - максимальное количество тех самых попыток, или же просмотра слотов), то мапа инициирует ресайз.

ПыСы забыл добавить линк на описание способов открытой адресации, только более формальным языком: https://math.gsu.by/wp-content/uploads/courses/structure/L8.6.4.html

Tariff: A Python package that imposes tariffs on Python imports
Article, Comments