Самый эффективный способ дублирования строк в массиве

Question

У меня есть массив массивов, который выглядит следующим образом.

[
  [1, "a", ...],
  [2, "a", ...],
  [3, "a", ...],
  [4, "a", ...],
]

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

Мне нужно выполнить некоторую работу с каждой строкой в ​​массиве, что может привести к тому, что некоторые строки (возможно, несколько, может быть, все) будут расширены до нескольких строк. Новые ряды необходимо упорядочить так, чтобы они следовали от того места, где находился исходный ряд. Например, окончательный массив может выглядеть так:

[
  [1, "a", ...],
  [2, "a", ...],
  [2, "b", ...],
  [2, "c", ...],
  [3, "a", ...],
  ...
  [3, "z", ...],
  [4, "a", ...],
]

Поскольку массив может быть большим (как по ширине, так и по высоте), мне нужно, чтобы это было как можно более быстрым. Мне кажется, что у большинства здравомыслящих методов обработки этого требования к памяти были бы примерно одинаковыми (общая потребная память была бы на небольшое количество больше, чем память, необходимая для готового массива).

Однако менее ясно, что Мне, что самый быстрый метод.

Возможные решения

Вот некоторые предложенные алгоритмы, но, несомненно, бесчисленное множество других. Какой метод даст наилучшую производительность?

• Метод 1: Используйте al oop для перебора массива, используйте array_splice() для вставки любых новых строк.
• Метод 2: Используйте array_shift(), чтобы удалить строку из исходного массива, вставить исходные и новые строки в массив результатов, используя $arrResults[] = $Row.
• Метод 3: Пользователь array_pop() для удаления строки из исходного массива, вставки исходных и новых строк в результаты, используя array_unshift().
• Метод 4: Как метод 2, но используйте array_reverse() перед запуском и затем используйте array_pop() вместо array_shift().
• Метод 5: Как метод 3, но используйте $arrResults[] = $Row вместо array_unshift() и затем используйте array_reverse() на окончательный массив.

Мои мысли

1. array_shift() медленнее, чем array_pop().
2. Следовательно, предположительно, array_unshift() медленнее array_push().
3. Я также предполагаю (но не проверял), что использование оператора [] равно или быстрее array_push().
4. array_splice() звучит как будет w, аналогично array_shift(), так как потребует полного переиндексации. Я не знаю, будут ли различия в реализации предпочтительнее одного над другим, но предположительно оба медленнее, чем array_push(), и в этом случае любое различие является спорным.
5. Метод array_reverse() позволяет избежать повторной индексации во время l oop, который, кажется, может быть самым быстрым способом. Тем не менее, я был бы обеспокоен требованиями к памяти.
6. И array_splice(), и array_reverse() возвращают результат, а не работают на месте, что подразумевает, что требования к памяти вдвое превышают то, что потребуется, если только Методы на месте вызываются.
7. Оба метода 4 и 5 потребуют некоторой дополнительной работы для обеспечения добавления новых строк в соответствующем порядке. Это не идеально, но приемлемо, если улучшение производительности достаточно хорошее.

Answer 1

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

Если вы можете временно справиться с загрузкой памяти, имеющей две копии массива, я рекомендую вам просто скопировать строки и копии на массив результатов, не удаляя их из оригинала. Затем в конце l oop замените исходную переменную массива на массив результатов. Сборщик мусора затем отбрасывает исходный массив.

Обратите также внимание, что PHP использует копирование при записи при назначении массивов. Так что все копии строк будут делиться своей памятью. Все, что вы временно дублируете, - это магистраль массива.

Если вы модифицируете строки после их дублирования, вы можете использовать unset() в исходном элементе массива, чтобы позволить его памяти освободиться.