Eine Variable mit n anderen vergleichen ohne Brute Force

Cybered

Cybered

Admiral Special
Mitglied seit
22.09.2002
Beiträge
1.625
Renomée
14
Standort
Unimatrix-Zero
Ist es unter Java möglich eine Variable (int) mit einer Menge von anderen zu vergleichen, ohne das zu fuß, sprich jeden vergleich einzeln machen zu müßen.

Konkret geht es um ein Lotto programm, was natürlich bei der auswahl der 6 Zahlen keine doppelten anzeigen soll. jetzt kann ich das mit 6 Zahlen ja gerade noch mit der Brute Force methode machen, also alles einzeln testen...aber wenn ich mehr zahlen hab...wie kann man es dann bequem lösen..bin für jeden ansatz dankbar...
thx4all
cybered
 
Was genau meinst Du denn mit "brute force", was hast Du denn bisher als Code?
Normalerweise kannst Du doch die Menge der Möglichkeiten in ein Array packen und dann mit einer for-Schleife einzeln abklappern. Aber vielleicht versteh ich das Problem nicht ganz *noahnung*
 
Worum es genau geht, habe ich auch nicht verstanden. Aber ich glaube, dass die Antwort in Richtung assoziative Container, z.B. Set geht.
 
Nun ja...Brute force bedeutet für mich das "dumme" ausprobieren bzw. in diesem Fall das die eine Variable mit jeder anderen Variable verglichen wird. wenn ich 1000 Variablen habe, muß meine eine mit 999 anderen vergleichen...um zu sehen ob sie doppelt ist.
Nun ja, bei der heutigen Rechnerleistung kein Akt...aber es muß doch die Möglichkeit geben, eine Varable einfacher mit anderen zu vergleichen.
Das mit dem Array stimmt schon...das hab ich ja schon...und jetzt will ich meine "neue" Zufallszahl mit den vorhandenen aus dem Array vergleichen...aber eben nicht jede einzeln...sondern irgendwie...anders *noahnung*
 
Cybered schrieb:
Nun ja...Brute force bedeutet für mich das "dumme" ausprobieren bzw. in diesem Fall das die eine Variable mit jeder anderen Variable verglichen wird. wenn ich 1000 Variablen habe, muß meine eine mit 999 anderen vergleichen...um zu sehen ob sie doppelt ist.
Nun ja, bei der heutigen Rechnerleistung kein Akt...aber es muß doch die Möglichkeit geben, eine Varable einfacher mit anderen zu vergleichen.
Das mit dem Array stimmt schon...das hab ich ja schon...und jetzt will ich meine "neue" Zufallszahl mit den vorhandenen aus dem Array vergleichen...aber eben nicht jede einzeln...sondern irgendwie...anders *noahnung*
Zum Vergrößern anklicken....

Und wie soll das anders gehen, rein konzeptionell gefragt? Du hast X Variablen, und willst wissen, ob die X+1 Variable ein Duplikat einer der vorherigen X Variablen ist. Wie willst du das anders entscheiden, außer die neue Variable mit den X vorherigen zu vergleichen, wenn du nichts über die X Variablen aussagen kannst? Geht nicht, sofern du keine Einschränkungen machen kannst.
 
Wenn ich es richtig verstehe, ist die Lösung ganz einfach, eine sortierte Liste.

Sortiere einfach jede neue Zahl in die Liste z.B. mit Quicksort oder sogar einer Hashtabelle.

Also hier Komplexitätsabschätzungen für jeweils n Elemente (Gesamtabschätzung, nicht pro Element):
1. Fall: Quicksort + binäres Suchen
O(n*logn)
Worst case: O(n²)

2. Fall: Hashtabelle
O(n) ideale Tabelle
Worst case: O(n²), dieser Fall wird aber garantiert nicht auftreten.

3. Lineare Suche (was du als Brute Force bezeichnest ;) )
O(n²)

Ist die Liste klein genug ist das einfachste Verfahren auch am schnellsten und vor allem auch am einfachsten zu implementieren.

Es ist sehr früh, deshalb alle Angaben ohne Gewähr.
 
Zuletzt bearbeitet:
Falls es darum gehen sollte, z.B. dafür zu sorgen, dass jedes Element nur ein Mal vorkommt, drängt sich das Set auf, wie ich bereits geschrieben hatte ;)

In c++ würde das so aussehen:
PHP: 
 // finde 6 unterschiedliche Zahlen, z.B. für 6 aus 49
 set<int> s;

  do {
    // in k wird die nächste gültige Zahl geladen
    int k = getTheNextValidNumber (); 

    s.insert(k);
  }
  while (s.size() < 6);

  // mittels iterator auf s zugreifen

In Java ist der Code ähnlich, ich glaube das insert heisst dort add.
 
Hmmm...also da ich das teil bis mittwoch fertig haben muß, werde ich das ganze erstmal mit der linearen Suche in mein kleines Programm einbauen. Werde aber mal versuchen die anderen Ansätze zumindest zu verstehen...wie ihr sicher merkt steh ich noch relativ weit unten auf der Programmierleiter *buck*

Und was ist falsch daran die lineare Suche als Brute Force zu bezeichnen ???

schon mal danke für alles
Cybered
 
eamC schrieb:
Wenn ich es richtig verstehe, ist die Lösung ganz einfach, eine sortierte Liste.

Sortiere einfach jede neue Zahl in die Liste z.B. mit Quicksort oder sogar einer Hashtabelle.

Also hier Komplexitätsabschätzungen für jeweils n Elemente (Gesamtabschätzung, nicht pro Element):
1. Fall: Quicksort + binäres Suchen
O(n*logn)
Worst case: O(n²)

2. Fall: Hashtabelle
O(n) ideale Tabelle
Worst case: O(n²), dieser Fall wird aber garantiert nicht auftreten.

3. Lineare Suche (was du als Brute Force bezeichnest ;) )
O(n²)

Ist die Liste klein genug ist das einfachste Verfahren auch am schnellsten und vor allem auch am einfachsten zu implementieren.

Es ist sehr früh, deshalb alle Angaben ohne Gewähr.
Zum Vergrößern anklicken....

Ähm, die lineare Suche, also ob ein Element in der Liste ist, läuft linear. Nun vergleich das mal mit den Aufwänden deiner anderen Vorschläge ;).
 
Cybered schrieb:
Und was ist falsch daran die lineare Suche als Brute Force zu bezeichnen ???
Zum Vergrößern anklicken....
Es ist zumindest unüblich. Die lineare Suche wird im Deutschen auch vollständige Suche genannt. Aber den Begriff Brute Force habe ich in dem Zusammenhang noch nie gehört.

Ein unterschwelliges Kriterium des Begriffes "Brute Force" mag sein, dass der Erfolg der Suche in vorgegebener Zeit nicht garantiert ist. Ein Paßwort kann nach bestimmter Zeit geknackt sein, oder ein Schachzug kann richtig berechnet worden sein. Aber es ist trotz "Roher Gewalt" nicht garantiert.
 
i_hasser schrieb:
Ähm, die lineare Suche, also ob ein Element in der Liste ist, läuft linear. Nun vergleich das mal mit den Aufwänden deiner anderen Vorschläge ;).
Zum Vergrößern anklicken....
Die Aufwände sind jeweils für die ganze Liste, nicht für das Prüfen eines Elementes.
Für jedes Element gilt ja:

Binäres Suchen = O(logn)
Hashtabelle ideal = O(1)
Lineares Suchen = O(n)

Und jetzt das Ganze n mal.

Oder meinst Du etwas anderes?

Und was ist falsch daran die lineare Suche als Brute Force zu bezeichnen
Zum Vergrößern anklicken....
Weil Lineares Suchen nicht Brute Force ist. BF ist das genau Umgekehrte, man sucht nach Treffern (Duplikaten) von Zeichen oder Zeichenketten durch "lineares Einsetzen" (also z.B. nach dem Alphabet).
Brute Force hat auch einen nicht-linearen Aufwand.
 
Zuletzt bearbeitet:
Aber er will ja n Elemente in die vorerst leere Liste nacheinander einsetzen und nicht bloß ein Element in eine bereits vorhandene Liste, stehen ich auf dem Schlauch? ;D

Egal wie die Aufwände sind, es ist auf jeden Fall schneller als durch lineares Suchen für große Listen.
Was das "set" angeht, das habe ich bisher noch nicht benutzt, weiß jemand wie das intern funktioniert?

PS: Ist es eine Hausaufgabe oder für private Zwecke?
 
Also so wie ich das sehe wäre ein Baum die Lösung mit dem geringsten Aufwand, einfach zu testen ob die Zahl schon da ist, ist die schnellere Lösung bei so kleinen Bereichen.

Wenn es darum geht das mit n Zahlen zu machen ist der Aufwand natürlich O(n²), bei 'nem Bäumchen wäre es n*logn. Noch schneller wäre es, ein Array zu pflegen, das die Zufallszahlen auf den Bereich mappt. So nach dem Motto beim ersten mal ein Array (bzw. eine Liste) mit l(i)=i für i=1..49, hat man eine Zahl rausgelöscht entfernt man den entprechenden Eintrag in der Liste (oder nimmt ein statisches Array und kopiert um). Die folgende Zufallszahl sollte dann nur noch von 1 bis 48 reichen, die letztendliche Zahl ist dann l. Das wäre, wenn man das Array umkopiert, O(n) (man muss ja die gezogene Zahl nur auf den Platz 49 (bzw. beim 2. mal 48 usw.) tauschen, bei der nächsten Zufallszahl kommt das eh nimmer dran, weil die nur bis 48 geht).
.
EDIT :
.
Sicher nicht. Wenn er eine Liste von n Zufallszahlen in einem Bereich m aufbauen will, in der n ungleiche Zahlen liegen, dann kann das kein konstanter Aufwand sein ;).

Die Variante mit dem Array lauft O(n), wenn es nur darum geht eine Variable hinzuzufügen, läuft die Sache O(1).

zB. so hier in C++:

Code: 
vector<int> list;
int l[]=new int[49];
for(int i=0;i<49;i++) int l[i]=i;

for(int i=0;i<6;i++)
{
  int r=rand()%(49-i);
  list.push_back(l[r]);
  
  int tmp=l[48-i];
  l[48-i]=l[r];
  l[r]=l[48-i]  
}
 
Zuletzt bearbeitet:
Ihr habt in euren hübschen theoretischen Betrachtungen einen Fehler. Wenn hier ein Lotto-Programm gebastelt werden soll, machen sämtliche genannten Versionen die Wahrscheinlichkeiten kaputt. Ihr überlegt, wie eine Zahl nicht doppelt angezeigt werden kann. Richtig wäre, wie eine Zahl nicht doppelt gezogen werden kann. Sie darf in der Ausgangsmenge garnicht mehr vorhanden sein, wenn sie einmal gezogen wurde. Damit erübrigt sich auch jeglicher Vergleich, um doppelte Anzeigen zu verhindern.
 
i_hasser schrieb:
Bei mir wird sie net doppelt gezogen, die Wahrscheinlichkeit bleibt erhalten ;).
Zum Vergrößern anklicken....

Ok, du hast das insofern gleich richtig gemacht. Die ursprünglich Frage bzw. Aufgabenstellung war nur schon inkorrekt. Es ist dabei gar kein Verglich notwendig. Ansonst wäre aber bei insgesamt 6 Variablen eine lineare Suche auch das sinnvollste. Bei einem so kleinen Vergleichsraum überwiegt der Overhead alternativer Methoden (Bäume, Hashing etc.) noch bei weitem die Vergleichsoperationen.
 
Hier mal ne einfache version:

Du verwendest einfach ein Set. In einem Set kann jedes Element (equals liefert true) nur einmal vorkommen. Als Ausprägung kannst du das HashSet nehmen. Das Set liefert eine contains-Methode, mit der du damit sehr schnell (Berechnung des Hashcodes -> check ob vorhanden) testen kannst, ob das Element vorhanden ist oder nicht.

Du kannst das auch für beliebige Objekte anpassen, die du in dem Set speichern willst, indem du in den Objekten die equals und hashcode-Methoden überschreibst.

Damit bist du zeitlich viel besser ( O(1) ) als mit jeder sortierenden Methode (mind. O(nlogn)

Und für lotto:
Du erstellst ein Set und fügst 49 Kugeln ein.
Zum ziehen holst du dir ne Zufallszahl zwischen 1 und Größe des Sets (length-Methode) und nimmst dann dieses Element raus (remove-Methode)
 
Zuletzt bearbeitet:
PuckPoltergeist schrieb:
Ok, du hast das insofern gleich richtig gemacht. Die ursprünglich Frage bzw. Aufgabenstellung war nur schon inkorrekt. Es ist dabei gar kein Verglich notwendig. Ansonst wäre aber bei insgesamt 6 Variablen eine lineare Suche auch das sinnvollste. Bei einem so kleinen Vergleichsraum überwiegt der Overhead alternativer Methoden (Bäume, Hashing etc.) noch bei weitem die Vergleichsoperationen.
Zum Vergrößern anklicken....

Ich würde ja fast wetten, dass meine Methode schneller ist. Wer hat Lust es zu implementieren?
Bei der linearen Suche müssen halt mit einer gewissen Wahrscheinlichkeit mehr als 6 Werte erstellt werten, und es sind 1+2+3+4+5 Vergleiche nötig.
 
i_hasser schrieb:
Ich würde ja fast wetten, dass meine Methode schneller ist. Wer hat Lust es zu implementieren?
Bei der linearen Suche müssen halt mit einer gewissen Wahrscheinlichkeit mehr als 6 Werte erstellt werten, und es sind 1+2+3+4+5 Vergleiche nötig.
Zum Vergrößern anklicken....

Und das hat dann was für einen Sinn? Da werden doch zwei unterschiedliche Sachen miteinander verglichen. Davon abgesehen ist natürlich deine Variante schneller, weil du 6 Kugeln aus 49 ziehst, ohne zurücklegen. Die Alternative wäre 6 Kugeln aus 49 zu ziehen mit zurücklegen + die Vergleich der neu gezogenen Kugel mit den schon vorhandenen. Ist doch logisch, dass letzteres langsamer ist, da ersteres gänzlich ohne Vergleiche auskommt.
 
Achso, das "Bei einem so kleinen Vergleichsraum überwiegt der Overhead alternativer Methoden" war auf Methoden mit Vergleich bezogen - dann ist die Sache natürlich klar.
 
i_hasser schrieb:
Achso, das "Bei einem so kleinen Vergleichsraum überwiegt der Overhead alternativer Methoden" war auf Methoden mit Vergleich bezogen - dann ist die Sache natürlich klar.
Zum Vergrößern anklicken....

Jupp, ich bezog mich darauf, ob man die Daten mit Bäumen oder Hashes sortiert, um dann effizient suchen, einfügen und entfernen zu können, oder ob man linear eine Liste durchstöbert, um dort nach Duplikaten zu forsten.
 
Also meine Lösung sieht wie folgt aus :
Ich erzeuge ein Array...mit 49 Feldern...dort schreibe ich mit einer Schleife alle Möglichkeiten von 1-49 rein.
Jetzt generiere ich eine Zufallszahl aus dem bereich 1-49 und springe diese Position dann im Array an...den Wert des Feldes speichere ich und überschreibe ihn anschliesend mit 0. Falls ich im nächsten Durchlauf (es sind ja 6 Zahlen zu ziehen) auf eine Null treffe probiere ich es erneut..solange bis der Wert != 0 ist ;)
Das ganze in Java ->

Code: 
import java.util.*;
class Lotto3
{
public static void main(String argv[])
	{
	Random zufall = new Random(); //Zufallsgenerator wird geladen
		
	int feld[] = new int[50];    	//Feld mit 49 Spalten 
	int Wert = 0;					//Wert für genutzte Felder
		for (int z=1;z<25;z++)		//Schleife zum Wiederholen
		{	
			System.out.print ("========="); //Trennstriche erzeugen
						
			for (int i=0;i<49;i++)	//Schleife zum Füllen des Feldes
			{ 
				feld [i] = i+1; 	//Feld füllen
			}
			
			for (int i=0;i<6;i++)	//Schleife zum auswählen der 6 Ziffern		
			{	
				System.out.println();		//geänderte Ausgabeform
				int position = feld [zufall.nextInt (49)] ; //Position zufälig auswählen
				int zahl = feld[position]; 	// Zuweisung der Zahl
				if (zahl==0)				//If Schleife zur Prüfung auf Inhalt		
				{
			 		while (zahl == 0)		//Wenn 0 dann neue Zahl raussuchen
					{	
						zahl = feld [zufall.nextInt(49)] ;	//Neue Zahl ermitteln
						feld [position] = Wert;	//Wert im Array mit 0 überschreiben
					}
					System.out.print (" >" + zahl+" ");	//geänderte Zahl markieren
				}
				else
				System.out.print ("  " + zahl + "  ");	//gefundene Zahl ausgeben
				feld [position] = Wert;		//Wert im Array mit 0 überschreiben
				
			}
			System.out.println ();	//Zeilenvorschub
		}
	}
}

Gruß
Cybered
 
Cybered schrieb:
Also meine Lösung sieht wie folgt aus :
Ich erzeuge ein Array...mit 49 Feldern...dort schreibe ich mit einer Schleife alle Möglichkeiten von 1-49 rein.
Jetzt generiere ich eine Zufallszahl aus dem bereich 1-49 und springe diese Position dann im Array an...den Wert des Feldes speichere ich und überschreibe ihn anschliesend mit 0. Falls ich im nächsten Durchlauf (es sind ja 6 Zahlen zu ziehen) auf eine Null treffe probiere ich es erneut..solange bis der Wert != 0 ist ;)
Zum Vergrößern anklicken....

Das ist aber eine Implementierung mit zurücklegen, was die Wahrscheinlichkeiten betrifft. Lotto arbeitet meines Wissens ohne zurücklegen.
 

Ähnliche Themen

bundymania
[Bundymania User Review] QPAD 8K Pro Gaming Laser Mouse
Antworten
0
Aufrufe
1K
bundymania
bundymania
heikosch
mITX-Gehäuse: Inter-Tech Q-6 & E-i7
Antworten
0
Aufrufe
34K
heikosch
heikosch
nazgul99
Arctic MC101: Erfahrungen unter Linux, Vergleich mit Llano A8-3850
2
Antworten
29
Aufrufe
13K
David64
David64
D
User Test - LG 23ET83V-W
Antworten
6
Aufrufe
3K
Danielduesentrieb
D
soulpain
Acer Iconia B1-A71
Antworten
0
Aufrufe
19K
soulpain
soulpain
Zurück
Oben Unten