Почему 2D-массив лучше, чем объекты, хранить координаты X-Y для лучшей производительности и меньшего объема памяти? - PullRequest
0 голосов
/ 27 декабря 2010

Предполагая, что я хочу сохранить n точек с целочисленными (x, y) координатами.Я могу использовать 2-й (2Xn) массив или использовать список / коллекцию / или массив из n объектов, где каждый объект имеет 2 целочисленных поля для хранения координат.Насколько я знаю, опция 2d array быстрее и потребляет меньше памяти, но я не знаю почему?Подробное объяснение или ссылки с деталями приветствуются.

Ответы [ 3 ]

0 голосов
/ 27 декабря 2010

Все зависит от того, насколько эффективно вы будете использовать пространство для хранения и каковы ваши требования к доступу. Необходимость выделить память для хранения массива 10 000 x 10 000 для хранения только 10 точек была бы ужасной тратой памяти. С другой стороны, экономия памяти путем сохранения точек в связанном списке также будет бессмысленной, если вы потратите столько времени на итерации списка, чтобы найти единственную точку, которая вам действительно нужна в сохраненных 10000000.

Некоторые недостатки обоих можно преодолеть. разреженные массивы, предварительная сортировка списка по некоторому правилу, так что «нужные» точки всплывают на верх и т. д. *

0 голосов
/ 27 декабря 2010

В большинстве языков с многомерным массивом, скажем, AxB, у вас просто есть достаточно большой объем памяти для хранения объектов A * B, и когда вы ищите элемент (m, n), все, что вам нужно сделать, это найти элемент в месте m * A + b. Когда у вас есть список объектов, с каждым списком связаны накладные расходы, плюс поиск является более сложным, чем простое вычисление адреса.

Если размер вашей матрицы постоянен, 2D-массив является самым быстрым вариантом. Если он должен расти и уменьшаться, хотя у вас, вероятно, нет другого выбора, кроме как использовать второй подход.

0 голосов
/ 27 декабря 2010

Это очень широкий вопрос, и в нем есть много частей.Во-первых, это относительно языка, на котором вы работаете. Давайте возьмем Java в качестве примера.

Когда вы создаете объект, он наследуется от класса основного объекта.Когда объект создается, накладные расходы связаны с тем, что пользовательский класс наследуется от Object.Компилятор должен виртуализировать определенные вызовы методов в памяти, чтобы при вызове .equals() или .toString() программа знала, какой из них вызывать (т. Е. Ваши классы '.equals() или Object' .equals()),Это выполняется с помощью таблицы поиска и определяется во время выполнения с помощью указателей.

Это называется виртуализацией.Теперь в Java массив на самом деле является объектом, так что вы действительно мало что получаете от массива массивов.Фактически, вы могли бы лучше использовать свой собственный класс, поскольку вы можете ограничить связанные с ним метаданные.Массивы в java хранят информацию об их длине.

Однако многие из коллекций имеют накладные расходы, связанные с ними.ArrayList например, изменит свой размер и сохранит метаданные о себе в памяти, которые вам могут не понадобиться.LinkedList имеет ссылки на другие узлы, что накладные расходы на его фактические данные.

Теперь то, что я сказал, верно только в отношении Java.В других языках ОО объекты ведут себя по-разному, а некоторые могут быть более / менее эффективными.

На таком языке, как C ++, когда вы выделяете массив, вы на самом деле просто получаете кусок памяти, и вам решать, что вы хотите с ним делать.В этом смысле это может быть лучше.С ++ имеет аналогичные накладные расходы со своими объектами, если вы используете переопределение (ключевое слово virtual), поскольку оно будет создавать эти виртуальные поиски в памяти.

...