== забудь слово Ошибка
https://youtu.be/5iygkx-XfrY

Mypy 0.981 Released

из всего списка мне зашло
import TypedDict from typing
и
интерфейс из протокола
остальное просто улучшения

== Updates about mypy, an optional static type checker for Python
https://mypy-lang.blogspot.com/2022/09/mypy-0981-released.html

весь список:
- Support for Python 3.6 and 2 Dropped
- Generate Error on Unbound TypeVar Return Type
- Methods with Empty Bodies in Protocols Are Abstract
- Implicit Optional Types Will Be Disabled by Default
- Experimental Support for General Recursive Types
- Generic NamedTuples and TypedDicts
- Better Support for Callable Attributes

== вполне. советую
https://youtu.be/gOB3hpAVIIQ

- Транзакция, транзакционная база данных
- Расшифровка ACID
- Atomicity (атомарность)
- Consistency (консистентность)
- Isolation (изоляция)
- Read committed
- Snapshot isolation (repeatable read)
- Демонстрация отличий read committed и repeatable read на примере MySQL
- MVCC
- Проблема lost update
- Durability

Так как я уже не могу закончить этот пост неделю, напишу, что есть. Главное -- писать, остальное не так важно.

Что такое хорошая хеш-функция?

Этот вопрос на первый взгляд всегда кажется более научным, чем практическим. Да, в теории есть какие-то критерии. Даже пытались выстроить 5 уровней хэш-функции. Что взломать сложно или какие-то c-way-collisions найти очень быстро нельзя.

Криптографические хэши очень давно устоялись в индустрии и если перформанс для вас не так важен, SHA-3 и вперед.

В науке практически ничего невозможно доказать про хэш-функции кроме universal hashing, поэтому индустрия здесь надеется на смысл, чтобы хоть как-то предсказать хэши было сложно в случае хэш-таблиц.

И я тут даже не хочу говорить о каких-то хэшах типа MurMur, Farmhash, Cityhash, Wyhash, и тд. Если вам интересно, можете посмотреть их сравнение на smhasher: этот репозиторий кстати очень недооценён, сравнивать хэш-функции на коллизии, случайность стоит, а вот мало кто такой неблагодарной работой занимается.

Вопрос, который я решал последние пару месяцев и о котором я всё не мог написать, а как находить хэш-функции с хорошим распределением и ещё желательно, чтобы они были быстрыми?

Мир как-то слишком мало ответов знает на этот вопрос. Можно даже проще сформулировать: даны не более 16 байт (hi, lo) и длина, какое минимальное количество инструкций надо, чтобы получить хороший хэш?

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

А что важно хэштаблице? Коллизии, потом скорее усложнение их поиска и чтобы "на проде" работало нормально. Коллизии чаще встречаются на размерах степеней двойки, как делают, скажем flat_hash_* в Abseil и Folly. Поэтому важно, чтобы нижние биты не сильно совпадали даже если нет коллизий :)

Итак, у нас есть хэш таблицы, у них не очень большие ключи и просто туча применений.

Попытка 1: crc

Инструкции CRC32 впаяны прям в процессоры x86 и Arm. Хоть это вычисление достаточно быстрое, CRC32C никогда не был сделан для хэш-таблиц, падает статистические тесты. Достаточно много коллизий, когда данные не слишком отличаются, это фактически означает, что если вы будете добавлять какие-нибудь указатели или числа/строки с одинаковым суффиксом, то коллизий будет достаточно много.

Этот факт я не особо знал. а вот ClickHouse повсеместно использует crc для хешей, можно идти ломать их join или что-нибудь ещё 😊 (не проверял, terms and conditions apply).

Ещё один страшный факт, что даже 64 битные crc32 инструкции возвращают 32 бита, если ваша хэштаблица приближается к 2^26 элементов, коллизий будет уже очень много.

Попытка 2: 128 битное умножение

Мы в abseil выбрали approach слегка другой, а название ему 128 битное умножение

(seed + number) * prime_number

Далее это число 128 битное, сделаем xor верхней и нижней части, это будет хэш для 8 байт. Для 16 повторить ещё раз c верхней частью и seed как результат нижней части.

На удивление это имеет достаточно хорошее распределение.

Зачем делать xor? Потому что если seed+number чётное, то умножение будет очень предсказуемым и нижние биты предсказуемы чаще. Считается, что при умножении средние и верхние биты числа не очень предсказуемы. Это хорошо на практике показано у PCG-random. Поэтому разбавить нижние биты всегда нужно чем-то.

Похожую идею можно увидеть даже у MurMur:

uint64_t fmix64 ( uint64_t k )
{
k ^= k >> 33;
k *= BIG_CONSTANT(0xff51afd7ed558ccd);
k ^= k >> 33;
k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
k ^= k >> 33;
return k;
}

Попытка 3: перебор

Для 16 байт мы знаем, что есть хэш функция с хорошим распределением в 6 инструкций. Вопрос, а какое минимальное? Можно взять какой-нибудь set и перебрать. Вопрос в том, какие данные брать: я решил брать около 1000 входов, где есть случайные числа и все их соседи, где отличаются на 2 бита.

3 инструкции не работают совсем, лучшая 4 инстручная последовательность

r0 = hi - seed;
r1 = lo + 0x71b1a19b907d6e33;
r2 = r0 * r1;
r3 = r2 ^ r2_hi;
return r3;

Ломается на распределениях побольше. Всего перебор дал где-то 40 вариантов, все сломались на бОльших распределениях.

Можно перебирать 5 инструкций, но количество операций уже растёт слишком экспоненциально. На каждом шаге выбор где-то из 100 вариантов (все пары переменных * операции (+-^*,shift,rotate,crc,&,|)), в итоге даже если не разрешать все сдвиги или rotate, получается много. 115^n примерно, где n количество инструкций, на каждую итерацию надо проверить около 1000 входов на коллизии, что достаточно затратно. В итоге для n = 5, 10^15-10^16 итераций, ну можно запустить map reduce pipeline на часы. Ура, нашли 25k вариантов.

Дальше я пока сдался, потому что ощущение, что я схожу с ума. Чтобы отсеивать дальше, надо уметь больше распределений или запускать прям smhasher на все найденные.

Ну либо пойти к DeepMind, пусть их RL штуки находят хэш функции, наверное, можно поумнее.

Но мне кажется я вот вот либо докажу, что не существует хорошей 5 инстручной хеш функции для 16 байт, либо найду её наконец-то. Даже если все найденные свалятся, то никто не знает, может, я просто не добавил нужную инструкцию в перебор.

Мораль: перебирать ассемблер адски тяжело. Отсеивать плохие хэш-функции быстро адски тяжело. Ускорения в оба направления могут помочь нам дать лучшие хэш-функции. Пока вопрос открыт. Продолжаю рисёрч.

Сходство строк в Python

Метод ratio() возвращает меру подобия/схожести последовательностей в виде числа с плавающей точкой в диапазоне [0, 1].

Почему такой штуки у меня не было когда работал в КонструкторскомБюро ? Потому что бомж
https://youtu.be/u_Z3c9DXY4A

​Чего его не любить? Хороший язык программирования...

#кек #twitter

Повторение мать...
https://youtu.be/qb6l4B57Qmw

Знакомьтесь с генеративной архитектурой. Наконец-то можно будет выбирать дизайн шаурмичной по своему вкусу.

Если честно, это лучшее, что происходило с графикой за последнее время.

С нетерпением жду, когда всё это перейдёт в объём и будет продакшн реди.

== Тесты статистической проверки принадлежности нормальному распределению Python
https://telegra.ph/Testy-statisticheskoj-proverki-prinadlezhnosti-normalnomu-raspredeleniyu-Python-10-13
- Тест Шапиро-Уилка
- Тест Колмогорова-Смирнова
- Тест Андерсона-Дарлинга
- Тест Лиллиефорса
- Критерий К-квадрата Д'Агостино
- Тест Харке-Бера

Проверяем, является ли заданная дата – праздником

Установка модуля - pip install holidays

В нашем примере мы проверяем является ли 25 декабря 2021 в Великобритании праздником. Наша программа выдает нам, что в этот день отмечается Рождество.

Подробнее про данный модуль можно почитать здесь.

Порядок разрешения методов

В Python существует так называемый Method Resolution Order (MRO), или порядок разрешения методов в классе. Всё, что вам нужно знать – это порядок, в котором Python ищет нужный атрибут или метод.

Этот порядок можно получить при помощи атрибута __mro__. Он говорит о том, что если мы в примере выше попробуем обратиться к атрибуту value, Python будет искать сначала в классе A, далее в B, затем в C и в самом конце в object.

Отсюда становится понятно, что артибут первее будет найден именно в классе B и равен он будет значению 1.

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

Требования росли, растут, и будут расти. Ну либо пишите на WordPress )))

Кажись, прощай Убунта) и XFCE. последние Кеды прям огонь

== Как поставить и насроить базовые пакеты в Монжаро. https://youtu.be/MH68As9TMKE

🛠 Инструмент для визуализация связей и структуры в базе данных, поддерживающий более 20 разных БД. Доступен как онлайн, так и для установки на собственном сервере:

- Онлайн: https://sqlflow.gudusoft.com/
- Селфхост: https://github.com/sqlparser/sqlflow_public/blob/master/install_sqlflow.md

#линк #sql

== The Art of Logging
https://betterprogramming.pub/creating-a-human-and-machine-freindly-logging-format-bb6d4bb01dca

еще один сервис по анализу EXPLAIN
https://explain.tensor.ru/about/#expanded

== Understanding a Kernel Oops!
https://www.opensourceforu.com/2011/01/understanding-a-kernel-oops/