Сравнение одной структуры данных с другой, результатом которой является время работы более 50 минут

Question

Я пишу код, который читается в текстовом файле (каждая строка чирикает), и проходит через каждый твит, сравнивая его со списком английских слов, чтобы узнать, слово написано неправильно.

Таким образом, список английских слов считывается из текстового файла, а затем сохраняется в списке. Когда я запускаю код только для этого, он работает менее чем за одну секунду. Когда я запускаю код для хранения каждого слова в файле твита (без проверки орфографии) для 100 000 твитов, он сохраняет каждое слово и его частоту в HashMap<String, Integer> примерно за 20-30 секунд.

Но когда я добавляю строку, чтобы проверить, правильно ли написано это слово, это вызывает смехотворное увеличение времени выполнения до такой степени, что я мог почти смотреть фильм до его окончания.

Простого аспект вызова 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; 
} 

Код хранения Tweets:

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(); 
    } 
} 

Любое предложение о том, где, чтобы улучшить код или как сделать сравнения более эффективным? Есть ли более быстрая структура данных для правильно написанных слов?

Answer 1

List.contains() is O (N), N - количество слов в словаре.

Используйте HashSet, где - O (1).

Использование буферизованного считывателя также ускорит работу. И избегать вызова toLowerCase() три раза на каждое слово тоже.