Блог

Главная - Вопросы по программированию - 2-мерный массив против простого массива

2-мерный массив против простого массива

#javascript #arrays #python-3.x #multidimensional-array

#javascript #массивы #python-3.x #многомерный массив

Вопрос:

Я хотел бы знать, что будет быстрее во время выполнения и что будет стоить меньше памяти, чем другое решение.

Я делал судоку, когда сам задал этот вопрос. Как вы знаете, sudoku представляет собой сеточный массив размером 9 x 9, и, как правило, все решатели вокруг sudoku реализуют array[9] [9] . Я полагаю, это потому, что это похоже на сетку, в которую вы привыкли играть.

Мой вопрос прост, поскольку сетка всегда представляет собой квадрат (например, 9×9), каково самое быстрое и минимальное потребление памяти между: — 2-мерный: Массив [9] [9] — Одномерный: массив [81]

Значения доступа в обоих случаях вычисляются (если массив начинается с индекса 0 и вам нужны 5-й столбец и 6-я строка в сетке 9×9): — Пара координат для 2D-массива (например: массив [5-1] [6-1]) — одна вычисляемая позиция (массив [((6-1) * 9) (5-1)])

Есть ли какие-либо способы проверить это?

Комментарии:

1. Не беспокойся об этом. Просто используйте структуру, которая наиболее удобна для алгоритма. Если у вас нет миллионов сеток, это не будет иметь никакого значения.

2. Но чтобы ответить на ваш вопрос, один массив будет занимать меньше памяти, поскольку он содержит всего 81 значение, в то время как массив массивов содержит 81 значение и 9 указателей.

3. Конечно, это то, что я сказал себе, но просто любопытство, если однажды, когда увеличатся размеры сетки, это должно иметь значение

4. Преждевременная оптимизация — корень всего зла

5. Да, если вы увеличите размер сетки до тысяч.

Ответ №1:

Как указано в комментариях, подход с одним массивом является самым дешевым (с точки зрения памяти)

Что касается скорости, timeit — ваш друг:

 import timeit



one_array = timeit.timeit(setup="a = [0]*81;s=3;x=2;y=1;", stmt='a[s*9 y*3 x]')
multi_array = timeit.timeit(setup="a = [[[0]*3]*3]*9;s=3;x=2;y=1;", stmt='a[s][x][y]')


print (one_array)
print (multi_array)
if one_array < multi_array:
    print('one_array is faster')
else:
    print("multi_array is faster!")

0.21741794539802967

0.13626013606615175

multi_array быстрее!

по крайней мере, в python …