1

给定如下数组：

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

谢谢你的帮助！

4

2 回答 2

4

我会这样做：

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直接发生变异，而不是返回更改后的副本。

于 2019-04-23T11:22:48.433 回答
1

该解决方案的时间复杂度为 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其最后两个元素由相应的键给出。例如，["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]

由 所创建的空散列具有 if没有键h = Hash.new {|h,k| h[k]=[]}的属性，比如说，hkk = ['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"index 处的行2。然后将数组[2,1]附加到 key 的值（数组）["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本身太大而无法保存在内存中，则必须将其写入数据库表并从中读取。

于 2019-04-24T01:18:28.863 回答