BinarySearch langsamer als LinearSearch? kann nicht sein

[borgetas]

Hallo,

ich muss die Methoden binarySearch und linearSearch für Arrays implementieren. Das habe ich so gemacht:

public static int linearSearch(Produkt key) { //Produkt ist eine selbst erstellte Klasse
		Produkt[] a = null;
		if (sarray == null) {
			a = benchmark(); //benchmark erstellt ein Array, falls kein von binarySearch erstellt wurde
			sarray = a;
		} else {
			a = sarray;
		}
		for (int i = 0; i < a.length; i++) {
			if (key.equal(a[i])) //equal vergleicht Elemente der Klasse Produkt
				return i;

		}
		return -1;//falls nicht vorhanden
	}

	public static int binarySearch(Sortable key) {
		Sortable[] a = null;
		if (sarray == null) {
			a = benchmark(); //benchmark erstellt ein Array, falls kein von linear Search erstellt wurde
			sarray = a;
		} else {
			a = sarray;
	
		}	
		quickSort(a); //array sortieren
		int first = 0;
		int upto = a.length;
		while (first < upto) {
			int mid = (first + upto) / 2;
			if (key.less(a[mid])) {
				upto = mid;
			} else if (key.greater(a[mid])) { //greater vergleicht Elemente der Klasse Produkt
				first = mid + 1;
			} else {
				return mid;
			}
		}
		return -1;
	}

Jetzt wenn ich für den gleichen Elementen mit beiden Suchoptionen suche, und die Zeit vergleiche ist linearSearch deutlich schneller. Wie kann das sein? BinarySearch sollte doch viel effizienter sein.

Danke im vorraus

 

[XHelp]

Wie sieht denn deine Zeitmessung dazu aus? Auf welcher größe probierst du es? Und in den Methoden passiert vieles, was da überhaupt nicht reingehört: erstellen eines Arrays, sortieren eines Arrays etc, das verfälscht natürlich die Zeitmessung.

 

[Marco13]

Hmja, speziell das Array zu sortieren, um dann mit dem "schnelleren" binarySearch arbeiten zu können, beißt sich irgendwie

 

[gassst]

Dämliche Schlussfolgerung; natürlich ist deine binarySearch methode langsamer, du sortierst ja auch dadrin.

 

[borgetas]

Ok, danke, ich werde das array vorher sortieren und dann probieren.

 

[borgetas]

Vielen Dank, war wirklich dumm von mir.
Problem gelöst.

 

[Marco13]

Du solltest trotzdem genau überlegen (und/oder posten) wie du die konkrete Zeitmessung machst. Wer mißt, mißt Mist

 

[borgetas]

Mit System.currentTimeMillis(); messe ich die Zeit bevor ich die Methode aufrufe, dann danach, und die Rechenzeit ist dann die Differenz der beiden.
Natürlich probiere ich für ganz viele Suchvorgange, ich suche für 2000 Elemente, nur danach gebe ich die Zeit aus.

 

[Marco13]

Ja, diese "vielen Durchläufe" sind wichtig, und besonders beim Suchen auch, dass nach vielen verschiedenen Elementen gesucht wird (besonders deutlich wird's eben, wenn man z.B. immer nach dem ersten oder letzten Element sucht). System.nanoTime() könnte noch etwas genauer sein, aber darauf sollte es nicht ankommen....