[Spofity]

Mam problem na #codewars #python może miał ktoś podobnie.

Mianowicie zadanie poelga na tym, że by znaleźć unikalną wartość w liscie
No i testy mi przechodzi prawidłowo, ale jak dam Attempt to jest błąd "Execution Timed Out", czyli coś jakby nieskoczona pętla czy coś, a to niemożliwe chyba. Mój kod:

def find_uniq(arr):
 for n in arr:
 if arr.count(n) == 1:
 return n # n: unique integer in the array
 return None

#programowanie #naukaprogramowania

[Spofity]

@Spofity: sorry, zapomniałem że to wykop: https://pastebin.com/VhikNhGP

[Makurise]

@Spofity: To nie oznacza nieskończonej pętli, tylko zbyt wolne działanie algorytmu względem oczekiwań testu

[L.....k]

Po prostu rozwiązanie jest nieefektywne i leci timeout na jakiejs bardzo duzej liscie

[bm9pY2h1ag]

@Spofity: bo masz bardzo wolny algorytm

[eovenn]

@Spofity: musisz przyśpieszyć działanie algorytmu.

[573188224813358837318]

@Spofity: Przy każdym kroku pętli for spwrawdzasz tablicę metodą count(), która też leci po całej liście, w ten sposób masz złożonością obliczeniową O(n2). Spróbuj znaleźć takie rozwiązanie, które nie będzie używało metody count.

[Spofity]

@Makurise: @Lunatik: @bm9pY2h1ag: @eovenn: @573188224813358837318: dzięki wszystkim, mieliście rację. Zamieniłem listę na set (czyli usunąłem zduplikowane wartości) i wtedy sprawdzałem ile razy każdy element setu pojawia się w liscie
Tak to wygląda teraz i przeszło od razu: https://pastebin.com/rn6MsZGb

Jak można by to ogarnąć jeszcze szybciej?

[bm9pY2h1ag]

@Spofity: już masz złożoność O(n) z tego co widzę, lepiej nie będzie

[L.....k]

@bm9pY2h1ag: Żadne O(n), przecież dalej odpala .count() na kazdym elemencie z seta

[bm9pY2h1ag]

@Lunatik: no a jaką złożoność ma count? n * 1 = n

[bm9pY2h1ag]

@Spofity: ale chwila, w secie czasem nie zawsze będzie count 1? jeśli w ogóle istenieje taka metoda? xd

[L.....k]

@bm9pY2h1ag: Jest to złożoność O(n * m) gdzie dla odpowiednio dużego m mamy O(n**2)
Poza tym wczytaj się w kod, on iteruje po unikalnych wartościach z seta, i woła count na oryginalnej niezmienionej liście. Ot całe przyśpieszenie względem oryginalnej metody

[Spofity]

on iteruje po unikalnych wartościach z seta, i woła count na oryginalnej niezmienionej liście. Ot całe przyśpieszenie względem oryginalnej metody

@Lunatik: @bm9pY2h1ag: otóż to

[ProfesorBigos]

@Spofity: @zarev: Da się chyba w O(n) korzystając z tego, że słowniki dodają i usuwają elementy w O(1).

def find_uniq(arr):
....oberved = dict()
....unique = dict()
....for element in arr:
........if element not in oberved:
............unique[element] = None
........else:
............unique.pop(element, None)
........oberved[element] = None
....for element in unique:
........return element
....return None

[ProfesorBigos]

przecież dokładnie to samo napisałem wyżej tylko zamiast dict użyłem set? ( ͡° ͜ʖ ͡°)

@zarev: Tak wiem, nie doczytałem, zauważyłem już po dodaniu mojego komentarza. Ale po przeczytaniu widzę u ciebie błędy. Pierwszy taki, że zwracasz None gdy w sekwencji jest więcej niż jeden unikalny element. A drugi, że set nie trzyma kolejności, więc gdy unikalnych będzie więcej niż jeden element, to nie ma gwarancji zwrócenia

[Hauleth]

@ProfesorBigos: @zarev: z treści wstawionej przez OPa można wywnioskować, że będzie tylko jedna liczba, która nie jest unikatem. Wtedy wystarczy XOR na wszystkich elementach listy i zwrócić wynik (zakładając, że wszystkie liczby są rożne od zera).