Algoritumus pro ověření unikátnosti záznamů v poli – Python – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Anonymní uživatel
~ Anonymní uživatel
0 příspěvků
24. 12. 2007   #1
-
0
-

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.

Nahlásit jako SPAM
IP: 88.102.249.–
Reklama
Reklama
Blujacker
~ Moderátor
0
Grafoman
24. 12. 2007   #2
-
0
-

co tohle?



>>> pole=[1,2,3,4,5,5]
>>> for prvek in pole:
if pole.count(prvek) > 1:
print "unikatnost porusena",prvek

Nahlásit jako SPAM
IP: 213.220.226.–
Navštivte server Matematika pro každého
Najdete zde články zabývající se matematikou základních a středních škol a databázi hlavolamů.
Pro vyzkoušení Vaš
Blujacker
~ Moderátor
0
Grafoman
24. 12. 2007   #3
-
0
-

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

Nahlásit jako SPAM
IP: 213.220.226.–
Navštivte server Matematika pro každého
Najdete zde články zabývající se matematikou základních a středních škol a databázi hlavolamů.
Pro vyzkoušení Vaš
Osiris
~ Anonymní uživatel
120 příspěvků
24. 12. 2007   #4
-
0
-

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 :-)

Nahlásit jako SPAM
IP: 85.70.130.–
stibi0
Návštěvník
24. 12. 2007   #5
-
0
-

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 :)

Nahlásit jako SPAM
IP: 88.102.249.–
už mám taky blogísek :) http://www.stibi.org/blog
stibi0
Návštěvník
24. 12. 2007   #6
-
0
-

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

Nahlásit jako SPAM
IP: 88.102.249.–
už mám taky blogísek :) http://www.stibi.org/blog
Osiris
~ Anonymní uživatel
120 příspěvků
25. 12. 2007   #7
-
0
-

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)


Samozřejmě můžeš použít i jinou strukturu (binární vyhledávací strom), ale časová složitost pak bude větší. Je klíčové, že u hashovací tabulky trvá Find i Insert konstantní čas.

Nahlásit jako SPAM
IP: 85.70.130.–
stibi0
Návštěvník
25. 12. 2007   #8
-
0
-

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

Nahlásit jako SPAM
IP: 88.102.249.–
už mám taky blogísek :) http://www.stibi.org/blog
stibi0
Návštěvník
25. 12. 2007   #9
-
0
-

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'

Nahlásit jako SPAM
IP: 88.102.249.–
už mám taky blogísek :) http://www.stibi.org/blog
Blujacker
~ Moderátor
0
Grafoman
25. 12. 2007   #10
-
0
-

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

Nahlásit jako SPAM
IP: 213.220.226.–
Navštivte server Matematika pro každého
Najdete zde články zabývající se matematikou základních a středních škol a databázi hlavolamů.
Pro vyzkoušení Vaš
stibi0
Návštěvník
25. 12. 2007   #11
-
0
-

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

Nahlásit jako SPAM
IP: 88.102.249.–
už mám taky blogísek :) http://www.stibi.org/blog
Osiris
~ Anonymní uživatel
120 příspěvků
25. 12. 2007   #12
-
0
-

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.

Nahlásit jako SPAM
IP: 85.70.130.–
geon0
Grafoman
25. 12. 2007   #13
-
0
-

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

Nahlásit jako SPAM
IP: 83.69.40.–
geon. volume doprava.
Tom@sQo0
Stálý člen
26. 12. 2007   #14
-
0
-

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...

Nahlásit jako SPAM
IP: 88.212.23.–
Tom@sQo
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 20 hostů

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý