Comment accélérer cet algorithme de comparaison d'objets?

Considérons une matrice de dimension Nx2, où chaque ligne contient les limites inférieure et supérieure d'un PDF uniforme (c'est-à-dire, la fonction de densité de probabilité).Comment accélérer cet algorithme de comparaison d'objets?

Je veux compter le nombre de chevauchements, où un chevauchement est définie comme étant la condition dans laquelle deux des PDF se chevauchent, par exemple:

PDF1: [2,5]
PDF2: [3,6]
Les deux Les fichiers PDF se chevauchent dans l'intervalle [3,5].

Il est évident que, si trois fichiers PDF p1, p2 et p3 se chevauchent, je compte trois chevauchements: p1 vs p2, p1 contre p3, p2 contre p3.

J'ai créé le code suivant Matlab qui compte les chevauchements:

for m = 1:N-1 
    for k = m+1:N 
     l1 = dataService.getObjectCoordinate(m,1); 
     l2 = dataService.getObjectCoordinate(k,1); 
     u1 = dataService.getObjectCoordinate(m,2); 
     u2 = dataService.getObjectCoordinate(k,2); 
     if (l1 <= l2 && l2 <= u1) || (l2 <= l1 && l1 <= u2) 
      numOverlaps = numOverlaps + 1; 
     end 
    end 
end

Cependant, comme vous pouvez l'imaginer, cela se passe comme O(N^2), qui est reeeeeally mal quand N est grand. J'ai commencé l'exécution il y a trois heures avec N=10000 et il fonctionne toujours. Pouvez-vous suggérer un moyen de réduire la complexité de l'algorithme proposé, en excluant peut-être certaines des comparaisons a priori?

Merci d'avance.

Source

2013-09-04 Eleanore

@ MZimmerman6: La question à laquelle j'ai lié a au moins une réponse qui le fait dans O (N · logN). –

@RodyOldenhuis Ouais je viens de regarder ça, et j'écris du code pour le faire en moins ... je pense. Nous verrons comment cela se passe. Jusqu'à présent ce que j'ai est en cours d'exécution en moins d'une seconde – MZimmerman6

Je reprends le commentaire que j'ai laissé plus tôt. Vous pouvez certainement le faire en moins de temps. Basé sur le lien fourni par Rody et Shoelzer, vous pouvez utiliser le code suivant pour effectuer cette opération dans le cadre d'un deuxième

tic 
numIntervals = 10000; 
ranges = sort(randi(100,[numIntervals,2]),2); 
[vals,idx] = sort(ranges(:,1)); 
ranges = ranges(idx,:); 
overlaps = false(numIntervals); 
for i = 1:numIntervals 
    temp = [ranges(:,1) <= ranges(i,2),ranges(:,1) >= ranges(i,1)]; 
    overlaps(:,i) = logical(all(temp,2)); 
end 
overlaps = tril(overlaps,-1); 
toc

ranges serait un tableau de vos points de début et de fin d'intervalle.

Le but de la partie inférieure du triangle à la fin est d'éliminer toutes les paires en double. Si P1 chevauche P2 alors évidemment P2 chevauchera P1. Cela supprimera également le fait que P1 se chevauche en supprimant la diagonale

Faites très attention à ce que cela fonctionne avec de grands nombres, car la quantité de mémoire utilisée remplira très rapidement votre RAM, selon la quantité dont vous disposez. J'ai essayé de tout garder comme un tableau logique pour aider à cela, mais il ajoute encore vite.

Vous pouvez certainement supprimer la partie de stockage et vous épargner une tonne de temps, mais alors vous devez gérer tout immédiatement dans chaque boucle.

Source

2013-09-04 13:29:15 MZimmerman6

Corrigez-moi si je me trompe, mais je pense que c'est juste O (N²) - à chaque itération vous faites des comparaisons 3N (n'oubliez pas le 'all()'), et vous faites une boucle N fois. Le fait qu'il fonctionne vite n'est pas parce que l'algorithme est rapide, c'est parce que 10000 n'est pas un si grand nombre. –

c'est probablement encore O (n^2) il utilise simplement la puissance des opérateurs logiques dans MATLAB. – MZimmerman6

Je me rends compte de cela, mais rappelez-vous que big-O fait référence à la complexité * algorithm *; il est implicitement supposé que la meilleure implémentation possible dans la langue est utilisée. Donc, en utilisant la puissance des opérateurs MATLAB * et * ayant un algorithme O (N · logN) rend les temps d'exécution comme celui que vous avez trouvé aussi possible pour N plus grand - votre O (N²) divergera beaucoup plus vite lorsque N grandit. –

Avez-vous profilé votre code? Une grande partie du problème peut être que vous appelez dataService.getObjectCoordinate() quatre fois par itération. Au lieu de cela, essayez d'obtenir toutes les données une fois et stockez-les dans des tableaux avant de faire des comparaisons. Ensuite, utilisez les techniques décrites dans les réponses aux questions Possible Interview Question: How to Find All Overlapping Intervals

Source

2013-09-04 13:11:53 shoelzer

Comment accélérer cet algorithme de comparaison d'objets?

Répondre

Questions connexes