В ruby ​​для двумерного массива, как я могу удалить строки, которые соответствуют другой строке, кроме одного значения?

Question

С учетом массива, подобного следующему:

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]]

Спасибо за вашу помощь!

Answer 1

Я бы сделал это так:

array.delete_if do |item|
  a, b, c = item
  array.include? [a + 1, b, c]
end

Это повторяет массив и для каждого элемента:

1. Разрушает массив на три отдельные переменные, a, b и c. (Вероятно, вы должны дать эти более описательные имена, когда используете это в своем собственном коде!)

2. Восстанавливает массив с шагом a и проверяет, присутствует ли этот новый массив в array.

3. Если это так, удалите этот элемент.

Обратите внимание, что это изменяет array напрямую, а не возвращает измененную копию.

Answer 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) && n == arr[h[rest].last].first + 1
          h[rest] << i
        end
  arr.values_at *(arr.size.times.to_a & 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 & keepers_idx.values.flatten
  #=> [0, 2, 5, 6, 7, 8, 9, 10, 11]

Пустой хеш, созданный h = Hash.new {|h,k| h[k]=[]}, имеет свойство, что если h не имеет ключа k, скажем k = ['a', 34], затем

h[k] #=> []

, поэтому мы можем написать

h[k] << 0
  #=> [0]

Использование proc по умолчанию эквивалентно:

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 & 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 & 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 & b, документ Array # & гарантирует, что «Порядок сохраняется из исходного массива [c].».

Обработка файла

Очевидно, элементы arrayсодержатся в большом файле.Давайте предположим, что файл имеет следующий формат для массива array, указанного выше.

s = array.map { |a| a.map(&: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 может иметь завершающий символ новой строки (это не имеет значения).Давайте запишем это в файл.

FName = 'temp'
File.write(FName, s)
  #=> 83

Проверьте это:

s == File.read(FName)
  #=> true

Метод можно изменить следующим образом.Два прохода выполняются через файл, читая построчно.

Первый проход создает хеш keepers.Этот хеш похож на keepers_idx выше, но значения изменены.Значения keeper_idx являются массивами индексов.Значения keepers являются массивами двухэлементных массивов вида [i,n], где i - индекс строки в файле, а n - первое целое число, полученное из этой строки.Рассмотрим, например, строку "1,b,82" с индексом 2.Затем массив [2,1] будет добавлен к значению (массиву) ключа ["b",82], значение которого было инициализировано в пустой массив.

При втором проходе по файлу строки извлекаются с заданными индексамина 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) && n == h[rest].last.last + 1
           h[rest] << [i,n]
         end
  keepers = keepers.values.flatten(1).map(&:first)
  keepers = (0..keepers.max).to_a & 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 & keepers

на

keepers.sort!

• В зависимости отформат файла, конечно, может потребоваться изменить convert.В настоящее время:

convert "1,a,34"
  #=> [1, "a", 34]

• Если массив, возвращаемый prune, слишком велик для хранения в памяти, одинможет заменить строку a << convert(line) на строку, которая записывает line в файл, ранее открытый для записи.

• Если хеш keepers сам по себе слишком велик для хранения в памяти, его придется записывать и читать из таблицы базы данных.