Split eine Liste der Daten durch eine andere Liste der Daten

Ich habe eine Anzahl von Knoten in einem Netzwerk. Die Knoten senden Statusinformationen jede Stunde, um anzuzeigen, dass sie am Leben sind. Also habe ich eine Liste von Nodes und die Zeit, als sie zuletzt am Leben waren. Ich möchte die Anzahl der lebendigen Knoten über die Zeit grafisch darstellen.

Die Liste der Knoten wird nach der Zeit sortiert, die sie zuletzt lebendig waren, aber ich kann nicht herausfinden, eine schöne Art zu zählen, wie viele sind zu jedem Datum lebendig.

from datetime import datetime, timedelta seen = [ n.last_seen for n in c.nodes ] # a list of datetimes seen.sort() start = seen[0] end = seen[-1] diff = end - start num_points = 100 step = diff / num_points num = len( c.nodes ) dates = [ start + i * step for i in range( num_points ) ] 

Was ich will, ist grundsätzlich

 alive = [ len([ s for s in seen if s > date]) for date in dates ] 

Aber das ist nicht wirklich effizient. Die Lösung sollte die Tatsache verwenden, dass die seen Liste sortiert ist und nicht über die ganze Liste für jedes Datum.

  • Wie kann man ein Array von Ganzzahlen schneller als Quicksort sortieren?
  • Schnellste Weg, um den Schwerpunkt eines Satzes von Koordinaten-Tupeln in Python ohne numpy zu berechnen
  • Leistungsprobleme mit App Engine memcache / ndb.get_multi
  • Ist es eine schlechte Praxis, Pythons getattr ausgiebig zu benutzen?
  • Aggregierte numpy Funktionen
  • Effiziente Python Pandas Stock Beta Berechnung auf vielen Dataframes
  • Python + numpy: effiziente Möglichkeit, die min / max n Werte und Indizes aus einer Matrix zu nehmen
  • Verknüpfen Sie eine einzelne Zeitreihe mit einer großen Anzahl von Zeitreihen
  • 3 Solutions collect form web for “Split eine Liste der Daten durch eine andere Liste der Daten”

    Dieser Generator durchläuft die Liste nur einmal:

     def get_alive(seen, dates): c = len(seen) for date in dates: for s in seen[-c:]: if s >= date: # replaced your > for >= as it seems to make more sense yield c break else: c -= 1 

    Das Python- Bisect-Modul findet für Sie den richtigen Index, und Sie können die Anzahl der Artikel vor und nachher abziehen.

    Wenn ich das richtig verstehe, wäre das O (Datum) * O (log (gesehen))


    Bearbeiten 1

    Es sollte möglich sein, in einem Durchgang zu tun, genau wie SilentGhost zeigt. Allerdings funktioniert itertools.groupby gut mit sortierten Daten, es sollte in der Lage sein, hier etwas zu tun, vielleicht wie das (das ist mehr als O (n), könnte aber verbessert werden):

     import itertools # numbers are easier to make up now seen = [-1, 10, 12, 15, 20, 75] dates = [5, 15, 25, 50, 100] def finddate(s, dates): """Find the first date in @dates larger than s""" for date in dates: if s < date: break return date for date, group in itertools.groupby(seen, key=lambda s: finddate(s, dates)): print date, list(group) 

    Ich habe SilentGhosts Generator-Lösung ein bisschen weiter mit expliziten Iteratoren. Dies ist die lineare Zeitlösung, an die ich gedacht habe.

     def splitter( items, breaks ): """ assuming `items` and `breaks` are sorted """ c = len( items ) items = iter(items) item = items.next() breaks = iter(breaks) breaker = breaks.next() while True: if breaker > item: for it in items: c -= 1 if it >= breaker: item = it yield c break else:# no item left that is > the current breaker yield 0 # 0 items left for the current breaker # and 0 items left for all other breaks, since they are > the current for _ in breaks: yield 0 break # and done else: yield c for br in breaks: if br > item: breaker = br break yield c else: # there is no break > any item in the list break 
    Python ist die beste Programmiersprache der Welt.