Zusammenhängenden Zeitraum in DB finden

[noisefloor]

Hallo,

folgende Problemstellung: In einer (SQLite-) Datenbank gibt es eine Tabelle, welche u.a. eine Spalte "date" enthält. Jedes Datum kann mehrfach vorkommen.

Gefragt ist nun der größte zusammenhänge Zeitraum, also welche Daten unmittelbar aufeinander folgen. Wie oft jedes Datum vorkommt ist dabei egal. Am Ende soll sowas rauskommen wie z.B.: "längster Zeitraum: 12.4.2013 - 17.4.2013"

Beispiel inkl. meiner Lösung: http://www.python-forum.de/pastebin.php?mode=view&s=336

Das funktioniert auch, kommt mir aber irgendwie "unelegant" vor. Zumal in der realen Anwendung die Tabelle tpyischerweise 1000 - 4000 Zeilen hat, im Extremfall aber auch 80000 Zeilen.

Hat jemand eine bessere Idee?

Gruß, noisefloor

[Sirius3]

Hallo noisefloor,

Du wirst nicht darum herum kommen, fast jeden Eintrag aus der Datenbank auslesen zu müssen.

Code: Alles auswählen

max_first_day = first_day = -1
max_num_days = num_days = 0
current_day = 0
for day in cursor.execute('''SELECT distinct julianday(date) from test order by date'''):
    day = int(day[0])
    if current_day+1 == day:
        num_days+=1
    else:
        if num_days > max_num_days:
            max_first_day = first_day
            max_num_days = num_days
        first_day = day
        num_days = 0
    current_day = day
print max_first_day, max_num_days

Das finden der längsten Kette kannst Du noch effizienter lösen:
Gegeben sei eine sortierte Liste days ohne doppelte Einträge.
n=len(days)
Falls days[n-1]-days[0]==n, hast Du die längste Kette schon gefunden.
Sonst teile n durch 2, 4, 8, ... und untersuche die Teillisten days[k*n:(k+1)*n].
Sobald Du eine Teilliste gefunden hast, die obere Bedingung erfüllt, teile nochmals und erweitere alle gefundenen Teillisten nach links und rechts mit einem ähnlichen Intervallverfahren.