ruby - 你能通过关键字搜索数组吗？

Question

如何获取像 ["foo",1,2,3] 这样的数组，并将其转换为可以通过关键字 "foo" 快速搜索的内容？

我正在尝试获取 csv 文件，并根据条件对其进行排序/过滤。例如，给定以下 csv 和标准:

foo,bar,foobar
1,2,3
4,5,6
7,8,9

@criteria = ["foobar", "foo"]

输出应如下(顺序很重要):

foobar,foo
3,1
6,4
9,7

我使用嵌套循环来对照 csv 的每个 index[0] 检查 @criteria 中的每个项目。

require 'csv'

@criteria = ["foobar", "foo"]
@newcsv = []
csv = CSV.read("./foo.csv", { headers: true, return_headers: false })
csv = csv.to_a.transpose
@criteria.each do |n|
  csv.each do |i|
    if i[0] == n
      @newcsv.push(i)
      end
  end
end
@newcsv = @newcsv.transpose
CSV.open("./transpose.csv", "wb") do |lines|
  @newcsv.each { |line| lines << line }
end

它适用于小矩阵，但我确信它不会扩展。我想知道哈希是否可以给我带来更好的性能。如何在不使用嵌套循环的情况下仅获取 @criteria 中的行？

Answer 1

所以这个答案是由另一个用户发布的，后来因为他或她“讨厌它”而被删除，但我认为它至少为原始发布者添加了一些有用的信息，所以我重新发布就在这里。

请注意，我不确定此代码是否具有比 n * n 矩阵的 O(n^2) 更快的渐近性能，但原作者不同意我的观点。至少，这是我的推理:

• 如果您有一个 n * n 矩阵，并且有 n - 1 个条件，那么创建索引不会考虑最坏的情况 n-1 + n-2 + .. + 2 + 1 = O(n^2) 步骤，具体取决于矩阵的条件和列的排序方式？

• 然后您最终仍然需要收集 n(n - 1) 个单元格，即使是通过恒定时间数组索引访问也是如此。

至少这是我的理由。也许我错了。如果是，请解释一下是怎么回事，以及下面代码的正确渐近运行时复杂度是多少!

原作者的回答

扫描数组中的元素效率很低，但是一旦有了索引，在该索引处查找元素就会很快。

给定标题行header = ["foo", "bar", "foobar"] 和@criteria = ["foobar", "foo"]，您可以将它们转换为索引:

indices = @criteria.map{|column| header.index(column)}
# => [2, 0]

然后，使用索引，您可以映射行:

[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
]
.map{|row| row.values_at(*indices)}

给出:

[
  [3, 1],
  [6, 4],
  [9, 7],
]

这样，大部分的计算复杂度都在于创建索引，只需要执行一次，所花费的时间可以忽略不计，剩下的都是通过索引查找元素，而复杂性很小，不像用户评论的那样。

以下是使用上述方法的一些示例代码:

require 'csv'

@criteria = ['foobar', 'foo']

table = CSV.read('./foo.csv', headers: true)
indices = @criteria.map { |column| table.headers.index(column) }
table.map { |row| row.values_at(*indices) }