Hash + mapping или index + mapping для сжатия использования строк - PullRequest
0 голосов
/ 02 ноября 2010

У меня есть ~ 200K именованных свойств и ~ 25K файлов. Я извлекаю, сохраняются ли свойства для каждого файла, используя Python в качестве набора свойств, один набор для каждого файла.

Чтобы выполнить это извлечение, я мог бы параллельно запускать сотни отдельных сценариев извлечения Python на вычислительной ферме. Каждый из них оставляет некоторое представление об извлечении множества из каждого файла.

Дальнейшая обработка включает чтение этих наборов 20K и обработку накопленных данных. создать отчет по этому набору файлов / свойств.

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

Я думал о создании центрального индекса отсортированных имен свойств и просто сохранении индекса - то же самое для имен файлов, как и для файлов .py для импорта.

Альтернативой использованию индекса в отсортированном списке имен было бы использование значения str. hash () в качестве индекса, что означало бы, вероятно, более быструю обработку, но меня беспокоит возможность две неравные строки, заканчивающиеся одинаковым значением hash (). Может ли это случиться?

Я бы использовал один и тот же исполняемый файл Python и версию ОС на всех машинах.

Ответы [ 2 ]

2 голосов
/ 02 ноября 2010

Знаете ли вы свойства заранее? Если вы сделаете это, вы, возможно, захотите рассмотреть Идеальное хеширование (т.е. вы можете распространять настройки хэша вместо полного списка свойств / файлов).

Очень грубый (но, возможно, работающий способ) будет иметь несколько различных хеш-функций (h1, h2 ...); начать, например с помощью str.hash () и вычислите хэши. Если есть столкновения, попробуйте использовать кортеж (h1 (свойство), h2 (свойство)) в качестве хеша. Если коллизии все еще существуют, используйте (h1 (свойство), h2 (свойство), h3 (свойство)) и т. Д. До тех пор, пока коллизий не будет. Функции h_x могут быть в некоторой степени настраиваемой функцией, и рекомендованным способом было бы попробовать некоторые случайные хеш-функции.

Однако мне кажется, что это может быть излишним, просто распространять список файлов / свойств может быть намного проще ...

0 голосов
/ 02 ноября 2010

Хеши могут сталкиваться. Вы должны учитывать это.

...