Zum Inhalt
wannacode

Lineare Suche

Kurz gesagt: Die lineare Suche prüft die Elemente nacheinander, bis sie das gesuchte findet oder am Ende ankommt: O(n) Vergleiche, und sie funktioniert auch mit einer unsortierten Liste.

Problem

Der Scanner im Lager

Im Lager stehen die Produkte in einer Liste, in der Reihenfolge, in der sie angekommen sind: das Mehl vom Montag, der Zucker vom Dienstag, das Öl, der Reis. Ein Mitarbeiter scannt eine Kiste, und das Programm muss das Produkt anhand seines Barcodes finden:

List<Product> shelf = List.of(
    new Product("3800200101112", "Mehl"),
    new Product("3800200104403", "Zucker"),
    new Product("3800200107251", "Öl"),
    new Product("3800200102690", "Reis"),
    new Product("3800200109958", "Salz"),
    new Product("3800200105837", "Kaffee"));

Die Barcodes sind nicht sortiert. Du kannst die Liste nicht in der Mitte aufschlagen und sagen „der Reis ist weiter hinten“: Der nächste Barcode kann alles sein. Wie findest du das Produkt, und was kostet es bei 50.000 Produkten und 2000 Scans am Tag?

Die Idee

Du schaust in jede Kiste

Da die Reihenfolge nicht hilft, bleibt nur eins: Du beginnst bei der ersten Kiste und vergleichst ihren Barcode mit dem gesuchten. Passt er, bist du fertig: Du gibst den Platz zurück. Wenn nicht, gehst du zur nächsten. Wenn die Kisten zu Ende sind, ist das Produkt nicht da.

Das ist die lineare Suche: Du gehst die Elemente nacheinander durch, bis du das gesuchte findest oder am Ende ankommst. Sie liefert den Platz (den Index) oder ein Zeichen für „nicht da“: -1, weil es keinen Platz -1 gibt.

Sieh es dir an

Der Zeiger am Regal

static int find(List<Product> shelf, String barcode) {
    for (int i = 0; i < shelf.size(); i++) {
        if (shelf.get(i).barcode().equals(barcode)) {
            return i;
        }
    }
    return -1;
}
int rice = find(shelf, "3800200102690");
System.out.println("3800200102690 -> " + rice + " " + shelf.get(rice).name());
System.out.println("3800200100000 -> " + find(shelf, "3800200100000"));
Ausgabe
3800200102690 -> 3 Reis
3800200100000 -> -1

static int find(List<Product> shelf, String barcode) {
    for (int i = 0; i < shelf.size(); i++) {
        if (shelf.get(i).barcode().equals(barcode)) {
            return i;
        }
    }
    return -1;
}


int rice = find(shelf, "3800200102690");
int missing = find(shelf, "3800200100000");
Schritt für Schritt, in Worten
  1. Der Scanner liest den Barcode des Reises: 3800200102690. find beginnt bei der ersten Kiste.
  2. Er vergleicht den Barcode jeder Kiste mit dem gesuchten: mehl, zucker, öl. Kein Treffer.
  3. Die vierte Kiste ist der Reis. return 3: gefunden nach 4 Vergleichen.
  4. Ein Barcode, den das Lager nicht hat: 3800200100000. find beginnt wieder von vorn.
  5. Der Zeiger geht an jeder Kiste vorbei, und keine passt.
  6. Die Kisten sind zu Ende: return -1 nach 6 Vergleichen. Ein fehlendes Produkt ist der schlechteste Fall: n Vergleiche bei n Kisten.

Der Reis wird nach 4 Vergleichen gefunden. Der fehlende Barcode geht durch alle 6 Kisten: Nur so lässt sich sagen, dass er nicht da ist.

Die Barcodes werden mit equals verglichen, nicht mit ==. Bei Text fragt ==, ob es dasselbe Objekt im Speicher ist, und der Barcode vom Scanner ist ein anderes Objekt mit denselben Ziffern.

Probier es aus

Ergänze

Was gibt find zurück, wenn die Kisten zu Ende sind?

static int find(List<Product> shelf, String barcode) {
    for (int i = 0; i < shelf.size(); i++) {
        if (shelf.get(i).barcode().equals(barcode)) {
            return i;
        }
    }
    return ;
}

Die Idee

Wie viele Vergleiche

Die Zahl der Vergleiche hängt davon ab, wo das Produkt liegt:

  • der beste Fall: die erste Kiste, 1 Vergleich;
  • der schlechteste Fall: die letzte Kiste oder ein Produkt, das nicht da ist, n Vergleiche;
  • der typische Fall: Wenn jeder Platz gleich wahrscheinlich ist, im Durchschnitt etwa n/2.

Der schlechteste und der typische Fall wachsen mit n, deshalb ist die lineare Suche O(n). Das Programm zählt mit:

static int comparisons(List<Product> shelf, String barcode) {
    int count = 0;
    for (Product product : shelf) {
        count++;
        if (product.barcode().equals(barcode)) {
            return count;
        }
    }
    return count;
}
System.out.println("Mehl: " + comparisons(shelf, "3800200101112"));
System.out.println("Reis: " + comparisons(shelf, "3800200102690"));
System.out.println("Fehlt: " + comparisons(shelf, "3800200100000"));
Ausgabe
Mehl: 1
Reis: 4
Fehlt: 6

Lass die beiden Extremfälle in einem großen Lager laufen. Wir zählen einen Vergleich pro Kiste:

  • Der Barcode fehlt (schlechtester Fall) O(n)
  • Das erste Produkt (bester Fall) O(1)
Algorithmusn = 10n = 1.000n = 100.000
Der Barcode fehlt (schlechtester Fall)101.000100.000
Das erste Produkt (bester Fall)111
Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

Die erste Kiste kostet bei jedem n 1 Vergleich: O(1). Ein fehlendes Produkt kostet n: Bei 100.000 Produkten sind das 100.000 Vergleiche. Der Speicher ist O(1): ein Index.

Probier es aus

Sage die Ausgabe voraus

Das Salz ist die fünfte Kiste im Regal. Wie viele Vergleiche macht die Suche?

static int comparisons(List<Product> shelf, String barcode) {
    int count = 0;
    for (Product product : shelf) {
        count++;
        if (product.barcode().equals(barcode)) {
            return count;
        }
    }
    return count;
}


System.out.println("Salz: " + comparisons(shelf, "3800200109958"));
Antwort

Sieh es dir an

Die eingebauten Funktionen suchen genauso

Jede Sprache hat eine fertige Suche in einer Liste. Darin steckt dieselbe Schleife:

List<String> barcodes = List.of(
    "3800200101112", "3800200104403", "3800200107251",
    "3800200102690", "3800200109958", "3800200105837");
System.out.println(barcodes.indexOf("3800200102690"));
System.out.println(barcodes.indexOf("3800200100000"));
System.out.println(barcodes.contains("3800200102690"));
Ausgabe
3
-1
true
indexOf liefert den Platz oder -1, und contains nur „ja“ oder „nein“. Beide vergleichen mit equals ab dem ersten Element: O(n). Für eine Liste von Produkten nach Barcode hat Java keine fertige Methode; du schreibst die Schleife oder nutzt einen Stream (IntStream.range(...).filter(...).findFirst()), der ebenfalls der Reihe nach vorgeht.

Ein Aufruf sieht nach einer Operation aus, aber darin stecken bis zu n Vergleiche. Die eingebaute Funktion ist um einen konstanten Faktor schneller als deine Schleife, nicht um eine Größenordnung.

Probier es aus

Finde den Fehler

Ein Kollege hat die Suche so geschrieben. Das Mehl wird gefunden, und der Reis „ist nicht da“:

static int find(List<Product> shelf, String barcode) {
    for (int i = 0; i < shelf.size(); i++) {
        if (shelf.get(i).barcode().equals(barcode)) {
            return i;
        } else {
            return -1;
        }
    }
    return -1;
}
System.out.println(find(shelf, "3800200101112"));
System.out.println(find(shelf, "3800200102690"));
Ausgabe
0
-1

In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Wann sie passt und wann nicht

Die lineare Suche ist die richtige Wahl, wenn:

  • es wenige Produkte gibt: Zehn oder hundert Vergleiche merkt man nicht;
  • du einmal suchst: Jeder schnellere Weg braucht erst mindestens n Schritte Vorbereitung;
  • die Daten unsortiert sind oder sich ständig ändern und es nichts zu pflegen gibt.

Sie passt nicht bei vielen Suchen. 2000 Scans am Tag in 50.000 Produkten sind bis zu 100.000.000 Vergleiche. Dann bereitest du die Daten einmal vor:

  • eine Tabelle Barcode → Produkt (HashMap): einmal 50.000 Schritte, danach ist jede Suche im Durchschnitt O(1);
  • eine sortierte Liste und die binäre Suche: Das Sortieren ist einmal O(n log n), und jede Suche danach ist O(log n), bei 50.000 etwa 16 Vergleiche.
Map<String, Product> byBarcode = new HashMap<>();
for (Product product : shelf) {
    byBarcode.put(product.barcode(), product);
}
System.out.println(byBarcode.get("3800200102690").name());
System.out.println(byBarcode.get("3800200100000"));
Ausgabe
Reis
null

Die Tabelle kostet Speicher: noch einmal n Plätze. Das ist derselbe Tausch von Zeit gegen Speicher wie beim Set in der Lektion „Speicherkomplexität“.

Übung

Alle Kisten eines Produkts

Löse die Aufgabe in deinem Editor.

Inventur. Ein Produkt kann mit mehreren Lieferungen gekommen sein und an mehreren Plätzen in der Liste stehen. Schreibe findAll(shelf, barcode), das alle Plätze des Barcodes zurückgibt, nicht nur den ersten. Das Regal ist wie oben, dazu mehr Reis und mehr Salz am Ende (Plätze 6 und 7).

Ausgabe
Reis: 3, 6
Salz: 4, 7

Weitere Aufgaben

  • Der letzte Platz. Gib den letzten Platz des Barcodes zurück. Wo fängt man besser an?
  • Nach Name, ohne Groß- und Kleinschreibung. Finde das Produkt nach Namen („reis“ und „Reis“ sind dasselbe). Wie viele Vergleiche sind es im schlechtesten Fall?
  • Produkte unter dem Mindestbestand. Liste alle Produkte mit weniger als 10 Stück auf Lager auf. Kannst du vor dem Ende aufhören?

Test

Teste dich

1. Die Liste hat 10.000 unsortierte Produkte. Wie viele Vergleiche macht die lineare Suche für ein Produkt, das nicht da ist?
2. Das Produkt ist da, und jeder Platz ist gleich wahrscheinlich. Wie viele Vergleiche braucht man im Durchschnitt bei n Produkten?
3. Warum gibt find nicht 0 zurück, wenn das Produkt nicht da ist?
4. Der Scanner macht am Tag 2000 Suchen in 50.000 Produkten. Was ist besser?
5. Wann ist die lineare Suche die richtige Wahl?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·