# Vier Stellen Keine Doppelt (Zufall)



## CeadeS (7. Jun 2006)

Hallo und Gute Nacht,  :lol: 
Wie im Titel beschrieben sitze ich jetzt schon bereits mehrere Tage an einem Problem. :### 
Ich möchte gerne eine Zufallszahl erstellen mit 4 Stellen und 10 Ziffern, welche jedoch nicht doppelt vorkommen dürfen. Sprich 1467 und nicht 1417. 
Ich habe mir bereits ein Verfahren ausgedacht welches mit Vertauschung arbeitet.
Ich generiere ein Array welches so Aussieht:

0|1|2|3|4|5|6|7|8|9

Nun Vertausche ich die Stellen mit einer Zufallszahl an jeder einzelnen Stelle.
Das Heißt:

0|1|2|3|4|5|6|7|8|9

Zufallszahl :3 also

2|1|0|3|4|5|6|7|8|9

Als nächstes z.B. Zufallszahl :7 also

2|1|6|3|4|5|0|7|8|9

Dies Ziehe ich nun bis zur letzten STelle durch und nehme die ersten oder letzten 4 Ziffern und speichere sie in meine Zahl ab.

Kennt irgendjemand vielleicht einen Weg, dies noch Effizienter durchführen zu können?

Hier die Vertauschung:

```
public class Zufall{
  public static void main(String[] args){
    int[] zahlen={0,1,2,3,4,5,6,7,8,9};
    // jetzt mischen, jede darf einmal
    for(int i=0; i<10; ++i){
      int j=(int)(Math.random()*10);
      int schieben=zahlen[i];
      zahlen[i]=zahlen[j];
      zahlen[j]=schieben;
    }
```
Ich glaube das dies nicht die effizienteste Methode ist und frage deshalb einmal in diesem Forum nach.
Ich möchte den Kürzesten und unaufwändigsten Code haben- *Zwang*   
Gruß


----------



## Wildcard (7. Jun 2006)

Also am einfachsten geht's IMO so:

```
List<Integer> digitList = new ArrayList<Integer>();
		for(int i=0;i<10;i++)
			digitList.add(i);
		Collections.shuffle(digitList);
		for(int i=0;i<4;i++)
			System.out.print(digitList.get(i));
```
Wenn's um Performance geht hat man entweder die Wahl verwendete Zahlen aus der Auswahl zu entfernen, oder beim ziehen zu prüfen ob die Zahl schon gezogen wurde und evtl. neu ziehen. Was performanter ist hängt von der Anzahl der vorhandenen Zeichen und der Länge der gewünschten Ausgabe ab.


----------



## CeadeS (7. Jun 2006)

Danke danke mein Prog is um ganze 3 Sekunden schneller geworden. :lol:  :lol:  :applaus: 
[schild=6 fontcolor=000000 shadowcolor=C0C0C0 shieldshadow=1]java-forum.org 4 the Win[/schild]


----------



## Wildcard (7. Jun 2006)

Freut mich ja das ich helfen konnte, aber wenn du das öfter ausführst und es um Performance geht hast du hoffentlich nicht meinen Code verwendet! Sag bitte das nicht  :lol:


----------



## RaoulDuke (7. Jun 2006)

Also wenn ich die beiden Codeschnipsel ausführe und die Ausführungszeit messe, dann ist die erste Lösung etwa um den Faktor 10 schneller als zweite Lösung.


----------



## Wildcard (7. Jun 2006)

Na auf den Test bin ich gespannt  :lol: 
Du hast auch sicher die Laufzeitoptimierung des JiT Compilers berücksichtigt?  :wink: 
Zeig doch bitte mal deinen Testcode


----------



## RaoulDuke (7. Jun 2006)

Ich hab einfach nur vorher und hinterher System.nanoTime() aufgerufen und die Differenz der Werte genommen. Das gibt bei beliebig häufigen aufrufen immer das ergebniss das der erste Codeschnipsel schneller fertig ist. Daher nehme ich einfach mal ganz naiv an das die erste Routine auch wirklich schneller arbeitet.


----------



## Wildcard (7. Jun 2006)

Ich hab ehrlich gesagt keine Ahnung welche schneller ist da ich's nicht versucht habe, und ich ja auch nur eine einfache und nicht eine schnelle Methode geposted habe.
Tatsache ist aber das solche Messungen niemals genau und oftmals völlig falsch sind.
Da der JiT Compiler ständig zur Laufzeit optimiert und der Ausgangscode unter Umständen nicht mehr viel mit dem Original zu tun hat sind solche Aussagen sehr schwierig zu treffen.


----------



## RaoulDuke (7. Jun 2006)

Ich habs mal durch den Netbeans Profiler laufen lassen.

Version 1 braucht bei mir ca 0.6ms. 

Bei Version 2 gehen alleine schon ~2,5ms drauf weil jeder der 10 "digitList.add(i)" ein Objekt vom Typ Integer erzeugt. Und ~1,2ms verbraucht der Classloader noch für irgendwas.

Denke nicht das sich das durch irgendwelchen Compileroptimierungen beheben lässt. Version 1 arbeitet komplett mit primitiven Datentypen und erzeugt nicht irgendwelche Objekte. War eigentlich zu erwarten das es schneller ist.

Version 1 wird übrigens nochmal um Faktor 10 schneller wenn man die Variablen i,j und schieben schon vor der Schleife Deklariert.


----------



## byte (7. Jun 2006)

Der Compiler optimiert auch nicht "ständig". Nach ein paar Durchläufen ändert sich da nix mehr bei solch kurzen Snippets.

Und das Arrays performanter sind als Collections, sollte eigentlich bekannt sein.


----------



## RaoulDuke (7. Jun 2006)

Hab die Snipplets jetzt nochmal 1000 mal hintereinander laufen lassen, dann ändert sich das Verhältnis etwas.

Version 1 braucht 43ms, Version 2 braucht 78ms und Version 1 mit Variablen ausserhalb der Schleife deklariert braucht insgesamt 29ms.

Scheinbar wurde es doch etwas optimiert bei den vielen Durchläufen, macht aber immernoch nen deutlichen Unterschied.


----------



## Wildcard (7. Jun 2006)

Um mal zu zeigen wie extrem aussagekräftig das ist (mit faktor 10 und so...)  :roll: 

```
public class Randomzahl
{
	
	static StringBuilder builder;
	static Random random = new Random();
	
	
	public static String methode1()
	{
		int[] zahlen={0,1,2,3,4,5,6,7,8,9};
	    // jetzt mischen, jede darf einmal
	    for(int i=0; i<10; ++i){
	      int j=(int)(Math.random()*10);
	      int schieben=zahlen[i];
	      zahlen[i]=zahlen[j];
	      zahlen[j]=schieben;
	    }
	    builder = new StringBuilder();
	    for(int i=0;i<4;i++)
	    	builder.append(zahlen[i]);
	    //System.out.println(builder.toString());
	    return builder.toString();
	}
	
	public static String methode2()
	{
		List<Integer> digitList = new ArrayList<Integer>();
		for(int i=0;i<10;i++)
			digitList.add(i);
		Collections.shuffle(digitList);
		builder = new StringBuilder();
		for(int i=0;i<4;i++)
			builder.append(digitList.get(i));
		//System.out.println(builder.toString());
		return builder.toString();
	}
	
	public static String methode3()
	{
		int[] zahlen={0,1,2,3,4,5,6,7,8,9};
		int zahl;
		int counter=0;
		int number;
		builder = new StringBuilder();
		while(counter<4)
		{
			number=random.nextInt(10);
			zahl = zahlen[number];
			if(zahl>-1)
			{
				builder.append(zahl);
				zahlen[number]=-1;
				counter++;
			}
		}
		//System.out.println(builder.toString());
		return builder.toString();
	}
	
	public static void main(String[] args)
	{
		long time1 = System.nanoTime();
		for(int i=0;i<100000;i++)
			methode1();
		long time2 = System.nanoTime();
		long time3 = System.nanoTime();
		for(int i=0;i<100000;i++)
			methode2();
		long time4 = System.nanoTime();
		long time5 = System.nanoTime();
		for(int i=0;i<100000;i++)
			methode3();
		long time6 = System.nanoTime();
		System.out.println(time2-time1);
		System.out.println(time4-time3);
		System.out.println(time6-time5);
	}
}
```
ausgabe:

```
235774938
300535683
86306500
```


----------



## RaoulDuke (7. Jun 2006)

Das der Faktor 10 bei 1000 Durchläufen nicht zutrifft habe ich ja auch gerade geschrieben. Bei einem einzigen Durchlauf passt er aber ganz gut.


----------



## Wildcard (7. Jun 2006)

Ein Durchlauf ist nichts. überhaupt nichts. Da ist die Systemzeit überhauptnicht genau genug
Und wenn da irgendwo bspw. ein print drinsteht kannst du den Rest der Messung sowieso vergessen.


----------



## RaoulDuke (7. Jun 2006)

Wenn die Systemzeit zu ungenau wäre, dann hätte ich nicht jedes mal mit Abweichung +/- 10% die gleichen Werte?

Und die prints habe ich genau aus dem Grund bei meinen Messungen aussen vor gelassen.


----------



## Wildcard (7. Jun 2006)

> This method provides nanosecond precision, but not
> * necessarily nanosecond accuracy. No guarantees are made about
> * how frequently values change.


----------



## RaoulDuke (7. Jun 2006)

Das es ungenau ist habe ich ja garnicht angezweifelt. Aber es ist offenbar genau genug für diesen Zweck, sonst hätte ich keine halbwegs reproduzierbaren Ergebnisse.

Ausserdem hab ich für die letzteren Tests nicht mit den Nanosekunden gearbeitet, sondern den Netbeans Profiler genommen. Ich unterstelle einfach mal das der halbwegs genau messen kann. Und die Messunterschiede waren reproduzierbar im Bereich mehrerer Millisekunden.


----------



## Wildcard (7. Jun 2006)

Es steht ja wohl ausser Frage das die Messung je länger sie dauert akurater wird.
Und wie du siehst sind die Unterschiede minimal (zumindest bei den beiden ersten Methoden).
Zum vergleich nach 10 Millionen durchläufen:

```
21096391581
29166956135
8745036590
```


----------



## byte (8. Jun 2006)

Sonst glaubt ihrs offenbar nicht: :roll:



> Use raw arrays in preference to collections to improve performance.


----------



## RaoulDuke (8. Jun 2006)

Wildcard hat gesagt.:
			
		

> Es steht ja wohl ausser Frage das die Messung je länger sie dauert akurater wird.
> Und wie du siehst sind die Unterschiede minimal (zumindest bei den beiden ersten Methoden).
> Zum vergleich nach 10 Millionen durchläufen:
> 
> ...



Sicher, haste recht. Bei vielen Durchläufen bin ich ja auch zu keinen anderen Ergebnissen gekommen. Da greift aber wie du schon sagtest sicherlich die automatische Optimierung, mich interessierte aber auch wie schnell der Code bei einer Erstausführung unoptimiert läuft. Und mit mehreren Durchläufen ist es nunmal nicht möglich die unoptimierte Ausführungszeit zu messen, oder kann man die Optimierung irgendwo zu Testzwecken abstellen?


----------



## Wildcard (8. Jun 2006)

RaoulDuke hat gesagt.:
			
		

> kann man die Optimierung irgendwo zu Testzwecken abstellen?


Keine Ahnung. Rein interessehalber: sag bescheid wenn du dementsprechend was findest  

_Edit Illuvatar, 9.6. 23:17: Getrolle abgetrennt nach da_


----------

