более плотная и компактная матрица

Question

Во многих случаях нам необходимо выполнить две или более различных операций с массивом, например flatten и compact.

some_array.flatten.compact 

Меня беспокоит, что он будет перебирать массив по два раза. Есть ли более эффективный способ сделать это?

Answer 1

Я на самом деле думаю, что это отличный вопрос. Но во-первых, почему все не слишком обеспокоены этим? Вот производительность flatten и flatten.compact сравнению:

Here's the code I used to generate this chart, and one that includes memory.

Надеюсь, теперь вы видите, почему большинство людей не будут беспокоиться: это просто еще один постоянный фактор вы добавляете при составлении flatten с compact, может быть, это ценно, по крайней мере, теоретически сказать: как мы можем сэкономить время и пространство этой промежуточной структуры? Опять же, асимптотически не супер ценно, а любопытно думать.

Насколько я могу сказать, вы не можете сделать это, используя flatten:

Прежде чем взглянуть на источник, я надеялся, что flatten может принимать блок так:

[[3, [3, 3, 3]], [3, [3, 3, 3]], [3, [3, 3, 3]], nil].flatten {|e| e unless e.nil? } 

Нет кости, хотя. Мы получаем это как возвращение:

[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, nil] 

Это странно, что она в основном подбрасывает блок прочь, как не-оп. Но это имеет смысл с source. Метод C flatten, используемый в ядре Ruby, не параметризуется для принятия блока.

Процедура в исходном коде Ruby читает для меня нечто странное (я не программист на C), но в основном это делает что-то вроде глубинного поиска. Он использует стек, который добавляет каждый новый вложенный массив для обработки, с которой он сталкивается. (Он заканчивается, когда никто не остается.) Я не рассчитал это формально, но это приводит меня к угадыванию сложности наравне с DFS.

Таким образом, исходный код мог быть написан таким образом, что это могло бы работать, если бы была включена дополнительная настройка, если блок был передан. Но без этого вы застряли в небольшом ударе!

Answer 2

Это не итерация по одному и тому же массиву два раза. flatten создает в целом массив, который имеет совершенно другую структуру от оригинальной. Поэтому первая и вторая итерации не повторяются по тем же элементам. Поэтому, естественно, вы не можете этого сделать.

Answer 3

Если массив имеет один слой глубиной, массивы могут быть объединены в набор.

require 'set' 
s = Set.new 
Ar.each{|a| s.merge(a)}