Rimuove gli spazi tra segmenti non sovrapposti di una matrice di elementi temporali

Question

Rimuove gli spazi tra segmenti non sovrapposti di una matrice di elementi temporali

#1 da (2 voti)
#2 da (1 voti)

3

Ho una matrice di elementi, ognuno con un'ora di inizio e un'ora di fine.

Questi formano una timeline, alcuni dei quali si sovrappongono e altri che non lo fanno (e hanno uno spazio tra i gruppi di elementi sovrapposti).

Ho scritto un codice che rimuove gli spazi tra gli elementi non sovrapposti (le linee rosse come nell'immagine qui sotto), tuttavia sta iniziando a diventare un po 'disordinato e non a casi da non perdere.

Esistegiàunalgoritmocherimuoveràglispazirossiesposteràtuttoinordine?

Ilmiocodicestabèsotto:

//sortbytime,lowesttohighestentries.Sort((a,b)=>a.TimeOffset.CompareTo(b.TimeOffset));varlookingForFirstGap=true;varstoredOffset=0.0;varindexToTrimFrom=0;for(vari=0;i<entries.Count-1;i++){//varprevious=entries[i-1];varcurrent=entries[i];varnext=entries[i+1];//vardistanceBack=previous.TimingsAbsolute.End-current.TimingsAbsolute.Start;vardistanceForward=next.TimingsAbsolute.Start-current.TimingsAbsolute.End;Console.WriteLine("Distance {0} -> {1} is {2}", i, i+1, distanceForward);

    if (!(distanceForward > 0))
        continue;

    if (lookingForFirstGap)
    {
        indexToTrimFrom = i + 1;
        Console.WriteLine("To trim from " + indexToTrimFrom);
        storedOffset = distanceForward; // we have found a gap, store the amount
        lookingForFirstGap = false; // now start looking for element where there is a gap after it
    }
    else
    {
        var indexToTrimTo = i;

        for (var x = indexToTrimFrom; x <= indexToTrimTo; x++)
        {
            // trim all
            Console.WriteLine("Adjust [" + x + "] by " + storedOffset);
        }

        if (distanceForward > 0)
        {
            indexToTrimFrom = i + 1;
            Console.WriteLine("To trim from " + indexToTrimFrom);
            storedOffset = distanceForward; // we have found a gap, store the amount
        }
        else
            lookingForFirstGap = true; // start looking for gap again
    }
}

c# algorithms sorting

posta g18c 24.09.2016 - 22:08

fonte

2 risposte

1

Inserendo questo come codice, @Karl mi ha aiutato a capire che suddividere questo ha reso tutto molto più semplice! I principi SOLID consentono un codice molto più semplice.

List<Tuple<int, int>> FindGaps(List<LogEntry> entries)
{
    var gaps = new List<Tuple<int, int>>();

    for (var i = 0; i < entries.Count - 1; i++)
    {
        var current = entries[i];
        var next = entries[i + 1];

        var distanceForward = next.TimingsAbsolute.Start - current.TimingsAbsolute.End;

        if (!(distanceForward > 0)) // there is no gap to the next element, continue
            continue;

        gaps.Add(new Tuple<int, int>(i, i+1)); // otherwise, we have found a gap...
    }

    return gaps;
}

List<Tuple<int, int>> FindContiguous(List<Tuple<int, int>> gaps, int totalLength)
{
    var previous = 0;
    var lastIndex = totalLength - 1;

    var contiguous = new List<Tuple<int, int>>();

    foreach (var gap in gaps)
    {
        contiguous.Add(new Tuple<int, int>(previous,gap.Item1));

        previous = gap.Item2;
    }

    if (previous != lastIndex)
    {
        contiguous.Add(new Tuple<int, int>(previous,lastIndex));
    }

    return contiguous;
}


List<LogEntry> RemoveGaps(List<LogEntry> entries, List<Tuple<int, int>> contiguous)
{
    var newList = new List<LogEntry>();

    var totalShift = 0.0;
    LogEntry previousLast = null;

    foreach (var seq in contiguous)
    {
        var startIndex = seq.Item1;
        var endIndex = seq.Item2;

        if (previousLast != null)
        {
            totalShift += entries[startIndex].TimingsAbsolute.Start - previousLast.TimingsAbsolute.End;
        }

        previousLast = entries[endIndex];

        for (var i = startIndex; i <= endIndex; i++)
        {
            var entry = entries[i];

            newList.Add(
                new LogEntry(
                    entry.Url,
                    entry.Status,
                    entry.HeaderSize,
                    entry.PayloadSize,
                    entry.TimeOffset-totalShift,
                    entry.Timings.Blocked,
                    entry.Timings.Dns,
                    entry.Timings.Connect,
                    entry.Timings.Ssl,
                    entry.Timings.Send,
                    entry.Timings.Wait,
                    entry.Timings.Receive,
                    entry.ConnectionId));    
        }
    }

    return newList;
}

public void Generate(List<LogEntry> entries, Guid testId)
{
    // sort by time, lowest to highest
    entries.Sort((a, b) => a.TimeOffset.CompareTo(b.TimeOffset));

    // get a list of contigous elements
    var contiguous = FindContiguous(FindGaps(entries), entries.Count);

    // now remove the gaps between the contiguous sequences of elements 
    var list = RemoveGaps(entries, contiguous);
}

risposta data 30.09.2016 - 00:55

fonte

Leggi altre domande sui tag c# algorithms sorting

Costruire 3D da 2D Quale pattern posso usare per fare calcoli che coinvolgono sottotipi di oggetti simili ma diversi?

score 2 · Accepted Answer

Stai provando a fare troppo in un ciclo. Sottraendo le lacune è difficile perché è difficile identificare le lacune. Identificare gli spazi vuoti è difficile a causa di tutti gli strani modi in cui gli intervalli si sovrappongono, quindi rimuovi prima il problema dell'intervallo sovrapposto.

Effettua un passaggio per appiattire gli intervalli, utilizzando un algoritmo da questa domanda . Quindi un passaggio per creare una lista di spazi vuoti, che dovrebbe essere molto semplice con la lista appiattita.

Ora sei pronto per scorrere l'elenco di intervalli originale. Per ciascun intervallo, vedere quanti spazi si verificano prima di esso e sottrarre il tempo cumulativo di ciascuno.