Што ўяўляе сабой «доступ масіва» ў кантэксце алгарытмаў?

Ніжэй прыводзіцца рэалізацыя сартавання LSD Radix ў Java з падручніка для сартавання масіва радкоў, дзе кожная радок утрымлівае роўна W знакаў.

Я хачу, каб падлічыць колькасць масіва мае доступ падчас выканання. Я чытаў, што LSD гатунак павінен патрабаваць п * з масіў доступаў, дзе п гэтая колькасць радкоў і з колькасць знакаў у кожнай радку. Аднак алгарытм ніжэй ажыццяўляе доступ больш аднаго масіва ў некалькі разоў. Калі я павялічваем лічыльнік на кожным з іх я ў канчатковым выніку са значным каэфіцыентам пс .

Так што ж уяўляе сабой «доступ масіва» ў кантэксце алгарытмаў? Ёсць толькі адзін асобнік доступу да масіву, які лічыцца больш важным, што я павінен разлічваць тут, ці гэты прыклад на самай справе неэфектыўная рэалізацыя, якая выкарыстоўвае больш доступу да масіву, чым гэта неабходна?

 public int lsdSort(String[] array, int W) {
  int access = 0;
 //Sort a[] on leading W characters.
  int N = array.length;
  String[] aux = new String[N];
  for (int d = W-1; d >= 0; d--)
  {//Sort by key-indexed counting on dth char.
    int[] count = new int[R+1];//Compute frequency counts.
    for (int i = 0; i < N; i++) {
        count[array[i].charAt(d) + 1]++;
    }
    for (int r = 0; r < R; r++) {
       //Transform counts to indices.
        count[r+1] += count[r];
    }
    for (int i = 0; i < N; i++) {
       //Distribute.
        aux[count[array[i].charAt(d)]++] = array[i];

    }  
    for (int i = 0; i < N; i++)//Copy back.
        array[i] = aux[i];
  }

  return access;
  }
4
Дзякуючы Юваль для невялікіх правак, якія палепшылі чытальнасць!
дададзена аўтар Lawyerson, крыніца

4 адказы

<Р> Я чытаў, што LSD гатунак павінен патрабаваць п раз з масівам мае доступ дзе п лік радкоў і з колькасцю знакаў у кожнай радку.

Вы ўпэўненыя, што вы не чыталі, што гэта O (НЗ) ? Гэта не тое ж самае на ўсіх. Гэта вялікі-O абазначэння . Справа ў тым, каб не вызначыць дакладную колькасць масіва доступ - гэта казаць пра тое, як ён расце (ці, дакладней, <ет> мяжа , як яна можа расці), а п або з павелічэнне. У гэтым выпадку лінейна ўзрастае - калі вы павялічваеце п на каэфіцыент 1000, вы б толькі чакаць, што агульны кошт вырасце ў 1000 таксама ... у той час як калі б гэта было Аб (п 2 в) алгарытм замест гэтага, ён можа вырасці на каэфіцыент 1000000 .. (Строга кажучы, любы O (НЗ) алгарытм таксама Аб (п 2 с) з-за гэтага толькі не мяжа, але давайце не будзем удавацца ў гэта.)

7
дададзена
@Parusa: Цалкам магчыма, што гэта на самай справе, што гэта значыць, і гэта сапраўды магчыма. Гэта здаецца менш <я> цікавы чым трохі вялікі-O, хоць.
дададзена аўтар Jon Skeet, крыніца
Дзякуй за ваш адказ. Гэта, здаецца, мае сэнс. Я толькі нядаўна пачаў вывучаць алгарытмы і я знаёмы з пазначэннямі вялікі-O. Мой падручнік, аднак робіць гэта, здаецца, як быццам Radix роду мяркуюцца толькі трэба сапраўды з масіў доступаў для кожнага радка п нягледзячы на ​​прапанову гэтага прыкладу рэалізацыі, які мяне збянтэжыў.
дададзена аўтар Lawyerson, крыніца
@JonSkeet Я думаю, што кніга проста спрабуе сказаць мне (хоць і ў заблытанай манеры), што Radix гатунку можна сартаваць ў лінейнае час, і што ён на самай справе <я> можна зрабіць гэта ў строга сп, але фактычная эфектыўнасць залежыць ад рэалізацыі. Дзякуй за ваш час!
дададзена аўтар Lawyerson, крыніца
Хоць я не бачу ніякіх прычын, чаму пс не павінна быць выканальна. Вам проста трэба з завесы пераборы масіва і ўвод значэнняў у хелперов масіў. Ну добра вы можаце сцвярджаць, што гэта 2лс , як мы павінны пісаць сімвалы назад, але іншы масіў ;-)
дададзена аўтар Voo, крыніца

Усе масіў звяртаецца ўнутры першага цыкла для істотна падлічваюць як сумарную колькасць масіва атрымлівае доступ, так што ваш гр. П колькі разоў вы гэта разам масіў доступаў. Гэта дае прыблізнае ўяўленне пра рост функцыі, а не фактычнага падліку доступаў.

1
дададзена
public int lsdSort(String[] array, int W) {
  int access = 0;
 //Sort a[] on leading W characters.
  int N = array.length;
  String[] aux = new String[N];
  for (int d = W-1; d >= 0; d--)
  {//Sort by key-indexed counting on dth char.
    int[] count = new int[R+1];//Compute frequency counts.
    for (int i = 0; i < N; i++) {
        count[array[i].charAt(d) + 1]++;
        access++;
        access++;
    }
    for (int r = 0; r < R; r++) {
       //Transform counts to indices.
        count[r+1] += count[r];
        access++;
    }
    for (int i = 0; i < N; i++) {
       //Distribute.
        aux[count[array[i].charAt(d)]++] = array[i];
        access++; 
        access++;
        access++;   
    }  
    for (int i = 0; i < N; i++)//Copy back.
        array[i] = aux[i];
        access++;
        access++;
  }

  return access;

  }

Масіў «доступ» альбо чытанне або запіс ...

1
дададзена
+1, для прыкладу. Я не разглядаў прырашчэннем некалькі разоў у межах адной і той жа пятлі. Дзякуй за ваш адказ!
дададзена аўтар Lawyerson, крыніца

У Big-O асімптатычнага абазначэння, лік доступу прапарцыйныя пастаянны. Пры аналізе кода, усё канстанты адкідаюцца.

У выпадку Radix сартавання Вялікі O з'яўляецца O (CN) . Але калі вы хочаце на самай справе падлічыць, колькі раз звяртаюся масіў трэба памножыць гэтую лічбу для некаторай канстанты да , дзе, што да спецыфічны для канкрэтных закадаваныя рэалізацый.

Напрыклад, гэтая функцыя Аб (п) , але колькасць раз масіў з'яўляецца доступ 2n : адзін для счытвання значэння, і адзін для яго абнаўлення. Нумар 2 адкідаецца.

for (i=0; i
1
дададзена