Sortierte Sätze Python 2.7

Ich habe eine Liste, die ich bin versucht zu entfernen doppelter Elemente aus. Ich bin mit python 2.7.1, so kann ich einfach die set() Funktion. Aber das verschiebt meiner Liste. Die für meinen konkreten Fall nicht hinnehmbar ist.

Unten ist eine Funktion, die ich geschrieben habe; der tut dies. Allerdings Frage ich mich, ob es einen besseren/schnelleren Weg. Auch jegliche Kommentare dazu wären sehr willkommen.

    def ordered_set(list_):

        newlist = []
        lastitem = None
        for item in list_:

            if item != lastitem:
                newlist.append(item)
                lastitem = item

        return newlist

Die obige Funktion setzt Voraus, dass keines der Elemente wird Keine, und dass die Elemente in order (ie, ['a', 'a', 'a', 'b', 'b', 'c', 'd'])

Obige Funktion gibt ['a', 'a', 'a', 'b', 'b', 'c', 'd'] als ['a', 'b', 'c', 'd'].

Es ist eine andere ähnliche Frage gibt einen link zu einer Umsetzung, stackoverflow.com/questions/1653970/...
Wäre es besser, die Liste automatisch sortiert und dublettenfrei? Oder ist es in Ordnung, um in regelmäßigen Abständen Spülen Sie die Liste der Duplikate?
Sie Beispiel-code bedeutet, dass _list ist eine Sequenz, die nur zusammenhängend Duplikate. Ist es das, was du meinst? Es funktioniert nicht für Eingaben wie diese [1, 2, -4, -4, 1]: 1 werden noch dupliziert werden, während -4 werden de-dupliziert.

InformationsquelleAutor rectangletangle | 2011-06-01

8

Verwenden Sie ein OrderedDict:
```
from collections import OrderedDict

l = ['a', 'a', 'a', 'b', 'b', 'c', 'd']
d = OrderedDict()

for x in l:
    d[x] = True

# prints a b c d
for x in d:
    print x,
print
```
dies erfordert, dass die Elemente von hashable; zum Beispiel, dies würde nicht funktionieren, wenn die Elemente von Listen oder Wörterbücher; ferner dies erfordert eine O(n) - operation, sondern eine Reihe von O(1) Operationen (die möglicherweise oder möglicherweise nicht das sein, was der OP will, nur etwas im Auge zu behalten)
Dies scheint zu funktionieren gut für meine Zwecke.
Ich habe noch nie eine for-Schleife beschrieben als "ein Bündel von O(1) Operationen" vor. Hm, n O(1) Operationen wäre... O(n)
Ich denke, es ist entlang den gleichen Linien wie die Beschreibung 4 als 2 + 2.
Aber was ist, wenn die Liste GROß ist? Speichern Sie die zusätzlichen Wahre wäre teuer Speicher-Weise. Ich weiß wirklich nicht verstehen, warum python hat keine geordnete Menge. Was ist falsch mit dem halten der insertion order by-default? Es ist einfach eine nette zusätzliche Eigenschaft zu haben!

InformationsquelleAutor mhyfritz

Andere sehr schnelle Methode, die mit " set:

def remove_duplicates(lst):
    dset = set()
    # relies on the fact that dset.add() always returns None.
    return [item for item in lst
            if item not in dset and not dset.add(item)]

Vielen Dank für die Ergänzung, Pavel.

InformationsquelleAutor Zaur Nasibov

7

Vorausgesetzt, die Eingabe-Reihenfolge ist ungeordnet, hier ist O(N) - Lösung (beide in Raum und Zeit).
Es entsteht eine Folge mit Duplikate entfernt werden, während die einzigartigen Elemente in der gleichen relativen Reihenfolge, wie Sie erschienen in der input-sequence.
```
>>> def remove_dups_stable(s):
...   seen = set()
...   for i in s:
...     if i not in seen:
...       yield i
...       seen.add(i)

>>> list(remove_dups_stable(['q', 'w', 'e', 'r', 'q', 'w', 'y', 'u', 'i', 't', 'e', 'p', 't', 'y', 'e']))
['q', 'w', 'e', 'r', 'y', 'u', 'i', 't', 'p']
```
[2,1,2,1] werden konnte [1,2], [2,1], ich bin damit einverstanden, dass [2,1] macht mehr Sinn, in diesem Fall ist es aber nicht stillschweigend in der Frage. Wenn es das set bestellt dann Ihre Lösung ist immer noch gut, also +1
genauso gut könnte upvote @zaur Lösung, da es auch tut, genau das gleiche mit einer Liste erfassen. Im Nachhinein, ich mag, dass man mehr, da sieht es aus wie Sie weniger code 🙂
Oops! @robert, ich war nicht Aufmerksamkeit auf die Chronologie. Ordnungsgemäß up-notiert 🙂
danke. Ja @zaur Lösung ist gut, aber schlägt fehl, wenn das element nicht zerlegt werden. (werden wir alle scheitern, wenn die Liste nicht bestellt). Ich denke, meine Lösung ist, könnte der Schnellste, aber noch nicht benched auf große arrays, die alle meine Speicher =)

InformationsquelleAutor Pavel Repin

Ich weiß, das wurde schon beantwortet, aber hier ist ein Einzeiler (plus import):

from collections import OrderedDict
def dedupe(_list):
    return OrderedDict((item,None) for item in _list).keys()

>>> dedupe(['q', 'w', 'e', 'r', 'q', 'w', 'y', 'u', 'i', 't', 'e', 'p', 't', 'y', 'e'])
['q', 'w', 'e', 'r', 'y', 'u', 'i', 't', 'p']

InformationsquelleAutor sunetos

2

Ich denke, das ist vollkommen OK. Sie erhalten O(n) Leistung, die ist das beste, was Sie hoffen konnte.

Wenn die Liste wurden ungeordnete, dann brauchen Sie einen Helfer set enthalten die Elemente, die Sie bereits besucht haben, aber in Ihrem Fall nicht nötig.

Jegliche Kommentare über die downvote?
Anscheinend nicht, und ich sehe keinen Grund dafür. Ein upvote.
Wieso der downvote? Ich sehe nichts falsch mit Tim Pietzckers post.

InformationsquelleAutor Tim Pietzcker
2

wenn Ihre Liste ist nicht sortiert dann deine Frage macht keinen Sinn.
z.B. [1,2,1] werden konnte [1,2] oder [2,1]

wenn Ihre Liste groß ist möchten Sie vielleicht schreiben Sie Ihr Ergebnis wieder in der gleichen Liste mit einer SCHEIBE, um Speicher zu sparen:
```
>>> x=['a', 'a', 'a', 'b', 'b', 'c', 'd']
>>> x[:]=[x[i] for i in range(len(x)) if i==0 or x[i]!=x[i-1]]
>>> x
['a', 'b', 'c', 'd']
```
inline löschen siehe Entfernen von Elementen aus einer Liste während der Iteration oder Entfernen von Elementen aus einer Liste während der Iteration ohne Verwendung von zusätzlichen Speicher in Python

einen trick, den Sie verwenden können, ist, dass, wenn Sie wissen, x ist sortiert, und Sie wissen, x[i]=x[i+j], dann brauchen Sie nicht zu überprüfen, irgendwas zwischen x[i] und x[i+j] (und wenn Sie das nicht benötigen, löschen Sie diese j-Werte, Sie können einfach kopieren Sie die gewünschten Werte in einer neuen Liste)

Also, während Sie können nicht schlagen n Operationen, wenn alles in der Gruppe ist einzigartig, d.h. len(set(x))=len(x)
Es ist wahrscheinlich ein Algorithmus, der n Vergleiche für den schlimmsten Fall aber können n/2 Vergleiche, da Ihr im besten Fall (oder kleiner als n/2 als Ihre beste Fall, wenn Sie wissen, irgendwie im Voraus wissen, dass len(x)/len(set(x))>2, weil die Daten, die Sie erzeugt haben):

Den optimalen Algorithmus verwenden wahrscheinlich die binäre Suche zum finden von maximalen j für jede minimale ich in einem Teile und herrsche Ansatz. Ersten Divisionen wäre vermutlich der Länge len(x)/approximiert(len(set(x))). Hoffentlich wird es auch durchgeführt werden könnte, selbst wenn len(x)=len(set(x)) es verwendet immer noch nur n Operationen.

InformationsquelleAutor robert king

Es ist unique_everseen Lösung beschrieben
http://docs.python.org/2/library/itertools.html

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in ifilterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

InformationsquelleAutor aloschilov

0

Sieht ok für mich. Wenn Sie wirklich wollen, zu verwenden, setzt etwas wie das hier tun:
```
def ordered_set (_list) :
    result = set()
    lastitem = None
    for item in _list :
        if item != lastitem :
            result.add(item)
            lastitem = item
    return sorted(tuple(result))
```
Ich weiß nicht, was Leistung, die Sie erhalten, sollten Sie es testen; wahrscheinlich das gleiche, weil der Methode, der ist heiß!

Wenn Sie wirklich paranoid sind, genau wie ich, Lesen Sie hier:

http://wiki.python.org/moin/HowTo/Sorting/

http://wiki.python.org/moin/PythonSpeed/PerformanceTips

Erinnerte mich nur dieses(es enthält die Antwort):

http://www.peterbe.com/plog/uniqifiers-benchmark

Haben Sie den code testen? Ihnen nie vergeben nichts zu result. Auch der ganze Sinn des Satzes ist, dass Sie nicht brauchen, um zu überprüfen, ob es bereits ein element enthalten ist oder nicht - Sie würden nur zu result = set(_list). Keine iteration erforderlich. Aber diese Methode (oder verkaufen) würde fehlschlagen, wenn die Reihenfolge der Elemente ist eine andere als die alphabetische...
Jeder, der versucht, mit dieser Funktion erhalten: NameError: global name 'newlist' ist nicht definiert
mein bad, behoben! danke, aber die Lösung war offensichtlich!

InformationsquelleAutor StefanNch

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.