Как я могу ускорить мою задачу Ruby / Rake, которая подсчитывает вхождения дат среди строк дат 300K?

Question

У меня есть массив строк 300K, которые представляют даты:

date_array = [
  "2007-03-25 14:24:29",
  "2007-03-25 14:27:00",
  ...
]

Мне нужно подсчитать вхождения каждой даты в этом массиве (например, все строки даты для "2011-03-25"). Точное время не имеет значения - только дата. Я знаю диапазон дат в файле. Итак, у меня есть:

Date.parse('2007-03-23').upto Date.parse('2011-10-06') do |date_to_count|
  count = 0
  date_array.each do |date_string|
    if Date.parse(date_string) >= date_to_count && 
       Date.parse(date_string) <= date_to_count
      count += 1
    end
  end
  puts "#{date_to_count} occurred #{count} times."
end

Подсчет вхождений только одной даты занимает больше 60 секунд на моей машине. Каким образом я могу оптимизировать выполнение этой задачи?

Возможно, полезные заметки: Я использую Ruby 1.9.2. Этот скрипт выполняется в задаче Rake с граблями 0.9.2. date_array загружается из файла CSV. На каждой итерации count сохраняется как запись в моей базе данных проекта Rails.

Answer 1

Да, вам вообще не нужно разбирать даты, если они отформатированы одинаково. Знание ваших данных - один из самых мощных инструментов, которые вы можете иметь.

Если строки даты и времени все в одном и том же формате (гггг-мм-дд ЧЧ: ММ: СС), вы можете сделать что-то вроде

data_array.group_by{|datetime| datetime[0..9]}

Это даст вам хэш, такой как строки даты в качестве ключей и массив дат в качестве значений

{
  "2007-05-06" => [...],
  "2007-05-07" => [...],
  ...
}

Таким образом, вы должны получить длину каждого массива

data_array.group_by{|datetime| datatime[0..9]}.each do |date_string, date_array|
  puts "#{date_string} occurred #{date_array.length} times."
end

Конечно, этот метод тратит память на массивы дат, когда они вам не нужны.

так как насчет

Более эффективный метод памяти

date_counts = {}
date_array.each do |date_string|
  date = date_string[0..9]
  date_counts[date] ||= 0 # initialize count if necessary
  date_counts[date] += 1
end

Вы получите хеш со строками даты в качестве ключей и счетчиками в качестве значений

{
  "2007-05-06" => 123,
  "2007-05-07" => 456,
  ...
}

Собираем все вместе

date_counts = {}
date_array.each do |date_string|
  date = date_string[0..9]
  date_counts[date] ||= 0 # initialize count if necessary
  date_counts[date] += 1
end

Date.parse('2007-03-23').upto Date.parse('2011-10-06') do |date_to_count|
  puts "#{date_to_count} occurred #{date_counts[date_to_count.to_s].to_i} times."
end

Answer 2

Это действительно ужасный алгоритм для использования.Вы просматриваете весь список для каждой даты, и, кроме того, вы анализируете одну и ту же дату дважды без видимой причины.Это означает, что для N дат в диапазоне и M дат в списке, которые вы выполняете, N * M * 2 разбора даты.

Что вам действительно нужно, так это использовать group_by и делать это за один проход:

dates = date_array.group_by do |date_string|
  Date.parse(date_string)
end

Затем вы можете использовать это как ссылку для ваших подсчетов:

Date.parse('2007-03-23').upto Date.parse('2011-10-06') do |date_to_count|
  puts "#{date_to_count} occurred #{dates[date_to_count] ? dates[date_to_count].length : 0} times."
end