Знаете ли Вы массивы?

Думаю, мало кто из готовящихся к своему первому интервью, при приеме на первую работу в должности (pre)junior программиста, ответит на этот вопрос отрицательно. Или хотя бы усомнится в положительном ответе. Конечно, такая простая структура данных с прямым доступом по индексу — никаких подвохов! Нет, в некоторых языках типа JavaScript или PHP массивы, конечно, реализованы очень интересно и по сути являются много большим чем просто массив. Но речь не об этом, а о «традиционной» реализации массивов в виде «сплошного участка памяти». В этом случае на основании индексов и размера одного элемента просто вычисляется адрес и осуществляется доступ к соответствующему значению. Что тут сложного?
Давайте разберемся. Например, на 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 << 2;

и это тоже повод поговорить. Но мы идем дальше и задаем ключевой вопрос: На сколько быстрее станет работать программа?. Обычные рассуждения такие: почти в 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("nTwo 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 (сто) раз быстрее не оптимизированного! Предложите поэкспериментировать на локальной машине. Пусть поиграет с настройками.
Кстати, а всем понятно, что происходит?

Автор: IEMazurok

Источник