Почему в хэше бесконечности Python есть цифры π?
Хэш бесконечности в Python имеет цифры, соответствующие Пи:
>>> inf = float('inf')
>>> hash(inf)
314159
>>> int(math.pi*1e5)
314159
Это просто совпадение или это намеренно?
Кажется, однажды кто-то был в легкомысленном настроении. Но почему нет?
Спросите Тима Питерса. Вот коммит, в котором он представил эту константу 19 лет назад: github.com/python/cpython/commit/…. Я сохранил эти специальные значения, когда перерабатывал числовой хэш в bugs.python.org/issue8188.
@MarkDickinson Спасибо. Похоже, что Тим, возможно, также использовал цифры е для хэша -inf.
@wim Ах да, правда. И, видимо, я изменил это на -314159. Я забыл об этом.
Ответы 3
_PyHASH_INF равно определяется как константа314159.
Я не могу найти никаких обсуждений по этому поводу или комментариев с указанием причины. Думаю, он был выбран более или менее произвольно. Я предполагаю, что пока они не используют одно и то же значимое значение для других хэшей, это не должно иметь значения.
Небольшая придирка: почти неизбежно по определению, что одно и то же значение будет использоваться для других хэшей, например. в этом случае hash(314159) также 314159. Также попробуйте в Python 3 hash(2305843009214008110) == 314159 (это ввод 314159 + sys.hash_info.modulus) и т. д.
@ShreevatsaR Я просто имел в виду, что до тех пор, пока они не выбирают это значение как хэш других значений по определению, выбор такого значимого значения не увеличивает вероятность коллизий хэшей.
Резюме: Это не совпадение; _PyHASH_INF жестко запрограммирован как 314159 в реализации Python по умолчанию на CPython и было выбрано как произвольное значение (очевидно, из цифр π) Тим Питерс, 2000 г..
Значение hash(float('inf')) является одним из системно-зависимых параметров встроенной хеш-функции для числовых типов, а также доступен как sys.hash_info.inf в Python 3:
>>> import sys
>>> sys.hash_info
sys.hash_info(width=64, modulus=2305843009213693951, inf=314159, nan=0, imag=1000003, algorithm='siphash24', hash_bits=64, seed_bits=128, cutoff=0)
>>> sys.hash_info.inf
314159
(Те же результаты с PyPy тоже.)
С точки зрения кода, hash — это встроенная функция. Вызов его для объекта с плавающей запятой Python вызывает функцию, указатель которой задается tp_hash атрибут встроенного типа с плавающей запятой (PyTypeObject PyFloat_Type), где является является функцией float_hash, определенный как return _Py_HashDouble(v->ob_fval), который, в свою очередь, имеет
if (Py_IS_INFINITY(v))
return v > 0 ? _PyHASH_INF : -_PyHASH_INF;
где _PyHASH_INF — определяется как 314159:
#define _PyHASH_INF 314159
С точки зрения истории, первое упоминание 314159 в этом контексте в коде Python (вы можете найти это с помощью git bisect или git log -S 314159 -p) было добавлено Тим Питерс в августе 2000 года, в том, что сейчас является коммитом 39dce293 в cpython репозитории git.
В сообщении коммита говорится:
Fix for http://sourceforge.net/bugs/?func=detailbug&bug_id=111866&group_id=5470. This was a misleading bug -- the true "bug" was that
hash(x)gave an error return whenxis an infinity. Fixed that. Added newPy_IS_INFINITYmacro topyport.h. Rearranged code to reduce growing duplication in hashing of float and complex numbers, pushing Trent's earlier stab at that to a logical conclusion. Fixed exceedingly rare bug where hashing of floats could return -1 even if there wasn't an error (didn't waste time trying to construct a test case, it was simply obvious from the code that it could happen). Improved complex hash so thathash(complex(x, y))doesn't systematically equalhash(complex(y, x))anymore.
В частности, в этом коммите он выдрал код static long float_hash(PyFloatObject *v) в Objects/floatobject.c и сделал просто return _Py_HashDouble(v->ob_fval);, а в определение long _Py_HashDouble(double v) в Objects/object.c добавил строчки:
if (Py_IS_INFINITY(intpart))
/* can't convert to long int -- arbitrary */
v = v < 0 ? -271828.0 : 314159.0;
Как уже упоминалось, это был произвольный выбор. Обратите внимание, что 271828 формируется из первых нескольких десятичных цифр е.
Связанные более поздние коммиты:
Марк Дикинсон, апрель 2010 г. (также), заставляя тип
Decimalвести себя аналогичноМарк Дикинсон, апрель 2010 г. (также), перенос этой проверки наверх и добавление тестовых случаев
Марк Дикинсон, май 2010 г. как выпуск 8188, полностью переписывая хеш-функцию на его текущая реализация, но сохраняя этот особый случай, давая константе имя
_PyHASH_INF(также удаляя 271828, поэтому в Python 3hash(float('-inf'))возвращает-314159, а не-271828, как в Python 2)Рэймонд Хеттингер, январь 2011 г., добавив явный пример в «Что нового» для Python 3.2 из
sys.hash_info, показывающий указанное выше значение. (См. здесь.)Стефан Кра, март 2012 г. изменяет модуль Decimal, но сохраняет этот хэш.
Кристиан Хаймс, ноябрь 2013 г. переместил определение
_PyHASH_INFизInclude/pyport.hвInclude/pyhash.h, где оно теперь живет.
Выбор -271828 для -Inf устраняет любые сомнения в том, что ассоциация pi была случайной.
@RussellBorogove Нет, но это делает это примерно в миллион раз менее вероятным;)
@cmaster: см. часть выше, где говорится о мае 2010 года, а именно раздел документации по хеширование числовых типов и выпуск 8188 — идея в том, что мы хотим, чтобы hash(42.0) было таким же, как hash(42), а также таким же, как hash(Decimal(42)), hash(complex(42)) и hash(Fraction(42, 1)). Решение (от Марка Дикинсона) является элегантным IMO: определение математической функции, которая работает для любого рационального числа, и использование того факта, что числа с плавающей запятой также являются рациональными числами.
@ShreevatsaR Ах, спасибо. Хотя я бы не стал гарантировать эти равенства, приятно знать, что есть хорошее, надежное и логичное объяснение кажущемуся сложным коду :-)
@cmaster На самом деле это необходимость. Хэшируемые объекты, которые сравниваются равными, должны иметь одинаковое хеш-значение.
@cmaster Хэш-функция для целых чисел — это просто hash(n) = n % M, где M = (2 ^ 61 - 1). Это обобщается для рационального n на hash(p/q) = (p/q) mod M с интерпретацией деления по модулю M (другими словами: hash(p/q) = (p * inverse(q, M)) % M). Причина, по которой мы хотим этого: если в диктофон d мы поместим d[x] = foo, а затем получим x==y (например, 42,0 == 42), но d[y] не то же самое, что d[x], тогда у нас будет проблема. Большая часть кажущегося сложным кода возникает из-за самой природы формата с плавающей запятой, для правильного восстановления дроби и необходимости специальных случаев для значений inf и NaN.
Конечно,
sys.hash_info.inf
возвращается 314159. Значение не генерируется, оно встроено в исходный код.
Фактически,
hash(float('-inf'))
возвращает -271828 или приблизительно -e в python 2 (сейчас -314159).
Тот факт, что два самых известных иррациональных числа всех времен используются в качестве хеш-значений, делает это совпадением маловероятным.
Не уверен, но я предполагаю, что это так же преднамеренно, как
hash(float('nan'))быть0.