Algorithmus, um nach nächsten Wertänderungen zu suchen

Question

Ich habe einen Namen und einen Int in der Tabelle gespeichert, wobei in Int Spalte 0 oder 1 als Wert hat.

N1, 1 
    N2, 0, 
    N3, 0 
    N4, 0, 
    N5, 1 
    N6, 0, 
    N7, 0, 
    N8, 1 
    N9 0 
    N10 0 
    N11 1 

Ich brauche für den nächsten Wertänderungen sehen von 0 auf 1 Ich brauche den Schlüsselwertpaar Ausgang als (N2, N5) WHERE in N2 es 0 hatte, dann 1 bei N5 war. Gleicher Weg (N2, N5), (N6, N8) und (N9, N11)

Jede Idee, wie kann ich Algorithmus für mehr als 100k Datensätze effizient schreiben?

Answer 1

Iterieren Sie über die Daten und verfolgen Sie das erste Auftreten einer 0 und 1, um ein Paar zu bilden.

Wenn Sie das nur einmal tun müssen, dann ist dies der richtige Weg. Außerdem sind 100k + Datensätze nicht so groß und C kann das glücklich angehen.

Sie könnte etwas Beschleunigung durch Kurzschließen Ihrer if-Anweisungen (zum Beispiel, wenn Sie bereits eine Null gefunden haben, suchen Sie nicht nach einer anderen, bis 1 gefunden wurde, damit ein Paar gemacht wurde).

Wie diese in Pseudo-Code:

string first_0 = ""; 
for row in table: 
    if first_0 == "" && row.Int == 0: 
    first_0 = row.Name; 
    if first_0 != "" && row.Int == 1: 
    print pair(first_0, row.Name); 
    first_0 = ""; 

Answer 2

Sie haben nicht genug Details des Problems Datenstrukturen zur Verfügung stellen, aber allgemeine Lösung für Fall vieler Abfragen einfach aussehen:

zusätzliches Feld hinzufügen (oder verknüpfte Tabelle) .
Tisch in umgekehrter Richtung Traverse, hält lastOne und lastZero id (oder Name)

int lastValues[2]; 
for i = last to first 
     currentEntry.nextChange = lastValues[1 - currentEntry.Value]; 
     lastValues[currentEntry.Value] = currentEntry.id