zaman aralıklarını (zaman birliği aralıkları)

Question

Ben birkaç kez bir dizi iç aralıkları örtüşen birleştirmek için:

[Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00, 
Tue, 24 May 2011 16:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00, 
Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 09:00:00 CEST +02:00, 
Tue, 24 May 2011 15:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00] 

Ben zaman aralıkları kombine örtüşen ile aynı diziyi almak istiyorum, bu yüzden çıkış Bu durum için olacaktır: zaman aralıkları vb örtüştüğü ve zaman

[Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00, 
Tue, 24 May 2011 15:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00] 

Yani yeni bir zaman aralığı oluşturur. Üst üste gelmezlerse, ayrılmaya devam edecekler. Başka bir örnek:

Girdi:

[Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00, 
Tue, 24 May 2011 16:00:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00] 

Çıkış (onlar örtüşme düğünle çünkü aynı olacaktır):

[Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00, 
Tue, 24 May 2011 16:00:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00] 

Bazı özyinelemeli yaklaşımda düşünüyordum ama bazı rehberliğine ihtiyacım burada ...

Answer 1

iki erimi örtüştüğü halinde truthy döndüren bir işlev verilen:

def ranges_overlap?(a, b) 
    a.include?(b.begin) || b.include?(a.begin) 
end 

(sepp2k and steenslag bu fonksiyon izniyle)

ve üst üste binen iki aralıkları birleştiren bir fonksiyonu:

def merge_ranges(a, b) 
    [a.begin, b.begin].min..[a.end, b.end].max 
end 

Daha sonra bu işlev, bir dizi aralık verildiğinde, birleştirilen tüm örtüşen aralıklarla yeni bir dizi döndürür:

def merge_overlapping_ranges(overlapping_ranges) 
    overlapping_ranges.sort_by(&:begin).inject([]) do |ranges, range| 
    if !ranges.empty? && ranges_overlap?(ranges.last, range) 
     ranges[0...-1] + [merge_ranges(ranges.last, range)] 
    else 
     ranges + [range] 
    end 
    end 
end 

Answer 2

yardımcı olabilecek algoritması çeşit:

Sort range array by start time (r1, r2, r3, r4, .. rn) 

for each range pair [r1, r2], [r2, r3] .. [rn-1, rn]: 
    if r1_end > r2_start: # they overlap 
     add [r1_start, r2_end] to new range array 
    else: # they do not overlap 
     add [r1] and [r2] to new range array (no changes) 

startover with the new range array until no more changes 

Answer 3

Diziler kümesinden en küçük ilk değeri ve en büyük son değeri bulmak istemez misiniz? (Zaman ile çalışma aralıkları çok!)

def self.merge_ranges(ranges) 
    ranges = ranges.sort_by {|r| r.first } 
    *outages = ranges.shift 
    ranges.each do |r| 
    lastr = outages[-1] 
    if lastr.last >= r.first - 1 
     outages[-1] = lastr.first..[r.last, lastr.last].max 
    else 
     outages.push(r) 
    end 
    end 
    outages 
end 

Bir örnek:

ranges = [Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00, 
Tue, 24 May 2011 16:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00, 
Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 09:00:00 CEST +02:00, 
Tue, 24 May 2011 15:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00] 

union = [ranges.collect(&:first).sort.first, ranges.collect(&:last).sort.last] 

Answer 4

Ben hile yapan bir kod bulduk biraz aranıyor

ranges = [1..5, 20..20, 4..11, 40..45, 39..50] 
merge_ranges(ranges) 
=> [1..11, 20..20, 39..50] 

burada Bulunan: http://www.ruby-forum.com/topic/162010

Answer 5

Facets gem, kullanımda olabilen Range.combine yöntemine sahiptir: http://rdoc.info/github/rubyworks/facets/master/Range#combine-instance_method

Answer 6

İşaretli yanıt, birkaç kullanım durumu dışında iyi çalışır. Böyle kullanım durumunda biri

[Tue, 21 June 13:30:00 GMT +0:00..Tue, 21 June 15:30:00 GMT +00:00, 
Tue, 21 June 14:30:00 GMT +0:00..Tue, 21 June 15:30:00 GMT +00:00] 

ranges_overlap koşul bu kullanım durumunda işlemez olduğunu. Bu yüzden şu ana kadar tüm kenar durumlarını ele aldım.

Answer 7

@ wayne-conrad tarafından sunulan çözüm çok iyi bir tanesidir. Bir problem için yerine getirdim, tökezledim. Sonra yinelemeli bir sürüm uyguladı ve ikiyi karşılaştırdım. Görünüşe göre, yinelemeli sürüm daha hızlıdır. Not: Range#overlaps? için ActiveSupport ve zaman yardımcıları kullanıyorum, ancak salt Ruby sürümü uygulamak çok önemsiz.

require 'active_support/all' 

module RangesUnifier 
    extend self 

    # ranges is an array of ranges, e.g. [1..5, 2..6] 
    def iterative_call(ranges) 
    ranges.sort_by(&:begin).reduce([ranges.first]) do |merged_ranges, range| 
     if merged_ranges.last.overlaps?(range) 
     merged_ranges[0...-1] << merge_ranges(merged_ranges.last, range) 
     else 
     merged_ranges << range 
     end 
    end 
    end 

    def recursive_call(ranges) 
    return ranges if ranges.size == 1 

    if ranges[0].overlaps?(ranges[1]) 
     recursive_call [merge_ranges(ranges[0], ranges[1]), *ranges[2..-1]] 
    else 
     [ranges[0], *recursive_call(ranges[1..-1])] 
    end 
    end 

    def merge_ranges(a, b) 
    [a.begin, b.begin].min..[a.end, b.end].max 
    end 
end 

five_hours_ago = 5.hours.ago 
four_hours_ago = 4.hours.ago 
three_hours_ago = 3.hours.ago 
two_hours_ago = 2.hours.ago 
one_hour_ago = 1.hour.ago 
one_hour_from_now = 1.hour.from_now 
two_hours_from_now = 2.hours.from_now 
three_hours_from_now = 3.hours.from_now 
four_hours_from_now = 4.hours.from_now 
five_hours_from_now = 5.hours.from_now 

input = [ 
    five_hours_ago..four_hours_ago, 
    three_hours_ago..two_hours_from_now, 
    one_hour_ago..one_hour_from_now, 
    one_hour_from_now..three_hours_from_now, 
    four_hours_from_now..five_hours_from_now 
] 

RangesUnifier.iterative_call(input) 
#=> [ 
# 2017-08-21 12:50:50 +0300..2017-08-21 13:50:50 +0300, 
# 2017-08-21 14:50:50 +0300..2017-08-21 20:50:50 +0300, 
# 2017-08-21 21:50:50 +0300..2017-08-21 22:50:50 +0300 
# ] 

RangesUnifier.recursive_call(input) 
#=> [ 
# 2017-08-21 12:50:50 +0300..2017-08-21 13:50:50 +0300, 
# 2017-08-21 14:50:50 +0300..2017-08-21 20:50:50 +0300, 
# 2017-08-21 21:50:50 +0300..2017-08-21 22:50:50 +0300 
# ] 

n = 100_000  

Benchmark.bm do |x| 
    x.report('iterative') { n.times { RangesUnifier.iterative_call(input) } } 
    x.report('recursive') { n.times { RangesUnifier.recursive_call(input) } } 
end 

# => 
#  user  system  total  real 
# iterative 0.970000 0.000000 0.970000 ( 0.979549) 
# recursive 0.540000 0.010000 0.550000 ( 0.546755)