Liste Verstehens in Python zu berechnen, minimum-und maximum-Werte einer Liste

ich habe den folgenden code, um zu berechnen, minimum-und maximum-Werte einer Liste, um Speicher zu speichern Effizienz 

x_min = float('+inf')
x_max = float('-inf')

for p in points_in_list:
    x_min = min(x_min, p)
    x_max = max(x_max, p)

wo points_in_list ist eine (große) Liste von zahlen. Ich möchte wissen, ob es eine Methode gibt, Sie zu berechnen mit einer Liste Verstehens der min-und max-Wert und speichern Sie den Speicher.

  • was bedeutet ein Punkt in points_in_list Aussehen? welche attribute haben Sie?
  • Haben Sie versucht min(points_in_list) und max(points_in_list)? Keine Liste Verständnis hier erforderlich.
  • es ist eine wirklich große Liste an (über 6 Millionen Werte) als points_in_list = [1,3,6,79,80,...,76] Anzahl der
  • Aufruf min oder max auf eine riesige Liste ist nicht zu produzieren, Probleme mit dem Speicher. Warum sollte es? Wurden Sie unter dem Eindruck, dass dies würde erfordern, dass eine Kopie der gesamten Liste?
  • Warum denken Sie, dass eine Liste Verständnis würde weniger Speicher als min?
  • Liste Verstehens erzeugen Listen, während Sie berechnen möchten einzelne Werte aus Listen.

InformationsquelleAutor Gianni Spear | 2014-08-05
  1. 7

    Ich bin ein großer fan von Generatoren und Verstehens, aber in diesem Fall scheint es, Sie sind nicht der richtige Weg zu gehen, denn:

    1. Sie berechnen möchten die min und die max von der Liste
    2. Ihre Liste ist riesig

    Wenn Sie wollten, um zu berechnen, nur eine der min oder max, Sie könnte verwenden Sie einfach die min/max-Funktion auf es. Aber da Sie beides wollen, müssten Sie die Schleife über die Liste doppelt zu extrahieren zunächst die min und dann max. I. e. so etwas wie dieses:

    x_min = min(points)
x_max = max(points)

    Let ' s play mit einigen einige timings. Ersten Aufruf von min-und max-auf der Liste:

    >>> import timeit
>>> def with_gens(l):
...     return min(l), max(l)
...
>>> timeit.timeit('with_gens(range(6000000))', 'from __main__ import with_gens', number=5)
1.7451060887015188

    und jetzt die Schleife nur einmal, verwenden Sie den code:

    >>> def with_loop2(l):
...     x_max = float('+inf')
...     x_min = float('-inf')
...     for el in l:
...         x_min = min(x_min, el)
...         x_max = max(x_max, el)
...     return x_min, x_max
...
>>> timeit.timeit('with_loop2(range(6000000))', 'from __main__ import with_loop2', number=5)
11.636076105071083

    Verrückt, nicht wahr?

    Gibt es kein memory problem mit diesem Ansatz. Jedoch, es stellt die x_max und x_min in jeder Schleife, das ist eigentlich eine unnötige Verschwendung: Sie wollen nur zum zurücksetzen der variable, wenn Sie gefunden haben, einen größeren/kleineren Wert. Wir können einfach diese Adresse.

    Also... lasst uns versuchen, die Schleife nur einmal, aber die Vermeidung unnötiger resettings.

    >>> def with_loop(l):
...     x_min = float('-inf')
...     x_max = float('+inf')
...     for el in l:
...         if el < x_min:
...             x_min = el
...         elif el > x_max:
...             x_max = el
...     return x_min, x_max
...
>>> timeit.timeit('with_loop(range(6000000))', 'from __main__ import with_loop', number=5)
3.961046726963332

    OH WUNDER

    Scheint es, während der Algorithmus der Schleife nur einmal ist auf dem Papier leistungsfähiger, es wird geschlagen, indem die innere Optimierung der min und max. Außerdem, der Unterschied zwischen der Einstellung der var in jeder Schleife und nur bei Bedarf ist riesig. Sie nie aufhören zu lernen.

    • könnte auch interessant sein, führen Sie die tests mit einer zufälligen Reihe von zahlen (anstatt einer sortierten Liste, wo x_max wird zugewiesen, jedes mal, und x_min wird nie zugewiesen) und sehen, ob das etwas ändert
    InformationsquelleAutor bgusach
  2. 7

    Angenommen, ein Punkt hat zwei Attribute, die x und y, dann können Sie

    x_min = min(p['x'] for p in points_in_list) zur Berechnung der min x

    Beispiel:

    >>> a = {'x': 10, 'y':10}
>>> b = {'x': 5, 'y':20}
>>> c = {'x': 50, 'y':50}
>>> points_in_list = [a,b,c]
>>> points_in_list
[{'y': 10, 'x': 10}, {'y': 20, 'x': 5}, {'y': 50, 'x': 50}]
>>> x_min = min(p['x'] for p in points_in_list)
>>> x_min
5
    • schön, was wäre die Zeit, die Komplexität der min(p['x'] für p in points_in_list), ist es O(N) angenommen, es gibt N Elemente in points_in_list? Und was ist in der min-Funktion als parameter zu übergeben, wird es als eine Liste (d.h. p['x'] für p in points_in_list) ?
    InformationsquelleAutor gefei
Schreibe einen Kommentar