[GO] Bases de l'exploration et de l'implémentation / mesure Java
TL;DR
- Débutants --Choisissez la bonne méthode de recherche et apprenez à raccourcir le temps d'exécution ――Il faut environ 0,5 seconde pour exécuter même un processus simple 2 milliards de fois.
- (Si vous répétez la connexion DB, cela prendra un temps extraordinaire.)
Principaux types de recherche et images
- Recherche linéaire --Dichotomie
- Recherche de hachage
Prenons un exemple de recherche d'un client en spécifiant mail_address.
Recherche linéaire
- Reportez-vous aux données cibles afin de vérifier si la clé de recherche mail_address correspond.
[Calcul](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)
S'il y a 1024 données, elles seront référencées 1024 fois. Stupide.
O(n)
Recherche de bisection
--Trier le tout par mail_address
- Reportez-vous aux données du milieu pour voir si elles correspondent.
- S'ils ne correspondent pas, jetez la moitié et reportez-vous au milieu de l'autre moitié --Une sorte de règle divisionnaire
[Calcul](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 cas = 2 ^ 10 cas = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 cas sont écartés de moitié, donc Vous pouvez le trouver en vous référant à au plus 10 données. intelligent.
O(\log n)
- Le bas du journal en informatique est 2.
2 ^ (log n) = n
Méthode de hachage
--Passez l'adresse mail de toutes les données cibles à la fonction de hachage et convertissez-la selon une certaine règle pour obtenir la valeur de hachage. --Passez la clé de recherche mail_address à la même fonction de hachage et convertissez-la selon la même règle pour obtenir la valeur de hachage.
- Fait référence aux données avec des valeurs de hachage correspondantes
- Aucun traitement supplémentaire n'est requis pour trouver la valeur de hachage xxx spécifiée à partir du bloc de valeurs de hachage des données cibles (exemple d'implémentation: Hash Table % 8F% E3% 83% 83% E3% 82% B7% E3% 83% A5% E3% 83% 86% E3% 83% BC% E3% 83% 96% E3% 83% AB))
[Calcul](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)
Même avec 1024 cas, vous pouvez vous référer directement aux données cibles en passant une fois par la fonction de hachage.
O(1)
Désavantage
En général, l'algorithme est un compromis entre un temps d'exécution plus rapide et une consommation de mémoire inférieure (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) Il y a et peut être fait avec des implémentations qui sont à la fois mauvaises, Il n'y aura pas d'algorithme qui donne les meilleures performances en même temps pour chaque La méthode de hachage ne fuit probablement pas et consomme de la mémoire
Qu'est-ce qui est utilisé dans la base de données?
Plan d'exécution PostgreSQL (expliquer, expliquer, analyser)
--Seq Scan: recherche linéaire --Index Scan: Quelque chose comme une dichotomie --Hash ~: méthode Hash
[Lutte contre l'analyse de l'index PostgreSQL uniquement, partie 3 | BLOG TECHSCORE](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] Lire le plan d'exécution à partir de zéro connaissance et améliorer les performances --Qiita EXPLIQUEZ - Document PostgreSQL 10.5
Implémentation / mesure Java
Avant de mettre en œuvre la recherche
Même une simple branche de traitement prend 0,61 seconde si elle est exécutée 2 milliards de fois
Code source à la base
Préparez 100 000 clients et recherchez votre adresse e-mail 1 000 fois. https://ideone.com/w0hDzg
Il est de 0,9 secondes lorsque le lieu (TODO) pour mettre le processus de recherche n'est pas implémenté.
import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
//Créer des données pour n personnes
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 + "M.";
//Trier par adresse e-mail
Arrays.sort(customer, (c1, c2) -> c1[0].compareTo(c2[0]));
//Nous allons également créer une carte de hachage avec la clé comme adresse e-mail et la valeur comme nom.
Map<String, String> hashmap = new HashMap<>(n);
for (String[] c : customer)
hashmap.put(c[0], c[1]);
//Même client(101e)Peut prendre le nom de
System.out.println(customer[101][0] + "Est le nom" + customer[101][1]);
//Vous pouvez également l'obtenir par adresse e-mail depuis la carte de hachage
System.out.println(customer[101][0] + "Est le nom" + hashmap.get(customer[101][0]));
System.out.println("Confirmation terminée");
//Ensuite, sélectionnez l'adresse e-mail de m personnes de manière appropriée
int m = 1000;
String[] keys = new String[m];
for (int j = 0; j < m; j++)
keys[j] = customer[rand.nextInt(n)][0];
//Un par un
for (int j = 0; j < m; j++){
String key = keys[j];
//Cherchons
// TODO
String found = null;
if (j % 100 == 0) {
System.out.println(key + "Est le nom" + Objects.toString(found, "inconnue"));
}
}
}
}
Recherche linéaire
C'est 3,9 secondes. lent! https://ideone.com/GIle7V
//Où c'était TODO
String found = null;
for (int i = 0; i < n; i++) {
if (Objects.equals(key, customer[i][0])) {
found = customer[i][1];
}
}
Recherche de bisection
1 seconde. En premier lieu, la préparation des données a duré 0,9 seconde, de sorte que la recherche elle-même n'a pratiquement pas pris de temps. https://ideone.com/eF7Txv
//Où c'était TODO
String found = null;
keyCustomer[0] = key;
int index = Arrays.binarySearch(customer, keyCustomer, (c1, c2) -> c1[0].compareTo(c2[0]));
found = customer[index][1];
Méthode de hachage
0,93 seconde. Presque pas de temps https://ideone.com/67PzQP
//Où c'était TODO
String found = null;
found = hashmap.get(key);
Recherche de bisection (1024 fois)
Puisque la différence entre la dichotomie et la méthode de hachage était le niveau d'erreur, Comparons en multipliant le nombre de recherches (m) par 1024. La dichotomie est de 1,69 seconde. https://ideone.com/ppG31d
Méthode de hachage (1024 fois)
Augmentons également le nombre de recherches (m) par la méthode de hachage de 1024 fois. C'est 1,16 seconde. https://ideone.com/ppG31d Le temps d'exécution augmente plus lentement à mesure que le nombre de clés de recherche augmente qu'avec une recherche de bissection. C'est la différence dans le montant du calcul
L'exploration est-elle réellement utilisée dans le développement?
Bien qu'il y ait peu d'opportunités pour les débutants d'en être conscients, ils l'utilisent. Considérez la situation dans laquelle vous recherchez la liste d'historique des commandes dans la base de données. Dans SQL, combinez la table client client (plus de 10 000) avec la table de commande de commande (plus de 10 000) et la table de détail de commande order_detail (plus de 10 000) pour obtenir les détails, puis la table de produit produit (plus de 10 000). Combinez super) pour obtenir le nom du produit. Si vous exécutez ce SQL et terminez dans un temps réaliste, l'administrateur de la base de données définit la contrainte de clé primaire / la contrainte unique / l'index appropriée, etc., et la base de données effectue une dichotomie en fonction de celle-ci. Les données d'arborescence utilisées pour) et la table de hachage utilisée pour la méthode de hachage sont préparées à l'avance et sont probablement utilisées lors de l'exécution de SQL. Sur le terrain, le traitement est lent car la définition de la base de données est manquante / seule la recherche linéaire est possible car la condition de jointure de table SQL est compliquée et elle est lente / vous ne remarquez pas ces problèmes tant que vous ne l'exécutez pas dans l'environnement de production / il y a place à l'amélioration Il existe de nombreuses situations malheureuses telles que le fait d'être laissé sans surveillance. Veuillez noter qu'il existe d'autres points suspects en dehors de votre responsabilité.
Hope this helps.
Autres références
[Qu'est-ce que le glossaire Linear Search-IT en ligne] (http://e-words.jp/w/%E7%B7%9A%E5%BD%A2%E6%8E%A2%E7%B4%A2.html) [Qu'est-ce qu'une recherche de deux minutes (recherche de deux minutes)? - IT Glossary e-Words](http://e-words.jp/w/%E4%BA%8C%E5%88%86%E6%8E%A2% E7% B4% A2.html) [Qu'est-ce que la méthode de hachage (recherche par hachage)? - 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) Recherche linéaire-Wikipedia Dichotomie-Wikipedia
Recommended Posts