Moyen le plus rapide de trouver si INT gray contient un nombre

Peu importe le niveau de Bytecode, mais au niveau du code natif,

if (pixels[i] != 0)

Non, il n'y a pas de solution plus rapide à moins que le tableau d'entiers est déjà trié, ce que je doute donnait que c'est un tableau de couleurs.

Pour analyser via un tableau non formé prend du temps linéaire "O (n)". C'est ce que vous faites et que vous sortez de la méthode dès qu'une correspondance est trouvée qui est bonne aussi.

Sans passer à une autre structure de données, non, il n'y a pas de meilleure façon de trouver si le tableau contient cette valeur. Vous devez regarder tous les éléments du tableau pour voir si elle est là, car si vous ne cochez pas un endroit particulier que vous pourriez manquer une copie de cette couleur de pixel.

Cela dit, il existe d'autres moyens que vous pouvez résoudre ce problème. Voici quelques réflexions sur la façon d'accélérer ce:

• Si chaque valeur est garantie pour être soit blanc ou noir, vous pouvez stocker deux valeurs booléennes supplémentaires à côté du tableau représentant si des pixels blancs ou noirs. De cette façon, une fois que vous avez exécuté la fois scan, vous pouvez lire les booléens juste en arrière. Vous pouvez également stocker un comptage du nombre de pixels blancs et noirs ainsi que le tableau, puis chaque fois que vous écrivez une mise à jour de pixel le nombre en décrémentant le nombre de pixels de la couleur d'origine et incrémenter le nombre de pixels de la nouvelle couleur. Cela vous donnera la possibilité de vérifier si un pixel d'une couleur donnée existe dans O (1) juste en voyant si le compteur correct est non nul.

• Par ailleurs, si vous connaissez quelque chose sur l'image (peut-être où les pixels blancs et noirs doivent être), vous pourriez envisager de faire l'itération dans un ordre différent. Par exemple, si les pixels que vous recherchez ont tendance à être regroupés dans le centre de l'image, la réécriture de la boucle pour vérifier il pourrait d'abord être une bonne idée car s'il y a des pixels de ce type vous les trouverez plus rapidement . Cela a toujours le même comportement pire des cas, mais pour les images « réalistes » pourrait être beaucoup plus rapide.

• Si vous avez plusieurs threads disponibles et le tableau est vraiment énorme (en millions d'éléments), vous pourriez envisager d'avoir plusieurs threads chacun recherche une partie du tableau de la valeur. Cela ne serait possible que si vous aviez une raison de soupçonner que la plupart de l'image n'a pas été blanche.

• Comme dans la plupart des images réalistes, vous pourriez supposer que l'image est un mélange de couleurs et vous êtes à la recherche de quelque chose d'une couleur, alors vous voudrez peut-être envisager de stocker l'image comme http://en.wikipedia.org/wiki/Sparse_array">sparse, où vous stockez une liste des pixels qui se trouvent être d'une couleur (par exemple, blanc), puis prendre tout le reste est noir. Si vous attendez la plupart des images d'être une couleur unie avec quelques valeurs aberrantes, cela pourrait être une très bonne représentation. De plus, il vous donnerait recherche constante de temps de si des pixels noirs ou blancs existent -. Simplement vérifier si la liste des pixels ensemble est vide ou est constitué de l'ensemble de l'image

• Si l'ordre n'a pas d'importance, vous pouvez également stocker les éléments dans certains récipient comme une table de hachage, ce qui pourrait vous donner O (1) recherche de l'élément est là ou non. Vous pouvez également trier le tableau, puis il suffit de vérifier les points d'extrémité.

• En tant que microoptimization, vous pouvez toujours considérer annexant à l'image réelle deux valeurs - un pixel blanc et un pixel noir - pour que vous puissiez toujours itérer jusqu'à ce que vous trouver la valeur. Cela permet d'éliminer l'une des comparaisons de la boucle (la vérification pour voir si vous êtes en limites) et est recommandée par certains auteurs pour les tableaux très grandes.

• Si vous supposez que la plupart des images sont un beau mélange de blanc et noir et sont d'accord avec obtenir la mauvaise réponse une petite fraction du temps, vous pourriez envisager de sonder quelques endroits aléatoires et de vérifier si l'un d'entre eux sont la bonne couleur. Si oui, alors clairement un pixel de la couleur correcte existe et que vous avez terminé. Dans le cas contraire, exécutez une analyse complète linéaire. Pour les images qui sont un beau mélange de couleurs, cela pourrait vous faire économiser une énorme quantité de temps, puisque vous pouvez sonder un petit nombre d'endroits (par exemple, O (log n) d'entre eux) et finissent par éviter un énorme balayage linéaire dans de nombreux cas. Ceci est exponentiellement plus rapide qu'auparavant.

• Si chaque valeur est blanc ou noir, vous pouvez également envisager de stocker l'image dans un vecteur de bits. Cela compresser la taille du tableau par un facteur de la taille de mot machine Vous pouvez ensuite itérer (probablement entre 32-128x compression) à travers le réseau comprimé et voir si une valeur est identique égale à 0 pour voir si des pixels sont blancs. Cela permet aussi d'économiser une énorme quantité d'espace, et je voudrais vraiment suggère de faire cela car il fait beaucoup d'autres opérations facile ainsi.

  Hope this helps!

Utilisation de l'intégré pour Forach est un TAD plus rapidement que l'indexé pour l'ID en tant qu'IM élimine une vérification liée

for(int pix:pixels){
    if(pix!=0)
        return true;
}

Si votre tableau est vraiment grand, cela pourrait valoir la peine de se diviser et de conquérir. Autrement dit, attribuez des segments des données à plusieurs threads (probablement t threads où t est le nombre de cœurs de processeur disponibles). Avec un ensemble de données suffisamment volumineux, le parallélisme peut amortir le coût de démarrage du fil.