[GO] Grundlagen der Exploration und Java-Implementierung / Messung
TL;DR
- Anfänger --Wählen Sie die richtige Suchmethode und lernen Sie, wie Sie die Ausführungszeit verkürzen ――Es dauert ungefähr 0,5 Sekunden, um selbst einen einfachen Prozess 2 Milliarden Mal auszuführen.
- (Wenn Sie die DB-Verbindung wiederholen, dauert dies außerordentlich lange.)
Wichtige Suchtypen und Bilder
- Lineare Suche --Dichotomie
- Hash-Suche
Betrachten Sie ein Beispiel für die Suche nach einem Kunden, indem Sie mail_address angeben.
Lineare Suche
- Beziehen Sie sich auf die Zieldaten, um zu überprüfen, ob der Suchschlüssel mail_address übereinstimmt.
[Berechnung](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8% A8% 98% E5% 8F% B7 #% E4% B8% 80% E8% 88% AC% E7% 9A% 84% E3% 81% AA% E3% 82% AA% E3% 83% BC% E3% 83 % 80% E3% 83% BC)
Wenn 1024 Daten vorhanden sind, wird 1024 Mal darauf verwiesen. Blöd.
O(n)
Halbierungssuche
- Sortieren Sie das Ganze nach mail_address
- Beziehen Sie sich auf die Daten in der Mitte, um zu sehen, ob sie übereinstimmen.
- Wenn sie nicht übereinstimmen, verwerfen Sie die Hälfte und beziehen Sie sich auf die Mitte der anderen Hälfte
- Eine Art Teilungsregel
[Berechnung](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8% A8% 98% E5% 8F% B7 #% E4% B8% 80% E8% 88% AC% E7% 9A% 84% E3% 81% AA% E3% 82% AA% E3% 83% BC% E3% 83 % 80% E3% 83% BC)
1024 Fälle = 2 ^ 10 Fälle = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 Fälle werden also zur Hälfte verworfen Sie finden es unter Bezugnahme auf höchstens 10 Daten. Clever.
O(\log n)
- Der untere Rand des Logs in der Informatik ist 2.
2 ^ (log n) = n
Hash-Methode
- Übergeben Sie die Mail-Adresse aller Zieldaten an die Hash-Funktion und konvertieren Sie sie gemäß einer bestimmten Regel, um den Hash-Wert zu erhalten.
- Übergeben Sie den Suchschlüssel mail_address an dieselbe Hash-Funktion und konvertieren Sie ihn nach derselben Regel, um den Hash-Wert zu erhalten.
- Bezieht sich auf Daten mit übereinstimmenden Hashwerten
- Es ist keine zusätzliche Verarbeitung erforderlich, um den angegebenen Hashwert xxx aus dem Block der Hashwerte der Zieldaten zu ermitteln (Implementierungsbeispiel: Hash-Tabelle. % 8F% E3% 83% 83% E3% 82% B7% E3% 83% A5% E3% 83% 86% E3% 83% BC% E3% 83% 96% E3% 83% AB))
[Berechnung](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8% A8% 98% E5% 8F% B7 #% E4% B8% 80% E8% 88% AC% E7% 9A% 84% E3% 81% AA% E3% 82% AA% E3% 83% BC% E3% 83 % 80% E3% 83% BC)
Selbst bei 1024 Fällen können Sie direkt auf die Zieldaten verweisen, indem Sie die Hash-Funktion einmal durchlaufen.
O(1)
Nachteil
Im Allgemeinen ist der Algorithmus [der Kompromiss zwischen schnellerer Ausführungszeit und geringerem Speicherverbrauch](https://ja.wikipedia.org/wiki/%E6%99%82%E9%96%93%E3%81%A8% E7% A9% BA% E9% 96% 93% E3% 81% AE% E3% 83% 88% E3% 83% AC% E3% 83% BC% E3% 83% 89% E3% 82% AA% E3% 83% 95) Es gibt und kann mit Implementierungen gemacht werden, die beide schlecht sind, Kein Algorithmus liefert jeweils die beste Leistung zur gleichen Zeit Die Hash-Methode ist wahrscheinlich dieselbe und verbraucht Speicher.
Was wird in der Datenbank verwendet?
PostgreSQL-Ausführungsplan (erklären, erklären, analysieren)
--Seq Scan: Lineare Suche
- Index-Scan: So etwas wie eine Zweiteilung --Hash ~: Hash-Methode
[Nur Scan-Kampf nach PostgreSQL-Index Teil 3 | TECHSCORE-BLOG](https://www.techscore.com/blog/2013/06/07/postgresql-index-only-scan-%E5%A5%AE%E9%97 % 98% E8% A8% 98-% E3% 81% 9D% E3% 81% AE3 /) [SQL] Lesen Sie den Ausführungsplan aus null Wissen und verbessern Sie die Leistung --Qiita EXPLAIN --PostgreSQL 10.5-Dokument
Java Implementierung / Messung
Vor dem Implementieren der Suche
Selbst ein einfacher Verarbeitungszweig benötigt 0,61 Sekunden, wenn er 2 Milliarden Mal ausgeführt wird
Quellcode zur Basis
Bereiten Sie 100.000 Kunden vor und suchen Sie Ihre E-Mail-Adresse 1000 Mal. https://ideone.com/w0hDzg
Es dauert 0,9 Sekunden, bis der Ort (TODO) für den Suchvorgang nicht implementiert ist.
import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
//Erstellen Sie Daten für n Personen
int n = 100000;
Random rand = new Random();
String[][] customer = new String[n][2];
for (int i = 0; i < n; i++)
customer[i][0] = String.valueOf((char) (rand.nextInt(26)+'a')) + i + "@ab.com";
for (int i = 0; i < n; i++)
customer[i][1] = i + "Herr.";
//Nach E-Mail-Adresse sortieren
Arrays.sort(customer, (c1, c2) -> c1[0].compareTo(c2[0]));
//Erstellen Sie auch eine Hash-Map mit dem Schlüssel als E-Mail-Adresse und dem Wert als Namen
Map<String, String> hashmap = new HashMap<>(n);
for (String[] c : customer)
hashmap.put(c[0], c[1]);
//Gleicher Kunde(101st)Kann den Namen annehmen
System.out.println(customer[101][0] + "Ist der Name" + customer[101][1]);
//Sie können es auch per E-Mail-Adresse von der Hash-Karte erhalten
System.out.println(customer[101][0] + "Ist der Name" + hashmap.get(customer[101][0]));
System.out.println("Bestätigung beendet");
//Wählen Sie dann die E-Mail-Adresse für m Personen entsprechend aus
int m = 1000;
String[] keys = new String[m];
for (int j = 0; j < m; j++)
keys[j] = customer[rand.nextInt(n)][0];
//Einer nach dem anderen
for (int j = 0; j < m; j++){
String key = keys[j];
//Lass uns suchen
// TODO
String found = null;
if (j % 100 == 0) {
System.out.println(key + "Ist der Name" + Objects.toString(found, "Unbekannt"));
}
}
}
}
Lineare Suche
Es sind 3,9 Sekunden. langsam! https://ideone.com/GIle7V
//Wo es TODO war
String found = null;
for (int i = 0; i < n; i++) {
if (Objects.equals(key, customer[i][0])) {
found = customer[i][1];
}
}
Halbierungssuche
1 Sekunde. Erstens betrug die Datenaufbereitung 0,9 Sekunden, sodass die Suche selbst fast keine Zeit in Anspruch nahm. https://ideone.com/eF7Txv
//Wo es TODO war
String found = null;
keyCustomer[0] = key;
int index = Arrays.binarySearch(customer, keyCustomer, (c1, c2) -> c1[0].compareTo(c2[0]));
found = customer[index][1];
Hash-Methode
0,93 Sekunden. Fast keine Zeit https://ideone.com/67PzQP
//Wo es TODO war
String found = null;
found = hashmap.get(key);
Halbierungssuche (1024 mal)
Da der Unterschied zwischen der Dichotomie und der Hash-Methode die Fehlerstufe war, Vergleichen wir, indem wir die Anzahl der Suchvorgänge (m) mit 1024 multiplizieren. Die Dichotomie beträgt 1,69 Sekunden. https://ideone.com/ppG31d
Hash-Methode (1024 mal)
Erhöhen wir auch die Anzahl der Suchvorgänge (m) mit der Hash-Methode um das 1024-fache. Es ist 1,16 Sekunden. https://ideone.com/ppG31d Die Ausführungszeit nimmt mit zunehmender Anzahl der Suchschlüssel langsamer zu als bei einer zweiminütigen Suche. Es ist die Differenz in der Berechnungsmenge
Wird Exploration tatsächlich in der Entwicklung eingesetzt?
Obwohl es für Anfänger nur wenige Möglichkeiten gibt, sich dessen bewusst zu werden, nutzen sie es. Betrachten Sie die Situation, in der Sie die Bestellverlaufsliste in der Datenbank durchsuchen. Kombinieren Sie in SQL die Kunden-Kundentabelle (mehr als 10.000) mit der Bestellbestellungstabelle (mehr als 10.000) und der Bestelldetail-Bestelltabelle (mehr als 10.000), um die Details abzurufen, und anschließend die Produktprodukttabelle (mehr als 10.000). Super kombinieren), um den Produktnamen zu erhalten. Wenn Sie diese SQL ausführen und in einer realistischen Zeit fertig sind, legt der DB-Administrator die entsprechende Primärschlüsseleinschränkung / eindeutige Einschränkung / Index usw. fest, und die DB führt darauf basierend eine Dichotomie durch. Die für) verwendeten Baumstrukturdaten und die für die Hash-Methode verwendete Hash-Tabelle werden im Voraus vorbereitet und wahrscheinlich bei der Ausführung von SQL verwendet. In diesem Bereich ist die Verarbeitung langsam, da die DB-Definition fehlt / nur eine lineare Suche möglich ist, weil die SQL-Tabellenverbindungsbedingung kompliziert ist, und sie ist langsam / Sie bemerken diese Probleme erst, wenn Sie sie in der Produktionsumgebung ausführen / es gibt Raum für Verbesserungen Es gibt viele unglückliche Situationen, wie zum Beispiel unbeaufsichtigt zu bleiben. Bitte beachten Sie, dass es andere verdächtige Punkte gibt, die außerhalb Ihrer Verantwortung liegen.
Hope this helps.
andere Referenzen
[Was ist E-Wörter für das lineare Such-IT-Glossar] (http://e-words.jp/w/%E7%B7%9A%E5%BD%A2%E6%8E%A2%E7%B4%A2.html) [Was ist eine zweiminütige Suche (zweiminütige Suche)? --IT Glossar e-Words](http://e-words.jp/w/%E4%BA%8C%E5%88%86%E6%8E%A2% E7% B4% A2.html) [Was ist eine Hash-Methode (Hash-Suche)? --IT Glossary e-Words](http://e-words.jp/w/%E3%83%8F%E3%83%83%E3%82%B7%E3 % 83% A5% E6% B3% 95.html) Lineare Suche-Wikipedia Dichotomie-Wikipedia
Recommended Posts