Wie kann ich Anagram-Programmcode schneller machen? (Java)

Question

Ich bin ein nicht so erfahrener Programmierer. Ich habe ein Anagramm-Programm geschrieben und das einzige Problem ist, dass es nicht schnell genug ist. Ich habe gesagt, dass meine verschachtelten for loop das Problem ist, aber ich kann nicht verstehen, wie es zu beheben (set1 ist ein HashSet mit allen Worten arbeite ich an, eine Karte ist ein LinkedHashMap<String, String> und Anagramm ein TreeMap<String, TreeSet<String>>):

for (String element : set1) { 
    char[] woord = element.toCharArray(); //alfabetical order of each word 
    Arrays.sort(woord); 
    String chartostring = new String(woord); 
    map.put(element, chartostring); // add each word with its sorted letters 
    TreeSet<String> order_words = new TreeSet<String>(); //creating list of anagrams 
    for (String o : map.keySet()) { //for each word 
     if (map.get(o).equals(chartostring)) { //check if there is a value in map which is equal to the sorted letters 
      order_words.add(o); //add word to list of anagrams 
      if (order_words.size() > 1) { //we want anagrams so only print if there are atleast 2 words 
       anagram.put(chartostring, order_words); 
      } 
     } 
    } 
} 

Kann mir bitte jemand helfen? Danke vielmals.

Answer 1

Die verschachtelte Schleife ist in der Tat langsam, weil Sie eine Map wie eine Liste iterieren. Wäre es nicht schön, wenn Sie die verschachtelte Schleife durch eine schnelle Suche in einer Hash-Map ersetzen könnten? Leider ist dies keine Option, wenn Sie mit Map<String,String> arbeiten, da mehrere Wörter eine identische sortierte Darstellung haben. Aus diesem Grund haben Sie eine Karte aus einem Wort in die sortierte Darstellung erstellt, nicht umgekehrt.

Was dies bedeutet, ist jedoch, dass Sie eine Karte aus einer sortierten Darstellung in eine Liste von Wörtern bauen:

Map<String,List<String>> sortedRepToWords 

Sie diese Karte in einer einzigen Schleife aufbauen können, bevor sie eine passende tun . Wenn diese Listenübersicht vorhanden ist, können Sie die verschachtelte Schleife eliminieren und sie durch ein Nachschlagen der gesamten Liste von sortedRepToWords ersetzen.

Answer 2

Ich weiß nicht, ob dies in Ihrem Fall besser ist, aber wenn ich key und value ein map brauche verwende ich die entrySet. So der Aufruf der get Methode avoied wird und ein Teil der Zeit wird gespeichert ...

https://stackoverflow.com/a/3870210/1811730

for (String element : set1) { 
    char[] woord = element.toCharArray(); //alfabetical order of each word 
    Arrays.sort(woord); 
    String chartostring = new String(woord); 
    map.put(element, chartostring); // add each word with its sorted letters 
    TreeSet<String> order_words = new TreeSet<String>(); //creating list of anagrams 
    for (Entry o : map.entrySet()) { //for each word 
     if (o.getValue().equals(chartostring)) { //check if there is a value in map which is equal to the sorted letters 
      order_words.add(o.getKey()); //add word to list of anagrams 
      if(order_words.size()>1){ //we want anagrams so only print if there are atleast 2 words 
        anagram.put(chartostring, order_words); 
       } 
     } 
    } 
} 

Wenn es nicht genug ist, ich glaube, Sie Ihren Code mit einer anderen Logik umschreiben sollten und versuchen, Implementieren Sie die Antwort von dasblinkenlight

Answer 3

Sie können dies in Reihenfolge von 1 (einzelne Schleife), wenn Sie das HashSet verwenden.

Set<char[]> dict_set = new HashSet<char[]>(); 
Set<char[]> anag_set = new HashSet<char[]>(); 

for (String element : set1) { 

// Sort the characters in string. 
char[] woord= element.toCharArray(); 
Arrays.sort(woord); 

//if already encountered add as a known anagram 
//else add the sorted charset to the dictionary. 

if (dict_set.contains(woord)) anag_set.add(woord) 
else dict_set.add(word); 

return anag_set; 
} 

Incase benötigen Sie alle Zeichenfolgen, die Anagramme und seine sortierte Form sind; Sie können eine Karte der sortierten Form und eine Liste aller zugehörigen Anagramme verwenden.

PS: es ist nur ein Pseudocode.

Answer 4

Einführung in Java 8 ...

import java.util.stream.Stream; 
import static java.util.stream.Collectors.*; 

Map<String, List<String>> tmp = set1.parallelStream() // Possibly using multiple cores... 
    .collect(groupingBy(s-> sortMe(s))); // One liner! 

List<List<String>> result = tmp.values().stream() 
    .filter(l -> l.size() > 1) // At least 2 anagrams 
    .collect(toList()); 

System.out.println(tmp); 
System.out.println(result); 

//...// 

// If you really want to use Java 8 for sorting a String... 
private String sortMe(String input) { 
    return Stream.of(input.split("")).sorted().collect(joining()); 
}