J'ai un ensemble de données volumineux que je veux parcourir afin de déterminer diverses statistiques sur les données définies à partir d'un point à temps "D1" à un moment donné dans le futur "D2". Fondamentalement, je souhaite ajouter une base de données à chaque fois que la différence entre les valeurs est supérieure à 10. Par exemple:
Datum[] data = x;
for( Datum d1 : data ){
Datum[] tail = y; //From d1 up to 10 elements ahead
for( Datum d2 : tail ){
//Calculate difference
if( (d2.val - d1.val) > 10 ){
//Insert into database
}
}
}
4 Réponses :
Un indice pour la boucle peut fonctionner beaucoup mieux qu'un itérateur, car vous pouvez indexer directement le tableau d'origine et éviter de copier à un nouveau tableau. Vous auriez beaucoup mieux la localité de mémoire, moins de chances de partage faux, etc.
J'ai supposé que c'était juste un peu pseudo-code pour obtenir le point sans tous les détails inintéressants. S'il crée vraiment un banquier à chaque fois que oui, ce serait la première chose à réparer!
Dans vos chaussures, la première chose que je ferais est de profiler un jeu de données typique et de découvrir où se passe le temps. Cela devrait donner quelques astuces quant à l'endroit où concentrer vos efforts d'optimisation.
En supposant que le calcul est aussi simple que la soustraction / comparaison, et les tableaux sont rapidement accessibles, votre suggestion de rechercher d'optimiser l'épargne à la base de données devrait être la priorité suivante. Par exemple, écrire un fichier texte et utiliser un insert en vrac peut donner des performances très rapides par rapport aux relevés d'insertion individuels. Si vous vous en tenez à utiliser des inserts séparés et utilisez JDBC, les mises à jour de lots seront une grande aide, car elles évitent la latence de communiquer avec la base de données.
Si cela n'est toujours pas assez rapide, envisagez de partitionnement de la matrice dans N partitions et de chaque partition traitée par un thread séparé. Cela sera particulièrement efficace si la transformation est liée à la CPU.
Enfin, recherchez les optimisations au niveau du code, telles que l'évitant des itérateurs en utilisant un index. Si le nombre d'éléments écrit dans la base de données est faible par rapport au nombre d'éléments itératés, la création d'itérateur peut être un goulot d'étranglement.
Si le nombre d'éléments est supérieur à 10, et de manière critique, plus que ce qui peut s'adapter au cache de la CPU, il sera plus efficace de rompre la numérisation en blocs plus petits. Par exemple, plutôt que de numériser 1000 éléments de Data2, rompez-la dans (disons) 10 analyses de 100, avec chacune des 10 analyses utilisant une valeur différente de D1. Ceci est similaire à la manière dont la multiplication matricielle est mise en œuvre de manière blanche et permet de mieux utiliser les caches de la CPU.
Bien que vous utilisiez deux boucles, ce qui est typiquement un algorithme O (N ^ 2), la seconde boucle comporte une taille fixe - 10 éléments, ce qui réduit donc un facteur constant simple - vous faites environ un facteur de 10 plus de travail.
Ce que vous avez est un algorithme de bals à balles classique qui sont O (k * n) avec K le "chevauchement" ou la partie que la boucle interne s'éteint. Dans votre cas, il est maximum 10, peu importe ce que N est
Datum[] data = x;
for(int i=0;i<data.length;i++ ){
Datum d1=data[i];
Datum[] tail = y; //From d1 up to 10 elements ahead
for(int j=i+1;j<Math.min(i+10,data.length);i++){
d2 = data[j];
//Calculate difference
if( (d2.val - d1.val) > 10 ){
//Insert into database
break;//inner loop
}
}
}
Il y a un asymptotiquement moyen plus rapide de résoudre ce problème, mais j'ai de sérieux doutes quant à savoir s'il serait plus rapide dans la pratique, car votre taille de fenêtre (10) est si petite. Si vous voulez augmenter cette taille - que je vais appeler K - pour être plus grand, vous voudrez peut-être envisager d'opter pour une approche comme ci-dessous.
Lorsque vous utilisez cet algorithme, vous devez conserver une fenêtre des éléments K qui prend en charge deux opérations:
Un moyen de faire cela serait de stocker tous vos éléments dans une structure de données combinant un arbre de recherche binaire équilibré et une file d'attente. La file d'attente contient tous les éléments K stockés dans l'ordre dans lequel elles apparaissent dans la séquence d'origine et sont utilisées afin que nous puissions nous souvenir de l'élément à expulser lorsque nous devons ajouter un nouvel élément. La BST équilibrée stocke une copie de chacun de ces éléments stockés dans l'ordre triché. Cela signifie que vous pouvez implémenter les opérations ci-dessus comme ceci:
collectivement, si vous avez des éléments et un total de z paires que vous devez insérer dans la base de données, cet algorithme prendra O (N log K + Z). Pour voir cela, notez que nous effectuons un total de n exemplaires de l'opération (1), qui prend une heure (log k) chacun. Nous faisons également des copies de l'opération (2), qui prend le temps de trouver des successeurs, puis de O (z) du temps total sur toutes les itérations pour répertorier toutes les paires correspondantes.
Le temps d'exécution asymptotique de cet algorithme est bon par rapport à l'algorithme O (NK) que vous avez posté à l'origine. En supposant que le nombre de matches n'est pas «vraiment énorme» (disons, de l'ordre de NK), cela sera beaucoup plus rapide que vous augmentez N et K.
Si les valeurs que vous stockez sont des entiers dans une petite gamme (disons, 0 à 10 000), vous pouvez accélérer encore plus loin en remplaçant la BST équilibrée avec une structure de données optimisée pour les entiers, comme un arborescence de van emme , qui réduit cela à O (n journal journal K + Z). Encore une fois, ce n'est que plus rapide asymptotiquement asymptotiquement, et si vous tenez K constante à 10, cela ne vaut presque certainement pas la peine.
J'espère que cela vous aide!
Je ne vois pas comment c'est O (n ^ 2) pour commencer avec. Vous êtes en boucle à chaque élément du tableau, puis regardez les 10 éléments suivants. Donc, c'est imo o (10 * N) = O (n), donc au mieux, vous pouvez réduire un peu la surcharge constante - mais cela n'apportera probablement pas d'importantes améliorations s'il n'y a pas d'ordre ou quelque chose sur les données
Les valeurs de données sont-elles dans un ordre particulier?
Je suis d'accord avec Voo. Vous regardez une distance fixe à l'avance, peu importe N, alors même si vous pouvez faire le même travail plusieurs fois, il s'agit simplement d'une constante multiplicative N plus de travail, de sorte que votre boucle est donc O (n).
C'est un bon point. Peut-être que je devrais regarder l'amélioration de la partie insert . Puisqu'il est plus qu'un simple insert.
Pour être plus précis, l'algorithme est O (NK), où K est le nombre d'autres éléments que vous regardez. Il est bon de quantifier ce second terme, car si vous décidez de le changer plus tard (par exemple, à 13 ou 20), vous pouvez raisonner sur le taux de croissance de la complexité de temps. Trouver une solution O (N log K) peut être possible ici, ce qui est définitivement meilleur si k pourrait changer de jour.
@TemplatetyTypeDef Les éléments suivants vous tirez tous dans le cache qui rend essentiellement toutes les opérations suivantes beaucoup moins chères). De plus, l'insertion dans la base de données semble être un candidat très probable où la plupart du temps est dépensé (si ce n'est pas ASYNC, c'est la première chose que je ferais!)
@ VOO- Je suis à peu près sûr que non O (N log K) algorithme existe pour cela, car il y a dans le pire des cas oméga (n ^ 2) paires à regarder. Cependant, vous pouvez trouver quelque chose comme une solution O (N log K + Z), où Z est le nombre total de paires rapportées. Et vous avez raison - ce n'est certainement pas le goulot d'étranglement de la performance. Cela dit, si cela devait devenir un, avoir ce type d'analyse pourrait expliquer pourquoi.