Реализация матрицы, которая более эффективна - использование Массива (2D) Массивов или 1D массив?
Какую хитрость использует автор?
«Хитрость» заключается в том, что
[119 ] Таким образом, в результате классы значений не могут быть созданы кодом приложения.
- когда класс абстрактный, вы не можете сделать экземпляры этого (не может вызвать
new).- когда класс является окончательным, вы не можете создавать подклассы
- , когда класс является абстрактным, и вы не можете создавать подклассы, тогда вы также не можете создать конкретный подкласс, который можно создать
Почему Scala определяет классы значений как абстрактные и окончательные.
Смысл классов значений заключается в том, что они определяются своим (неизменным) значением / содержанием. Идентификация объекта не имеет значения.
Компилятор Scala также пытается оптимизировать классы значений, не создавая вообще никаких объектов, где это возможно (просто используя распакованные примитивы напрямую). Это работает только в том случае, если мы можем быть уверены, что вы можете просто ставить и распаковывать по желанию.
В Java
new Integer(1)и другомnew Integer(1)два разных объекта, но это бесполезно для класса с чистыми значениями (если вы хотите использовать эти разные экземпляры как объекты монитора блокировки или что-то еще, где вам нужна идентификация объекта, вы просто путаете себя и других и не должны были использоватьInteger).
6 ответов
«Эффективный» - не универсальный термин.
Решение с массивом массивов является более эффективным с точки зрения хранения, где массив может быть разреженным (т. е. вы можете использовать нулевой указатель для представления строки матрицы всех нулей). Это будет (в C):
int *x[9];
, где каждое «int *» будет выделяться отдельно.
2D-массив (который не обязательно является массивом массивов), как правило, будет быстрее (эффективнее). с точки зрения скорости), так как он вычисляет ячейки памяти с помощью математики, не обращаясь к ячейкам памяти. Я говорю о конструкции:
int x[9][9];
1D-массив в форме:
int x[81];
вряд ли будет быстрее, чем эквивалентная 2D-версия, поскольку вам все равно придется выполнить вычисления в какой-то момент, чтобы найти правильную ячейку (вручную в вашем коде, а не позволить компилятору сделать это).
После редактирования, где Java был добавлен в качестве требования:
Я считаю, что Java 2D-массивы относятся к массиву массивов (что потребует двух обращений к памяти, в отличие от того, который требуется для 1D-массива), поэтому 1D-массив с ручным расчетом индекса вполне может быть быстрее. Таким образом, вместо того, чтобы объявлять и использовать:
int x[width][height];
x[a][b] = 2;
, вы можете получить больше скорости с:
int x[width*height];
x[a*height+b] = 2;
Вам просто нужно быть осторожным, чтобы не перепутать формулу где-либо (т.е. не менять местами 4 и 7 по неосторожности)
Эта разница в скорости основана на том, как я думаю, что Java написана под прикрытием, так что я могу ошибаться (но я сомневаюсь в этом :-). Мой совет, как всегда для вопросов оптимизации, мера, не угадай!
Я собираюсь разбить ряды с ответами на сегодняшний день и предложить следующую причину, что 1D-массив вполне возможен быстрее.
2D массив включает в себя 2 обращения к памяти. Например, [x] [y] сначала должен найти A [x], а затем выполнить другой поиск этого массива [y].
Традиционно 1D-реализацией будет A [x + (width * y)]. Когда ширина находится в регистрах (или литерале), это означает 2 математических операций и 1 поиск вместо 2 поисков. Поиски на несколько порядков медленнее, чем математические операции, поэтому, если ширина указывается в регистре даже в небольшой процент времени или является литералом, она будет быстрее.
Конечно, применяются стандартные предостережения. Всегда профилируйте и избегайте преждевременной оптимизации.
Коммерческий пакет конечных элементов, который я использовал в своей карьере в качестве инженера-механика, используя массив 1D в качестве основы для его вычисления линейной алгебры. Методы конечных элементов приводят к матрицам, которые являются большими, разреженными и полосатыми. Хранить все эти нулевые элементы вне группы не имело смысла.
Единственный раз, когда вы увидите 2D-массивы, используются для небольших академических задач или задач, которые не редки (например, методы граничных элементов).
В зависимости от языка разницы не будет. Реальный вопрос заключается в том, как распределяется 2D-матрица. Является ли это единым непрерывным пространством из байтов X * Y, или он выделен как Y независимых массивов размера X. Последнее обычно делается при создании разреженных матриц.
Я не думаю, что на этот вопрос можно ответить без написания примера кода и проверки результатов . Например, этот вопрос дал следующие результаты:
sum(double[], int): 2738 ms (100%)
sum(double[,]): 5019 ms (183%)
sum(double[][]): 2540 ms ( 93%)
Наиболее быстрыми являются зубчатые массивы, за которыми следуют одномерные массивы, за которыми следуют многомерные массивы. Быстрее всего, это не то, что предсказывали бы люди. Эти результаты, вероятно, бесполезны для Java, так как Java имеет различные оптимизации (и нет многомерных массивов в Java).
Я был бы очень осторожен, делая предположения. Например, если вы зацикливаетесь на строке двумерного массива, Java может оптимизировать поиск индекса или вне пределов, проверяя, не может ли это быть, если вы используете одномерный массив с встроенными вычислениями индекса.
I предлагаю написать простую программу для проверки скорости на нужной платформе.
В общем случае наиболее эффективной реализацией для любого алгоритма является та, которая имеет наименьшее количество кода. Это по многим причинам:
- Меньше кода -> меньше времени для его написания
- Меньшее количество строк кода означает меньше ошибок (поскольку ошибки для KLOC довольно постоянны для данного программиста), которые легче найти (так как они могут не прячутся в несколько строк кода)
- Если ваш алгоритм не подходит для задачи, его легче заменить, когда он содержит 10 строк вместо 100
- Компактная реализация обычно приводит к чистому интерфейсу, который делает код, который использует библиотеки clean (так что эффект умножается). Это также может привести к более сложной реализации библиотеки, если это сделает код клиента более эффективным (т.е. Вы концентрируете усилия в одном месте, чтобы сделать все остальное более простым).
Это также во многом зависит от шаблонов доступа. Вы всегда ходите по всей матрице? Это редкость? Вы предпочитаете обрабатывать строки или столбцы?
В крайнем случае (матрица с миллиардом строк и столбцов с использованием только 10 ячеек), HashMap может быть более эффективным, чем любая реализация массива. Для других задач может быть более эффективно смешивать подходы в зависимости от проблемы (например, HashMap массивов мини-матриц, когда ячейки «слипаются» в гигантском пустом пространстве).
Если ваши проблемы требуют найти строку / столбец и затем обработать эти значения, может быть более эффективно использовать 2D-подход, поэтому первый доступ возвращает массив, который вы можете затем обработать, не беспокоясь о границах, одноразовых ошибках,