Algoritmus pro sloučení časových úseků   zodpovězená otázka

VB.NET, Algoritmy, WinForms

Zdravím,

Nechci objevovat Ameriku a tak se ptám, zda jste někdo už řešil následující:

Mějme několik objektů třídy TimeRange například v list(of TimeRange)

0) 1.1.2015 - 4.1.2015

1) 5.1.2015 - 8.1.2015

2) 10.1.2015 - 13.1.2015

3) 6.1.2015 - 9.1.2015

4) 3.1.2015 - 6.1.2015

5) 11.1.2015 - 14.1.2015

Výsledkem má být následující nový list(of TimeRange)

0) 1.1.2015 - 9.1.2015

1) 10.1.2015 - 14.1.2015

Prozatím jsem to řešil následujícím kódem, který ale ještě neskončí úplně redukovaným listem. Ale i tak je to hodně procházení tuším N2 ???

Máte případně někdo typ, na algoritmus "funkce JOIN"

Public Class TimeRange
    Private _dateStart As Date
    ReadOnly Property DateStart As Date
        Get
            Return _dateStart
        End Get
    End Property
    Private _dateEnd As Date
    ReadOnly Property DateEnd As Date
        Get
            Return _dateEnd
        End Get
    End Property
    Private _duration As New TimeSpan
    ReadOnly Property Duration As TimeSpan
        Get
            Return _duration
        End Get
    End Property

    Public Sub New(ByVal start As Date, ByVal konec As Date)
        _dateStart = start
        _dateEnd = konec
        _duration = konec - start
    End Sub
    Public Sub New(ByVal start As Date, ByVal trvani As TimeSpan)
        _dateStart = start
        _duration = trvani
        _dateEnd = start.Add(trvani)
    End Sub
    Public Sub ChangeStartByDuration(ByVal NoveTrvani As TimeSpan)
        _duration = NoveTrvani
        _dateStart = _dateEnd.Add(-NoveTrvani)
    End Sub
    Public Sub ChangeEndByDuration(ByVal NoveTrvani As TimeSpan)
        _duration = NoveTrvani
        _dateEnd = _dateEnd.Add(NoveTrvani)
    End Sub
    Public Sub ChangeStartAndKeepEnd(ByVal NovyStart As Date)
        _dateStart = NovyStart
        _duration = _dateEnd - _dateStart
    End Sub
    Public Sub ChangeEndAndKeepStart(ByVal NovyKonec As Date)
        _dateEnd = NovyKonec
        _duration = _dateEnd - _dateStart
    End Sub
    Public Sub ChangeStartAndKeepDuration(ByVal NovyStart As Date)
        _dateStart = NovyStart
        _dateEnd = _dateStart.Add(_duration)
    End Sub
    Public Sub ChangeEndAndKeepDuration(ByVal NovyKonec As Date)
        _dateEnd = NovyKonec
        _dateStart = _dateEnd.Add(-_duration)
    End Sub

    Shared Function Join(ByVal data As List(Of TimeRange)) As List(Of TimeRange)
        Dim NewColl As New List(Of TimeRange)
        NewColl.Add(data(0))

        For Each dt As TimeRange In data
            Dim Y As Integer = NewColl.Count - 1
            For x As Integer = 0 To Y
                If dt.DateStart >= NewColl(x).DateStart AndAlso dt.DateEnd <= NewColl(x).DateEnd Then
                    'nic nedělat
                ElseIf dt.DateEnd < NewColl(x).DateStart Then
                    'přidat do kolekce
                    NewColl.Add(dt)
                    Exit For
                ElseIf dt.DateStart > NewColl(x).DateEnd Then
                    'přidat do nové kolekce
                    NewColl.Add(dt)
                    Exit For
                ElseIf dt.DateStart <= NewColl(x).DateStart AndAlso dt.DateEnd >= NewColl(x).DateEnd Then
                    'nahradit v nové kolekci, protože údaj je z obou stran větší
                    NewColl(x) = dt
                    Exit For
                ElseIf dt.DateStart < NewColl(x).DateStart Then
                    ' změníme start, necháme konec
                    NewColl(x).ChangeStartAndKeepEnd(dt.DateStart)
                    Exit For
                ElseIf dt.DateEnd > NewColl(x).DateEnd Then
                    'změníme konec, necháme start
                    NewColl(x).ChangeEndAndKeepStart(dt.DateEnd)
                    Exit For
                Else
                    MsgBox("Ještě nevím, zda jsem na něco nezapomněl")
                End If
            Next
        Next

        'nyní máme novou kolekci ale může se uvnitř také prolínat, takže budeme porovnávat části uvnitř kolekce a pouze redukovat a redukovat
        Dim redukovano As Boolean = False
        While redukovano = False
            Dim KolekceSeZmenila As Boolean = False
            Dim pocetPolozek As Integer = NewColl.Count - 1
            Dim TempCOLL As New List(Of TimeRange)
            TempCOLL.Add(NewColl(0))

            For x As Integer = 0 To pocetPolozek
                For y As Integer = 0 To TempCOLL.Count - 1

                Next
            Next
            NewColl = TempCOLL
            If KolekceSeZmenila = False Then redukovano = True
        End While

        Return NewColl
    End Function

End Class
nahlásit spamnahlásit spam 0 odpovědětodpovědět

Dobrý den,

má myšlenka: Vytvořím nový List(of Date) do kterého vložím všechny počáteční a koncové datumy. Tento List tedy bude mít 2*data.Count položek. List seřadím (podle datumu vzestupně). Pak tento seznam procházím cyklem. Pokud se jedná o počáteční datum (datum získané z DateStart), inkrementuji proměnou count. Pokud se jedná o koncové datum, dekrementuji proměnou count.

Podle proměné count pak poznám začátky a konce nových sjednocených intervalů. Když se count inkrementuje z nuly, je jasné že se jedná o počátek sjednoceného intervalu.

Musí samozřejmě platit, že DateStart <= DateEnd

   Shared Function Join(ByVal data As List(Of TimeRange)) As List(Of TimeRange)
        'Vytvořit seznam datumů (počáteční i koncové datum do jednoho seznamu)
        'Seznam je typu Tuple<DateTime, Boolean>, tedy dvojice datum a boolean, kdy boolean hodnota je true, pokud se jedná o DateStart; false v případě DateEnd
        Dim dateTimes As New List(Of Tuple(Of DateTime, Boolean))
        For Each item In data
            dateTimes.Add(New Tuple(Of DateTime, Boolean)(item.DateStart, True))
            dateTimes.Add(New Tuple(Of DateTime, Boolean)(item.DateEnd, False))
        Next

        'Seřadit seznam podle data (volá funkci DateBoolComparer)
        dateTimes.Sort(AddressOf DateBoolComparer)
        'dateTimes.Sort(New Comparison(Of Tuple(Of Date, Boolean))(AddressOf DateBoolComparer))

        'Nyní vlastní sjednocení časových úseků
        'Program si drží proměnou count, která říká, kolik časových úseků (TimeRange) již začalo
        ' - tato proměná se inkrementuje, když se jedná o DateStart, tedy boolean hodnota je true (Item2)
        ' - v případě DateEnd se hodnota dekrementuje
        Dim count As Integer = 0
        Dim beginTime As Date
        Dim result As New List(Of TimeRange)


        For Each i In dateTimes
            If i.Item2 Then
                If count = 0 Then beginTime = i.Item1 'pokud se hodnota count inkrementuje z nuly na jedničku, jedná se o počátek časového intervalu
                count += 1
            Else
                count -= 1
                If count = 0 Then result.Add(New TimeRange(beginTime, i.Item1)) 'pokud se hodnota count dekrementuje z jedničky na nulu, jedná se o konec časového intervalu, celý interval se přidá do kolekce result
            End If
        Next

        Return result
    End Function

'Porovná 2 instance Tuple(Of DateTime, Boolean)
Private Shared Function DateBoolComparer(x As Tuple(Of Date, Boolean), y As Tuple(Of Date, Boolean)) As Integer
        Dim c = x.Item1.CompareTo(y.Item1) 'porovnat datumy

        'pokud jsou datumy stejné, je nutné porovnat podle hodnoty boolean (true < false)
        If c = 0 Then
            Return -1 * x.Item2.CompareTo(y.Item2)
        Else
            Return c
        End If
    End Function
nahlásit spamnahlásit spam 0 odpovědětodpovědět

Hezký den, já bych šel na to úplně jinak. Setřídil bych si intervaly podle začátku "From" a slučoval je. Asi takhle

public static void Main(string[] args)
        {
            var tr1 = new Timerange {From = new TimeSpan(10, 30, 0), To = new TimeSpan(11, 0, 0)};
            var tr2 = new Timerange { From = new TimeSpan(10, 45, 0), To = new TimeSpan(11, 30, 0) };

            var tr3 = new Timerange { From = new TimeSpan(12, 45, 0), To = new TimeSpan(13, 0, 0) };
            var tr4 = new Timerange { From = new TimeSpan(12, 50, 0), To = new TimeSpan(12, 55, 0) };

            var tr5 = new Timerange { From = new TimeSpan(17, 0, 0), To = new TimeSpan(19, 0, 0) };

            var ranges = Join(tr3, tr2, tr1, tr5, tr4);

            foreach (var s in ranges)
            {
                Console.WriteLine("{0} - {1}", s.From, s.To);
            }
        }

        private static IEnumerable<Timerange> Join(params Timerange[] timeranges)
        {
            if (timeranges == null || !timeranges.Any())
                return Enumerable.Empty<Timerange>();

            var sortedTimeranges = timeranges.OrderBy(x => x.From).ToArray(); // setřídit podle začátku intervalu
            var first = sortedTimeranges[0];
            var previous = new Timerange {From = first.From, To = first.To};

            var resultList = new List<Timerange>();

            for (int i = 1 /* nemá smysl zpracovávat první */; i < timeranges.Length; i++)
            {
                var current = sortedTimeranges[i]; 
                
                if (current.From <= previous.To && current.To >= previous.From) // lze intervaly sloučit ?
                {
                    if (current.To > previous.To) // a má to smysl ?
                        previous.To = current.To; // tak je slučme
                }
                else // nelze sloučit
                {
                    resultList.Add(previous); // vyhodím na výstup

                    previous = new Timerange {From = current.From, To = current.To}; // začínám s novým intervalem
                }

                if (i == timeranges.Length - 1) // je poslední, dále se zpracovávat nebude => hodit na výstup
                {
                    resultList.Add(previous);
                }
            }

            return resultList;
        }

        private class Timerange
        {
            public TimeSpan From { get; set; }

            public TimeSpan To { get; set; }
        }
nahlásit spamnahlásit spam 0 odpovědětodpovědět

Ještě jsem zapomněl dodat, že setříděním si zajistíme to, že pokud interval "int[i]" nelze sloučit z "int[i + 1]" tak nelze sloučit ani s žádným intervalem "int[i + n]". Dělají to tak databáze (alg. Merge Join). Počet průchodů potom bude "n" + třízení "n*log(n)"

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Dobrý den,

to setřídění na začátku mě nenapadlo. Takhle je to pak opravdu jednoduché.

Děkuji.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Jsem rád, že pomohlo :) .

nahlásit spamnahlásit spam 0 odpovědětodpovědět
                       
Nadpis:
Antispam: Komu se občas házejí perly?
Příspěvek bude publikován pod identitou   anonym.
  • Administrátoři si vyhrazují právo komentáře upravovat či mazat bez udání důvodu.
    Mazány budou zejména komentáře obsahující vulgarity nebo porušující pravidla publikování.
  • Pokud nejste zaregistrováni, Vaše IP adresa bude zveřejněna. Pokud s tímto nesouhlasíte, příspěvek neodesílejte.

přihlásit pomocí externího účtu

přihlásit pomocí jména a hesla

Uživatel:
Heslo:

zapomenuté heslo

 

založit nový uživatelský účet

zaregistrujte se

 
zavřít

Nahlásit spam

Opravdu chcete tento příspěvek nahlásit pro porušování pravidel fóra?

Nahlásit Zrušit

Chyba

zavřít

feedback