Детерминированный ключ сериализации

Question

Я пишу класс сопоставления, который сохраняется на диске. В настоящее время я разрешаю только ключи str, но было бы неплохо, если бы я мог использовать еще пару типов: возможно, до всего, что можно хэшировать (т. Е. Те же требования, что и для встроенного dict), но более разумно, я бы принял строку , unicode, int и кортежи этих типов.

С этой целью я хотел бы вывести детерминистическую схему сериализации.

Вариант 1 - травление ключа

Первой мыслью было использовать модуль pickle (или cPickle) для сериализации ключа, но я заметил, что выходные данные pickle и cPickle не соответствуют друг другу:

>>> import pickle
>>> import cPickle
>>> def dumps(x):
...     print repr(pickle.dumps(x))
...     print repr(cPickle.dumps(x))
... 
>>> dumps(1)
'I1\n.'
'I1\n.'
>>> dumps('hello')
"S'hello'\np0\n."
"S'hello'\np1\n."
>>> dumps((1, 2, 'hello'))
"(I1\nI2\nS'hello'\np0\ntp1\n."
"(I1\nI2\nS'hello'\np1\ntp2\n."

Существует ли какая-либо комбинация реализации / протокола pickle, которая является детерминированной для некоторого набора типов (например, можно использовать cPickle только с протоколом 0)?

Вариант 2 - Repr и ast.literal_eval

Другой вариант - использовать repr для сброса и ast.literal_eval для загрузки. Я написал функцию, чтобы определить, выживет ли данный ключ в этом процессе (он довольно консервативен для типов, которые он позволяет):

def is_reprable_key(key):
    return type(key) in (int, str, unicode) or (type(key) == tuple and all(
        is_reprable_key(x) for x in key))

Вопрос для этого метода заключается в том, является ли repr сам по себе детерминированным для типов, которые я здесь разрешил. Я считаю, что это не выдержит барьер версии 2/3 из-за изменения литералов str / unicode. Это также не будет работать для целых чисел, где 2**32 - 1 < x < 2**64 переходит между 32 и 64-битными платформами. Существуют ли другие условия (т. Е. Строки по-разному сериализуются при разных условиях в одном и том же интерпретаторе)? Редактировать: Я просто пытаюсь понять условия, которые это нарушает, не обязательно преодолевать их.

Вариант 3: Пользовательский репр

Другой вариант, который, вероятно, излишний, - написать свой собственный repr, который сглаживает вещи repr, с которыми я знаю (или подозреваю, что это может быть) проблема. Я только что написал пример здесь: http://gist.github.com/423945

(Если все это с треском проваливается, тогда я могу сохранить хэш ключа вместе с указателем ключа и значения, а затем перебрать строки, в которых есть совпадающий хеш, ища тот, который распределяется по ожидаемому ключу, но это действительно усложняет некоторые другие вещи, и я бы предпочел этого не делать. Редактировать: Оказывается , что встроенный hash также не является детерминированным на разных платформах. Поцарапайте это.)

Есть идеи?

Answer 1

Важное замечание: repr() не является детерминированным, если в объект, который вы пытаетесь сериализовать, встроен словарь или тип набора. Ключи могут быть напечатаны в любом порядке.

Например, print repr({'a':1, 'b':2}) может распечатываться как {'a':1, 'b':2} или {'b':2, 'a':1}, в зависимости от того, как Python решает управлять ключами в словаре.

Answer 2

Прочитав большую часть исходного кода (CPython 2.6.5) для реализации repr для основных типов, я пришел к выводу (с достаточной уверенностью), что repr этих типов фактически является детерминированным. Но, честно говоря, это было ожидаемо.

Я считаю, что метод repr восприимчив к почти всем тем же случаям, при которых метод marshal выходит из строя (long s> 2 ** 32 никогда не может быть int на 32-битном машина, не гарантируется не переходить между версиями или интерпретаторами, и т. д.).

В настоящее время я решил использовать метод repr и написать всеобъемлющий набор тестов, чтобы убедиться, что repr возвращает одинаковые значения на различных платформах, которые я использую.

В долгосрочной перспективе пользовательская функция repr сгладит все различия между платформами и реализациями, но, безусловно, излишне для рассматриваемого проекта. Я могу сделать это в будущем, однако.

Answer 3

«Любое значение, которое является приемлемым ключом для встроенного dict», неосуществимо: такие значения включают произвольные экземпляры классов, которые не определяют __hash__, или сравнения, неявно использующие их id для целей хеширования и сравнения, и значения id не будут одинаковыми даже для всех прогонов одной и той же программы (если только эти прогоны не являются строго идентичными во всех отношениях, что очень сложно организовать - идентичные входные данные, идентичные времена запуска, абсолютно идентичная среда, и т. д.)

Для строк, юникодов, целых чисел и кортежей, чьи элементы являются всеми этими видами (включая вложенные кортежи), может помочь модуль marshal (в пределах одной версии Python: код маршалинга может и действительно изменяется по всем версиям). E.g.:

>>> marshal.dumps(23)
'i\x17\x00\x00\x00'
>>> marshal.dumps('23')
't\x02\x00\x00\x0023'
>>> marshal.dumps(u'23')
'u\x02\x00\x00\x0023'
>>> marshal.dumps((23,))
'(\x01\x00\x00\x00i\x17\x00\x00\x00'

Это Python 2; Python 3 будет аналогичным (за исключением того, что все представления этих байтовых строк будут иметь начальный b, но это косметическая проблема, и, конечно, u'23' становится недопустимым синтаксисом, а '23' становится строкой Unicode). Вы можете увидеть общую идею: ведущий байт представляет тип, такой как u для строк Unicode, i для целых чисел, ( для кортежей; затем для контейнеров следует (как целое число с прямым порядком байтов) число элементов, за которыми следуют сами элементы, и целые числа сериализуются в форму с прямым порядком байтов. marshal предназначен для переноса между платформами (для данной версии; не для разных версий), поскольку он используется в качестве основной сериализации в скомпилированных файлах байт-кода (.pyc или .pyo).

Answer 4

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

• Вы создаете серверную часть SQLite для словаря.
• Вы хотите, чтобы ключи были больше, чем тип базовой строки (какие типы).
• Вы хотите, чтобы он пережил барьер Python 2 -> Python 3.
• Вы хотите поддерживать большие целые числа выше 2 ** 32 в качестве ключа.
• Возможность хранить бесконечные значения (потому что вы не хотите коллизий хешей).

Итак, вы пытаетесь создать общее решение «это может сделать все» или просто пытаетесь решить непосредственную проблему, чтобы продолжить работу в текущем проекте? Вам нужно потратить немного больше времени, чтобы составить четкий набор требований.

Использование хэша показалось мне лучшим решением, но потом вы жалуетесь, что у вас будет несколько строк с одинаковым хешем, что означает, что вы будете хранить достаточно значений, чтобы беспокоиться о хэше. *