Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 2.06.2014 | нет комментариев

Думаю, немного кто из подготавливающихся к своему первому интервью, при приеме на первую работу в должности (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 раз неторопливей! Сейчас самое время понаблюдать за реакцией претендента на должность. Какая будет реакция на странную (вернее обыкновенную в практике разработчика) стрессовую обстановку. Если на лице подзащитного изобразился энтузиазм и он стал жать на кнопочки временно позабыв о Вашем существовании, то это отличный знак. До определенной степени. Вы чай не хотите взять на работу изыскателя, которому плевать на итог плана? Тогда не задавайте ему вопрос «Отчего?». Попросите переделать 2-й вариант так, Дабы он подлинно работал стремительней первого.
Сейчас дозволено отважно заниматься некоторое время своими делами. Через пол часа у Вас будет довольно материала, для того, Дабы оценить основные личностные и высокопрофессиональные качества претендента.
Кстати, когда я коротко описал эту задачку на своем рабочем сайте, то особенно знаменитый комментарий был «Вот такая эта Ваша 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 (сто) раз стремительней не оптимизированного! Предложите поэкспериментировать на локальной машине. Пускай поиграет с настройками.
Кстати, а каждому ясно, что происходит?

Несколько слов в оправдание

Хочу сказать несколько слов в оправдание такого метода собеседования при найме. Да, я не проверяю познание синтаксиса языка и владение конструкциями данных. Допустимо, при цивилизованном рынке труда это все работает. Но в наших условиях тотальной нехватки квалифицированных кадров, доводится оценивать скорее перспективную адекватность претендента той работе с которой он столкнется. Т.е. способность обучиться, прорваться, разобраться, сделать.
По духу это схоже на «собеседованию» при комплекте легионеров в старинном Риме. Грядущего вояку крепко пугали и глядели краснеет он либо бледнеет. Если бледнеет, то в стрессовой обстановки у претендента кровь отливает от головы и он склонен к пассивной реакции. Скажем, упасть в обморок. Если же соискатель краснел, то кровь у него к голове приливает. Т.е. он склонен к энергичным действиям, кидаться в драку. Такой считался годным.
Ну и последнее. Отчего я рассказал об этой задаче каждому, а не продолжаю применять её на собеседованиях? Легко, эту задачу теснее «выучили» потенциальные соискатели и доводится применять другие.
Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB