https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=9193&view=findpost&p=90290 Sat, 30 Aug 2003 07:21:29 +0000 https://forum.sources.ru/index.php?showtopic=9193&view=findpost&p=90290 То есть никто не заставляет сразу заполнять весь массив. При промахе заполняй нужную ячейку вычисленным значением. Ещё можно при промахе проделывать некоторую фиксированную операцию над хэшем и перепроверять ячейку по новому адресу. Сколько раз это делать -- зависит от отношения скоростей вычисления хэша и вычисления собственно функции.
Способ эффективнее вряд ли возможен. Можно, конечно, завести массив на 2^34 байт, но сомнительно, что у тебя 16Гб памяти  ;)
Да, и если можно как-то разделить аргументы по предполагаемой частоте использования -- так и вообще замечательно. Но не всегда возможно  :(]]> sector Алгоритмы https://forum.sources.ru/index.php?showtopic=9193&view=findpost&p=90289 Fri, 29 Aug 2003 23:23:48 +0000 https://forum.sources.ru/index.php?showtopic=9193&view=findpost&p=90289 Имеется довольно долго вычисляемая функция f(x), x - дворд, функцию эту считать надо очень-очень много раз в секунду, причем довольно часто для одних и тех же значений x, не подскажут ли знающие люди хороший способ организации кэша значений f(x) для ускорения вычислений?

Имеется следующий алгоритм(прочитал в какой-то доке по архиваторам): сочиняем простую хэш-функцию h(x), возвращающую значение в интервале от 0 до H и массив C[0..H] содержащий в каждом элементе пару (x, y = f(x)) причем h(C[i].x) == i

Т.е. когда надо посчитать значение f(x) находим элемент C[h(x)] и проверяем, действительно ли C[h(x)].x == x, если да - соответственно берем значение из кэша C[h(x)].y, если нет, имеем типа кэш-промах, считаем f(x) напрямую.
Так вот я думаю может получше способы есть, а? Заранее спасибо.]]> Ivan_Govnoff Алгоритмы