Java - Как эффективно отображать слова из списка слов при вводе

Я сделал небольшую программу на Java, которая загружает список слов из текстового файла, который выбирает пользователь, и сохраняет его слово за словом в TreeSet. Теперь мне нужно написать функцию, которая всякий раз, когда пользователь вводит что-то в текстовое поле (keyPressed), вызывает функцию и находит/возвращает все слова в этом TreeSet, которые начинаются с букв, введенных пользователем. Я новичок в использовании Наборы, поэтому моим решением будет итерация от первого до последнего элемента в наборе и распечатка тех, которые удовлетворяют критериям:

Iterator <String>itr = dictionary.iterator();
String currentWord;
String tempUserInput = "av"; // Temporary, to simulate user input
while(itr.hasNext()){
   currentWord = itr.next();
   if (currentWord.startsWith(tempUserInput)) {
      System.out.println(currentWord); // Temporary, to simulate output
   }
}

Это работает правильно, но, поскольку для возвращаемого значения необходимо передать более 300 000 слов, мой вопрос: есть ли более эффективное решение этой проблемы?


java iterator startswith treeset
person Vorta    schedule 11.11.2012    source источник

Ответы (1)


arrow_upward
3
arrow_downward

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

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

public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)

Это может работать, передавая в качестве fromElement текущую набранную строку, а в качестве toElement ту же строку с добавленным достаточным количеством 'z' символов, что и самая длинная строка в наборе (эта длина может быть рассчитана при заполнении TreeSet). Например:

subSet("foo", true, "foozzzzzzzz", true);
person Jack    schedule 11.11.2012
comment
subSet(foo, true, foo+�, false); охватывает все случаи. - person Fabien; 28.11.2012