Algoritumus pro ověření unikátnosti záznamů v poli – Python – Fórum – Programujte.com

Zdravím, ze všeho nejdřív chci popřát krásné Vánoce.

Kdyby jste si mezi užíváním si klidu, našli chvilku pro nápovědu k mému problému, byl bych vděčný.
Zajímal by mě optimální algoritmus, pomocí kterého zjistím, zdali každá položka v poli je unikátní, že se v tom jednom poli neopakuje.
Nemusí to být přímo hotové řešení v Pythonu, postačí mi i teoretické řešení.

Děkuji velice.

co tohle?

>>> pole=[1,2,3,4,5,5]

>>> for prvek in pole:

	if pole.count(prvek) > 1:

		print "unikatnost porusena",prvek

ale tak mě napadá že to co jsem napsal asi není nejoptimálnější řešení. Záleží na tom jak vlastně funguje funkce count . Možná by bylo rychlejší toto:

>>> pole=[1,2,3,4,5,5]

>>> s=[]

>>> for prvek in pole:

	if prvek not in s:s.append(prvek)



	

>>> if len(s) != len(pole):print"unikatnost porusena"



unikatnost porusena

Výše uvedená řešení rozhodně nejsou optimální.

Blujacker - count si myslím funguje v O(n), takže je ten čas O(n*n)
to druhé řešení má také stejnou kvadratickou časovou složitost - insert do pole může trvat O(n).

Jde to v lineárním čase (čili není potřeba ani prvky třídit).

1) Vytvoř si hashovací tabulku
2) Postupně do ní insertuj hodnoty
3) Pokud nastane kolize, tak skonči, obsahuje 2 stejné hodnoty
4) Pokud si vložil všechny hodnoty, tak jsou různé.

Insert do hashovací tabulky trvá O(1), celkem to trvá tedy O(n), což je nádhera :-)

Onen anonymní dotaz je můj, nevšiml jsem si, že nejsem přihlášený.
Jenom co jsem do dopsal, trklo mě použití count ...
Díky osirisovi za tip, zkusím, snad to dám dohromady :)

To Osiris : hashovací tabulkou myslíš pythonovksý dict ? Není mi jasné, jak chceš v tomto případě ohlídat kolizi vkládaných dat :(

To stibi :
No já napsal teoretický řešení. Dict (pokud je to hashovací tabulka), tak musí mít Find/Insert, ne?

Napíšu ti to v pseudokódu, v Pythonu bohužel neprogramuji:

h <= new hash table

for each prvek in pole:

   if h.Find(prvek) then return false

			      else h.Insert(prvek)

Osiris: už chápu, díky, později sem pastnu hotové řešení kdyby to někdo potřeboval.

No tak zrovna elegantně jsem to nevyřešil .. ale funguje to, nedařilo se mi ukončit skript hned když zjistil že v dočasném poli už hodnota existuje, pořád mi to ta pravdivostní podmínka vyhodnocovala jinak než by měla :(

def check_unique(data):

	temp = []

	for x in data:

		if x in temp:

			pass

		else:

			temp.append(x)

			

	if len(data) == len(temp):

		return True

	else:

		return False

	

	

pole = [1,2,3,4,5]



if check_unique(pole):

	print 'ok'

else:

	print 'duplicita'

To stibi : není tohle náhodou úplně to stejný co jsem psal já???

Blujacker: ou, tak to je pěkné faux pas ..jo, přesně to stejné :)

To stibi :

No právě je nutné využít tu hashovací tabulku. Tohle není optimální, nicméně pro normální použití je to dobré.
Pokud ta pole budou mít miliony prvků, tak je ale rozhodně nutné udělat to pomocí té hashovací tabulky.

jasně. Jen to přeložím: hashovací tabulka == slovník. Dobré cvičení na metody slovníku ;-)

ahoj,
mozno pomoze kusok pokecu okolo toho:
http://cs.wikipedia.org/wiki/Hashovací_tabulka
pre lepsiu predstavu, Hashovacia funkcia je napriklad cislo % 255 :-)
pre programatorov v c++ -> ten slovnik v pythone je tusim to iste ako (hash_)map v c++
to carovne O(nieco) a podobne je vlastne asymtoticka zlozitost(skuste google),
napr. O(n) hovori, ze kolkokrat viac prvkov mas, tolkokrat nejaka akcia dlhsie trva... O(n*n) znamena ze napr. ak zvysis pocet prvkov 2 krat, tak sa cela funkcia budevykonavat 4 krat dlhsie....O(1) znamena, ze sa bude vykonavat v rovnakom=konstantnom case nezavisle od toho, kolko prvkov to ma ;-) -> preto je dobra hash_mapa, ktora vsetko vykonava v konstatntnom kratkom case...