Pourquoi mon temps de recherche devient-il plus court, plus je fais de recherches?
Question
Je fais une affectation qui m'oblige à mesurer le temps pris par deux algorithmes de recherche différents, séquentiels et binaires (je suppose qu'il fait le point sur l'efficacité). J'ai une liste cible d'environ 280 mots à rechercher et une liste de pool de recherche d'environ 1200 mots. J'ai lu les deux fichiers et stocké les mots dans Arraylists.
Voici le bit pertinent pour l'algorithme séquentiel que j'ai implémenté jusqu'à présent:
long startTime = System.nanoTime();
//search sorted list for as long as end of list has not been reached and
//current list item lexicographically precedes target String
while((compareResult > 0)&&(position != searchPool.size()-1)){
//update to current position
position += 1;
compareResult = target.compareTo(searchPool.get((int)position));
comparisonCount += 1;
}//end while loop
long endTime = System.nanoTime();
timeElapsed = endTime - startTime; //timeElapsed also a long
Après cela, j'affiche le nombre de comparaisons faites et le temps écoulé (en millisecondes, donc je divise par un million en premier).
Le temps renvoyé pour les premiers nombres est d'environ 0,5 à 0,7 ms. Ce nombre oscille vers le bas au 32e mot qui prend 0,1 ms. Les 150 mots restants prennent tous 0,0 ms.
Je m'attendais à une corrélation directe entre le nombre de comparaisons et le temps écoulé. Une idée de ce qui ne va pas?
Mis à part: il m'est venu à l'esprit que le nombre de comparaisons faites par la méthode de comparaison (c'est-à-dire la longueur des mots) pourrait affecter le temps, mais même les mots longs qui n'apparaissent pas dans la liste recherchée (et doivent donc être comparés à tous les éléments avant cela la conclusion est atteinte) ne prenez pas du tout le tout s'ils apparaissent plus bas.
La solution
JVM optimise les chemins de code fréquemment exécutés afin qu'ils deviennent plus rapides. En fonction de l'application, les premières itérations peuvent également impliquer l'établissement d'une connexion, le chargement d'une ressource, etc.
Donc, en tant que stratégie générale, vous devez éliminer les premiers échantillons. Et prendre la mesure comme moyenne sur des échantillons plus importants pour des résultats plus fiables.