En fråga om random och sortering i Python

[ZerQ]

Hejsan

Jag sitter och leker med ett program men har en övergripande fråga om hur man bäst angriper ett problem.

Problemet: Jag har kör random.randrange och slumpar fram ett x antal integer tal som jag vill inte skall bli samma. Hur angriper man bäst att skanna efter likadana nummer?

Jag har 2 vägar att gå, Det ena är att köra klart en seq av tal och sedan gå igenom hela listan steg för steg, det andra är att börja jämföra talen redan när man skapar dom.

Vilket sätt är bäst att ordna detta?

[micke_nordin]

Vad gör du med talen? Om du sparar dem i en array är det ju trivialt att kolla igenom arrayen och se efter om talet finns där redan innan du sparar det.

/Micke

[Substrata]

Enklast är nog att lagra dem i ett set, som ju inte tillåter dubbletter.

Om du använder en vanlig array gissar jag att tidskomplexiteten trots allt är O(n²) i båda fallen eftersom du stegar igenom alla poster för varje post. Vill du få bättre resultat behöver du hålla datat sorterat, exempelvis genom binära sökträd, och jag förmodar att Pythons set gör just något liknande.

En annan metod, om applicerbar, är att använda godtyckligt stora heltal för att flagga vilka tal som är tagna. Givet ett slumptal m så testar du gentemot bit m i heltalet innan du går vidare.

[cthulhu]

Sitter sjalv och liker lite med python, men min erfarenhet fran C++ dar jag pysslat med just mycket slumptal och faktiskt hade en bug som uppstod av att jag hade tva identiska slumptal, vilket skedde ca var 10^15 gang, eftersom en double lagras i 52 bitar, dvs. 2^52 = 10^15 = 1 000 000 000 000 000 ggr innan jag far tva identiska tal, i snitt. Nu funkar ju inte python lika dant, eftersom man inte initierar dem pa samma satt som i C (med double/float/integer), men detta ger i alla fall en vink om att det inte hande sarskilt ofta.

[David Andersson]

Problemet: Jag har kör random.randrange och slumpar fram ett x antal integer tal som jag vill inte skall bli samma. Hur angriper man bäst att skanna efter likadana nummer?

Nu vet jag inte alla förutsättningar, men om x också är antalet tillåtna värden på slumptalen (största slumptal - minsta slumptal + 1 = x = listans längd), så borde random.shuffle vara effektivast.

Kod: Markera allt

lista = range(10)
random.shuffle(lista)
print lista