比较一个数据结构与另一个数据结构导致运行时间超过50分钟

我正在编写读取文本文件（每行一条推文）的代码，并通过每条推文将它与英文单词列表进行比较以查看是否该单词拼写错误。比较一个数据结构与另一个数据结构导致运行时间超过50分钟

所以英文单词列表也从文本文件中读入，然后存储在列表中。当我单独运行代码时，它在不到一秒的时间内运行。当我运行用于存储推文件中的每个单词的代码（不检查拼写）时，它将大约20-30秒将每个单词及其频率存储在HashMap<String, Integer>中。

但是，当我添加一行来检查单词拼写是否正确时，会导致可笑的运行时间增加，以至于在完成运行之前几乎可以观看电影。

调用isSpelledCorrectly(X)（它只调用list.contains(x)，其最坏情况下的运行时间为O（n））的一个简单方面，但它似乎相当混乱，它导致代码从30秒运行时间变为50分钟运行时间？

代码：

拼写：

static List<String> spellCheck = new ArrayList<String>(); 

public AssignTwo() throws IOException{ 
    spellCheck = initCorrectSpelling("C:\\Users\\Gregs\\InfoRetrieval\\src\\english-words"); 
} 

public static List<String> initCorrectSpelling(String filename) throws IOException { //store correct spelling of words in list 
    Scanner scanner = new Scanner(new FileInputStream(filename)); 
    try{ 
     while(scanner.hasNextLine()){ 
      String next = scanner.nextLine(); 
      spellCheck.add(next); 
     } 
    } 
    finally{ 
     scanner.close(); 
    } 
    return spellCheck; 
} 

public static boolean isSpelledCorrectly(String word){ //check if any given word is spelled correctly by seeing if it is 
    boolean output = false;        //contained within the spellCheck list 
    if(spellCheck.contains(word)) output = true;      
    return output; 
}

码存储鸣叫：

public static HashMap<String, Integer> misSpell; 
public AssignOne() throws IOException {   //read in file from path, test functions 
    index("C:\\Users\\Gregs\\InfoRetrieval\\src\\tweets"); 
} 

public static void index(String filename) throws IOException { 
    misSpell = new HashMap<String, Integer>(); 
    Scanner scanner = new Scanner(new FileInputStream(filename)); 
    try{ 
     while(scanner.hasNextLine()){ 
      String line = scanner.nextLine();  
      String[] lineArr = line.split(" "); 
      for(int i=3; i<lineArr.length; i++){ 
       int count=1; 
       lineArr[i] = lineArr[i].replaceAll("[^a-zA-Z0-9]", ""); 
       //if(!AssignTwo.isSpelledCorrectly(lineArr[i].toLowerCase())){ //with this line commented out, runtime <30sec, with line >50mins 
        if(misSpell.containsKey(lineArr[i].toLowerCase())){    
         count = 1 + misSpell.get(lineArr[i].toLowerCase());    
        } 
        misSpell.put(lineArr[i].toLowerCase(), count); 
       //} 
      } 
     } 
    } 
    finally{ 
     scanner.close(); 
    } 
}

在哪里可以提高代码或如何使对比更加高效什么建议吗？是否有更快的数据结构来拼写正确的单词？

来源

2016-11-26 NoName

List.contains（）是O（N），N是字典中单词的数量。使用HashSet，其中contains（）是O（1）。使用缓冲读卡器也会加快速度。 –

谢谢我会尝试，并给你一个运行时更新 – NoName

对每个单词三次调用toLowerCase（）也是一个浪费时间。 –

List.contains()是O（N），N是词典中单词的数量。

使用HashSet，其中是O（1）。

使用缓冲读取器也会加快速度。并且避免在每个单词上调用toLowerCase（）三次也是如此。

来源

2016-11-26 11:24:31

比较一个数据结构与另一个数据结构导致运行时间超过50分钟

回答

相关问题