Usuwanie duplikatów z listy
Robert
posortowaną listę dowolnych obiektów, chcemy z niej usunąć
duplikaty. Zacząłem pisać:
def uniq(l):
for e in l:
if e!=prev_e: yield e
prev_e = e
no ok, a teraz trzeba przed pętlą zainicjować czymś prev_e.
Pytanie: czym??? Po 5 minutach jedyne, co byłem w stanie wymyślić,
to:
def uniq(l):
def mega_hack(): pass
prev_e = mega_hack
for ... itd
Jak to zobaczyłem to mi się włos zjeżył i przepisałem to inaczej:
def uniq(l):
if l==[]: return l
prev_e, l = l[0], l[1:]
yield prev_e
for ... i to co wcześniej
Możnaby argumentować, że to jednak nie jest tak eleganckie, jak
było w oryginalnym pomyśle. Pytanie: ktoś zna jakieś lepsze
rozwiązanie?
PS. Od razu powiem, że konwersja na set (w ogólności) nie wchodzi w
grę.
PPS. Warunek posortowania listy gwarantuje, że nie ma na niej po
przejściu uniq żadnych duplikatów; można go odrzucić, a wtedy
żądamy usunięcia duplikatów następujących po sobie.
Rob Wolfe
Robert napisał(a):
> Witam, w trakcie pracy dziś przyszedł mi do głowy taki problem: mamy
> posortowaną listę dowolnych obiektów, chcemy z niej usunąć
> duplikaty. Zacząłem pisać:
[...]
> def uniq(l):
> if l==[]: return l
> prev_e, l = l[0], l[1:]
> yield prev_e
> for ... i to co wcześniej
>
> Możnaby argumentować, że to jednak nie jest tak eleganckie, jak
> było w oryginalnym pomyśle. Pytanie: ktoś zna jakieś lepsze
> rozwiązanie?
A co powiesz na to:
>>> def unique(l):
... return [v for i, v in enumerate(l) if i == 0 or v != l[i-1]]
>>> unique("aaabbbcccddd")
['a', 'b', 'c', 'd']
>>> unique([1, 1, 1, 2, 2, 3, 3, 4])
[1, 2, 3, 4]
> PS. Od razu powiem, że konwersja na set (w ogólności) nie wchodzi w
> grę.
Jeśli nie ma założenia, że kolejność elementów musi być
zachowana,
to jest chyba najbardziej wydajne rozwiązanie w pythonie:
>>> list(set("aaabbbcccddd"))
['a', 'c', 'b', 'd']
> PPS. Warunek posortowania listy gwarantuje, że nie ma na niej po
> przejściu uniq żadnych duplikatów; można go odrzucić, a wtedy
> żądamy usunięcia duplikatów następujących po sobie.
Powyższa funkcja spełnia ten warunek.
--
pozdrawiam
Rob
Robert
Rob Wolfe wrote:
> A co powiesz na to:
>
> >>> def unique(l):
> ... return [v for i, v in enumerate(l) if i == 0 or v != l[i-1]]
> >>> unique("aaabbbcccddd")
> ['a', 'b', 'c', 'd']
> >>> unique([1, 1, 1, 2, 2, 3, 3, 4])
> [1, 2, 3, 4]
No, niewątpliwie krótsze od mojego 2go rozwiązania, ale
sprowadzające się do przepisania go w stylu funkcyjnym. A o tym nie
pomyślałem :)
Jest drobny problem techniczny - Twoja implementacja (podobnie z
resztą, jak moja 2ga) wymaga, aby obiekt l wspierał __getitem__, a
teoretycznie nie powinno być to wymagane - uniq powinno działać
również np. dla generatorów.
>
> > PS. Od razu powiem, że konwersja na set (w ogólności) nie wchodzi w
> > grę.
>
> Jeśli nie ma założenia, że kolejność elementów musi być
> zachowana,
> to jest chyba najbardziej wydajne rozwiązanie w pythonie:
Po pierwsze, kolejność elementów powinna być zachowana, ale w
ostateczności można ten warunek opuścić. Poważniejszym problemem
jest to, że żeby zrobić set, elementy listy muszą być hashowalne,
a do uniq powinna wystarczyć możliwość ich porównania.
Robert
Rob Wolfe wrote:
> Jeśli nie ma założenia, że kolejność elementów musi być
> zachowana,
> to jest chyba najbardziej wydajne rozwiązanie w pythonie:
Acha, i jeszcze jedno: przy konwersji na set nie masz gwarancji czasu
działania O(n) (chociaż oczywiście w większości przypadków czas
byłby liniowy). Ponadto, wykorzystanie set'a wymaga zhaszowania
każdej instancji ciągu, co dla dużych obiektów jest ciężkie.
Jeśli np. w liście są listy, z których wiele ma wspólne, krótkie
prefixy, to implementacja z porównaniami, nie dość, że zawsze
będzie O(n) [może być w takim przypadku nawet o(n)], to będzie
znacznie bardziej wydajna, niż z haszowaniem całych obiektów.
Wojciech Muła
> Witam, w trakcie pracy dziś przyszedł mi do głowy taki problem: mamy
> posortowaną listę dowolnych obiektów, chcemy z niej usunąć
> duplikaty. Zacząłem pisać:
>
> def uniq(l):
> for e in l:
> if e!=prev_e: yield e
> prev_e = e
No to może funkcja groupby z modułu itertools:
>>> import itertools
>>> l='aaaaabbbbbccccccddddddddddeeeeeeeeeeeeeeeeeffffffffffffff'
>>> a=[i[0] for i in itertools.groupby(l)]
>>> a
['a', 'b', 'c', 'd', 'e', 'f']
>>>
w.
--
Tępi głupcy są własnymi nieprzyjaciółmi, gdy dopuszczają
się złych uczynków, których owoce są gorzkie.
Filip Wasilewski
> Witam, w trakcie pracy dziś przyszedł mi do głowy taki problem: mamy
> posortowaną listę dowolnych obiektów, chcemy z niej usunąć
> duplikaty. Zacząłem pisać:
>
> def uniq(l):
> for e in l:
> if e!=prev_e: yield e
> prev_e = e
>
> no ok, a teraz trzeba przed pętlą zainicjować czymś prev_e.
> Pytanie: czym???
Pomysł z generatorem jest bardzo dobry. Idąc dalej tym tropem, jeśli
użyje się iteratora do przeglądania kolekcji wejściowej, bardzo
łatwo można dostać się do pierwszego elementu.
def uniq_sorted(collection):
it = iter(collection)
prev = it.next()
yield prev
for elem in it:
if elem != prev:
prev = elem
yield prev
W przypadku gdy kolekcja jest pusta, it.next() rzuci wyjątek
StopIteration, który rozpropagowany na zewnątrz funkcji zakończy
iterację w naturalny sposób.
>>> print list(uniq_sorted(iter('aaddfffggss')))
['a', 'd', 'f', 'g', 's']
>>> print list(uniq_sorted([1]))
[1]
>>> print list(uniq_sorted(""))
[]
fw
Rob Wolfe
> Rob Wolfe wrote:
>
>> A co powiesz na to:
>>
>> >>> def unique(l):
>> ... return [v for i, v in enumerate(l) if i == 0 or v != l[i-1]]
>> >>> unique("aaabbbcccddd")
>> ['a', 'b', 'c', 'd']
>> >>> unique([1, 1, 1, 2, 2, 3, 3, 4])
>> [1, 2, 3, 4]
>
> No, niewątpliwie krótsze od mojego 2go rozwiązania, ale
> sprowadzające się do przepisania go w stylu funkcyjnym. A o tym nie
> pomyślałem :)
Nie chodziło mi o styl funkcyjny a o "list comprehension",
czyli tworzenie listy w miejscu. Jest to generalnie bardziej
wydajne od generatora. Oczywiście wiele zależy od tego w jakim
kontekście miałyby być te funkcje użyte, do jak dużych sekwencji itp.
> Jest drobny problem techniczny - Twoja implementacja (podobnie z
> resztą, jak moja 2ga) wymaga, aby obiekt l wspierał __getitem__, a
> teoretycznie nie powinno być to wymagane - uniq powinno działać
> również np. dla generatorów.
Można tak napisać funkcję, że sprawdzi ona z jakim obiektem mamy do czynienia
i użyje najbardziej adekwatnego algorytmu:
def unique(l):
try:
l[0]
except TypeError:
# przejscie do nastepnego algorytmu
else:
# moj generator z __getitem__
return (v for i, v in enumerate(l) if i == 0 or v != l[i-1])
# tu Twoj 1-szy algorytm
>> > PS. Od razu powiem, że konwersja na set (w ogólności) nie wchodzi w
>> > grę.
>>
>> Jeśli nie ma założenia, że kolejność elementów musi być
>> zachowana,
>> to jest chyba najbardziej wydajne rozwiązanie w pythonie:
>
> Po pierwsze, kolejność elementów powinna być zachowana, ale w
> ostateczności można ten warunek opuścić. Poważniejszym problemem
> jest to, że żeby zrobić set, elementy listy muszą być hashowalne,
> a do uniq powinna wystarczyć możliwość ich porównania.
Fakt, ale rezygnowanie z wydajności na rzecz ogólności
za wszelką cenę, to nie jest chyba najrozsądniejsze podejście.
--
pozdrawiam
Rob
Rob Wolfe
> Rob Wolfe wrote:
>
>> Jeśli nie ma założenia, że kolejność elementów musi być
>> zachowana,
>> to jest chyba najbardziej wydajne rozwiązanie w pythonie:
>
> Acha, i jeszcze jedno: przy konwersji na set nie masz gwarancji czasu
> działania O(n) (chociaż oczywiście w większości przypadków czas
> byłby liniowy).
Dlaczego nie? Tak dobrze znasz implementację pythonowego set'a?
Klasyczną tablicą haszującą jest słownik, a sam set to AFAIK
nieco bardziej zmyślna struktura.
> Ponadto, wykorzystanie set'a wymaga zhaszowania
> każdej instancji ciągu, co dla dużych obiektów jest ciężkie.
> Jeśli np. w liście są listy, z których wiele ma wspólne, krótkie
> prefixy, to implementacja z porównaniami, nie dość, że zawsze
> będzie O(n) [może być w takim przypadku nawet o(n)], to będzie
> znacznie bardziej wydajna, niż z haszowaniem całych obiektów.
Żebyś wiedział ile razy już się przekonałem jak to z pozoru
mniej wydajne rozwiązania biją na głowę niezwykle wyszukane
konstrukcje. W kwestii wydajności ostateczną wyrocznią
jest praktyka.
A więc zobaczmy:
-----8<---unique.py------8<------
import timeit
import string
from itertools import groupby
def unique_list_comp(l):
return [x for i, x in enumerate(l) if i == 0 or x != l[i-1]]
def unique_set(l):
return list(set(l))
def unique_group_by(l):
return [i[0] for i in groupby(l)]
def unique_brute_force(l):
u = []
for x in l:
if x not in u:
u.append(x)
return u
def test_all(seqname, seq, n, f=None):
print "\nseq = %s * %d" % (seqname, n)
if f:
seq = f(seq * n)
else:
seq = seq * n
for fn in sorted(globals().keys()):
if fn.startswith("unique_"):
test(fn, seqname, seq)
def test(fn, seqname, seq):
t = timeit.Timer("%s(%r)" % (fn, seq), "from __main__ import %s" % fn)
print "%20.20s: %5.2f" % (fn, t.timeit(40000))
if __name__ == "__main__":
import sys
print "python: ", sys.version.split()[0], sys.platform
test_all("ascii", string.ascii_letters, 10)
test_all("ascii_sorted", string.ascii_letters, 10, sorted)
test_all("ascii", string.ascii_letters, 100)
test_all("ascii_sorted", string.ascii_letters, 100, sorted)
test_all("0..99", range(10), 10)
test_all("0..99_sorted", range(10), 10, sorted)
test_all("0..99", range(100), 100)
l1 = (string.ascii_lowercase, string.ascii_uppercase, string.digits)
l2 = (string.ascii_uppercase, string.ascii_lowercase, string.digits)
l3 = (string.digits, string.ascii_lowercase, string.uppercase)
test_all("[l1, l2, l3]", [l1, l2, l3], 100)
test_all("[l1, l2, l3]_sorted", [l1, l2, l3], 100, sorted)
test_all("[l1, l2, l3]_sorted", [l1, l2, l3], 1000, sorted)
-----8<---unique.py------8<------
Wyniki:
python: 2.4.1 linux2
seq = ascii * 10
unique_brute_force: 25.28
unique_group_by: 9.49
unique_list_comp: 11.54
unique_set: 1.63
seq = ascii_sorted * 10
unique_brute_force: 24.72
unique_group_by: 2.07
unique_list_comp: 10.12
unique_set: 1.74
seq = ascii * 100
unique_brute_force: 238.41
unique_group_by: 87.85
unique_list_comp: 113.05
unique_set: 13.78
seq = ascii_sorted * 100
unique_brute_force: 239.31
unique_group_by: 12.35
unique_list_comp: 99.41
unique_set: 14.98
seq = 0..99 * 10
unique_brute_force: 1.81
unique_group_by: 1.88
unique_list_comp: 2.19
unique_set: 0.46
seq = 0..99_sorted * 10
unique_brute_force: 1.81
unique_group_by: 0.47
unique_list_comp: 1.95
unique_set: 0.46
seq = 0..99 * 100
unique_brute_force: 978.97
unique_group_by: 175.44
unique_list_comp: 220.12
unique_set: 34.17
seq = [l1, l2, l3] * 100
unique_brute_force: 6.17
unique_group_by: 7.69
unique_list_comp: 8.82
unique_set: 4.47
seq = [l1, l2, l3]_sorted * 100
unique_brute_force: 5.89
unique_group_by: 3.09
unique_list_comp: 7.66
unique_set: 4.41
seq = [l1, l2, l3]_sorted * 1000
unique_brute_force: 63.16
unique_group_by: 33.45
unique_list_comp: 79.63
unique_set: 46.58
--
pozdrawiam
Rob
Wojciech Muła
> Żebyś wiedział ile razy już się przekonałem jak to z pozoru
> mniej wydajne rozwiązania biją na głowę niezwykle wyszukane
> konstrukcje. W kwestii wydajności ostateczną wyrocznią
> jest praktyka.
Święte słowa! Ostatnio eksperymentowałem z algorytmem który efektywnie
wyznacza jednocześnie minimum i maksimum listy. Wyniki mnie kompletnie
zaskoczyły - użycie standardowych funkcji pythonowych, czyli zwykłe
(min(L), max(L)) okazało się ok. 10 razy szybsze od tej teoretycznie
szybszego algorytmu. Może w jakimś C czy C++ implementacja wyszłaby
rzeczywiście dobrze, ale w przypadku Pythona, to się kompletnie nie
sprawdziło.
Piotr Dembiński
[...]
> Żebyś wiedział ile razy już się przekonałem jak to z pozoru
> mniej wydajne rozwiązania biją na głowę niezwykle wyszukane
> konstrukcje. W kwestii wydajności ostateczną wyrocznią
> jest praktyka.
Tu jeszcze masz czas liniowy:
def unique_dict(l):
d = {}
for e in l:
d[e] = None
return d.keys()
I wyniki testów z mojego komputera:
python: 2.4.3 linux2
seq = ascii * 10
unique_brute_force: 40.49
unique_dict: 7.15
unique_group_by: 18.27
unique_list_comp: 21.20
unique_set: 3.01
seq = ascii_sorted * 10
unique_brute_force: 40.71
unique_dict: 7.06
unique_group_by: 3.63
unique_list_comp: 17.61
unique_set: 3.47
seq = ascii * 100
unique_brute_force: 570.76
unique_dict: 92.37
unique_group_by: 224.15
unique_list_comp: 271.17
unique_set: 36.91
seq = ascii_sorted * 100
unique_brute_force: 581.82
unique_dict: 87.68
unique_group_by: 28.77
unique_list_comp: 213.28
unique_set: 35.18
seq = 0..99 * 10
unique_brute_force: 4.36
unique_dict: 2.04
unique_group_by: 4.80
unique_list_comp: 5.06
unique_set: 1.24
seq = 0..99_sorted * 10
unique_brute_force: 4.14
unique_dict: 2.07
unique_group_by: 1.28
unique_list_comp: 4.37
unique_set: 1.25
seq = 0..99 * 100
unique_brute_force: 2665.30
unique_dict: 205.53
unique_group_by: 468.24
unique_list_comp: 514.16
unique_set: 86.11
seq = [l1, l2, l3] * 100
unique_brute_force: 15.10
unique_dict: 15.72
unique_group_by: 19.96
unique_list_comp: 21.93
unique_set: 12.40
seq = [l1, l2, l3]_sorted * 100
unique_brute_force: 14.15
unique_dict: 14.63
unique_group_by: 8.09
unique_list_comp: 18.13
unique_set: 12.25
seq = [l1, l2, l3]_sorted * 1000
unique_brute_force: 152.64
unique_dict: 157.23
unique_group_by: 93.91
unique_list_comp: 195.94
unique_set: 127.70
--
http://www.piotr.dembiński.prv.pl
Filip Wasilewski
> Żebyś wiedział ile razy już się przekonałem jak to z pozoru
> mniej wydajne rozwiązania biją na głowę niezwykle wyszukane
> konstrukcje. W kwestii wydajności ostateczną wyrocznią
> jest praktyka.
Dokładnie.
> A więc zobaczmy:
[...]
>
> def test(fn, seqname, seq):
> t = timeit.Timer("%s(%r)" % (fn, seq), "from __main__ import %s" % fn)
^^^^^^^^^^^^^^^^^
Ten hack ma *niemiłosiernie duży* wpływ na wynik pomiaru, gdyż w
każdej iteracji niepotrzebnie tworzona jest cała sekwencja. Poza tym
compile w timeit.Timer wykłada się (Python 2.4.3, win32) na
>>> timeit.Timer("len(%r)" % range(100000))
Rozwiązanie "na szybko":
def test(fn, seqname, seq):
test.seq = seq
t = timeit.Timer("%s(test.seq)" % (fn, ), "from __main__ import %s,
test" % fn)
print "%20.20s: %5.2f" % (fn, t.timeit(1000))
Zwracam też uwagę na porównywanie ze sobą metod działających
tylko na posortowanych danych wejściowych z metodami opartymi na
funkcjach set i dict.
Poniżej zamieszczam zmodyfikowany test i wyniki z mojego komputera.
Rozwiązanie brute force pomijam. Zmniejszyłem też liczbę iteracji o
rząd, czyli do 4000 (jakiś niecierpliwy jestem;).
Podsumowując, list(set(seq)) oraz [i[0] for i in groupby(l)] są
często wystarczająco dobre dla kolekcji zawierających niewiele
unikalnych elementów, zarówno posortowanych jak i nie. Z drugiej
strony dla kolekcji posortowanych oczywiste jest, że podejścia
sekwencyjne w stylu unique_iter i unique_list_comp będą zawsze lepsze
od rozwiązań bazujących na strukturach haszujących, o ile tylko
zostaną odpowiednio zaimplementowane. Ich dodatkową zaletą jest
również uporządkowanie wyniku w kolejności odpowiadającej
kolejności sekwencji wejściowej.
cheers,
fw
-----8<---unique.py------8<------
import timeit
import string
from itertools import groupby
def unique_list_comp(l):
return [x for i, x in enumerate(l) if i == 0 or x != l[i-1]]
def unique_set(l):
return list(set(l))
def unique_group_by(l):
return [i[0] for i in groupby(l)]
def unique_dict(l):
d = {}
for e in l:
d[e] = None
return d.keys()
def unique_iter(l):
def fun(collection):
it = iter(collection)
prev = it.next()
yield prev
for elem in it:
if elem != prev:
prev = elem
yield prev
return list(fun(l))
def test_all(seqname, seq, n, f=None):
if isinstance(seq, (list, tuple, str, unicode)):
print "\nseq = %s * %d" % (seqname, n)
seq = seq * n
if f:
seq = f(seq)
else:
print "\niter = %s" % (seqname,)
fns = [fn for fn in sorted(globals().keys()) if
fn.startswith("unique_")]
for fn in fns:
test(fn, seqname, seq)
def test(fn, seqname, seq):
test.seq = seq
t = timeit.Timer("%s(test.seq)" % (fn, ), "from __main__ import %s,
test" % fn)
print "%20.20s: %5.2f" % (fn, t.timeit(4000))
if __name__ == "__main__":
import sys
print "python: ", sys.version.split()[0], sys.platform
test_all("ascii_sorted", string.ascii_letters, 10, sorted)
test_all("ascii_sorted", string.ascii_letters, 100, sorted)
test_all("0..9_sorted", range(10), 10, sorted)
test_all("0..99", range(100), 100, sorted)
test_all("0..999_sorted", range(1000), 1)
test_all("0..9999_sorted", range(10000), 1)
test_all("xrange(1000)", xrange(1000), 0)
test_all("xrange(10000)", xrange(10000), 0)
l1 = (string.ascii_lowercase, string.ascii_uppercase,
string.digits)
l2 = (string.ascii_uppercase, string.ascii_lowercase,
string.digits)
l3 = (string.digits, string.ascii_lowercase, string.uppercase)
test_all("[l1, l2, l3]_sorted", [l1, l2, l3], 100, sorted)
test_all("[l1, l2, l3]_sorted", [l1, l2, l3], 1000, sorted)
del unique_list_comp, unique_iter
test_all("[l1, l2, l3]", [l1, l2, l3], 100)
test_all("ascii", string.ascii_letters, 10)
test_all("ascii", string.ascii_letters, 100)
test_all("0..9", range(10), 10)
test_all("0..99", range(100), 100)
-----8<---unique.py------8<------
python: 2.4.3 win32
seq = ascii_sorted * 10
unique_dict: 0.33
unique_group_by: 0.19
unique_iter: 0.36
unique_list_comp: 0.79
unique_set: 0.15
seq = ascii_sorted * 100
unique_dict: 3.05
unique_group_by: 0.86
unique_iter: 2.76
unique_list_comp: 7.61
unique_set: 1.21
seq = 0..9_sorted * 10
unique_dict: 0.07
unique_group_by: 0.04
unique_iter: 0.06
unique_list_comp: 0.15
unique_set: 0.04
seq = 0..99 * 100
unique_dict: 6.09
unique_group_by: 1.61
unique_iter: 4.24
unique_list_comp: 13.42
unique_set: 2.54
seq = 0..999_sorted * 1
unique_dict: 0.81
unique_group_by: 1.62
unique_iter: 0.94
unique_list_comp: 1.66
unique_set: 0.51
seq = 0..9999_sorted * 1
unique_dict: 13.93
unique_group_by: 16.63
unique_iter: 9.51
unique_list_comp: 17.35
unique_set: 10.94
iter = xrange(1000)
unique_dict: 0.97
unique_group_by: 1.68
unique_iter: 0.99
unique_list_comp: 1.90
unique_set: 0.57
iter = xrange(10000)
unique_dict: 14.70
unique_group_by: 16.74
unique_iter: 9.87
unique_list_comp: 19.18
unique_set: 11.48
seq = [l1, l2, l3]_sorted * 100
unique_dict: 0.25
unique_group_by: 0.05
unique_iter: 0.22
unique_list_comp: 0.48
unique_set: 0.15
seq = [l1, l2, l3]_sorted * 1000
unique_dict: 2.45
unique_group_by: 0.44
unique_iter: 2.01
unique_list_comp: 4.81
unique_set: 1.37
seq = [l1, l2, l3] * 100
unique_dict: 0.25
unique_group_by: 0.57
unique_set: 0.15
seq = ascii * 10
unique_dict: 0.36
unique_group_by: 0.87
unique_set: 0.19
seq = ascii * 100
unique_dict: 3.46
unique_group_by: 8.32
unique_set: 1.61
seq = 0..9 * 10
unique_dict: 0.07
unique_group_by: 0.19
unique_set: 0.04
seq = 0..99 * 100
unique_dict: 6.08
unique_group_by: 15.80
unique_set: 2.52
--
Rob Wolfe
>> def test(fn, seqname, seq):
>> t = timeit.Timer("%s(%r)" % (fn, seq), "from __main__ import %s" % fn)
> ^^^^^^^^^^^^^^^^^
>
> Ten hack ma *niemiłosiernie duży* wpływ na wynik pomiaru, gdyż w
> każdej iteracji niepotrzebnie tworzona jest cała sekwencja. Poza tym
> compile w timeit.Timer wykłada się (Python 2.4.3, win32) na
>>>> timeit.Timer("len(%r)" % range(100000))
Fakt. Też mi się to nie podobało. :)
> Rozwiązanie "na szybko":
> def test(fn, seqname, seq):
> test.seq = seq
> t = timeit.Timer("%s(test.seq)" % (fn, ), "from __main__ import %s,
> test" % fn)
> print "%20.20s: %5.2f" % (fn, t.timeit(1000))
>
Działa super. Dzięki.
> Zwracam też uwagę na porównywanie ze sobą metod działających
> tylko na posortowanych danych wejściowych z metodami opartymi na
> funkcjach set i dict.
>
> Poniżej zamieszczam zmodyfikowany test i wyniki z mojego komputera.
> Rozwiązanie brute force pomijam. Zmniejszyłem też liczbę iteracji o
> rząd, czyli do 4000 (jakiś niecierpliwy jestem;).
>
> Podsumowując, list(set(seq)) oraz [i[0] for i in groupby(l)] są
> często wystarczająco dobre dla kolekcji zawierających niewiele
> unikalnych elementów, zarówno posortowanych jak i nie. Z drugiej
> strony dla kolekcji posortowanych oczywiste jest, że podejścia
> sekwencyjne w stylu unique_iter i unique_list_comp będą zawsze lepsze
> od rozwiązań bazujących na strukturach haszujących, o ile tylko
Przy ogromnych sekwencjach pewnie tak, ale przy stosunkowo
niedużych testy na to nie wskazują.
> zostaną odpowiednio zaimplementowane. Ich dodatkową zaletą jest
> również uporządkowanie wyniku w kolejności odpowiadającej
> kolejności sekwencji wejściowej.
Tak, czasami to jest duży plus.
[...]
> python: 2.4.3 win32
[...]
> seq = 0..9999_sorted * 1
> unique_dict: 13.93
> unique_group_by: 16.63
> unique_iter: 9.51
> unique_list_comp: 17.35
> unique_set: 10.94
To mnie zaciekawiło. Teoretycznie set powinien zostać pobity
przez iter przy długiej posortowanej sekwencji tak jak u Ciebie.
Jednak moje wyniki (test z Twoimi poprawkami) są inne:
seq = 0..9999_sorted * 1
unique_dict: 12.94
unique_group_by: 16.74
unique_iter: 11.71
unique_list_comp: 20.03
unique_set: 7.67
seq = 0..99999_sorted * 1
unique_dict: 145.52
unique_group_by: 170.70
unique_iter: 123.07
unique_list_comp: 204.90
unique_set: 93.66
Wiedziałem, że set jest niezły, ale te testy trochę przerastają
moje oczekiwania.
Nawiasem mówiąc ciekawe, że u Ciebie iter zwyciężył.
Czyżby windows nie lubił tablic haszowalnych. :)
--
pozdrawiam
Rob
Filip Wasilewski
> "Filip Wasilewski" <filipwa...@gmail.com> writes:
>
> > Podsumowując, list(set(seq)) oraz [i[0] for i in groupby(l)] są
> > często wystarczająco dobre dla kolekcji zawierających niewiele
> > unikalnych elementów, zarówno posortowanych jak i nie. Z drugiej
> > strony dla kolekcji posortowanych oczywiste jest, że podejścia
> > sekwencyjne w stylu unique_iter i unique_list_comp będą zawsze lepsze
> > od rozwiązań bazujących na strukturach haszujących, o ile tylko
> Przy ogromnych sekwencjach pewnie tak, ale przy stosunkowo
> niedużych testy na to nie wskazują.
... o ile tylko zostaną odpowiednio zaimplementowane. - miałem tutaj
na myśli coś bardziej hardcorowego, czyli implementację
niskopoziomową tak jak dla `set`. Inaczej rzeczywiście bardzo
ciężko przebić dopieszczone algorytmy wbudowane.
Coś w tym musi być. Na linuksie porównywalne czasy uzyskałem dla
sekwencji rzędu 100'000 elementów, ale już dla 150'000 znów było
odwrotnie. Taka trochę loteria.
Aha, wersję z groupby lepiej zapisać w takiej postaci:
def unique_group_by(l):
return [k for k,v in groupby(l)]
Przed użyciem warto też sprawdzić, czy naprawdę działa ona z
kolekcjami nieposortowanymi, żeby przekonać się, że nie do końca
:D
>>> unique_group_by([1,2,3,1,2,3])
[1, 2, 3, 1, 2, 3]
>>> unique_group_by(sorted([1,2,3,1,2,3]))
[1, 2, 3]
cheers,
fw
Rob Wolfe
> Aha, wersję z groupby lepiej zapisać w takiej postaci:
>
> def unique_group_by(l):
> return [k for k,v in groupby(l)]
>
> Przed użyciem warto też sprawdzić, czy naprawdę działa ona z
> kolekcjami nieposortowanymi, żeby przekonać się, że nie do końca
> :D
>
>>>> unique_group_by([1,2,3,1,2,3])
> [1, 2, 3, 1, 2, 3]
>>>> unique_group_by(sorted([1,2,3,1,2,3]))
> [1, 2, 3]
Tak, tak, założenie było, że przy nieposortowanych kolekcjach
ma usuwać tylko elementy sąsiadujące.
>>> unique_group_by([1,1,1,2,3,3,3,1,2,2,2,3])
[1, 2, 3, 1, 2, 3]
--
pozdrawiam
Rob
Marek Pułczyński
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52560
ktorego autorem jest Tim Peters
def unique(s):
"""Return a list of the elements in s, but without duplicates.
For example, unique([1,2,3,1,2,3]) is some permutation of [1,2,3],
unique("abcabc") some permutation of ["a", "b", "c"], and
unique(([1, 2], [2, 3], [1, 2])) some permutation of
[[2, 3], [1, 2]].
For best speed, all sequence elements should be hashable. Then
unique() will usually work in linear time.
If not possible, the sequence elements should enjoy a total
ordering, and if list(s).sort() doesn't raise TypeError it's
assumed that they do enjoy a total ordering. Then unique() will
usually work in O(N*log2(N)) time.
If that's not possible either, the sequence elements must support
equality-testing. Then unique() will usually work in quadratic
time.
"""
n = len(s)
if n == 0:
return []
# Try using a dict first, as that's the fastest and will usually
# work. If it doesn't work, it will usually fail quickly, so it
# usually doesn't cost much to *try* it. It requires that all the
# sequence elements be hashable, and support equality comparison.
u = {}
try:
for x in s:
u[x] = 1
except TypeError:
del u # move on to the next method
else:
return u.keys()
# We can't hash all the elements. Second fastest is to sort,
# which brings the equal elements together; then duplicates are
# easy to weed out in a single pass.
# NOTE: Python's list.sort() was designed to be efficient in the
# presence of many duplicate elements. This isn't true of all
# sort functions in all languages or libraries, so this approach
# is more effective in Python than it may be elsewhere.
try:
t = list(s)
t.sort()
except TypeError:
del t # move on to the next method
else:
assert n > 0
last = t[0]
lasti = i = 1
while i < n:
if t[i] != last:
t[lasti] = last = t[i]
lasti += 1
i += 1
return t[:lasti]
# Brute force is all that's left.
u = []
for x in s:
Rob Wolfe
Marek Pulczynski napisal(a):
> Uzywam tego:
>
> http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52560
Ta receptura powstala przed pojawieniem sie seta, a szczególnie
jego bardzo wydajnej implementacji w wersji 2.4 pythona. Obecnie
czesc powyzszej funkcji, która korzysta ze slownika nalezy
zastapic
wlasnie setem.
Poczytaj komentarze do tej receptury.
--
pozdrawiam
Rob
Piotr Dembiński
[...]
> For best speed, all sequence elements should be hashable. Then
> unique() will usually work in linear time.
Najlepsze jest to, że w przypadku obiektów typu podstawowego
'instance', funkcja mieszająca jest metodą, którą można przedefiniować
i której czas wykonania może być zależny od wielkości rozwiązywanego
problemu 8-)
Piotr Dembiński
[...]
> def unique_group_by(l):
> return [k for k,v in groupby(l)]
>
> Przed użyciem warto też sprawdzić, czy naprawdę działa ona
> z kolekcjami nieposortowanymi, żeby przekonać się, że nie
> do końca :D
unique_list_comp też jest niepoprawne