Сравнение матриц

[Puhovoi]

Доброго времени суток!

Задача такова: есть матрица-эталон и 50.000.000 других матриц. Нужно вычислить процент совпадений каждой матрицы с эталонной. Размерность эталона и дочерних - 50*50.

Весьма приближенно выглядит так:

  for i := 1 to 50000000 do
  begin
    r := 0;
    for x := 1 to 50 do
      for y := 1 to 50 do
        if m[x, y] = m2[i][x, y] then inc (r);
    // вычисляем процент совпадения и т.п.
  end;

Где m - массив-эталон, а m2 - лист других массивов.

Все это безобразие выполняется 14.9 сек. Нужно добиться результата в 100 мс.

Вопрос - как?

Заранее спасибо за ответы.

[NetSpace]

нужно сократить количество проверок на равенство:

if m[x, y] = m2[i][x, y] then inc (r);

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

if(m[x, y] <> m2[i][x, y]) then continue;//или break попробуйте;

он вам должен выйти из цикла по Y.
но в цикле по X, наверное, должен продолжать работать, но вам и этого нет смысла доканчивать - надо и его прервать.
значит,надо поставить ещё одну строчку:

for i := 1 to 50000000 do
  begin
    r := 0;
    marker:=1;//сначала матрицу по умолчанию считаем нормальной
    for x := 1 to 50 do
    begin
      for y := 1 to 50 do
        if m[x, y] = m2[i][x, y] then inc (r);
        if(m[x, y] <> m2[i][x, y]) then
        begin
           marker:=0;//ага! палево! - матрица косячная попалась!
           continue;//или break попробуйте сами
        end;
       // вычисляем процент совпадения и т.п.
   end;
   if(marker=0) then continue;//или break...
end;

[Прик]

Задачка, граждане, чисто разводная: либо автор народ разводит, либо его.

Повезло же автору с высокопроизводительным кластером.
А у простых смертных даже с одной операцией сравнения в циклах эти 12,5 млрд итераций на двухядерном интеле крутятся ~4 минуты.
А какая память в его распоряжении, где он собирается хранить 50 млн. матриц размерностью 250 элементов? Завидно.
Ведь даже для целочисленных массивов потребуется не менее 50 Гб ОЗУ (в реальности много больше).
Одна незадача: где он столько матриц возьмет? А через тысячи подключенных периферийных устройств., наверное

Отсюда вывод: т.к. задача чисто теоретическая, то и ответ такой же. Чтобы добиться результата в 100 мс нужно обратиться к спонсорам, чтобы те увеличили производительность этого крутого компа в 150 раз.

2 NetSpace. Если прочитать условие задачи внимательно ("Нужно вычислить процент совпадений каждой матрицы..." Т.е. определить сколько в каждой матрице элементов не совпадают (совпадают) с элементами эталонной, а не то сколько матриц совпадают с эталонной), то о предложенной вами оптимизации здесь речи идти не может. Задача поставлена так, что все 12.5 млрд итераций в этих трех циклах обязательно нужно провернуть.

[TinMan]

Прик прав. Делим 15 сек на 50 млн и получаем время обсчета одной матрицы 0.3 микросекунды. Если и дальше пойти, то получим единичное сравнение элементов (с выборкой чисел) происходит за 300/2500 = 1/8 наносекунды, что равно одному такту на процессоре с частотой 8 ГГерц. Хорошо, пусть 4 ядра и прога скомпилирована под мультипоточность. Но все равно сильно сомнительно..

Ко всему прочему, если важна скорость И матрицы все фиксированного размера, а также координаты отличий не важны - зачем тогда организовывать ДВОЙНОЙ цикл?.. Одинарным циклом было бы быстрее )).

Может, там 14.5 мин фигурирует? )) про 100 миллисекунд вообще молчу..

[Stilet]

то о предложенной вами оптимизации здесь речи идти не может.

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

[Puhovoi]

Прик, часть я умолчал - матрицы дочерние генерируются по опр. принципу, все 50 млн. в памяти хранить не нужно.

Если приблизить к реальности, будет выглядеть так:

var
  start, ended : ttime;
  m1 : array [1..50, 1..50] of boolean;
  m2 : array [1..50, 1..50] of boolean;
  x, y, r, i : integer;
begin
  // заполнение первой матрицы
  for x := 1 to 50 do
    for y := 1 to 50 do m1[x, y] := true;
  // заполнение второй матрицы
  for x := 1 to 50 do
    for y := 1 to 50 do m2[x, y] := true;

  start := now;
  for i := 1 to 50000000 do
  begin
    r := 0;
    for x := 1 to 50 do
      for y := 1 to 50 do
        if m[x, y] = m2[x, y] then inc (r);
  end;
  ended := now;
  start := ended - start; // ~ 2 мин. 14 сек.

Код без генерации и высчитывания процента, просто для тестирования скорости сравнения. Т.е. - 50 млн. раз сравниваем две одинаковые матрицы на данный момент. Насчет времени и правда напутал - 2 мин. 14 сек. выходит, я забыл вывод минут сделать всего-навсего.

[Stilet]

for x := 1 to 50 do
for y := 1 to 50 do

Однозначно бинарный поиск тебе в руки. сократишь кол-во итераций второго цикл в 10 раз