J'ai des millions de matrices de taille fixe (100) int. Chaque tableau est trié et a des éléments uniques. Pour chaque tableau, je souhaite trouver tous les tableaux qui ont 70% d'éléments communs. À l'heure actuelle, je reçois environ 1 million de comparaisons (en utilisant Arrays.BinySearch ()) par seconde, qui est trop lente pour nous.
Quelqu'un peut-il recommander un meilleur algorithme de recherche?
3 Réponses :
Vous pouvez essayer un trier de fusion ignorer des doublons. Ceci est une opération O (n) pour trier des tableaux. Si les deux tableaux ont 70% d'éléments en commun, la collection résultante aura 130 ou moins uniques. Dans votre cas, vous n'avez pas besoin du résultat, vous ne pouvez donc pas compter le nombre d'entrées uniques et arrêter dès que vous atteignez 131 ou la fin des deux tableaux.
éditer (2) Le code suivant peut faire ~ 176 milliards de dollars. Comparativement en environ 47 secondes en utilisant 4 cœurs. Faire le code multi-threadé avec 4 cours n'était que de 70% plus rapide.
Utilisation de Bitset ne fonctionne que si la plage des valeurs INT est relativement petite. Sinon, vous devez comparer l'int [] (j'ai laissé le code dans si vous en avez besoin)
Vous voudrez peut-être regarder des filtres de fleurs.
Votre résultat est donc une liste de paires de matrices avec au moins 70 éléments communs?
Les matrices statiques sont-elles une fois que la comparaison commence? Les nouveaux tableaux sont-ils générés tout le temps? En d'autres termes, est-il possible de convertir / de préproduire les tableaux dans une autre structure de données pour optimiser la recherche?
Ouais, le résultat est une liste de paires de matrices avec au moins 70 éléments communs.
Ouais, les tableaux sont statiques et numéros de tableaux comme étant également fixes.
En outre, combien de matchs attendez-vous? Les INT sont-ils grossièrement uniformément distribués? Je demande cela parce que s'il n'y a pas beaucoup de matchs, alors l'exclusion heuristique pourrait aider.
J'attends environ 10% des matchs sur la base de mon ensemble de données initial.
Pas beaucoup d'idée de floraison des filtres. Laissez-moi obtenir des informations à ce sujet. Merci de suggestion.
Utilisation de
Arrays.binaireRearch () n'a aucun sens ici pour moi. Pour comparer deux tableaux, il vous suffit de passer les deux en parallèle et de compter les éléments communs à la volée. Ce que je veux dire, c'est très similaire à Mergesort.Avec des matchs à 10% et des millions de matrices, vous obtenez plus de 1E6 * 1E6 * 0,1 = 1E11 paires correspondantes, c'est un peu trop, n'est-ce pas? Je suppose que j'ai mal compris quelque chose. Pourriez-vous clarifier cela? Une autre question: quelle gamme a-t-elle réside dans l'INT?
Ouais, la paire correspondante est énorme. Les INT sont partout sur la place. Pas de portée particulière. À l'heure actuelle, nous faisons cette comparaison dans la carte Réduire le cadre. Mais même avec 10 machines, sa difficulté à obtenir le processus dans un délai raisonnable. Je suis donc essai pour optimiser la comparaison sur une seule machine avant de passer au cadre distribué.
Suis-je le seul à penser que c'est exactement le genre de chose qui pourrait être écrit en montage?