Пользователь
0,0
рейтинг
7 февраля 2014 в 21:49

Разработка → Знаете ли Вы массивы? из песочницы tutorial

Думаю, мало кто из готовящихся к своему первому интервью, при приеме на первую работу в должности (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 << 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% медленнее чем последовательный. Возможно и в правду какую-то роль может сыграть кэш. Однако, в исходной ситуации производительность проседала в разы. Значит есть еще что-то.

Постепенно в лидеры выходит версия про дополнительные действия при переходе от одной строки массива к другой. И это правильно. Осталось разобраться, что же именно там происходит.
Igor Mazurok @IEMazurok
карма
4,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (178)

  • +17
    Вопрос на понимание того, как работают кеши процессора. Имхо, если вы не считаете математику на джаве, эти знания редко пригождаются.
    • 0
      Почему только Java? Там есть код и на Паскале с тем же эффектом. Ну и касается это наверное всех, кто работает с массивами. А уж «математика» в массиве или картинка роли не играет.
      • 0
        Ну картинки, видео тоже, да. Просто обычно все эти работы с картинками и прочим уже давно реализованы в библиотеках и самому ничего не приходится делать.
        • +5
          Все зависит от проектов, с которыми Вы сталкиваетесь. Я конечно слышал о программистах, которые никогда не работали с массивами… Но мне, даже при работе с «готовой» библиотекой OpenCV, приходилось довольно много крутить большими массивами.
          • –6
            Ни разу не работал с изображениями в коммерческом коде. И не знаю никого, кто бы работал. Думаю таких проектов подавляющее большинство.
            • 0
              Обработка графики. Со всеми вытекающими. Очень перспективная область, между прочим.
        • 0
          Это одна из таких «мелочей», которые относятся к «общей грамотности». Библиотеки могут и не спасти.

          Многие, скажем, без всякой задней мысли составляют крупную строку, складывая отдельные строчки простым плюсом. Да, в стандартной библиотеке есть под такую задачу класс (в Java это StringBuilder), но если разработчик о нём не знает, его это не спасёт, и тормозить будет. А в обширном мире практического программирования наткнуться на подзадачу склеивания тонны строк недолго, как и на алгоритм с массивами.
          • 0
            Согласен.

            К теме не относится, но, честно говоря, в Java и во многих других языках на мой взгляд неудачная структура данных для хранения строк выбрана. Можно хранить строки в виде Ropes и тогда никакой проблемы складывать их в цикле не будет.
            • +2
              Ну, это уже холивар. Выбор реализации структуры данных зависит от того, какие именно операции чаще всего с ним выполняются в программе. Ropes рассчитаны на быструю конкатенацию O(1), но индексирование в них проходит за O(h). habrahabr.ru/post/144736/
              • +3
                Индексация строкам почти никогда не нужна. В 99% случаев она используется для итерирования по символам, а итерация в ropes в целом аналогична строкам. А когда нужна — можно сделать какой-нибудь метод optimize, который склеивает внутреннее дерево в один массив и вызывать его один раз перед запуском этого алгоритма.
              • 0
                Сейчас как раз пишу реализацию Ropes по этой статье. В ней я как раз писал про то что есть оптимизации индексирования, основанные на том что доступ к символам почти всегда последовательный — это значит что можно кэшировать листовой узел в котором в последний раз нашелся символ и диапазон индексов который он представляет. За счет того что в следующий раз обращение наверняка будет производиться к соседним символам индексация пройдет за О(1). Можно даже пойти дальше и вместо одного кэша поддерживать 2-3, чтобы оптимизировать даже те сценарии, когда символы поочередно выбираются с разных концов строки, однако на практике одного.
                В общем, основная мысль в том что индексация в Ropes на практике происходит за амортизированное O(1). Главная же их фишка — вставка в середину строки за то же О(1), чего обычные строки и StringBuilder'ы не умеют.
          • +7
            Просто не могу удержаться и не попроавить. Как раз в Java компилятор заменит простую конктенацию вызовом StringBuilder'а. И константы заранее все соединит.

            Пример
            public class Test {
                public static void main(String[] args) {
                    String s = "Some " + "string " + 1 + " concatenated: " + 2L + ":" + (byte)3 + ":" + 1.0d;
            	    System.out.println(s);
                    String s2 = "Another one " + args[0] + args[1] + args[2] + args[3];
                    System.out.println(s2);
                }
            }
            

            $ javac Test.java && javap -c Test
              public static void main(java.lang.String[]);
                Code:
                   0: ldc           #2                  // String Some string 1 concatenated: 2:3:1.0
                   2: astore_1      
                   3: getstatic     #3                  // Field java/lang/System.out:Ljava/io/PrintStream;
                   6: aload_1       
                   7: invokevirtual #4                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
                  10: new           #5                  // class java/lang/StringBuilder
                  13: dup           
                  14: invokespecial #6                  // Method java/lang/StringBuilder."<init>":()V
                  17: ldc           #7                  // String Another one 
                  19: invokevirtual #8                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
                  22: aload_0       
                  23: iconst_0      
                  24: aaload        
                  25: invokevirtual #8                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
                  28: aload_0       
                  29: iconst_1      
                  30: aaload        
                  31: invokevirtual #8                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
                  34: aload_0       
                  35: iconst_2      
                  36: aaload        
                  37: invokevirtual #8                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
                  40: aload_0       
                  41: iconst_3      
                  42: aaload        
                  43: invokevirtual #8                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
                  46: invokevirtual #9                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
                  49: astore_2      
                  50: getstatic     #3                  // Field java/lang/System.out:Ljava/io/PrintStream;
                  53: aload_2       
                  54: invokevirtual #4                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
                  57: return        
            }
            



            Конечно если строка конкатенируется в цикле или в разных методах, то компилятор уже не спасёт.
            • 0
              вам не кажется, что в случае «без цикла» — один хрен: что с конкатенацией, что со СтрингБилдером?
              • 0
                Если надо сложить два десятка строк длиной по миллиону символов, то, может быть, StringBuilder тоже окажется выгодней. Хоть и без цикла.
                • 0
                  на большом аоличестве строк или на больших строках — да. На малом количестве малых строк — это гадание на кофейной гуще
              • 0
                У voronaam это в примере и показано. Если компилятор сможет вычислить строчку в compile-time, то поклеит. Если нет — создаст StringBuilder.
                • 0
                  вопрос не в этом, а в том, всегда ли замена конкатенации на СтрингБилдер быстрее.
                  • 0
                    Что вы понимаете под конкатенацией? Оператор + или String#concat(String)?

                    Если первое — то оно с java 1.5 использовало StringBuilder внутри, а в java 1.4.2 (возможно, что и раньше — не проверял) использовало StringBuffer.
                    java se 1.4.2
                    The Java language provides special support for the string concatenation operator ( + ), and for conversion of other objects to strings. String concatenation is implemented through the StringBuffer class and its append method. String conversions are implemented through the method toString, defined by Object and inherited by all classes in Java. For additional information on string concatenation and conversion, see Gosling, Joy, and Steele, The Java Language Specification.


                    Если второе — то оно иногда может быть выгоднее за счет меньшего количества выделений памяти в худшем случае, но оно менее удобно (не приводит типы автоматически), может вызвать NPE (если первая строка — null).
              • 0
                Принципиальная разница в том, что результат String.concat() — полноценная строка. Уже само по себе плохо что это полноценный объект (который должен будет подчистить GC), так это ещё и строка — а значит она окажется в строковом кэше. Который (насколько я помню), до Full GC чистить никто не будет.

                В StringBuilder'е же строка это просто char*, который Java-объектом не является.

                Раз уж у нас тут ветка ликбеза получается…
                • +2
                  Судя по коду в java 7 ни то, ни другое не intern'ит строку. Т. е. в строковый пул не попадает. По умолчанию inter'ятся литералы (3.10.5 в jls7).

                  И то, и другое создает массив char'ов и String на его основе:
                  — в случае concat он создается в методе String#concat и переиспользуется в new String(char[], boolean);
                  — в случае StringBuilder#toString() он создается в new String(char[], int, int).

                  В StringBuilder'е — char[] — вполне себе java-объект.
            • 0
              Заметьте, что из Java я упомянул только класс для сборки строк (чтобы было понятно, о чём речь), а сам пример совершенно абстрактный.

              Я лично не очень рад доверять разницу между сложностью в О(N) и в O(N^2) компилятору без 100%-ной уверенности, что получится более быстрый вариант (а здесь, из синтаксиса, на вид не должен, если понимать операции). Здесь компилятор спасёт, но он (вы и сами отметили) спасёт не везде. Особенно если речь пойдёт о другой реализации компилятора или вообще не о Java.
          • 0
            Со строками возможны и обратные грабли.
            Если приходит большая строка, из которой выбирается лишь маленькая подстрока, то в памяти остаётся вся исходная строка. Когда таких строк много, память внезапно кончается. Ситуация, конечно, крайне редкая, но возможная.
            • +1
              Потом народ для защиты от такого начинает интернить строки… И OOM случается по permgen'у ,)
            • +3
              ой вей? Начинаея с java7u6 поведение другое.
              • 0
                Действительно, в 7 уже делается arraycopy. А вот в 6 и ранее передавался внутренний массив char и новые индексы смещений.
      • 0
        А при чем тут массивы? Можно аналогично подсчитывать любые операции с небольшими объемами данных (строки, математику, хеши т.д.) и результат будет неожиданным из-за работы кешей
  • 0
    Кэш?
  • +3
    Так что же происходит? Объясните кто-нибудь в подробностях, пожалуйста.
    • 0
      Я склонен дождаться версий читателей. Пока есть только одна — кэш.
      • +5
        Хм, «раздербанил» код теста с помощью javap. Код второго цикла гораздо больше и наличие имеется imul и dup_x2, в отличие от кода первого.
        Есть предположение что массив хранится в «одну линию», и, поскольку во-втором массиве идет обращение к элементам массива не по-порядку, строка за строкой, а вразнобой, то появляется дополнительный код, вычисляющий смещение.
      • 0
        Помимо кэша есть еще JIT, который и срабатывает при больших N.
    • +6
      А почитать статью специально этому посвящённую — не судьба? То, что тут происходит описано в пятой части. И да, кеш имеет к этому отношение, но дело в том, что в современных процессорах вокруг кеша наверчено мнооого всего. Обращение по строкам быстрее обращений по столбцам, но это не вся правда. Там есть чудеса со строками кеша и прочим. Есть красивый манёвр с кривой Пеано. Вообще есть много чего и очень грустно наблюдать ситуацию, когда люди (с надеждой и замиранием сердца) говорят «кеш», как будто это слово в три буквы описывает всю ситуацию…
  • +5
    А точно пишут именно так?
    g[i][i] = i << 2;
    Еще один повод поговорить.
    • 0
      Пишут и не такое, но спасибо, исправил.
  • –2
    Cache, конечно, тут и думать не надо. Вместо последовательного обращения к памяти получили обращения в разные места памяти.
  • –2
    Помимо кэша, ОС приходится обращаться не к соседним ячейкам памяти, а к далеко-лежащим, что сильно увеличивает скорость
    • –3
      Т.е. уменьшает. Вы имеете ввиду страничироване памяти?
      • +5
        какое словно интересное :)
      • 0
        Да, конечно я имелв виду «уменьшает скорость», а увеличивает — время =)
  • –9
    Почитав про кеш и про про­стран­ствен­ную ло­каль­ность я бы написал так:

    for ($i=0; $i < $n; $i++){
    $mass[$i][$i] = 2*$i;
    for ($j=0; $j < $i; $j++){
    if($j==0){
    $s = $n-$i;
    $k = $i;
    }
    $mass[$i][$j] = $mass[$s][$k] = 2*$j;
    $k++;
    }
    }
    • +1
      Не повлияло в лучшую сторону
  • 0
    В пользу теории о кеше говорит то, что если n уменьшить до 64, то время выполнения будет приблизительно равным.
    • 0
      Для таких маленьких массивов скорость исполнения измеряется с большой погрешностью. Кстати, обратите внимание на нарушение закономерности при изменении размера всего на единицу 117 — 118. Причем работает на виртуальном сервере ideone.com/r4ZXu5. На локальной машине вы это вряд ли получите.
  • +1
    А то что при каждом обращении по индексу происходит проверка — не зашли ли вы за границы массива не учитывается (только в Java, во FreePascal ее нет)? Можно сохранить в одной верхней итерации ссылку на массив и использовать его, чтобы избежать лишних проверок.
  • +4
    А в java двумерный массив хранится точно также как и в си?
    Кстати, на скорость инициализации еще будет влиять то, по столбцам мы его будем заполнять или по строчкам.
    • +2
      Так мы об этом и говорим
  • +1
    Я может быть чего-то не понимаю, но есть же вот такое:

    http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#fill(int[], int)
    • +1
      fill() позволит заполнить линейный массив одинаковыми значениями. Мы обсуждаем вопрос почему так сильно различается скорость перебора элементов двумерного массива «по строкам» и «по столбцам». Относительная парадоксальность ситуации в том, что обычно декларируется (так оно и есть), что массив структура данных с эффективным произвольным доступом. Постепенно в обсуждении формируется идея, что при доступе по строкам производится O(n+m) обращений к элементам массива. А при доступе по столбцам — O(n*m).
      • 0
        Нет, это то все понятно, но ведь изначально была задача «Теперь просим инициализировать элементы массива чем-нибудь. Хоть единицами, хоть суммой индексов.».
        И, кстати, интересно бы еще посмотреть на результаты чего-то такого:

        for (int[] row : arr)
            Arrays.fill(row, 1);
        
        

        будет ли значительное проседание?
  • –7
    Мне очень понравилась версия про кэш процессора. Основная его идея — последовательный доступ быстрее случайного. Давайте поисследуем его чуть-чуть. Напишем простой код. Даже без двумерного массива. Просто, работаем с элементами массива подряд (вариант 1) и в случайном порядке (вариант 2). Вот он — ideone.com/tMaR2S. При таком размере массива (1200 целых чисел), случайный доступ чуть-чуть быстрее. Можно снова поиграть с размером массива и получить самые разные результаты.
    • +3
      Меняем one/two местами и получаем обратный результат, даже немного лучший для последовательно заполнения: ideone.com/T5rfeM
    • +4
      Тест не очень чистый, первый прогон влияет на второй.
      • +2
        Добавлю ещё то, что размер массива имеет значение: на 5 миллионах (гарантированно не влезает в ближний кэш) последовательный доступ быстрее случайного, независимо от их взаимного расположения.
  • +2
    «Краснеющих» хорошо только туда, где будут сплошные стрессы. «Бледнеющие» могут лучше себя показать в спокойной обстановке.
    • 0
      Правильно. Вот их в легионеры и брали таких. Здесь схожесть ситуации в том, что интересно понаблюдать за действиями-рассуждениями потенциального программиста работающего над задачей, простой по формулировке, но не понятной для него по поведению кода.
  • 0
    Процессорный кеш может и как то влияет, но скорее всего проблема в проверках границ массивов.
    Код на Java
    One time 17.966596 msc
    Two time 23.864461 msc

    Код на С
    1st=14.017 msc
    2nd=8.937 msc
    • –2
      Так отключите
    • 0
      не знаю почему эта байка с проверкой границ массива так долго ходит по миру, если вы бегаете по массиву даже в таком цикле for ( int i = 0; i < ar.length /2 + 1; i++ ) то проверка делается всего один раз.
  • 0
    Мне кажется причина в том, что во втором варианте некоторые ключи массива перезаписываются повторно.
    • 0
      Где? Какие?
  • +8
    По моему кеш проца оказывает минимальное влияние в данном случае. Основное это доступ к элементам — в java массивы хранятся построчно, поэтому доступ по столбцам гораздо менее эффективен, что можно подтвердить следующим тестом:
    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] = 1;
        }
        }
        en = System.nanoTime();
        System.out.println("\nTwo time " + (en - st)/1000000.d + " msc");
         
        // two
        st = System.nanoTime();
        for(int j = 0; j < n; j++) {
        for(int i = 0; i < n; i++) {
        g[i][j] = 1;
        }
        }
        en = System.nanoTime();
        System.out.println("\nTwo time " + (en - st)/1000000.d + " msc");
        }
        }
    

    у меня 70.225679 msc против 2943.409599 msc.

    Если вопрос именно по симметричной матрице, то в java 2d массив — это именно массив массивов ( в отличие например от С), поэтому у каждого массива может быть свой размер — можно хранить и заполнять только нижний треугольник матрицы.
    • –1
      Вы абсолютно правы, что дело в порядке доступа. Но как быть с этим ideone.com/tMaR2S?
      • +8
        тут вы меряете скорость работы random, которая на порядок меньше скорости работы с массивом ideone.com/A50fQA
      • 0
        (ниже уже есть)
    • +3
      Да, все верно. Тормоза вызваны именно тем, что двумерный массив представлен как массив из массивов, в результате для получения определенного элемента надо сделать несколько дополнительных операций по получению вложенного массива, вместо прямого доступа к нужному элементу. Поэтому и получается, что случайный доступ медленнее последовательного. Так что кэш процессора тут вообще не при чем…
      Пример:
      ideone.com/crcmVU
      Код
      class A {
        public static void main(String[] args) {
          int n = 5000;
      
          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] = 10; 
            }
          }
          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] =  20;
            for(int j = 0; j < i; j++) {
              g[j][i] = g[i][j] = 20; 
            }
          }
          en = System.nanoTime();
          System.out.println("\nTwo time " + (en - st)/1000000.d + " msc");
          
          // 3 Обычный массив такого же размера, как и двухмерный, линейный проход по всем элементам
          int arrLen = n*n;
          int[] arr = new int[arrLen];
          st = System.nanoTime();
          for(int i : arr) {
            arr[i] = 30;
          }
          en = System.nanoTime();
          System.out.println("\n3 time " + (en - st)/1000000.d + " msc");
          
              
          // 4 Тот же массив, но работаем как с двухменым массом
          st = System.nanoTime();
          int i, j;
          for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++) {
              arr[i*n+j] = 40;
            }
          }
          en = System.nanoTime();
          System.out.println("\n4 time " + (en - st)/1000000.d + " msc");
        }
      }
      

      Результат:
      Two time 71.998012 msc
      Two time 551.664166 msc
      3 time 63.74851 msc
      4 time 57.215167 msc

      Ну и плюс, скорее всего, свою лепту обычно вносит оптимизатор — я не джавист, так что как оно там внутрях работает и что делает я не знаю.
      • +3
        > что двумерный массив представлен как массив из массивов
        Строго говоря в Java вообще нет двумерных массивов, поэтому автор всех здорово запутал своими параллелями с Си и Паскалем.
        Видимо отсюда и весь налет мистики.

        В Си и Паскале двумерные массивы есть (насколько я помню), и там размерность массива NxK будет означать непрерывный блок памяти размером NxK в котором с помощью pointer arithmetics можно вычислить адрес каждой конкретной ячейки — но в Java ничего такого нет. «Двумерный» массив в Java это одномерный массив ссылок на одномерные массивы, каждый из которых может быть разной длинны например, а то и просто отсутствовать (null ссылка).

        Вроде такого:
        int a[][] = new int[4][];
        a[1]=new int[2];
        a[2]=new int[3];
        a[3]=new int[2];

        В результате имеем:
        a[0] — null
        a[1] — массив 2-х интов, a[1][2] — ok, a[1][3] — out of bounds
        a[2] — массив 3-х интов, a[2][3] — ok, a[2][4] — out of bounds
        a[3] — опять массив 2-х интов.

        Когда в Java надо завести именно двумерный массив, как в Си — заводим одномерный длинной NxK и делаем враппер который при доступе по i,j будет вычислять индекс как произведение i и j и доступаться к одномерному массиву уже по этому индексу.

        Единственная новость о массивах в Java которую я вынес из статьи это то, что в Java есть такой convenience как int g[][] = new int[n][n]; который сразу еще и дочерние подмассивы создает. Хотя наверно лучше б его не было — ибо сбивает с толку (что автор статьи нам продемонстрировал на практике).

        • 0
          Строго говоря в Java вообще нет двумерных массивов, поэтому автор всех здорово запутал своими параллелями с Си и Паскалем. Видимо отсюда и весь налет мистики.

          Да, это если строго. А по факту получается, что int[][] генерирует вложенные массивы, а не перемножает i и j и делает массив соответствующего размера. Т.е.:
          int a[][] = new int[N][K]
          int b[] = new int[N*K];
          a != b;
          

          Кроме того, я так предполагаю, что в мануале по Java этот момент указан…
          Так и есть, одна из первых ссылок в гугле ведет вот сюда: www.learn-java-tutorial.com/Arrays.cfm#Multidimensional-Arrays-in-Memory
          int[][] nums = new int[3][6];
          image
          • +1
            «Да, это если строго. А по факту получается, что int[][] генерирует вложенные массивы, а не перемножает i и j и делает массив соответствующего размера»
            Да, я же имнно об этом и писал.
        • +1
          P.S.
          > как произведение i и j
          Oops, ошбочка, i*N+j (-:
          • +3
            Все и так поняли =)
      • 0
        Вы не правы. Виноват в первую очередь кеш. Чтобы в этом убедиться добавьте 5-ый тест, в котором в присвоении будет arr[j*n+i] = 40; и сравните с четвертым.

        p.s. Надеюсь оптимизатор не поменяет местами циклы.
        • 0
          Это зависит от того, на каком языке написано.

          Если мы говорим про C или Pascal, то можем почувствовать напрямую влияние кэша (при случайном доступе), ошибок предсказателя переходов и тому подобные низкоуровневые эффекты. Если мы говорим о Java с его массивами-объектами, кучей, GC и барьерами в Java Memory Model — то вмешиваются ещё куча эффектов, которые могут доминировать над тем, что определяет результат на C или C++.

          Кроме того, подход к тестированию производительности кода на Java должен учитывать работу на конкретной JavaVM. В частности, работу JIT на HotSpot, коли мы тестируемся на ней. Т. е. измерение времени выполнения, как оно приведено в статье — абсолютно бесполезно. Как минимум, об этом здесь говорили leventov, gvsmirnov.
          • 0
            То что на яве к результатам влияния кэша может добавиться куча других эффектов — само собой, но как вы уже заметили — влияние кэша будет в обоих случаях, а в конкретном синтетическом примере это десятки раз.
            В общем подход должен учитывать не только виртуальную машину, но и железо, на котором код исполняется. Например у GPU есть текстурный кэш, который изначально двухмерный.
  • 0
    Проблема точно в кэше, в данном случае в расположении в памяти двумерных массивов. Если в первом цикле заменить g[i][j] на g[j][i], его скорость упадет в 20, поскольку в одном случае проход идет по строкам, элементы каждой строки в памяти близко, а в другом — по столбцам, элементы которых далеко. Я пока не знаю, как ее решить, ясно, что нельзя обращаться к элементам других строк в цикле.
    • 0
      Перепроверил на таком коде:
      public class Test2 {
        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*n + 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++) {
            for(int j = 0; j < n; j++) {
              g[j*n + i] = i + j; 
            }
          }
          en = System.nanoTime();
          System.out.println("\nTwo time " + (en - st)/1000000.d + " msc");
        }
      }
      

      Байт код второго цикла больше. Может и не кэше дело, а в способах адресации.
  • +26
    Замеры кода на Java в один прогон без прогрева и построение на этих результатах далеко идущих выводов — это тоже повод поговорить…

    Хотя тут вы получили более-менее верные оценки, это чистое везение.

    Причина замедления в том, что на каждой итерации идет дереференс массива g[j], чтение его длины, проверка на границы при записи i-го элемента, весь фарш. А когда во внутреннем цикле обращаются только к одному массиву g[i], это все JIT выносит за цикл.

    118 (скорее, 128) — это какой-то внутренний порог в HotSpot, когда он делает какой-то продвинутый анализ объектов (только массивов?) в методе, только если их меньше этого количества.

    Кстати, я на Java 8 этот порог не нашел. Возможно, теперь они все равно анализируют первые 128(?) объектов в методе, поэтому производительность деградирует постепенно с ростом N.
    • +7
      import org.openjdk.jmh.annotations.*;
      
      import java.util.concurrent.TimeUnit;
      
      
      @State(Scope.Benchmark)
      @BenchmarkMode(Mode.AverageTime)
      @OperationsPerInvocation(ArrayFill.N * ArrayFill.N)
      @OutputTimeUnit(TimeUnit.NANOSECONDS)
      public class ArrayFill {
          public static final int N = 380;
          public int[][] g;
      
          @Setup
          public void setup() {
              g = new int[N][N];
          }
      
          @GenerateMicroBenchmark
          public int simple(ArrayFill state) {
              int[][] g = state.g;
              for(int i = 0; i < g.length; i++) {
                  for(int j = 0; j < g[i].length; j++) {
                      g[i][j] = i + j;
                  }
              }
              return g[g.length - 1][g[g.length - 1].length - 1];
          }
      
          @GenerateMicroBenchmark
          public int optimized(ArrayFill state) {
              int[][] g = state.g;
              for(int i = 0; i < g.length; i++) {
                  g[i][i] = 2* i;
                  for(int j = 0; j < i; j++) {
                      g[j][i] = g[i][j] = i + j;
                  }
              }
              return g[g.length - 1][g[g.length - 1].length - 1];
          }
      }
      
      
    • –15
      Не беспокойтесь — я проверял на многих прогонах. И с прогревом тоже поэкспериментировал. К слову, автоматический прогрев по участкам кода без многократного вызова функции обычно не производится.
      Для демонстрации пишется короткий и прозрачный для понимания код, который демонстрирует проблему. Что я и сделал. Вы говорите везение? Чем больше работаешь, тем чаще везет.
      Про спец обработку массива новой строки совершенно правильно уже писал MuLLtiQ, который воспользовался javap. Там действительно идет громоздкий дереференс. Но если уже раздерибанили байткод, то есть смысл досмотреть до конца? Что там еще? И кстати, можно ли все таки воспользоваться симметричностью и сделать все быстрее чем по строкам?
      • +9
        Ну вот, проверяете один код, а публикуете другой. А народ его и запускает.

        Я байткод и тем более ассемблер вообще не смотрел, это все предположения.

        Как справедливо заметил voronaam, провальна любая попытка сэкономить на одном вшивом сложении. Если бы в цикле стояло целочисленное деление, и это был бы Си с плоскими массивами, вот тогда можно было бы.

        Нет, самый простой вариант конкретно этой задачи на Java — он же и самый быстрый.
        Что там еще?
        Разворачивание цикла, а в усложненном варианте — нет (предположение)
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            Нюанс в том, что используется массив примитивов, именно поэтому мы и наблюдаем эффект. Если же изменить тип на Integer, то оптимизированный метод будет быстрее.
        • –11
          Я видимо плохо объясняю. Я публикую код, который наилучшим образом демонстрирует проблему.
          Если бы я публиковал код в котором у меня неожиданно просел fps после рефакторинга, это было бы бессмысленно. Я выделил проблему, проверил все возможные накладки и опубликовал короткий понятный код, демонстрирующий проблему. Если Вам почему-то хочется считать, что все хорошо получилось только по счастливой случайности, боюсь я не смогу Вас переубедить.
          • НЛО прилетело и опубликовало эту надпись здесь
            • +5
              или просто сказать таким интервьюируемым «спасибо, удачи» и пойти работать в другое место.
            • 0
              Вот поэтому сейчас «майндфаки» на собеседованиях не в почёте. Гугл тоже с год как от них отказался. Майндфак и его решение на собеседовании может свидетельствовать как о неадекватности проводящего собеседование, так и о себеседуемом :)
  • 0
    Гениально! До сегодняшнего дня не задумывался. Чтобы увидеть и понять эффект достаточно поменять местами i c j в вычислении индекса.

    Кому интересно вот моя версия на С++
    // test-time.cpp : main project file.
    
    #include "stdafx.h"
    #include <windows.h>
    #include <iostream>
    
    using namespace System;
    
    __int64 GetTime()
    {
    	__int64 value = 0;
    	QueryPerformanceCounter((LARGE_INTEGER *)&value);
    	return value;
    }
    
    int main(array<System::String ^> ^args)
    {
    	int n = 8000;
        int* g = new int[n*n];
    
        __int64 st, en;
     
    	// one
        st = GetTime();
        for(int i = 0; i < n; i++) {
          for(int j = 0; j < n; j++) {
            g[i*n +j] = i + j; 
          }
        }
        en = GetTime();
        std::cout << "\n1 time ";
    	std::cout << (en - st);
    
    	// two
        st = GetTime();
        for(int i = 0; i < n; i++) {
          for(int j = 0; j < n; j++) {
            g[j*n +i] = i + j;  //j и i меняем местами
          }
        }
        en = GetTime();
        std::cout << "\n1 time ";
    	std::cout << (en - st);
    
    
    	Console::ReadKey();
        return 0;
    }
    </spoiler>
    
  • +4
    Вы еще и результаты вычислений в элементах массива g не используете. Но HotSpot их не выкинул, почему-то. Поразительно, что замеры дали адекватные результаты
    • –5
      Совершенно верно. Но почему Вы считаете, что автор непременно глуп и невнимателен? Результаты вычислений суммировались, чтоб их не выкинул оптимизатор. Когда убедился, что ничего не выбрасывается, исключил лишнее из кода. Еще раз говорю, код демонстрирует проблему. И Вы это подтверждаете. Что Вас смущает?
  • 0
    А не может ли это всё быть результатом того, что при компиляции в машинный код первого варианта JIT использует какие-то SIMD-команды процессора, а во втором варианте — нет? Ассемблерный код вариантов программы на компилируемых языках кто-то смотрел?
    • 0
      Я не смотрел, но уверен, что не использует, потому что 1) скорость была бы выше, а она довольно умеренная 2) это должна быть довольно хитрая команда, которая каждым 32 байтам присваивает значение на 1 больше, чем предыдущим. Сомневаюсь, что такая команда существует вообще.
  • +3
    Интересная задача! Посмотрел код и вот что видно. В варианте два тело цикла
          35: aaload        
          36: iload_3       
          37: aload_1       
          38: iload_3       
          39: aaload        
          40: iload_2       
          41: iload_2       
          42: iload_3       
          43: iadd          
          44: dup_x2        
          45: iastore       
          46: iastore       
    

    А в варианте один только
          27: aaload        
          28: iload_3       
          29: iload_2       
          30: iload_3       
          31: iadd          
          32: iastore       
    


    Мне кажется дело в лишнем aaload. В первом варианте компилятор работает с массивом как с одномерным. Во втором, он строго следуюет написанному коду и постоянно пихает в стек ссылку на очередной внутренний массив как на отдельный массив. Ему же надо найти g[j].

    Ну и вообще получается, что раз количество операций записи у нас одинаково (мы же весь массив инициируем), то мы хотели сэкономить на вычилении каждого из элементов. Но вычисление элемента у нас один iadd, так что после «оптимизации» мы потратили больше операций вычисляя координаты в памяти куда писать.
    • –8
      Это супер близко к полному решению. Дальнейшие разборки потребуют вникнуть в полученный код. Только учтите, что просто число команд еще не делает погоду. Да, второй цикл в два раза короче (6 команд), но он и выполняется в два раза большее число раз.
      • +2
        Хм, вообще-то мой комментарий был совсем не о количестве команд в листинге. Для интереса я заменил функцию вычисления элемента с i + j на rand.nextInt(100) / (1 + rand.nextInt(100)) * rand.nextInt(100), оставив при этом весь остальной код тем же (то есть матрица по-прежнему получится диагональная). И вот результат:

        One time 2072.3487 msc
        Two time 1246.582756 msc
        

        То есть оптимизировать таким образом имеет смысл если операция вычисления Mij = Mji достаточно «дорогая».
    • +3
      Посмотрел и дизассемблер. Ещё интересно, что JVM вынесла проверку границ за пределы цикла в «неоптимизированном» варианте. В первом варианте есть только одно место с комментарием «implicit exception», в втором их три. Я не слишком часто читают дизассемблерный код из JVM, так что дальше разбираться пожалуй не буду.

      Буду следить за обновлениями в топике. Спасибо за задачку!

      P.S. Ничего себе у вас задачки для (pre)juniour'ов :)
  • +4
    Есть еще такая вещь, как cache contentions. Суть в том, что при некоторых обстоятельствах(«удачном» размере матрицы) g[i][j] и g[j][i] приходятся на одну линию кэша(см en.wikipedia.org/wiki/CPU_cache#Associativity). Получается что при обращение к первому адресу в L1 из L2 подтягивается одна область памяти. При обращении к второму — другая. И так _каждое_! обращение. Т.е. вместо кэширования области памяти и дальнейшего чтения последующих напрямую из L1 мы каждый раз ждем перечитывания из L2. Та же история может быть с L2, только обходится еще дороже — перечитывать из L3 или того хуже из памяти.
    Подробно про такие вещи хорошо рассказывается в «Optimizing software in C++» by Agner Fog — www.agner.org/optimize/optimizing_cpp.pdf
  • +9
    Я думаю, что это не задача для новичка, потому, что это архитектурно-зависимая проблема.
    Также задача зависит от уровня оптимизации компилятора, который может «удачный» вариант развернуть в неудачный ассемблер. Был у меня такой опыт, когда мне нужно было оптимизировать кусок кода, но после компиляции, ассемблер на выходе был хуже, чем изначальный вариант. А все потому, что своими действиями я сбивал оптимизатор компилятора и тот принимал малопитательные решения.
    Если уже говорить о кешах — тут вообще тоска — размер строки кэша может варьироваться от 16 байт до 256. Я думаю что даже эти рамки можно поставить под сомнение. Так что же, писать код который будет зависеть от процессора? А как быть с системами реального времени где кэш часто отсутствует в меру своей непредсказуемости? Да и не стоит забывать про то что есть системы без поддержки страниц памяти, или наоборот с поддержкой огромных страниц.
    Ну а если конкретнее — Вы хотели инициализировать массив — мой ответ memset!
    • –8
      Задач для новичка не бывает. Есть просто задачи. Человек их решает, мыслит, выдвигает гипотезы. Ты наблюдаешь, общаешься. Вы видите, как коллективный разум на три счета здесь раскрутил ситуацию?
      memset конечно форевер, но это подмена задачи. Вопрос именно в доступе, а не в том, что мы с ним делаем.
      А согласитесь, забавная вышла задачка на ровном месте. Нет?
      • 0
        Странный подход с тем же успехом можно пытаться на вступительных экзаменах по математике не просить решать школьные задачи, а попросить из фундаментальных принципов придумать и обосновать, к примеру, интеграл. И посмотреть, как человек мыслит и выдвигает гипотезы. Но лично я знаю всего одного человека, который смог интеграл придумать самостоятельно, а подавляющее большинство людей приходит учиться, что бы учиться и проверять надо что они знаю, и есть ли смысл их учить. Или у вас в конторе все сплошь гении мирового масштаба, у в руководство берут по предъявлению нобелевского сертификата?
  • 0
    Когда мы последовательно записываем адреса, то вторая запись в границах одной кэш линейки застоллит процессор — он будет ждать окончания записи линейки в основную память. Когда доступы идут в разнобой (особенно в последнем примере с рандомным доступом к линейному массиву), то writeback происходит спекулятивно, без столла.
    • –1
      Согласен. А что writeback всегда происходит после изменения одного элемента массива?
      • +1
        Нет, пожалуй что writeback здесь будет происходить вообще только при выстеснении линейки из кэша…

        Кстати, в примере с одномерным массивом, если тела циклов поменять местами, то второй цикл будет все равно работать быстрее. То есть второй цикл будет всегда быстрее, можно предположить что вступает в игру прогрев кэшей.
        • –1
          Точно. Увлекся полемикой.
          Согласен с Вашим предположением.
          Более точные эксперименты подтверждают.
    • +2
      > Когда мы последовательно записываем адреса, то вторая запись в границах одной кэш линейки застоллит процессор
      совершенно неверно.
      • 0
        Да, это я маху дал :)
  • +1
    К стати — вариант с кэшем не совсем уместен по отношению к первому примеру, поскольку второй индекс — это как раз строка, то есть во внутреннем цикле будет проход как раз по строке — последовательно в памяти. Прошу прощения — невнимательно читал. Ведь я же все знаю про массивы! ;)

    Все-таки мало кому из начинающих разработчиков может прийти в голову думать о проблемах касательно способа доступа к памяти или особенностях реализации компилятора/виртуальной машины/интерпретатора.

    Изначальный код, возможно, будет превосходно работать с каким-то компилятором в силу того, что он попадает под определенный шаблон оптимизации, точно так же, как и во многих случая i*2 === i<<1 для беззнаковых целых, если процессор поддерживает операцию сдвига.
    Или например в с/с++ массивы вида int (a*)[n] и int **a неравноправны по отношению как к потреблению памяти так и доступа.

    Я согласен, что задача интересна тем, чтоб посмотреть как человек будет пытаться анализировать ситуацию. И да, возникают вопросы =)
  • +4
    Запостил провокационный вопрос на SO, пусть господа соревнуются в точности ответа ;)
    Только — цыц!
    stackoverflow.com/questions/21639405/java-2d-array-fill-innocent-optimization-caused-terrible-slowdown
    • +1
      … и правильный ответ там на него уже дали.
      • 0
        Правильный-то правильный, но довольно поверхностный, к сожалению. А вот Chen Gupta (думаю, что это IEMazurok) порадовал :)
        • +3
          Порадовал чем? Там же очередной лжебенчмарк, замеряющий время интерпретации + время JIT-компиляции. Небось, еще и на клиентской 32-битной JVM. Если измерять по-честному, разница получается мизерная, причем то в пользу одного, то в пользу другого варианта, в зависимости от опций JVM (UseCompressedOops).

          [sarcasm]Чего уж там, давайте сразу на 10 итераций ручной loop unrolling сделаем — глядишь, будет еще эффективнее.[/sarcasm]
          • +1
            Легендой порадовал :)
  • +7
    Ничего загадочного. В «оптимизированном» варианте просто-напросто больше операций. Гораздо больше.
    Если в простом примере на одной итерации внутреннего цикла, грубо говоря, делается один store (не зависящий от предыдущих), то во втором примере на каждой итерации делается:
      1. load указателя на j-ю строку;
      2. load длинны массива;
      3. bounds check;
      4. и два store.
    причем эти операции не могут выполняться конвейерно, т.к. зависят от результатов предыдущих операций.
    Добавим ко всему этому, что обращение к памяти сильно разнесено, а, значит, кеши и префетчи не работают, куча TLB промахов и всё такое.
  • +1
    Интересно вот: а действительно ли в условиях нынешней сумасшедшей конкурентной гонки находится возможность заниматься вот такой оптимизацией?

    Или же в данном примере проверяется навыки кандидата в оптимизации? Которые потом применяются не в улучшении производительности в работе с массивами, а в других, более серьезных ситуациях.

    Расскажите, многоопытные товарищи
    • +1
      Возможность и необходимость оптимизации, наверное, находится. Ведь не всегда есть возможность заставить пользователя удвоить число ядер или частоту — иногда надо выигрывать и за счёт более подходящего кода. Если рассматривать «оптимизацию» как улучшение существующего кода, то упражнение не о том — скорее, оно показывает, как писать надо, а как не надо. Чтобы при наличии выбора у человека было больше информации (пусть и для данного конкретного компилятора и процессора). А проверялось, насколько я понял, умение разбираться в не очень знакомой ситуации, а массивы и оптимизация тут, в общем, ни при чём — это всего лишь выбор игрового сценария.
      • +1
        Выбор, мягко говоря, неудачный. Это все равно что дать человеку решать шахматную задачу,
        рассказать как ходят фигуры, но не сказать что пешка может стать ферзем.
        Человек, на основании своих базовых знаний, просто не сможет логически вывести такой вариант.
        • 0
          Думаю, что к его распоряжению все знания интернета. И главное, может быть, даже не то, что даст он правильный ответ или нет, а куда и как будет копать.
          • 0
            В случае java, за этими несколькими строчками кода, будет еще jit компилятор с profile optimization со своими правилами и багами. Что может сказать человек претендующий на junior позицию в этом случае?
            • 0
              Нам в универе рассказывали об этом казусе еще на третьем курсе, в рамках ассемблера :-)
              А я тогда еще даже и не работал программистом :-)
  • +7
    Premature optimization is the root of all evil — Donald Ervin Knuth
    • +1
      In established engineering disciplines a 12% improvement, easily obtained, is never considered marginal and I believe the same viewpoint should prevail in software engineering — Donald Ervin Knuth
      • +1
        Ключевое слово здесь «premature». После того как выбраны алгоритмы, система написана и обладает необходимой функциональностью, есть тесты и измерена производительность на реальных данных и не хватает этих самых 12%, вот тогда можно приступать к такого рода оптимизации. Заниматься этим до — значит просто терять время и тормозить проект.
        • +3
          Premature optimization — это попытки экономии «на спичках», когда мы не понимаем — будет реальный выигрыш или нет. К сожалению под флагом борьбы с ними зачастую люди с легкостью вводят в систему прокладки и абстракции, каждая из которых вроде как и не сильно на что-то влияет, а в сумме — они дают ощутимое замедление и/или увеличение в размерах.

          Потеря 12% десять раз — это замедление программы (или увеличение потребности в памяти или… нужное подчеркнуть) втрое. И если вы спохватитесь уже тогда, когда «система написана и обладает необходимой функциональностью», то в большинстве случаев вам придётся всё выкинуть к чёртовой бабушке и начать заново.

          Простой пример: как вы будете бороться с тем, что ваша тормозит тупо из-за того, что у вас вместо конечного автомата обработка запросов осуществляется в виде сплошного участка кода, что требует отводить на каждый запрос свой поток? А с тем, что у вас борьба за православный DI привела к тому, что объекты, которые, в общем-то, не меняются во время запроса при этом преобразуются 100500 раз?

          Из моего опыта: программисты на C/C++ иногда грешат этими самыми «premature optimizations», но по сравнению с программистами на Java, готовыми под развеваемыми вами знамёными выпускать монстров требующих гигабайт памяти и многоядерных процессоров для решения задач где, по хорошему, и 16-битного контроллера с парой мегабайт памяти должно хватать — они паиньки.
          • +2
            Тут мы вступаем на зыбкую почву «эффективности». По сути, даже код на ассемблере, в какой то мере абстракция. Ниже лежит процессор со спекулятивным исполнением команд, branch predictor, декодеры команд, scheduler микрокоманд, иерархическая модель памяти + NUMA и т.д. Чем выше уровень абстракций — тем быстрее можно получить работающий софт. Но вот вычислить этот максимально допустимый уровень и есть основная задача.
  • +9
    Зря вы подобные «бенчмарки» выкладываете, всё-таки.

    Вот увидят «новички» ваш код и то, каким уверенным слогом вы рассказываете о том, что там происходит. И будут потом писать так же: замерять один раз, без прогрева, с DCE, и прочими радостями.

    А те, кто знает, что с таким подходом не так, не будут вас всерьёз воспринимать. А вам от этого комментарии читать обидно будет.
  • 0
    Похожий пример досконально разобран в «What Every Programmer Should Know About Memory» by Ulrich Drepper.
    Теперь намного раньше кончаются все кэши — L1D, L2, L3. Также не стоит забывать про Translation Look-Aside Buffer(TLB).
    Добавлю интересный артефакт — подобный тест может быть своеобразным бенчмарком TLB внутри виртуальной машины, так как она там более многоуровневая.
  • 0
    Странно, а если использовать два массива, то второй вариант работает быстрее. Хотя, наверное, что-то похожее уже предлагали выше :) Что не так? Оптимизированный вариант быстрее, прямой доступ к ячейке памяти быстрее перебора… или я уже переседел в субботу на работе?
    • 0
      У в этом примере массив целиком помещается в кэш -> оптимизированный вариант работает быстрее.
      • 0
        Да, я уже разобрался. Спасибо.
  • 0
    Не ясно следующее:

    Самым быстрым является простой способ заполнения симметричного массива с помощью двух вложенных циклов? Так и отвечать работодателю на собеседовании, если он вдруг задаст такую задачку?

    Или же существует лучшее решение?
    • –4
      Существует лучшее решение. С помощью четырёх вложенных циклов. Есть и другие. В соответствующей статье об этом довольно много написано. Конкретно про работу с массивами — в пятой части.

      P.S. Топикстартер — молодец: среди программистов на C/C++ обычно людей, понимающих что происходит, много, но программисты на Java в 90% почему-то пребывают в наивной убеждённости, что они-то уж работают на высокоуровневом языке и до них-то все эти кеши и префетчи никак добраться не могут. Что, разумеется, ни разу не так, но осознать это непросто, так как опыта «чистого» общения со всей этой машинерией у них (в отличие от программистов, работающих на C/C++) нету.
      • +3
        Довольно опрометчиво судить о коде на Java в 2014 году по статье о C++ 2007-го.
  • +2
    По-моему все просто первый вариант векторизуется, второй — нет.
  • 0
    Что за чушь, бежать от таких работодателей сломя голову, вот оптимизировал:

    int n = 8000;

    int g[][] = new int[n][n];
    int gTmp[] = new int[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++) {
    gTmp[i] = 1;
    }

    for (int j = 0; j < n; j++) {
    g[j] = gTmp;
    }
    en = System.nanoTime();
    System.out.println("\nTwo time " + (en — st) / 1000000.d + " msc");

    One time 39.901124 msc

    Two time 0.133835 msc
    • 0
      я что-то не понимаю, или второй вариант заполняет не суммой индексов?
      • +1
        Можно и суммой индексов, так же быстро. Но на С++:

        int N=8000;
        int **A=new int*[N];
        int *B=new int[2*N-1];
        
        for(int a=0;a<2*N-1;a++) B[a]=a;
        for(int a=0;a<N;a++) A[a]=B+a;
        

      • +1
        в задании автор просит инициализировать массив чем угодно.
    • +1
      Ваш вариант подходит для заполнения неизменяемого массива — но не для инициализации изменяемого. А вообще, идея хорошая, особенно вариант ниже на плюсах…
    • 0
      а потом говорим:
      gTmp[0] = -999;
      for (int i = 0; i < n; i++) {
      	for (int j = 0; j < n; j++) {
      		System.out.print(g[i][j] + " ");
      	}
      	System.out.println();
      }
      

      И видим, что на самом деле у нас в двумерном массиве используется N ссылок на один и тот же массив gTmp, т, е. используется в N раз меньше памяти. И правильный вариант такой:
      st = System.nanoTime();
      for (int i = 0; i < n; i++) {
      	gTmp[i] = 1;
      }
      
      for (int j = 0; j < n; j++) {
      	System.arraycopy(gTmp, 0, g[j], 0, n);
      }
      en = System.nanoTime();
      


      Один прогон которого даст примерно одинаковые времена:

      One time 56.96192 msc

      Two time 50.87872 msc
      • 0
        спасибо капитан, но в ТЗ не было никаких ограничений, я заполнил массив «чем угодно».
        • 0
          Я рад, что для Вас это очевидно. Но вас же читают дети:)
        • +1
          Тогда и первый цикл надо заменить на Arrays.fill (который прямой memset).

          А вообще, если вы так понимаете задачу, то вот этот код тоже подойдёт:
            int g[][] = new int[n][n];
          

          Всё. Я «заполнил» массив нулями. Ноль вполне себе «что угодно».
  • +14
    В статье превышен градус самомнения и преждевременной оптимизации. Но мне все-таки правда интересно, где и в каких проектах такая оптимизация может быть полезной? Ведь по сути это экономия на спичках, а если нет, и правда нужна каждая миллисекунда при обработке матриц больших размеренностей, то неужели для java нет jni библиотеки для таких типовых операций на матрицах?
    • 0
      Ответ на вопрос, «почему так происходит» был дан lunserv в комментарии чуть выше: habrahabr.ru/post/211747/#comment_7289139
      Я его чуть дополнил примером.
      Но мне все-таки правда интересно, где и в каких проектах такая оптимизация может быть полезной? Ведь по сути это экономия на спичках, а если нет, и правда нужна каждая миллисекунда при обработке матриц больших размеренностей, то неужели для java нет jni библиотеки для таких типовых операций на матрицах?

      На самом деле, для разных задач бывают разные требования. Если данную ситуацию рассматривать с общей точки зрения (обычное программирование) — это не экономия на спичках и не оптимизация, а выбор правильного решения задачи. Применение массива с массивами имеет смысл только для данных, в которых строки или столбцы могут быть разной размерности и не критично по скорости. Все. Во всех остальных случаях, когда в массиве данных строки и столбцы одинаковые или важна скорость, то следует применять обычный линейный массив, чтобы исключить лишний код, который может быт вставлен «шибко умным» компилятором и/или оптимизатором. Сюда относятся, например изображения, матрицы, таблицы и т.п. Ибо в любом случае, память в ПК линейная, т.о. это самое естественное представление данных.
      • 0
        А что быстрее — двойное обращение по индексу, или умножение на размер по одной из координат, который тоже надо брать из памяти? Кроме того, если машина 32-битная, а массив гигабайтный, то единым куском его могут и не дать. Там массив массивов может оказаться правильнее.
        • 0
          Если в целом — то монопенисуально, т.е. без разницы — будет там перемножение индексов или сложение смещений адресов в массиве. Это если смотреть с точки зрения конечных действий. Все зависит от конретной реализации в конкретной железке. Просто не забываем, что там еще может оказаться код проверки на попадание индекса в размер массива, какие-то еще процедуры инициализации и все такое прочее. А так я уже сказал — выбор конкретного решения зависит от конкретной задачи. В разных случаях один и тот же код может быть разной степени правильности. Как отрицательной, так и положительной.
  • +7
    Неудачная попытка сэкономить на спичках в ущерб понятности кода. Для собеседований годится только разве что для того, чтобы дать ответ на вопрос «знаком ли кандидат с эффектами падения производительности из-за случайного доступа к памяти». К применению джавы в реальном мире имеет очень слабое отношение, как и к квалификации кандидата. Если, конечно, работа по предлагаемой вакансии не состоит в тюнинге и пропатчивании джавского JIT-компилятора.
  • +4
    Ну так разобрались бы перед тем, как пост писать.
  • +3
    Вообще такой пример надо «оптимизировать» распараллеливанием по ядрам исходного алгоритма (сохранится эффективность последовательного доступа и будут задействованы все ядра).
  • +21
    Все проблемы в следующей фразе:
    «По этому обращаем его внимание на тот факт, что значения расположены симметрично и просим сэкономить на итерациях циклов. Конечно, зачем пробегать все значения индексов, когда можно пройти только нижний треугольник?»
    А дело в том, что экономить нужно не на итерациях, а на операциях. Всё же просто:
    — В оригинальном коде у нас N^2 записей в память — и как ты тут не оптимизируй, именно столько и останется. тут не соптимизировать.
    — Далее, а стоит ли что нибудь нам i+j? Да ничего оно не стоит. Эта сумма на самом деле индуктивная и заменять такие выражения на инкремент умели еще в 70-х. :) Да к тому же это и пофиг, как i+j так и v+1 вычислаются с латенси в 1 такт, причем на исполнение программы этот 1 такт вообще никак не влияет, пойдет в параллель.
    — адресная арифметика? Так же индуктивность + целочисленная арифметика. Intel CPU уже давно содержат по 3 целочисленных сложителя, у AMD тоже не один.
    — Обслуживание циклов? Цикл короткий, с вероятностью 99% попадает под LSD (Loop Stream Detector). Profit.

    Итого, имеем, что у нас есть N квадрат записей в память. Остальные операции можно не считать. Так что тут оптимизировать? Тут любое прикосновение к коду будет не оптимизацией, а пессимизацией, что автор нам успешно и продемонстрировал.

    Вот если бы вместо (i+j) мы считали (int)(sin((double)(i+j))) тогда можно было о чем-нибудь говорить.

  • –3
    Хорошая статья, заинтриговала. Жду полного решения ;)
  • +1
    Как способ потроллить / проверить соискателя — годится, а как бенчмарка — не очень.
    Максимальная скорость, если именно за максимумом гоняться, — достигнется на каком-то крайне неочевидном алгоритме.
    Потому что в нём будут
    — префетчи
    — разворачивание внутреннего и/или внешнего циклов
    — выравнивания по границам линеек
    — использование SIMD-интринсиков
    причём размеры префетчей и развёртываний будут зависеть от конкретной архитектуры, т.е. где-то рядом будет ещё и код, интересующийся версией процессора.

    На сях-плюсях проще не трахать себе мозг всеми этими делами, а взять готовую матричную библиотеку наподобие Eigen или MKL.
    На яве — не знаю, не играл.

    MKL, кстати, сильно различается по скорости первого и последующих запусков, — прогревает свои кэши.
  • –10
    Прочитал стать и первое ощущение от прочитанного — уровень юниоров программистов упал примерно раз в пятьдесят. Это действительно при наборе программистов такие собеседования или все же каких-нибудь сисадминов? Теперь понимаю почему я не могу пройти собеседования, собеседующие просто не понимают о чем я говорю :)
  • –2
    Андрей Терещенко, любезно разрешил разместить здесь цитату из нашего с ним обсуждения этой же темы на фейсбуке. Возможно она покажется полезной.
    Цитата
    image
    "… И вот интересная картинка к коду ideone.com/k8h9k0 (предыдущий комментарий). На ней видно, как в определенные моменты с ростом размера данных, время исполнения увеличивается. Так на желтой линии по сравнению с черной видно влияние кеша, а разница между желтой и оранжевой (или синей и черной) — влияние вложенных массивов."
  • +3
    А что там разбираться то? Запускаем, компилируем, смотрим ассемблерный выхлоп:
    Осторожно, ASM
    быстрый случай:
    Project3.dpr.16: for i:=1 to n-1 do
    0040712F 8B1D98BB4000     mov ebx,[$0040bb98]
    00407135 4B               dec ebx
    00407136 85DB             test ebx,ebx
    00407138 7E2C             jle $00407166
    0040713A B901000000       mov ecx,$00000001
    Project3.dpr.17: for j:=1 to n-1 do
    0040713F 8B1598BB4000     mov edx,[$0040bb98]
    00407145 4A               dec edx
    00407146 85D2             test edx,edx
    00407148 7E18             jle $00407162
    0040714A B801000000       mov eax,$00000001
    Project3.dpr.18: g[i,j] := i + j;
    0040714F 8B359CBB4000     mov esi,[$0040bb9c]
    00407155 8B348E           mov esi,[esi+ecx*4]
    00407158 8D3C08           lea edi,[eax+ecx]
    0040715B 893C86           mov [esi+eax*4],edi
    0040715E 40               inc eax
    Project3.dpr.17: for j:=1 to n-1 do
    0040715F 4A               dec edx
    00407160 75ED             jnz $0040714f
    Project3.dpr.18: g[i,j] := i + j;
    00407162 41               inc ecx
    Project3.dpr.16: for i:=1 to n-1 do
    00407163 4B               dec ebx
    00407164 75D9             jnz $0040713f
    


    медленный случай:
    Project3.dpr.22: for i:=1 to n-1 do
    004071E2 8B1D98BB4000     mov ebx,[$0040bb98]
    004071E8 4B               dec ebx
    004071E9 85DB             test ebx,ebx
    004071EB 7E2C             jle $00407219
    004071ED B901000000       mov ecx,$00000001
    Project3.dpr.23: for j:=1 to n-1 do
    004071F2 8B1598BB4000     mov edx,[$0040bb98]
    004071F8 4A               dec edx
    004071F9 85D2             test edx,edx
    004071FB 7E18             jle $00407215
    004071FD B801000000       mov eax,$00000001
    Project3.dpr.24: g[j,i] := i + j;
    00407202 8B359CBB4000     mov esi,[$0040bb9c]
    00407208 8B3486           mov esi,[esi+eax*4]
    0040720B 8D3C08           lea edi,[eax+ecx]
    0040720E 893C8E           mov [esi+ecx*4],edi
    00407211 40               inc eax
    Project3.dpr.23: for j:=1 to n-1 do
    00407212 4A               dec edx
    00407213 75ED             jnz $00407202
    Project3.dpr.24: g[j,i] := i + j;
    00407215 41               inc ecx
    Project3.dpr.22: for i:=1 to n-1 do
    00407216 4B               dec ebx
    00407217 75D9             jnz $004071f2
    



    Код практически не меняется за исключением кусочка с присвоением.
    Для быстрого случая:
    00407155 8B348E           mov esi,[esi+ecx*4]
    00407158 8D3C08           lea edi,[eax+ecx]
    0040715B 893C86           mov [esi+eax*4],edi
    


    Для медленного случая:
    00407208 8B3486           mov esi,[esi+eax*4]
    0040720B 8D3C08           lea edi,[eax+ecx]
    0040720E 893C8E           mov [esi+ecx*4],edi
    


    В ecx у нас в обоих случаях счетчик внешнего цикла (i), а в eax — вложенного (j).
    А поскольку ecx меняется в 10000 раз меньше, то инструкция mov esi,[esi+ecx*4] в первом случае будет закеширована на каждые 10000 операций. Если в первом случае кешмиссов будет 10000, то во втором 10000*10000.
    Я не знаю как у кого, но у нас на численных методах в универе была даже задача: оптимизация умножения больших матриц, которая заключалась в транспонировании матрицы перед умножением. Выйгрыш в скорости в процентном соотношении был даже выше чем в вашем примере.

    p.s. Я не понял, а где подсветка ASM для тега Source? Нету чтоль?
    • 0
      Дополню свой комментарий.
      Вообще массив массивов использовать — это может и удобно для чтения кода, но чревато более частыми кешмиссами, ибо это будет не один кусок данных в памяти, как менеджер памяти раскидает — так оно и будет. И для массивов размерности [10000, 1] — перерасход памяти, так как массивы в большинстве ЯП хранят по отрицательному смещению служебную информацию (счетчики ссылок, размер и т.п.), а поскольку память под массив выделяется менеджером памяти, то менеджер памяти под блок памяти тоже хранит служебную информацию ;)
      Итого выделив массив в 4 байта мы реально можем выделить 12-16 байт памяти. Я уже молчу о том, что выделить 10000 раз память под массив в 4 байта — это на порядки медленнее чем выделить один раз 40000 байт.

      В общем рекомендую использовать одномерные массивы, а индекс считать самому, чтобы не получить в пах от производительности. Ну и само собой не забывать про кеш.
      • 0
        А если предполагаются матрично-матричные операции (умножение там, транспонирование...), то наиболее дружественное к кэшу размещение — Z-порядок, или порядок Мортона, поверх одномерных массивов.
    • +1
      И еще дополню:
      Пока лидирует версия, что «виноват» кэш процессора.

      Т.е. случайный доступ к элементам большого массива на ~10% медленнее чем последовательный. Возможно и в правду какую-то роль может сыграть кэш. Однако, в исходной ситуации производительность проседала в разы. Значит есть еще что-то.

      И все таки виноват кэш процессора. Как это работает:
      Представим, что в кэш у нас влезло 50К элементов. При случайном доступе к массиву в 100К элементов у нас вероятность попасть в кэш аж 50%. Для чистоты эксперимента давайте увеличим одномерный массив до 10000*10000 = 100КК элементов, и бегать будем по нему не случайным доступом, а двойным циклом по индексам g[i*10000+j] в одном случае, и g[j*10000+i] во втором. Вы сильно удивитесь, но разница будет не 10% как при случайном доступе.
    • +1
      Я не понял, а где подсветка ASM для тега Source? Нету чтоль?
      Учитывая количество различных ассемблеров даже в пределах x86_64, ожидаемо, что её нет.
      • 0
        У всех разных ассемблеров есть общая часть, каждая строка может быть представлена как:
        <инструкция> [операдны] [; комментарий]
        есть еще лейблы, просто строки с комментариями, макросы, но думаю распарсить и правильно выровнять код в общем случае — не большая проблема. Под подсветкой я имел ввиду не столько подсветку, сколько выравнивание.
        • 0
          Кроме собственно ассемблерного кода, который публикуется относительно редко, народ часто выкладывает листинг дизасемблера. Там может быть колонка с адресами, с командами as-is (до дизассемблирования), бывают разные варианты записи констант (навскидку 0, $0, #0), разное количество аргументов (в ARM команда push/pop может применяться к группе регистров, до 13 штук разом), разные способы обозначения косвенной адресации, постинкрементов и прочей нечисти. Так что не факт, что появятся в разумном будущем.
  • 0
    Делаю ставку на кэш и векторизацию / распараллеливание.
  • +1
    А как называется ваша контора?
    • +1
      А с какой целью интересуетесь? Потроллить автора на собеседовании, обходить стороной? ,)
      • +3
        Второе.
  • +2
    А почему бы не спросить в лоб: знает ли соискатель про профайлеры :)
  • 0
    Статья, вне всякого сомнения, интересная и полезная. Но — не про массивы.
  • 0
    Вот код вообще без массивов, но второй луп бегает в 50 (!) раз медленнее (если я конечно ничего не перепутал).

    public class App 
    {
        int x = 0;
        public void doit() {
            ++ x;
        }
        
        public static void main( String[] args ) throws Exception
        {
            final int NUM = 1000000000;
            final App a = new App();
            int s = 0;
            for (int w = 0; w < 10; ++ w) {
                a.x = 0;
                long t1 = System.nanoTime();
                for (int k = 0; k < NUM; ++ k) { // first loop
                    a.doit();
                }        
                double r1 = System.nanoTime() - t1;
    
                a.x = 0;
                long t2 = System.nanoTime();
                for (int k = 0; k < NUM; ++ k) { // second loop
                    a.doit();
                }        
                double r2 = System.nanoTime() - t2;
            
                System.out.println( r1/NUM + "\t" + r2/NUM);
            }
        }
    }
    


    Вот что он печатает:
    0.044185653	2.537382267
    0.049913582	2.077448235
    0.04407932	2.153127426
    0.045671495	2.118753017
    0.045120937	2.110466841
    0.044090422	2.101584099
    0.044260234	2.079228211
    0.044720426	2.107346468
    0.045007642	2.092461545
    0.044005747	2.078015597
    


    Я даже не знаю в какую сторону думать.
    • +2
      44мс — это очень мало для цикла из миллиарда итераций. Даже если процессор с тактовой частотой 4ГГц делает по итерации за такт, выходит 250мс. Но реальное время должно быть еще больше — ведь на каждой итерации не менее четырех команд (++x, ++k, сравнение и условный переход).

      По всей видимости, оптимизатор из первого цикла что-то вырезал. Кабы не сам цикл. Правда, в таком случае 44мс становится уже нереально много…

      В любом случае, такое поведение оптимизатора заставляет по-новому взглянуть на бенчмарки автора и задать вопрос: а что они вообще измеряют?
      • 0
        javap -c App.class показывает, что куски асемблера для обоих циклов одинаковые.
        Ниже xlix123, похоже что объяснил, почему это происходит.
        • +1
          javap показывает байткод для JVM, а не ассемблер который будет выполнять ваш CPU.
    • 0
      Особенность profile optimization, похожий баг.

      $ java -version
      java version "1.7.0_45"
      Java(TM) SE Runtime Environment (build 1.7.0_45-b18)
      Java HotSpot(TM) 64-Bit Server VM (build 24.45-b08, mixed mode)
      
      $ java App
      0.039184857     2.360865017
      0.038515955     1.953248084
      0.033702157     1.955458985
      0.033699063     1.953420415
      0.03370587      1.952605481
      0.033703395     1.956728721
      0.033702775     1.954714283
      0.033710201     1.954150574
      0.033706178     1.95341268
      0.033711439     1.952654055
      
      $ java -XX:MaxTrivialSize=50 App
      0.039914707     0.01686856
      0.045489296     0.033697825
      0.033701847     0.033747329
      0.033702776     0.033704942
      0.03370061      0.033698754
      0.033699992     0.033697207
      0.033698135     0.033700919
      0.033698445     0.033698135
      0.033698135     0.033699373
      0.033708345     0.033699682
      
  • –1
    Возможно повторюсь, но ошибка здесь в частом ненужном обращении к индексам. Сразу надо заметить, что «оптимизация» треугольниками ложная, т.к. (i+j) — это ничего не стоящая операция, по сравнению с правильным обходом массива.
    Надо понимать, что в Java двумерные массивы не являются матрицами, а массивами из массивов. Поэтому оптимальным способом представления матрицы является ее компактификация в одномерный массив. Но раз уж задание с двумерным массивом, попробуем оптимизировать…
    g[i] дает указатель на одномерный массив строки, причем вычисляется при заполнении каждого столбца. При этом происходит вычисление смещения элемента, проверка выхода за границы и доступ к объекту по указателю. Это можно исключить:

    for(int i = 0; i < n; i++) { int[] row = g[i]; for(int j = 0; j < n; j++) { row[j] = i + j; } }
  • 0
    Воспользоваться симметрией, наверно, не получится — накладные расходы на доступ к произвольным элементам съедают все.
    Вариант Throwable хорош, но до него додумался оптимизатор — работает он ровно так же, как первоначальный код.
    Удивительно, но такой вариант работает немного быстрее:
    for(int i = 0; i < n; i++) {
    	g[0][i] = i;
    }
    for(int i = 1; i < n; i++) {
    	for(int j = 0; j < n; j++) {
    		g[i][j] = g[i-1][j]+1;
    	}
    }
    

    Возможно, из-за первой строки?
  • 0
    Для заполнения — Array.fill например.
    Для Си и иже с ними — вообще memset(buf, X, sizeof(buf[0])*n*n);
  • 0
    g: Array of Array of Integer;

    n := 10000;
    SetLength(g, n, n);

    for i:=1 to n-1 do
    for j:=1 to n-1 do
    g[i,j] := i + j;


    Динамические массивы в паскале начинаются с нулевого индекса.
  • 0
    Проверял на двумерных массивах на Java и на С++, а также на одномерных, с искусственно реализованной двумерностью вида A[i*n+j].

    C++
    [][]One time 90 mcs
    [][]Two time 710 mcs
    []One time 80 mcs
    []Two time 830 mcs

    Во всех случаях, за исключение первого (массив массивов) имеем одну и ту же физическую модель — обычной линейной памяти (двумерный массив в Си «строгается» по строчкам). Вывод: разные скорости — эффект вытеснения из кэша хоть по LRU, хоть по FIFO. Если «прыгать» по адресам через n элементов (т.е. по столбцам), то независимо от размера подгружаемого в кэш блока периодически будет возникать ситуация, когда будет вытесняться тот блок, в которому будет СЛЕДУЮЩЕЕ обращение. Разница, похоже, соответствует отношению времени доступа к «оперативной памяти» и кэш.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.