Arhn - архитектура программирования

Как можно улучшить скорость вложенных массивов в Julia?

Следующая функция nested_arrays генерирует (что удивительно) вложенный массив «глубины» n. Однако при работе даже с небольшими значениями n (2, 3 и т. Д.) Запуск и отображение вывода занимает достаточно много времени.

julia> nested_arrays(n) = n == 1 ? [1] : [nested_arrays(n - 1)]
nested_arrays (generic function with 1 method)

julia> nested_arrays(1)
1-element Array{Int64,1}:
 1

julia> nested_arrays(2)
1-element Array{Array{Int64,1},1}:
 [1]

julia> nested_arrays(3)
1-element Array{Array{Array{Int64,1},1},1}:
 Array{Int64,1}[[1]]

julia> nested_arrays(10)
1-element Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1}:
 Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1}[Array{Array{Array{Array{Array{Int64,1},1},1},1},1}[Array{Array{Array{Array{Int64,1},1},1},1}[Array{Array{Array{Int64,1},1},1}[Array{Array{Int64,1},1}[Array{Int64,1}[[1]]]]]]]]]

Интересно, что при использовании макроса @time или ; в конце строки вычисление результата занимает относительно мало времени. Вместо этого большую часть времени занимает фактическое отображение результата в REPL.

Это странное поведение не отображается, например, в Python.

In [1]: def nested_lists(n):
   ...:     if n == 1:
   ...:         return [1]
   ...:     return [nested_lists(n - 1)]
   ...: 

In [2]: nested_lists(10)
Out[2]: [[[[[[[[[[1]]]]]]]]]]

In [3]: %time nested_lists(100)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 37.7 µs
Out[3]: [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[1]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]

Почему эта функция в Юлии такая медленная? Джулия перекомпилирует функцию display для разных типов T в Array{T, 1}? Если да, то почему?

Можно ли повысить скорость этого кода или просто не делать этого в Юлии? В практическом смысле меня больше всего беспокоит, например, загрузка сложного вложенного файла JSON, в котором просто использовать n-мерный массив было бы невозможно.

arrays nested julia
24.03.2017

Ответы:


1

Да, это полностью связано со временем компиляции. Вы можете увидеть это, @time вставив display. Во второй раз вы показываете это быстро:

julia> nested_arrays(n) = n == 1 ? [1] : [nested_arrays(n - 1)]
nested_arrays (generic function with 1 method)

julia> @time display(nested_arrays(15));
1-element Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1},1},1},1},1}:
 Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1}[Array{Array{Array{Array{Array{Int64,1},1},1},1},1}[Array{Array{Array{Array{Int64,1},1},1},1}[Array{Array{Array{Int64,1},1},1}[Array{Array{Int64,1},1}[Array{Int64,1}[[1]]]]]]]]]]]]]]
 11.682721 seconds (8.83 M allocations: 371.698 MB, 1.82% gc time)

julia> @time display(nested_arrays(15));
1-element Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1},1},1},1},1}:
 Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1},1}[Array{Array{Array{Array{Array{Array{Int64,1},1},1},1},1},1}[Array{Array{Array{Array{Array{Int64,1},1},1},1},1}[Array{Array{Array{Array{Int64,1},1},1},1}[Array{Array{Array{Int64,1},1},1}[Array{Array{Int64,1},1}[Array{Int64,1}[[1]]]]]]]]]]]]]]
  0.001688 seconds (2.38 k allocations: 102.766 KB)

Так почему это так медленно? Дисплей здесь рекурсивно просматривает все массивы и печатает их вложенными друг в друга. Это рекурсивный вызов show с 14 различными типами - один с 14 вложенными массивами, затем его элемент с 13 вложенными массивами, затем его элемент с 12… и так далее! Каждый из этих show методов компилируется независимо. Компиляция специализированных методов для определенных типов элементов - ключевая часть того, как Джулия может создавать очень эффективный код. Это означает, что он может специализировать каждую отдельную операцию, выполняемую с каждым элементом, без какой-либо проверки или отправки типа во время выполнения. К сожалению, в этом случае это мешает.

Вы можете обойти это с помощью массива Any[]; в контексте файла JSON это имеет большой смысл, поскольку вы не знаете, будет ли он содержать строки, массивы или числа и т. д. Это намного быстрее, поскольку ему нужно только скомпилировать метод show для массива Any[] один раз, а затем рекурсивно использует его.

# new session
julia> nested_arrays(n) = n == 1 ? Any[1] : Any[nested_arrays(n - 1)]
nested_arrays (generic function with 1 method)

julia> @time display(nested_arrays(15));
1-element Array{Any,1}:
 Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[1]]]]]]]]]]]]]]
  1.571632 seconds (767.12 k allocations: 32.472 MB, 1.04% gc time)

julia> @time display(nested_arrays(15));
1-element Array{Any,1}:
 Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[1]]]]]]]]]]]]]]
  0.000606 seconds (839 allocations: 30.859 KB)

julia> @time display(nested_arrays(100));
1-element Array{Any,1}:
 Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[Any[1]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
  0.002523 seconds (17.76 k allocations: 579.297 KB)
24.03.2017
  • Я бы добавил, что это пример, когда склонность Джулии компилировать специализированные версии функций - что обычно делает Джулию быстрой - неверна: было бы лучше просто скомпилировать единственную медленную универсальную версию функции show для массивов. Python всегда так поступает, и в этом случае это будет правильным поступком. В будущем эвристику специализации можно будет легко усовершенствовать без изменения языковой семантики. 25.03.2017
    • Новые материалы
    Коллекции публикаций по глубокому обучению
    Последние пару месяцев я создавал коллекции последних академических публикаций по различным подполям глубокого обучения в моем блоге https://amundtveit.com - эта публикация дает обзор 25..
    Представляем: Pepita
    Фреймворк JavaScript с открытым исходным кодом Я знаю, что недостатка в фреймворках JavaScript нет. Но я просто не мог остановиться. Я хотел написать что-то сам, со своими собственными..
    Советы по коду Laravel #2
    1-) Найти // You can specify the columns you need // in when you use the find method on a model User::find(‘id’, [‘email’,’name’]); // You can increment or decrement // a field in..
    Работа с временными рядами спутниковых изображений, часть 3 (аналитика данных)
    Анализ временных рядов спутниковых изображений для данных наблюдений за большой Землей (arXiv) Автор: Рольф Симоэс , Жильберто Камара , Жильберто Кейрос , Фелипе Соуза , Педро Р. Андраде ,..
    3 способа решить квадратное уравнение (3-й мой любимый) -
    1. Методом факторизации — 2. Используя квадратичную формулу — 3. Заполнив квадрат — Давайте поймем это, решив это простое уравнение: Мы пытаемся сделать LHS,..
    Создание VR-миров с A-Frame
    Виртуальная реальность (и дополненная реальность) стали главными модными терминами в образовательных технологиях. С недорогими VR-гарнитурами, такими как Google Cardboard , и использованием..
    Демистификация рекурсии
    КОДЕКС Демистификация рекурсии Упрощенная концепция ошеломляющей О чем весь этот шум? Рекурсия, кажется, единственная тема, от которой у каждого начинающего студента-информатика..