如何从日期范围查询表中找到一组缺失日期

有一些与我的问题相关的stackoverflow的帖子，但不是所有的相似。如何从日期范围查询表中找到一组缺失日期

我想要一个高效的，有点优雅的（如果可能的话）解决方案，以便在比较用户指定的日期范围和postgresql中的汇总表之后得到缺失日期数组。我知道的一种方法是将范围放在日期列表中，然后通过查询EXIST或结果== nil？/ empty？等单独比较所有日期。但是，如果用户要做大范围，这可能是资源消耗和缓慢。

除了当前列出的方法之外，是否有任何方法？

谢谢

来源

2012-12-17 Tom Choi

首先，我们需要对日期进行排序。在红宝石这很简单，只要

sorted_dates = dates.sort

如果你知道的日期进行排序，然后才开始与第一日期和增量由一个作为你通过你的日期范围迭代。如果数组中的下一个日期不是您所期望的日期，请将缺少的日期添加到您的missing_dates数组中，并继续递增，直到达到所包含的日期。

此代码可能类似于以下内容：

def find_missing_dates(sorted_dates) 
    current_date = sorted_dates[0] 
    missing_dates = Set.new 
    sorted_dates.each do |date| 
    while current_date != date 
     missing_dates << current_date 
     current_date += 1.day 
    end 
    current_date += 1.day 
    end 
end

这是O（N）的平均情况，因此要获得更有效率，我们可以在半递归分裂。

def dates_between(lower, upper) 
    (lower..upper).to_a - [lower,upper] 
end 

def find_missing_dates(sorted_dates, missing_dates = Set.new) 
    min_date = sorted_dates[0] 
    max_date = sorted_dates[-1] 
    if (min_date - max_date).to_i == (sorted_dates.count - 1) 
     missing_dates 
    else 
     middle_date_lower = sorted_dates[sorted_dates.count/2 - 1] 
     middle_date_upper = sorted_dates[sorted_dates.count/2] 
     unless (middle_date_upper - middle_date_lower) == 1 
     missing_dates.merge(dates_between(middle_date_lower, middle_date_upper)) 
     end 
     find_missing_dates(sorted_dates[0..(sorted_dates.count/2 - 1)], missing_dates).merge(find_missing_dates(sorted_dates[(sorted_dates.count/2)..-1])) 
    end 
end 

find_missing_dates(sorted_dates)

这仍然是最坏的情况下O（N），但平均的情况下是为O（log N）

来源

2015-11-11 22:44:02

如何从日期范围查询表中找到一组缺失日期

回答

相关问题