Ruby查找哈希数组的性能

Question

Ruby查找哈希数组的性能

4

目前我遇到了这个问题例如，我有一个哈希数组

data = [
  {:id => 1,:start_date => "2015-01-02",:end_date => "2015-01-05"},
  {:id => 2,:start_date => "2015-01-06",:end_date => "2015-01-07"},
  {:id => 3,:start_date => "2015-01-10",:end_date => "2015-01-20"}
]

我希望找到在上述哈希值的开始日期和结束日期范围内具有"2015-01-04"的确切哈希值。

根据文档，我发现有三种方法可以实现这一目标：

1）使用select语句

finding_hash = data.select {|h| h[:start_date] <= "2015-01-04" && h[:end_date] >= "2015-01-04"}

finding_hash将返回所需哈希值的数组但是在执行SELECT之后，我确保只有一个哈希值与条件匹配，则需要使用finding_hash.first来获取所需的哈希值。

2）使用find

finding_hash = data.find{|h| h[:start_date] <= "2015-01-04" && h[:end_date] >= "2015-01-04"}

这种做法中，finding_hash就是我需要的结果哈希值。

3)传统循环。

data.each do |t|
  if (t[:start_date] <= "2015-01-04" && t[:end_date] >= "2015-01-04")
    return t
    break
  end
end

那么哪种方法是最快的呢？我确实需要高性能，因为我的数据非常大！

谢谢您，对我的糟糕英语表示歉意！

- Duong Bach

2

如果你的数据非常大，那么你应该将它存储在数据库中并进行索引。即使是SQLite也可以处理类似这样的数据。 - mu is too short

可以安全地假设数组中的哈希值按日期排序吗？ - spickermann

@spickermann：不，这是随机的，我的朋友。 - Duong Bach

所以你有三段代码，想知道哪个更快。为什么不测量一下性能呢？ - Sergio Tulentsev

@SergioTulentsev：很抱歉，我不知道正确的做法，所以我添加了新的2个值start_time和end_time。在每段代码的结尾处，我输出了end_time - start_time，但效果并不好... - Duong Bach

请使用此链接 http://ruby-doc.org/stdlib-1.9.3/libdoc/benchmark/rdoc/Benchmark.html。 - Sergio Tulentsev

4个回答

2

你尝试的所有方法都是Enumerable方法，但本地的Array方法更快。尝试使用find_index。即使需要进行单独调用以加载哈希表，它仍然比下一个最快的方法快大约20％：

index = data.find_index {|h| h[:start_date] <= "2015-01-04" && h[:end_date] >= "2015-01-04"}
x = data[index]

我的基准测试：

n = 1_000_000

data = [
  {:id => 1,:start_date => "2015-01-02",:end_date => "2015-01-05"},
  {:id => 2,:start_date => "2015-01-06",:end_date => "2015-01-07"},
  {:id => 3,:start_date => "2015-01-10",:end_date => "2015-01-20"}
]

Benchmark.bm do |x|
  x.report 'Enumerable#select' do
    n.times do
      data.select do |h|
        h[:start_date] <= "2015-01-04" && h[:end_date] >= "2015-01-04"
      end
    end
  end

  x.report 'Enumerable#detect' do
    n.times do
      data.detect do |h|
        h[:start_date] <= "2015-01-04" && h[:end_date] >= "2015-01-04"
      end
    end
  end

  x.report 'Enumerable#each  ' do
    n.times do
      finding_hash = {}
      data.each do |t|
        if (t[:start_date] <= "2015-01-04" && t[:end_date] >= "2015-01-04")
          finding_hash = t
          break t
        end
      end
    end
  end

  x.report 'Array#find_index ' do
    n.times do
       index = data.find_index {|h| h[:start_date] <= "2015-01-04" && h[:end_date] >= "2015-01-04"}
       x = data[index]
    end
  end
end

结果如下：

Enumerable#select  1.000000   0.010000   1.010000 (  1.002282)
Enumerable#detect  0.790000   0.000000   0.790000 (  0.797319)
Enumerable#each    0.620000   0.000000   0.620000 (  0.627272)
Array#find_index   0.520000   0.000000   0.520000 (  0.515691)

- infused

1

v3 是最快的：

def v1
  @data.select {|h| h[:start_date] <= "2015-01-04" && h[:end_date] >= "2015-01-04"}
end

def v2
  @data.find{|h| h[:start_date] <= "2015-01-04" && h[:end_date] >= "2015-01-04"}
end

def v3
  @data.each do |t|
    if (t[:start_date] <= "2015-01-04" && t[:end_date] >= "2015-01-04")
      return t
      break
    end
  end
end

select 操作总是最慢的，因为它必须遍历整个数组。我不确定为什么 find 比 v3 更慢。这可能与开销有关。

然而，对于您的数据，find 和 v3 可能是相同的。下面的结果不一定适用于您的数据。

t = Time.now; 10000.times{ v1 }; Time.now - t
=> 0.014131

t = Time.now; 10000.times{ v2 }; Time.now - t
=> 0.013138

t = Time.now; 10000.times{ v3 }; Time.now - t
=> 0.008799

在示例数据上运行与在实际数据上运行是不同的。

如果实际数据太大，您可以在数据子集上运行它以获得更好的答案。

顺便说一下，您可以将v3重写为：

data.each do |t|
  break t if (t[:start_date] <= "2015-01-04" && t[:end_date] >= "2015-01-04")
end

就我所知，操作数组将会非常笨拙和缓慢。您可能希望将其保存在数据库中并运行查询。对于大型数据集，这可能至少快两个数量级。

- B Seven

1

所有这些变量都是O(n)复杂度。如果你的范围不重叠，你可以使用数组的bsearch，它的复杂度为O(log n)。你应该首先对你的范围进行排序。

sorted = data.sort_by { |x| x[:start_date] }
sorted.bsearch { |x| ..check if range of `x` includes value.. }

- lx00st

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- pangpang · Accepted Answer

你可以通过基准测试来进行测试。

例如：

require 'benchmark'

n = 1000000

data = [
  {:id => 1,:start_date => "2015-01-02",:end_date => "2015-01-05"},
  {:id => 2,:start_date => "2015-01-06",:end_date => "2015-01-07"},
  {:id => 3,:start_date => "2015-01-10",:end_date => "2015-01-20"}
]


Benchmark.bm do |x|

x.report { n.times do
   data.select {|h| h[:start_date] <= "2015-01-04" && h[:end_date] >= "2015-01-04"}
   end
}

x.report { n.times do
 data.find{|h| h[:start_date] <= "2015-01-04" && h[:end_date] >= "2015-01-04"}
  end

 }

x.report {
n.times do
   finding_hash = {}
   data.each do |t|
     if (t[:start_date] <= "2015-01-04" && t[:end_date] >= "2015-01-04")
       finding_hash = t
       break
     end
    end
end
}

end

输出：

       user     system      total        real
   1.490000   0.020000   1.510000 (  1.533589)
   1.070000   0.010000   1.080000 (  1.096578)
   1.000000   0.010000   1.010000 (  1.011021)

测试结果与n的值和数据大小有关。