🈁 🍧 🚔 配列を知っていますか？ ↖️ ⛲️ 💆🏿

（前）ジュニアプログラマーとして最初の仕事に就職するときに、最初のインタビューの準備をしている人はほとんどいないと思います。または、少なくとも肯定的な答えを疑います。もちろん、インデックスによる直接アクセスを備えたこのような単純なデータ構造-トリックはありません！いいえ、JavaScriptやPHPなどの一部の言語では、配列はもちろん非常に興味深い方法で実装されており、実際には単なる配列以上のものです。しかし、これはそれについてではなく、「連続的なメモリ」の形での配列の「伝統的な」実装に関するものです。この場合、インデックスと1つの要素のサイズに基づいて、アドレスが単純に計算され、対応する値がアクセスされます。何がそんなに複雑なの？
それを理解しましょう。たとえば、Javaで。疑いを持たない申請者に、整数n x nの配列を作成するように依頼します。男は自信を持って精神に何かを書く：

int g[][] = new int[n][n];

. -. , . :

for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
          g[i][j] = i + j; 
      }
}

for(int i = 0; i < g.length; i++) {
      for(int j = 0; j < g[i].length; j++) {
          g[i][j] = i + j; 
      }
}

, . , , . , . , , ? - :

for(int i = 0; i < n; i++) {
    g[i][i] = 2* i;
    for(int j = 0; j < i; j++) {
        g[j][i] = g[i][j] = i + j; 
    }
}

g[i][i] = 2* i;

g[i][i] = i + i;

g[i][i] = i << 1;

. : ?. : 2 ; 2 (); . 30. , .
. - n ( ), , .

class A {
  public static void main(String[] args) {
    int n = 8000;
 
    int g[][] = new int[n][n];
    long st, en;
 
    // one
    st = System.nanoTime();
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        g[i][j] = i + j; 
      }
    }
    en = System.nanoTime();
    System.out.println("\nOne time " + (en - st)/1000000.d + " msc");
 
    // two
    st = System.nanoTime();
    for(int i = 0; i < n; i++) {
      g[i][i] =  i + i;
      for(int j = 0; j < i; j++) {
        g[j][i] = g[i][j] = i + j; 
      }
    }
    en = System.nanoTime();
    System.out.println("\nTwo time " + (en - st)/1000000.d + " msc");
  }
}

? 10-100 ! . ( ) . , . . , ? «?». , .
. , , .
, , « Java ». . Free Pascal Windows

program Time;
uses
   Windows;
   var
      start, finish, res: int64;
      n, i, j: Integer;
      g: Array of Array of Integer;
begin
   n := 10000;
   SetLength(g, n, n);
   QueryPerformanceFrequency(res);
   QueryPerformanceCounter(start);
   for i:=1 to n-1 do
      for j:=1 to n-1 do
         g[i,j] := i + j;
   QueryPerformanceCounter(finish);
   writeln('Time by rows:', (finish - start) / res, ' sec' );
   QueryPerformanceCounter(start);
   for i:=1 to n-1 do
      for j:=1 to n-1 do
         g[j,i] := i + j;
   QueryPerformanceCounter(finish);
   writeln('Time by cols:', (finish - start) / res, ' sec' );
end.

«» . .
?
1. ? …
2. ?

Java, n. , ideone.com n=117 «» . n=118 100 () ! . .
, , ?

. , . , . , . .. , , , .
«» . . , . , . , . .. , . .
. , ? , «» .
. fps . .

, «» . .. , . . . , — ? — ideone.com/tMaR2S. 100000 . ?
(Big_Lebowski), . . , leventov. ideone.com/yN1H4g. .. ~10% . - . , . -.

. . , .

配列を知っていますか？

More articles: