Любые идеи о том, как быстро найти 2D-массив?

Question

Я создаю двумерный массив, подобный этому, как матрица:

{{1, 2, 4, 5, 3, 6},
{8, 3, 4, 4, 5, 2},
{8, 3, 4, 2, 6, 2},
//code skips... ...

}

(Массив не отсортирован). Я хочу получить все позиции «4» вместо того, чтобы искать в массиве один за другим.один, и вернуть позицию, как я могу найти ее быстрее / эффективнее?заранее.

Answer 1

Вы не можете. Там нет волшебного пути. Ваш алгоритм всегда должен проверять каждую ячейку в вашей матрице, поэтому она всегда будет O(n*m) для матрицы размера n * m.

Если вы можете отсортировать свою матрицу в первую очередь, тогда вы можете использовать O(log(n) * m), поскольку вы можете использовать двоичный поиск внутри каждой строки.

Answer 2

Нет очевидной алгоритмической оптимизации (если у вас нет априорных знаний о данных, например, что они отсортированы, или вы не знаете, сколько их 4). Однако есть микрооптимизации, которые вы можете использовать, например, если ваш массив 32-битный int и вы можете использовать SSE, то вы можете загружать и сравнивать 4 элемента одновременно.

Answer 3

Единственный способ сделать это меньше, чем m * n - это предварительно отсортировать его. Из вашего вопроса не ясно, возможно ли это.

Answer 4

Вы можете выбрать скорость или потребление памяти. Если память не важна, вы можете создать список позиций, в которых хранятся значения. Таким образом, у вас все еще есть ваш массив m * n, но, кроме того, массив «списков позиций». Вы должны будете создать методы "setter", которые записывают позицию в списках каждый раз, когда значение добавляется или изменяется. Так что идея не в том, чтобы улучшить поиск, а в том, чтобы его избежать.

Пример:

У вас есть массив 2 * 2.

{{0,0}
 {0,0}}

И вы хотите добавить 4 в. Поэтому вы должны вызвать свой метод write, который вызывается с параметрами X, Y и Value. Этот метод изменит ваш массив на

{{4,0},
 {0,0}}

но также создать список

List4=>{(0,0)}

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

{{4,0}
 {4,0}}
List4=>{(0,0),(1,0)}

Так что, если вы хотите найти все 4 в вашей матрице, вам просто нужно перейти на все позиции в вашем List4. Конечно, вам придется создать список для каждого значения в вашем массиве. Таким образом, вы можете иметь максимум m * n списков с позициями, если матрица содержит каждое значение только один раз.