Vermeiden Objekt aliasing in python?

Ich versuche, eine Funktion schreiben, die überprüfen, ob eine Liste sortiert ist (Rückkehr True oder False). Wie kann ich vermeiden, dass mehrere Variablen auf das gleiche Ding?

def is_sorted(t):
    a = t
    a.sort()

Wenn ich das mache, er sortiert beide a und t. Wie kann ich diese vermeiden?

  • "Wie kann ich diese vermeiden?" Von der Suche nach einem besseren design. Dies ist -- vielleicht -- die langsamste Art und Weise, dies zu tun. Die einzige Sache, die könnte langsamer sein, wäre die Umsetzung Ihrer eigenen version von sort.
  • Es ist etwas, das erkenntnistheoretische über die Antworten, die beinhalten, dass die Sortierung der Liste: es ist völlig unwahrscheinlich, dass das Programm keine Verwendung haben für, zu einem anderen Ergebnis als True nachdem die Liste bereits sortiert. Nur in sehr seltenen Fällen würde die Antwort auf die ursprüngliche is_sorted() Abfrage noch relevant sein. Außerdem, ist die Sortierung einer bereits sortierten Liste ist nah genug zu A(n), also Warum die Mühe Abfragen, anstatt nur geradeaus und ruft sort() oder sorted()?
InformationsquelleAutor Johnny | 2011-01-06
  1. 9

    Hier ist das O(n) Weg, es zu tun

    >>> from itertools import islice, izip
>>> def is_sorted(L):
...     return all(i<=j for i,j in izip(L, islice(L,1,None)))
... 
>>> is_sorted(range(50))
True
>>> is_sorted(range(50)+[20])
False

    Es zu Kurzschlüssen, so dass, wenn die Liste unsortiert direkt in der Nähe der Anfang, es wird sehr schnell

    Hier ist ein einfaches Programm zum vergleichen einige der alternativen

    import random
import time
from itertools import islice, izip

def is_sorted1(L):  # 0.0006s
    return all(i<=j for i,j in izip(L, islice(L,1,None)))

def is_sorted2(L):  # 0.117s
    return all(L[i] < L[i+1] for i in range(len(L)-1) )

def is_sorted3(L):  # 2.344s
    return L == sorted(L)

def is_sorted4(L):  # 0.0002s
    return all(L[i] < L[i+1] for i in xrange(len(L)-1) )

A = [range(random.randrange(100000)) for i in range(100)]
for a in A:
    random.shuffle(a)

for f in is_sorted1, is_sorted2, is_sorted3, is_sorted4:
    s=time.time()
    for a in A:
        f(a)
    print time.time() - s
    • Naja, ich bezweifle, dass Johnny versteht, was dies bedeutet ;p Vielleicht hilft dies ja: izip(L, islice(L,1,None)) Folien ein Fenster über L. Es gibt eine Reihenfolge wie [(L[0],L[1]), (L[1],L[2]), ...]
    • Es kann einfach nit-Kommissionierung, aber die Indizierung einer Python-Liste sollte viel billiger sein, als das schneiden und komprimieren es.
    • viel billiger"? Bitte verwenden Sie timeit - und post-Vergleich zeigt, was wirklich passiert ist, nicht das, was sollte geschehen.
    • die Indizierung ist schneller mit CPython2.6 auf das computer, aber beachten Sie, dass es unerlässlich war, zu verwenden xrange intead range
    • Man sollte Sie nicht brauchen, um alles zu Messen. Die Leistungsmerkmale der Python-interpreter und standard-Bibliotheken sind gut dokumentiert, und Big O sagt den rest. Meine mit range statt xrange war ein Anfänger-Fehler (xrange verworfen wurde in Python 3).
    • vs. xrange bekannt ist. "die Indizierung einer Python-Liste sollte viel billiger sein, als das schneiden und komprimieren es" nicht so bekannt ist. Ohne aktuelle zahlen, ist es-tatsächlich-Vermutung. Mit tatsächlichen zahlen ist es Theorie + Beweise == Wissenschaft.
    • Viel besser bekannt ist die Tatsache, dass die überprüfung, ob eine Sequenz sortiert ist, sollte viel billiger sein, als das Sortieren es. 😉

    InformationsquelleAutor John La Rooy
  2. 6

    BEARBEITEN: siehe diese Antwort für den richtigen Weg, es zu tun. Ich lasse meine Antwort hier für die Nachwelt (was ist der richtige Weg, diese situation zu bewältigen?), aber es sollte nicht als die beste Antwort auf die Frage, auch wenn es ein richtige Antwort auf die Frage.

    Beantworten Ihre spezifische Frage, die Sie verwenden können copy.copy (oder verwenden Sie das slice-syntax [:]) erstellen Sie eine Kopie der ursprünglichen Liste:

    import copy

def is_sorted(t):
    a = copy.copy(t) # could also do: a = t[:]
    a.sort()
    return a == t

    Jedoch eine bessere Methode wäre, um die sorted - Funktion geben Sie eine sortierte Kopie der Liste:

    def is_sorted(t):
    return sorted(t) == t

    Oder: is_sorted = lambda t: sorted(t) == t

    • deepcopy übertrieben ist, angesichts der specs. copy oder [:] genügen, da die Elemente in der Liste nicht geändert wird.
    • Guter Punkt. Ich werde ändern Sie meine Antwort zu löschen, die deepcopy-Referenzen.
    • Die Prüfung, ob eine Sequenz sortiert ist O(n) Vergleiche und O(0) vertauscht. Die Sortierung für die sane-test ist in O(n log(n)).
    • Während python-code bleibt über 100-mal langsamer als C-code, ist es oft schneller, um Missbrauch zu Sortieren, auf diese Weise in der Praxis, da das Protokoll(n) nicht fangen, der 100 bis n ist sehr groß. Wenn die Liste sehr unsortiert, ein python-loop viel schneller wenn
    • Eine swap-Kosten in Größenordnungen, die mehr als ein Vergleich, und das O(n) ist nur für vollständig sortierte Sequenzen. Es gibt eine große Konstante, multipliziert die n log(n) bei der Sortierung. Die Lösung, die Sie gab in Ihrer Antwort ist die richtige.
    InformationsquelleAutor Alex Vidal
  3. 3

    durch die Schaffung einer Kopie Ihrer Liste mit so etwas wie dies:

    def is_sorted(t):  
    a = t[:]  # create a copy
    a.sort()
    • Sie sollten nicht ermutigen, diese Art von bad-design durch die Beantwortung der Frage direkt. Es ist eine schlechte Frage.
    • Vielen Dank für die Beratung mit freundlichen GRÜßEN 🙂
    • Soll ich sagen ", Während Ihre Antwort ist sehr gut, die Frage war sehr schlecht."
    InformationsquelleAutor mouad
  4. 3

    Kredit für diese minimale Antwort gehört @gnibbler

    is_sorted = all(q[i] < q[i+1] for i in xrange(len(q)-1) )
    • diese durchläuft die gesamte Liste, auch wenn das erste element größer ist als der zweite. Sie können all() hier statt reduzieren und der code wird übersichtlicher zu. all(q[i] < q[i+1] for i in range(len(q)-1))
    • Es muss nicht Durchlaufen der ganzen Liste, weil es ist ein generator-Ausdruck (nicht eine Liste generator), und die and_ - operator wertet in Kurzschluss-Mode: es wird verbrauchen die input-iterator während es findet True. Eine Lösung mit all ist besser.
    • reduce() nicht weiß, dass es aufhören kann, wenn es feststellt, Wahr ist, so dass der generator-Ausdruck würde müssen vollständig, bis zum Ende.
    • +1: nicht Herumspielen, Sortieren und vergleichen. Nur bewerten die notwendig Prädikat. Viel schneller. Und einfacher auch.
    • Du hast Recht über reduce(). Meine Antwort wurde bereits von Ihnen positiv bewertet werden, so korrigierte ich ihn. Die Kommentare und Ihre Antworten enthalten, die Spur von Veränderungen, außer meiner ursprünglichen reduce(operator.and_, q[i] < q[i+1] for i in range(len(q)-1))
    InformationsquelleAutor Apalala
  5. 2

    Können Sie entweder eine Kopie der t und dann Sortieren, etwa so: a = t[:] oder verwenden sortiert, das gibt eine neue sortierte Liste.

    Alternativ nutzen Sie die sortedlist Struktur von blist, dann wird Ihre Liste immer sortiert werden.

    InformationsquelleAutor Seth
  6. 0

    Dies ist eine sehr schlechte Art und Weise, hinsichtlich der Leistung, zu überprüfen, ob eine Liste geordnet ist. Sie sollten stattdessen Durchlaufen Sie überprüfen, dass jedes element größer oder gleich dem vorherigen.

    • Heffeman, theoretisch hast du Recht. Aber Python ist eine Art Umsetzung ist so schnell im Vergleich zur eigentlichen python-code, der nur der Vergleich einer Liste eine sortierte version von sich selbst ist oft schneller.
    • Punkt getroffen. Sollte dort gebaut werden-in der Funktion, die dies tut, würde damit den Aufwand für das erstellen einer Kopie der Liste nur um zu überprüfen, dass es monoton! Oh, es macht mich fühle mich schmutzig, nur darüber nachzudenken.
    • Es wäre schön, in einigen Fällen, aber ich verstehe, warum es nicht da ist. Die meisten der Zeit, wenn man interessiert zu wissen, wenn eine Sequenz ist sortiert, es ist, weil man will, dass die Reihenfolge sortiert, in dem Fall kann man nur verwenden list.sort oder sorted. Wenn es eine Art nur, wenn die unsortierte situation, dann TimSort (der Sortier-Algorithmus verwendet, um Python) ist O(n) auf einer sortierten Liste, die ist, was die Prüfung für Monotonie über ist, um mit zu beginnen. Also nochmal, einfach die Liste Sortieren.
    • OK, aber ich kann nicht scheinen, um zu schütteln, verschmutzte sensation.... 😉
    InformationsquelleAutor David Heffernan
Schreibe einen Kommentar