Geekly Articles each Day
📜 ⬆️ ⬇️

Do you know arrays?

I think very few of those who are preparing for their first interview, when applying for the first job as a (pre) junior programmer, will answer this question in the negative. Or at least doubt the positive response. Of course, such a simple data structure with direct access by index - no dirty tricks! No, in some languages ​​such as JavaScript or PHP, arrays are, of course, implemented very interesting and in fact are much more than just an array. But this is not about this, but about the “traditional” implementation of arrays in the form of a “continuous memory area”. In this case, based on the indices and the size of one element, the address is simply calculated and the corresponding value is accessed. What's so complicated?
Let's see. For example, in Java. We ask the unsuspecting applicant to create an array of integers n x n . A person confidently writes something in the spirit:
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% . - . , . -.

. . , .

')

Source: https://habr.com/ru/post/211747/

More articles:


All Articles