Классика баз данных - статьи
Скалярное произведение
В двухмерном случае скалярное произведение определяется следующим образом. Для двух массивов A[I, J] и B[I, J] результатом их скалярного произведения по измерению J является вектор C [I], где C[i] = ∑j (A[i, j] * B [i, j]).
Заметим, что это определение является естественным обобщением стандартного определения скалярного произведения векторов на случай массивов: мы вычисляем скалярное произведение всех пар векторов, получаемых путем итерирования по всем значениям остающихся измерений.
Тестовый набор состоит в вычислении скалярного произведения двух целочисленных массивов A и B с числом измерений, изменяющимся от 3 до 6. Сначала тестовый набор пропускался с использованием систем ASAP и Matlab, в которых массивы поддерживаются как прирожденный тип данных. В этом эксперименте в каждом массиве содержалось 250 миллионов элементов (2Гб исходных целочисленных данных двойной точности), равномерно распределенных по всем измерениям. Мы вычисляли скалярное произведение для всех возможных измерений и подсчитывали среднее время выполнения этого набора матричных вычислений. Результаты были получены на машине с 64-битовым процессором Athlon, работавшим на частоте 2 Ггц, и 1 Гб основной памяти.
Аналогичный тестовый набор пропускался с использованием ASAP и одной из популярных коммерческих РСУБД, в базе данных которой каждый массив представлялся как таблица с атрибутами dimension-1, …, dimension-n, значение. В этом случае каждый массив состоял из 25 миллионов элементов (100 Мб исходных целочисленных данных с одинарной точностью), и использовалась машина с процессором Pentium, работавшим на частоте 3.2 Ггц, и 1 Гб основной памяти. РСУБД использовала 502-680 Мб для каждого массива в зависимости от числа измерений, и значения измерений также нужно было сохранять.
Наконец, мы исследовали два сценария: (i) сценарий «малого шага» («low stride»), в котором все элементы обрабатываемого вектора хранятся поблизости один от другого (насколько это возможно), и (ii) сценарий «большого шага» («high stride»), в котором элементы обрабатываемого вектора рассредоточены по массиву.
