?

Log in

No account? Create an account
 
 
06 June 2009 @ 11:28 am
Алгоритмы и программирование  
Не знаю, много ли профессионалов (или любителей :) ) в этой области среди моих читателей - не оные пожалуйсти пропустите.

Решаю одну проблему по работе и вот такая задачка получилась:

Задача: Нужно построить функцию отображающую исходное множество s которое есть подмножество S (cм. дальше) в множество t целых чисел от нуля до сравнительно небольшого tmax (в моем случае tmax равно или 128 или 256 или, может, 64).
S – два варианта: или 64-битные двоичные слова (то есть, числа от 0 до 2**64) или последовательности символов – слова (длинну можно ограничить).
s – подмножество S размером порядка 20 милионов элементов.
Если аргумент не принадлежит множеству s, результат нас не интересует и может быть любым.
И – требования к функции:
1. Время на одно вычисление должно быть небольшим: сравнимым, скажем, с использованием хеш-таблицыю
2. Размер программы (код и данные) должен минимален - критичен. Скажем, значетельно меньше чем объем всех значений S.
3. Времы построения функции некритачно, но должно быть прктически применимым. Скажем несколько минут на современном компьютере – годится.

С первого взгляда, можно, вроде, построить perfect hash – и сделать хеш-таблицу размером 20Mbytes со всеми значениями t. Если верить статьям (которые я внимательно еще не прочитал), perfect hash функция будет стоить еще 10 – 20 Mbytes (хотя я не уверен, насколько это гарантировано, в особенности буз использования алгоритмов с экспоненциальной оценкой).
Интересно, нельзя ли меньше.

Постановка то очевидная – наиболее компактная кодировка функции, буз требования проверки области определения. Но скорость вычисления должна быть не очень плохой. C*N; C*log(N), возможно, тоже подойдет. Может это известная задача, никто не знает?

Для tmax = 1 - задача, кстати тоже может оказаться полезной: упакованная форма предиката при гарантии, что он будет вычисляться для значений аргумента, принадлежащих к области определения.