如何從日期範圍查詢表中找到一組缺失日期

有一些與我的問題相關的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

如何從日期範圍查詢表中找到一組缺失日期

回答

相關問題