рубин Looking массив хэш-Performance

Question

В настоящее время я сталкиваюсь на этот вопрос Например, у меня есть этот массив хэш

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» в диапазоне выше датой_начала хэшей и игровая end_date

Следуйте документ, который я узнать, есть 3 способа сделать это

1) Использование выберите

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

finding_hash возвращает массив необходимой хэш Но, как я это сделать, я уверяю, что там будет всегда только один хэш совпадает с условием сделать после того, как это сделать ВЫБРАТЬ я должен finding_hash.first, чтобы получить хэш я хочу

2) Использование найти

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

Этот способ делать, то finding_hash IS результат хеширования мне нужно

3) Традиционные петлю

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

Так какой из них самый быстрый способ сделать это. Мне нужна производительность, потому что мои данные довольно большие!

Спасибо и извините за мой плохой английский!

Answer 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 

Выполнение этого на образцах данных - это не то же самое, что использовать его на реальных данных.

Если реальные данные слишком велики, вы можете запустить их на подмножество данных, чтобы получить лучший ответ.

BTW, вы можете переписать v3 как:

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

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

Answer 2

можно проверить с помощью benchmark

Например:

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) 

Результаты испытаний связана с величиной п и размера данных.

Answer 3

Все методы, которые вы пробовали, это методы 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) 

Answer 4

Все эти варианты - сложность O (n). Если ваши диапазоны не перекрываются, вы можете использовать bsearch массива, который является сложностью O (log n). Сначала вы должны отсортировать диапазоны.

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