如何减少搜索时间？（编辑1）

Question

我的代码有问题，当我调用somme_2方法时运行程序花费的时间太长，我想减少运行时间。顺便说一句，我在这个程序中使用的 txt 文件几乎包含 500_000 行。您知道如何解决吗？

这是我的主要

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        Somme2 somme2 = new Somme2("src/dico.txt");
        //somme2.remove(alphabeticalOrder("Amsterdam" + "ADN"), "adn");
        //somme2.remove(alphabeticalOrder("Amsterdam" + "ADN"), "riflassent");
        somme2.somme_2(alphabeticalOrder("volontiers" + "tranquillement"));

    }

    private static String alphabeticalOrder(String word) {
        word = word.toLowerCase();
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < word.length(); i++) {
            list.add(word.charAt(i));
        }
        Collections.sort(list);
        String string = "";
        for (int i = 0; i < list.size(); i++) {
            string = string + list.get(i);
        }
        return string;
    }
}

这是我的 class，其中包含 somme_2 函数：

import java.io.FileNotFoundException;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.*;

public class Somme2 {
    private String path;

    public Somme2(String path) {
        this.path = path;
    }

    /***
     * values() returns a list which contains every word in our file.
     * @return List<String>
     * @throws FileNotFoundException
     */
    private List<String> values() throws IOException {
        return Files.readAllLines(Path.of(path));
    }

    /***
     * alphabeticalOrder() returns the word in the parameter, alphabetically
     * @param word
     * @return String
     */
    private String alphabeticalOrder(String word) {
        word = word.toLowerCase();
        char[] chars = word.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }

    /***
     * addToHashMap() returns a hashMap, which uses as a key alphabetically words, and as value classical words
     * @return HashMap<String, List<String>>
     * @throws FileNotFoundException
     */
    private HashMap<String, List<String>> addToHashMap() throws IOException {
        HashMap<String, List<String>> hashMap = new HashMap<>();
        for (String value : values()) {
            String word = alphabeticalOrder(value);
            if (hashMap.containsKey(word)) {
                hashMap.get(word).add(value);
            }
            else {
                List<String> list = new ArrayList<>();
                list.add(value);
                hashMap.put(word, list);
            }
        }
        return hashMap;
    }

    /***
     * findTheLetter return the index of the letter
     * @param letter
     * @param word
     * @return
     */
    private int findTheLetter(char letter, char[] word) {
        for (int i = 0; i < word.length; i++) {
            if (word[i] == letter) {
                return i;
            }
        }
        return 0;
    }

    private char[] removeLetter(char letter, char[] word) {
        int x = findTheLetter(letter, word);
        char[] newWord;
        if (word.length == 1) {
            newWord = new char[word.length];
        } else {
            newWord = new char[word.length - 1];
        }
        for (int i = 0; i < word.length - 1; i++) {
            if (i < x) {
                newWord[i] = word[i];
            }
            else {
                newWord[i] = word[i + 1];
            }
        }
        return newWord;
    }

    public String remove(String word, String string) {
        char[] myWord = string.toCharArray();
        char[] words = word.toCharArray();
        for (int i = 0; i < string.length(); i++) {
            words = removeLetter(myWord[i], words);
        }
        return new String(words);
    }


    /***
     * somme_2
     * @param alph
     * @throws FileNotFoundException
     */
    public void somme_2(String alph) throws IOException {
        HashMap<String, List<String >> hashMap = addToHashMap();
        List<String> strings = new ArrayList<>();
        strings.addAll(hashMap.keySet());
        String alphWord = "" + alph;
        for (String string : strings) {
            if (hashMap.containsKey(remove(alphabeticalOrder(alphWord), string))) {
                System.out.println("\"" + hashMap.get(string) + "\" and \"" + hashMap.get(remove(alphWord, string)) + "\" give \"" + alphWord + "\"");
                return;
            }
        }
        System.out.println("There are no words");
    }
}

如果您想知道，这是 txt 文件的一部分：

A
ABS
ADN
ADNc
ADP
ADSL
AIEA
ARN
ARNm
ASBL
ASC
ASCII
AUD
Aarhus
Aaron
Aarschot
Abbeville
Abd
Abdelkader
Abel
Abidjan
Abitibi-Témiscamingue
Abkhazie
Abraham
Abu
Abuja
Abymes
Abyssinie
Acadie
Acapulco
Accra
Achaïe
Achgabat

我刚刚解决了时间问题，但现在我的程序有时会显示如下结果： “[constitutionnaliserions]”和“[V, v]”给出“aeeeiilllmnnnooqrrstttuv”

这是错误的，因为按字母顺序排列的“constitutionnaliserions”+“V”没有给出“aeeeiilllmnnnooqrrstttuv”。

感谢您的帮助！

Answer 1

你肯定能做一件事。让我列出您可以做些什么来改善您的运行时间：

将 word.length() 移到 for 循环之外，例如：String wordSize=word.length();
将 strings.size() - 1 移动到 for 循环之外，如 int stringsSize=strings.size()-1;
在 Java 的情况下，您可以选择 TreeSet，它是 Set 接口的实现。您可以将 Collection 对象传递给此 class 的构造函数，它将自动对对象进行排序。此外，当您添加任何对象时，它将按排序顺序放置。
也不要 system.out.println 因为它是同步方法，最好将输出记录到文件位置..

希望这个答案能帮助您改进运行时间。

Answer 2

有很多方法可以改进您的代码。

让我们从最重要的部分开始：算法

您遍历所有可能的对并检查条件，但您只能遍历所有单词 1 次，并为每个单词尝试找到“互补”单词。

示例：alph = 'aabbcc' 并且在当前对所有单词的迭代中我们有 word = 'acc'。我们想在我们的文件中找到另一个词 (complementaryWord)，它与 word 结合会给我们 alph。很明显，这个complementaryWord应该是abb（abb + acc = aabbcc），这个词很容易找到，因为你已经有了hashmap了.

总体而言，它将复杂性从 O(n^2) 提高到 O(n)。

代码改进

alphabeticalOrder 做了很多不必要的对象分配，整体看起来不太好。尝试在此处直接使用 char[]。此外，如果您知道单词可能只包含特定的字母集（比如只包含拉丁字母或其他字母表），您可以使用 bucket sort 来提高时间复杂度。
Scanner 对于大输入文件来说很慢。例如，使用 BufferedRead 或使用较新的 Files.readAllLines().
读取行
删除重复计算：例如，计算alphabeticalOrder(value)一次并将结果存储在变量中。
在addToHashMap()use computeIfAbsent()to make it shorter and clearer
使用 equals() 来比较字符串而不是 hashCode()。如评论中所述，如果 s1.hashCode() == s2.hashCode() 并不意味着 s1.equals(s2).

Answer 3

好的，我只是添加了一个 if 来检查我的测试是否正确，这很有效，感谢您的帮助！

    /***
     * somme_2
     * @param alph
     * @throws FileNotFoundException
     */
    public void somme_2(String alph) throws IOException {
        HashMap<String, List<String >> hashMap = addToHashMap();
        List<String> strings = new ArrayList<>();
        strings.addAll(hashMap.keySet());
        String alphWord = "" + alph;
        for (String string : strings) {
            if (hashMap.containsKey(remove(alphabeticalOrder(alphWord), string))) {
                if (alphabeticalOrder(string + remove(alphabeticalOrder(alphWord), string)).equals(alphabeticalOrder(alphWord))) {
                    System.out.println("\"" + hashMap.get(string) + "\" and \"" + hashMap.get(remove(alphWord, string)) + "\" give \"" + alphWord + "\"");
                    System.out.println("\"" + string + "\" and \"" + remove(alphWord, string) + "\" give \"" + alphWord + "\"");
                    return;
                }
            }
        }
        System.out.println("There are no words");
    }

如何减少搜索时间？（编辑1）

How can I reduce the time of the search? (edit1)

java

performance

hashmap

让我们从最重要的部分开始：算法

代码改进

如何减少搜索时间？ （编辑1）

How can I reduce the time of the search? (edit1)

java

performance

hashmap

让我们从最重要的部分开始：算法

代码改进

如何减少搜索时间？（编辑1）