Disons que j'ai une chaîne et je veux voir combien de fois les mots dans la matrice ci-dessous correspondent à mon chaîne psudocode la réponse serait "3" juste curieuse quelle est la façon la plus efficace de le faire en Java?
5 Réponses :
Je stockerais probablement les mots dans l'entrée dans un hashset, puis itérer sur la matrice et voir si chaque mot dans le tableau est .Contient dans l'ensemble.
Ici, il est en code ... l'entrée est " dans le monde entier en 80 jours ". P>
1 a: 235000 1 b: 351000 1 c: 75000 1 d: 10725000
quelque chose comme ça? Pas sûr de "plus efficace", assez simple.
Set<String> s1 = new HashSet<String>(Arrays.asList("This is a test string and I have some stopwords in here".split("\\s")));
Set<String> s2 = new HashSet<String>(Arrays.asList("a", "and", "the", "them", "they", "I"));
s1.retainAll(s2);
System.out.println(s1.size());
La chose la plus efficace à faire est de trier à la fois "test" et "tableau", puis itérer sur les deux: n.log (n) + n
test -> ['A', 'et', 'a' j'ai ',' ici ', dans, est, ..., "ça"] Array -> ['A', 'et', 'Le', ',', ',' ils ',' ils ',' i ']
Matchs de test de tableau 'A' 'A' 1 'A' 'et' 1 'et' 'et' 2 'et' '' 'a' 2 'le' 'ici' 2 'le' 'in' 2 'Le' 'est' 2 ...
@Airculez c'est, car les deux tableaux commandés sont traversés simultanément. Le seul problème avec cet algorithme est que ce n'est pas si trivial d'implifier :)
+1, mais ce n'est pas la façon la plus efficace. Bien que nous avons ici (n journal (n)), les opérations de hachage prennent une heure constante et ainsi l'objectif peut être atteint dans O (n).
@Aircule pas comme ça. Vous avez deux index différents (I et J) et augmentez celui avec la plus petite valeur: si (a [i] <= b [j]) {++ i} else {++ j};
Gardez deux pointeurs, un qui garde une trace de votre position dans «Test» et un dans «Array», disons i et j. Ensuite, vous avez quelques conditions: si T [I] == A [J], ajoutez le mot à votre ensemble, incrément i et j. Si T [I]> A [J], J ++. sinon, j'ai ++. De cette façon, vous pouvez itération à travers les deux tableaux de O (n) temps.
@ Nikita-Rybak Hashing semble amusant, mais une fois que vous l'avez implémenter, vous vous rendrez compte que c'est un énorme goulot d'étranglement dans le processus. Même si vous utilisez un hachage roulant.
@Aircule Je ne sais pas quel est le hachage roulant, mais je n'ai jamais entendu aucune plainte de performance sur les hachages. (Not Hashset en particulier, mais idée en général) Le hash n'est qu'un tableau, après tout.
Une variation mineure sur la réponse de Nikita (UP 1 pour Nikita). Si vous utilisez une liste pour S1, vous obtenez le nombre d'occurrences (au cas où un mot apparaît plusieurs fois dans la phrase).
Stockez vos chaînes dans HASHTABLE (HASHMAP de (string et entier)), puis itérateur sur le texte et augmentez la valeur entière du mot correspondant dans HASHTABLE. Ensuite, itérateur sur Hashtable et somme toutes les valeurs entières.
Question intéressante, laissez-moi voir si je peux trouver quelque chose de mieux que l'algorithme naïf
Qu'en est-il des répétitions? Réponses ci-dessous lire les données en ensembles, qui marquerait 3 pour "A et le" mais seulement 1 pour "A A A". Est-ce le comportement souhaité, ou devrait-il faire rapport 3?