Разреженный массив O (1) с индексами, являющимися последовательными продуктами

Question

Я бы хотел предварительно вычислить массив значений некоторой унарной функции f.

Я знаю, что мне понадобятся только значения для f(x), где x имеет вид a*b, где оба значения a и b являются целыми числами в диапазоне 0..N.

Очевидный оптимизированный по времени выбор - просто создать массив размером N*N и просто предварительно рассчитать только те элементы, которые я собираюсь прочитать позже. Для f(a*b) я бы просто проверил и установил tab[a*b]. Это самый быстрый из возможных методов, однако он займет много места, так как в этом массиве много индексов (начиная с N+1), которые никогда не будут затронуты.

Другое решение - создать простую древовидную карту ... но это сильно замедляет сам поиск очень , вводя множество ветвей. Нет.

Интересно - есть ли решение сделать такой массив менее разреженным и меньшим, но все же быстрым O (1) без ветвления при поиске?

редактировать

Я могу услышать много комментариев о хэш-карте ... Я перейду к тесту, как он ведет себя (Я ожидаю значительного падения производительности по сравнению с обычным поиском из-за ветвления; меньше, чем в деревьях, но все же. .. посмотрим, прав ли я!) .

Я хотел бы подчеркнуть: я бы в основном оценил аналитическое решение , в котором бы использовался какой-то умный способ (?), Чтобы воспользоваться тем фактом, что используются только индексы "продукта". Я чувствую, что этот факт может быть использован для получения лучшего результата, чем обычная функция хэш-карты, но я сам вне идей.

редактировать

Следуя вашим советам, я попробовал std::unordered_map из gcc 4.5. Это было немного медленнее, чем простой поиск в массиве, но на самом деле намного быстрее, чем основанный на дереве std::map - в конечном счете, я в порядке с этим решением. Теперь я понимаю, почему невозможно сделать то, что я изначально хотел; спасибо за объяснения!

Я просто не уверен, действительно ли хеш-карта экономит память! :) Как описал @Keith Randall, я не могу получить объем памяти ниже N*N/4 и подход треугольной матрицы описанный @Sjoerd дает мне N*N/2. Я думаю, что для хэш-карты вполне возможно использовать больше N*N/2 пространства, если размер элемента небольшой (зависит от накладных расходов контейнера) - что сделало бы самый быстрый подход и наиболее эффективным с точки зрения памяти! Я постараюсь проверить это.

Хотел бы я принять 2 ответа ...

Answer 1

Начните с просмотра двумерного массива: tab[a][b]. Это все еще требует размера N * N.

Будет использоваться каждая запись, но будет дублирование: f(a,b) = f(b,a). Таким образом, требуется только треугольная матрица (за счет одной ветви для a> b против a if (a < b) return tab[b*(b+1) + a]; // assuming 0 <= a < b < N else return tab[a*(a+1) + b]; // assuming 0 <= b <= a < N Или

if (a < b) return tab[b*(b-1) + a]; // assuming 1 <= a < b <= N
else return tab[a*(a-1) + b];       // assuming 1 <= b <= a <= N

РЕДАКТИРОВАТЬ: память, используемая треугольной матрицей (N + 1) * N / 2, примерно половина размера квадратной матрицы Все еще квадратично, хотя: (

EDIT2: обратите внимание, что er все еще дублирует матрицу: например, f(3, 2) = f(6, 1). Я не думаю, что это может быть устранено без введения большого количества ветвей и петель, но это просто внутреннее чувство.

Answer 2

Кажется, здесь не так много структуры, чтобы воспользоваться ею. Если вы спрашиваете, существует ли способ упорядочить таблицу так, чтобы вы могли избежать хранения записей, которые не могут произойти (потому что они имеют главный фактор больше N), вы не сможете сэкономить много. Существует теория гладких чисел , которая утверждает, что плотность N-гладких чисел вблизи N ^ 2 составляет ~ 2 ^ -2. Таким образом, в лучшем случае вы можете уменьшить (максимальное) требование к хранилищу не более чем в 4 раза.

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

Answer 3

Хеш-таблицы обеспечивают хороший баланс между скоростью поиска и объемом памяти. Стандартная библиотека C ++ не предоставляет хеш-таблицу, хотя иногда она доступна как нестандартное расширение. См., Например, SGI hash_map .

Библиотека Poco C ++ также имеет классы HashTable и HashMap, см. Документацию .

Answer 4

Почему бы просто не хэшировать комбо A и B и поместить результаты в карту? И делать это лениво, чтобы вы просто получили те, которые хотите?

public Result f(Type1 a, Type2 b) {
    TypePair key = new TypePair(a, b);
    Result res = map.get(key);
    if (res == null) {
        res = reallyCalculate(a, b);
        map.put(key, res);
    }
    return res;
}

Базовое запоминание.