Время выполнения алгоритма Опции

[sheka]

Упорядочить отдельно каждое сечение трехмерного массива А [p, m, n] насквозь по колонкам по неубыванию.

сортировка (Показать/Скрыть)

  function PCube_SelectExchange2_byTruthIndex(var Cube: PCube; const p, m, n: word): longint;
  var
    B: MyType;
    i,
    ks, js,
    jt, kt: word;
    StartTime, FinishTime: TTime;
  Begin
    with StartTime do GetTime(Hours,Minutes,Seconds,HSeconds);
    for i := 1 to p do
      for ks := 1 to n do
        for js := 1 to m do
        begin
          for jt := js+1 to m do
            if Cube^[i]^[jt]^[ks] <= Cube^[i]^[js]^[ks] then
            begin
              b := Cube^[i]^[jt]^[ks];
              Cube^[i]^[jt]^[ks] := Cube^[i]^[js]^[ks];
              Cube^[i]^[js]^[ks] := b;
            end;
          for kt := ks+1 to n do
            for jt :=1 to m do
              if Cube^[i]^[jt]^[kt] <= Cube^[i]^[js]^[ks] then
              begin
                b := Cube^[i]^[jt]^[kt];
                Cube^[i]^[jt]^[kt] := Cube^[i]^[js]^[ks];
                Cube^[i]^[js]^[ks] := b;
              end;
        end;
    with FinishTime do GetTime(Hours,Minutes,Seconds,HSeconds);
    PCube_SelectExchange2_byTruthIndex := ResTime(StartTime, FinishTime);
  end;

Сортировка выдает удивительные вещи для разных размеров массива, хотя по идее должна выдавать одинаковые(как-бы логично):
Ведь если(допустим массив отсортирован) посчитать количество таких (первых)

выражений (Показать/Скрыть)

if Cube^[i]^[jt]^[ks] <= Cube^[i]^[js]^[ks] then

то получится p*n*(m²+m-2)/2, а таких (вторых)

выражений (Показать/Скрыть)

if Cube^[i]^[jt]^[kt] <= Cube^[i]^[js]^[ks] then

то получится p*m*(n²+n-2)/2*m
Если все это упростить и построить график http://www.wolframalpha.com/input/?i=plot+...10%2C+n%3D1..10 то он окажется почти симметричным относительно m и n, без резких перегибов в какую либо сторону.

Сообщение отредактировано: sheka - 16.04.2011 11:52

[volvo]

И все равно нельзя сравнивать время обработки матриц. Количество сравнений - одинаковое (что-то я проморгал, не туда воткнул счетчик, согласен). Но...

Сравним количество перемещений: (Показать/Скрыть)

  function PCube_SelectExchange2_byTruthIndex(var Cube: PCube; const p, m, n: word): longint;
  var
    B: MyType;
    i,
    ks, js,
    jt, kt: word;
    StartTime, FinishTime: TTime;
    cnt : longint;
  Begin
    cnt := 0;
    with StartTime do GetTime(Hours,Minutes,Seconds,HSeconds);
    for i := 1 to p do
      for ks := 1 to n do
        for js := 1 to m do
        begin
          for jt := js+1 to m do
          begin
            if Cube^[i]^[jt]^[ks] <= Cube^[i]^[js]^[ks] then
            begin
              inc(cnt);
              b := Cube^[i]^[jt]^[ks];
              Cube^[i]^[jt]^[ks] := Cube^[i]^[js]^[ks];
              Cube^[i]^[js]^[ks] := b;
            end;
          end;
          for kt := ks+1 to n do
          begin
            for jt :=1 to m do
              if Cube^[i]^[jt]^[kt] <= Cube^[i]^[js]^[ks] then
              begin
                inc(cnt);
                b := Cube^[i]^[jt]^[kt];
                Cube^[i]^[jt]^[kt] := Cube^[i]^[js]^[ks];
                Cube^[i]^[js]^[ks] := b;
              end;
          end;
        end;
    with FinishTime do GetTime(Hours,Minutes,Seconds,HSeconds);
    writeln ('count = ', cnt);
    PCube_SelectExchange2_byTruthIndex := ResTime(StartTime, FinishTime);
  end;

(я надеюсь, теперь я не ошибся с местом? )

Для чистоты эксперимента я решил прогнать этот тест на абсолютно одинаковых данных:

  // -- 60 randoms for test --
  const RSize = 5 * 6 * 2;
  var R : array[1 .. RSize] of MyType;

   procedure PCube_Init(var Cube: PCube; const p, m, n: word);
   var
     i, j, k: word;
     curr : Word;
   begin
     curr := 1;
     for i := 1 to p do
       for j := 1 to m do
         for k := 1 to n do
         begin
           Cube^[i]^[j]^[k] := R[curr];
           Inc(Curr);
         end;
   end;
   procedure PCube_Print(var Cube: PCube; const p, m, n: word);
   var
     i, j, k: word;
   begin
     for i := 1 to p do
     begin
       writeln;
       writeln('Layer:', i);
       for j := 1 to m do
       begin
         for k := 1 to n do
         begin
           write(Cube^[i]^[j]^[k]:5);
         end;
         writeln;
       end;
     end;
   end;

При входе в Menu, еще до Repeat, выполняется
    for i := 1 to RSize do
    begin
      R[i] := Random(100);
    end;

, т.о., генерируются случайные данные, которые потом будут использованы для инициализации матрицы. И проверим, сколько перемещений делается в матрице (5*6*2), и сколько - в матрице (5*3*4). Как? Вот так:

      2: // Выбрана сортировка Cube в меню
      begin
      (*
        Create(Cube,p,m,n);
        CubeFill[FillType](Cube,p,m,n);
        Time := CubeSort[SortType](Cube,p,m,n);
        writeln('Time = ',Time);
        Destroy(Cube,p,m,n);
      *)
        writeln('first');
        p := 5; m := 6; n := 2;
        PCube_Create(Cube,p,m,n);
        PCube_Init(Cube,p,m,n);
        PCube_Print(Cube,p,m,n);
        readln;

        Time := CubeSort[3](Cube,p,m,n);
        PCube_Print(Cube,p,m,n);
        writeln('Time = ',Time);
        Destroy(Cube,p,m,n);

        readln;

        writeln('second');
        p := 5; m := 3; n := 4;
        PCube_Create(Cube,p,m,n);
        PCube_Init(Cube,p,m,n);
        PCube_Print(Cube,p,m,n);
        readln;

        Time := CubeSort[3](Cube,p,m,n);
        PCube_Print(Cube,p,m,n);
        writeln('Time = ',Time);
        Destroy(Cube,p,m,n);
      end;

, дальше все без изменений.

Запускаем, выполняем, и получаем: (Показать/Скрыть)

1. Vector Sort
2. Cube Sort
3. Complex
4. Exit
2
first

Layer:1
   54   59
   71   84
   60   85
   54   84
   42   62
   64   38

Layer:2
   43   29
   89    5
   96   27
   38   47
   79   81
   52   47

Layer:3
   56   39
   92   83
    7   33
    8   64
    2   36
   83   95

Layer:4
   77   14
   87   87
   97   47
   79   80
   46   52
   78   67

Layer:5
   11   72
   63   58
   14   53
   94   75
   52   10
   41   47

count = 170

Layer:1
   38   62
   42   64
   54   71
   54   84
   59   84
   60   85

Layer:2
    5   47
   27   52
   29   79
   38   81
   43   89
   47   96

Layer:3
    2   56
    7   64
    8   83
   33   83
   36   92
   39   95

Layer:4
   14   78
   46   79
   47   80
   52   87
   67   87
   77   97

Layer:5
   10   53
   11   58
   14   63
   41   72
   47   75
   52   94
Time = 0

second

Layer:1
   54   59   71   84
   60   85   54   84
   42   62   64   38

Layer:2
   43   29   89    5
   96   27   38   47
   79   81   52   47

Layer:3
   56   39   92   83
    7   33    8   64
    2   36   83   95

Layer:4
   77   14   87   87
   97   47   79   80
   46   52   78   67

Layer:5
   11   72   63   58
   14   53   94   75
   52   10   41   47

count = 135

Layer:1
   38   54   62   84
   42   59   64   84
   54   60   71   85

Layer:2
    5   38   47   81
   27   43   52   89
   29   47   79   96

Layer:3
    2   33   56   83
    7   36   64   92
    8   39   83   95

Layer:4
   14   52   78   87
   46   67   79   87
   47   77   80   97

Layer:5
   10   41   53   72
   11   47   58   75
   14   52   63   94
Time = 0

Чувствуешь разницу? На первой матрице count = 170, на второй - 135. Как думаешь, какая из них будет обрабатываться дольше? Здесь по значению Time этого не видно, очень маленькие размеры. Но у второй матрицы (в данном случае) явно есть преимущества в скорости. В эту сторону тоже посмотри...