#arrays #ruby
#массивы #ruby
Вопрос:
Учитывая массив, подобный следующему:
array = [[1, "a", 34], [1, "a", 72], [1, "b", 82],
[2, "a", 72], [2, "b", 34], [2, "b", 32],
[3, "a", 72], [3, "b", 82], [3, "b", 34],
[4, "a", 93], [4, "b", 15]]
Я хотел бы знать, как, используя ruby, я мог бы удалить все строки, которые соответствуют всем значениям в другой строке, кроме первого значения, которое должно быть равно n-1
.
Таким образом, это будет означать, что [1, "a", 72]
удаляется, поскольку есть строка с [2, "a", 72]
, которая также будет удалена, поскольку [3, "a", 72]
присутствует.
[2, "b", 34]
также будет удалено, поскольку есть [3, "b", 34]
Поэтому скрипт вернет следующий массив:
array = [[1, "a", 34], [1, "b", 82],
[2, "b", 32],
[3, "a", 72], [3, "b", 82], [3, "b", 34],
[4, "a", 93], [4, "b", 15]]
Спасибо за вашу помощь!
Ответ №1:
Я бы сделал это так:
array.delete_if do |item|
a, b, c = item
array.include? [a 1, b, c]
end
Это повторяется по массиву и для каждого элемента:
-
Разрушает массив на три отдельные переменные,
a
,b
иc
. (Вероятно, вам следует дать эти более описательные имена, когда вы используете это в своем собственном коде!) -
Восстанавливает массив с помощью
a
incremented и проверяет, присутствует ли этот новый массив вarray
. -
Если да, удалите этот элемент.
Пожалуйста, обратите внимание, что это изменяет array
напрямую, а не возвращает измененную копию.
Комментарии:
1. Вы можете назначить a, b и c непосредственно в аргументах блока:
array.delete_if{|a,b,c| array.include?([a 1,b,c]) }
2. Большое спасибо за ваш ответ, это именно то, что я искал! Есть ли причина, по которой определено
item
перед определениемa,b,c
? Не было бы проще удалить вторую строку и определитьa,b,c
в аргументах блока?3. @Dobby Добро пожаловать! Вероятно, было бы проще сделать именно это, я просто забыл об этой функции.
Ответ №2:
Это решение имеет временную сложность O (n).
Код
def prune(arr)
keepers_idx =
arr.each_with_index.
with_object(Hash.new {|h,k| h[k]=[]}) do |((n,*rest),i),h|
h[rest].pop if h.key?(rest) amp;amp; n == arr[h[rest].last].first 1
h[rest] << i
end
arr.values_at *(arr.size.times.to_a amp; keepers_idx.values.flatten)
end
Пример
Я добавил элемент [5, "b", 34]
в конец массива, указанного в вопросе:
array = [
[1, "a", 34], [1, "a", 72], [1, "b", 82],
[2, "a", 72], [2, "b", 34], [2, "b", 32],
[3, "a", 72], [3, "b", 82], [3, "b", 34],
[4, "a", 93], [4, "b", 15], [5, "b", 34]
]
prune(array)
#=> [[1, "a", 34], [1, "b", 82], [2, "b", 32], [3, "a", 72], [3, "b", 82],
# [3, "b", 34], [4, "a", 93], [4, "b", 15], [5, "b", 34]]
Объяснение
prune
возвращает уменьшенный массив, но не изменяет его аргумент, array
. Если array
требуется заменить, напишите
array = prune(array)
или измените последнюю строку метода на:
array.replace(array.values_at *keepers_idx.values.flatten(1).sort)
в зависимости от требований.
Значения в keepers_idx
являются индексами элементов array
, которые должны быть сохранены, последние 2 элемента которых задаются соответствующими ключами. Например, сохраняемые массивы, которые заканчиваются на индексах ["b", 82]
и 2
. ………. и 7
. Обратите также внимание, что когда arr = array
,
keepers_idx
#=> {["a", 34]=>[0], ["a", 72]=>[6], ["b", 82]=>[2, 7], ["b", 34]=>[8, 11],
# ["b", 32]=>[5], ["a", 93]=>[9], ["b", 15]=>[10]}
и
arr.size.times.to_a amp; keepers_idx.values.flatten
#=> [0, 2, 5, 6, 7, 8, 9, 10, 11]
The empty hash created by h = Hash.new {|h,k| h[k]=[]}
has the property that if h
does not have a key k
, say k = ['a', 34]
, then
h[k] #=> []
so we can write
h[k] << 0
#=> [0]
Use of the default proc is equivalent to:
h[k] = [] unless h.key?(k)
h[k] << 0
Шаг за шагом
Теперь давайте пройдемся по коду для примера массива.
arr = array
enum = arr.each_with_index.with_object(Hash.new {|h,k| h[k]=[]})
#=> #<Enumerator: #<Enumerator: [[1, "a", 34], [1, "a", 72],
# [1, "b", 82],...[5, "b", 34]]:each_with_index>:with_object({})>
Первое значение генерируется счетчиком (см. Enumerator #next), передается в блок, а переменным блока присваиваются значения с помощью процесса, известного как декомпозиция массива:
((n,*rest),i),h = enum.next
#=> [[[1, "a", 34], 0], {}]
n #=> 1
rest #=> ["a", 34]
i #=> 0
h #=> {}
Теперь мы выполняем вычисление блока.
h.key?(rest)
#=> {}.key(["a", 34]) => false
поэтому мы не выполняем h[rest].pop
. Продолжение,
h[rest] << i
#=> h[["a", 34]] << 0 => [0]
h #=> {["a", 34]=>[0]}
Следующий элемент генерируется enum
, передается в блок, переменным блока присваиваются значения, и выполняется вычисление блока.
((n,*rest),i),h = enum.next
#=> [[[1, "a", 72], 1], {["a", 34]=>[0]}]
n #=> 1
rest #=> ["a", 72]
i #=> 1
h #=> {["a", 34]=>[0]}
h.key?(rest)
#=> {}.key(["a", 72]) => false => *no* h[rest].pop
h[rest] << i
#=> h[["a", 72]] << 1 => [1]
h #=> {["a", 34]=>[0], ["a", 72]=>[1]}
После еще одного аналогичного шага,
h=> {["a", 34]=>[0], ["a", 72]=>[1], ["b", 82]=>[2]}
Теперь все изменится.
((n,*rest),i),h = enum.next
#=> [[[2, "a", 72], 3], {["a", 34]=>[0], ["a", 72]=>[1], ["b", 82]=>[2]}]
n #=> 2
rest #=> ["a", 72]
i #=> 3
h #=> {["a", 34]=>[0], ["a", 72]=>[1], ["b", 82]=>[2]}
h.key?(rest)
#=> h.key?(["a", 72]) => true
n == arr[h[rest].last].first 1
#=> 2 == arr[h[["a", 72]].last].first 1
#=> 2 == arr[[1].last].first 1
#=> 2 == arr[1].first 1
#=> 2 == [1, "a", 72].first 1 => true
итак, мы выполняем
h[rest].pop
#=> h[["a", 72]].pop => 1
h #=> {["a", 34]=>[0], ["a", 72]=>[], ["b", 82]=>[2]}
Продолжение,
h[rest] << i
#=> h[["a", 72]] << 3 => [3]
h #=> {["a", 34]=>[0], ["a", 72]=>[3], ["b", 82]=>[2]}
Остальные вычисления для получения keepers_idx
аналогичны, производя:
keepers_idx
#=> {["a", 34]=>[0], ["a", 72]=>[6], ["b", 82]=>[2, 7], ["b", 34]=>[8, 11],
# ["b", 32]=>[5], ["a", 93]=>[9], ["b", 15]=>[10]}
Наконец,
arr.values_at *(0..arr.size-1).to_a amp; keepers_idx.values.flatten
a = keepers_idx.values
#=> [[0], [6], [2, 7], [8, 11], [5], [9], [10]]
b = a.flatten
#=> [0, 6, 2, 7, 8, 11, 5, 9, 10]
c = arr.size.times.to_a
#=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
d = c amp; b
#=> [0, 2, 5, 6, 7, 8, 9, 10, 11]
arr.values_at *d
#=> arr.values_at(0, 2, 5, 6, 7, 8, 9, 10, 11)
#=> [[1, "a", 34], [1, "b", 82], [2, "b", 32], [3, "a", 72], [3, "b", 82],
#=> [3, "b", 34], [4, "a", 93], [4, "b", 15], [5, "b", 34]]
При вычислениях c amp; b
массив doc #amp; гарантирует, что «Порядок сохранен из исходного массива [ c
]»..
Обработка файла
Очевидно, элементы array
содержатся в большом файле. Давайте предположим, что файл имеет следующий формат для массива array
, указанный выше.
s = array.map { |a| a.map(amp;:to_s).join(",") }.join("n")
puts s
1,a,34
1,a,72
1,b,82
2,a,72
2,b,34
2,b,32
3,a,72
3,b,82
3,b,34
4,a,93
4,b,15
5,b,34
s
может иметь конечную новую строку (это не имеет значения). Давайте запишем это в file.
FName = 'temp'
File.write(FName, s)
#=> 83
Проверьте это:
s == File.read(FName)
#=> true
Метод может быть изменен следующим образом. Через файл выполняются два прохода, чтение построчно.
The first pass constructs the hash keepers
. This hash is similar to keepers_idx
, above, but the values are modified. The values of keeper_idx
are arrays of indices. The values of keepers
are arrays of two-element arrays of the form [i,n]
, where i
is the index of the line in the file and n
is the first integer obtained from that line. Consider, for example, the line "1,b,82"
at index 2
. The array [2,1]
would then be appended to the value (array) of the key ["b",82]
, the value having been initialised to an empty array.
Второй проход через файл извлекает строки с индексами, заданными keepers
, хранящиеся в отсортированном массиве lines_to_keep
. Я вернул массив извлеченных строк, преобразованный в массивы из трех элементов. (Смотрите комментарий в конце, если это не разрешено из-за нехватки памяти.)
def prune(fname)
keepers =
File.foreach(fname).
with_index.
with_object(Hash.new {|h,k| h[k]=[]}) do |(line,i),h|
n, *rest = convert(line)
h[rest].pop if h.key?(rest) amp;amp; n == h[rest].last.last 1
h[rest] << [i,n]
end
keepers = keepers.values.flatten(1).map(amp;:first)
keepers = (0..keepers.max).to_a amp; keepers
next_line = keepers.shift
File.foreach(fname).
with_index.
with_object([]) do |(line,i),a|
if i == next_line
a << convert(line)
next_line = keepers.shift
break a if keepers.nil?
end
end
end
def convert(line)
a,b,c = line.chomp.split(',')
[a.to_i, b, c.to_i]
end
prune(FName)
#=> [[1, "a", 34], [1, "b", 82], [2, "b", 32], [3, "a", 72], [3, "b", 82],
[3, "b", 34], [4, "a", 93], [4, "b", 15], [5, "b", 34]]
Примечания:
- Возможно, будет быстрее заменить строку
keepers = (0..keepers.max).to_a amp; keepers
с помощью
keepers.sort!
- В зависимости от формата файла, конечно, может потребоваться изменение
convert
. В настоящее время:
convert "1,a,34"
#=> [1, "a", 34]
-
Если массив, возвращаемый
prune
, слишком велик для хранения в памяти, можно заменить строкуa << convert(line)
на строку, которая записываетline
в файл, ранее открытый для записи. -
Если хэш
keepers
сам по себе слишком велик для хранения в памяти, его нужно будет записать в таблицу базы данных и прочитать из нее.
Комментарии:
1. Спасибо за ваш ответ! Я не знаком с временной сложностью, означает ли временная сложность O (n), что она будет выполняться быстрее или медленнее, чем другой предложенный ответ?
2. @Hildobby Это будет выполняться быстрее, чем мой ответ: мой ответ
O(n^2)
наихудший, тогда как этоO(n)
.3. Хилдобби, смотри эту Wiki для объяснения временной сложности.
4. Спасибо @CarySwoveland ! Это отлично работает и действительно намного быстрее, чем другое предлагаемое решение. Однако для очень больших файлов я получаю следующую ошибку
stack level too deep (SystemStackError)
в этой строке:arr.values_at *(arr.size.times.to_a amp; keepers_idx.values.flatten)
как я могу это решить?5. Насколько велики файлы, которые вызывают ошибку? Кроме того, среди всех элементов
[a,b,c]
в проблемном файле, есть ли у вас какое-либо представление о количестве уникальных массивов[b,c]
(которые являются ключами в моем хэше)?