Эффективность поиска JList - PullRequest
Новая
       6

Эффективность поиска JList

3 голосов
/ 19 января 2012

Я наткнулся на некоторый код Java для поиска префикса в JList.Однако, глядя на это, основа алгоритма довольно неэффективна: используется линейный поиск по списку для каждого нажатия клавиш и медленное преобразование регистра в узком цикле.

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

for (int i=0; i < jList1.getModel().getSize(); i++) {
    String str = ((String)jList1.getModel().getElementAt(i)).toLowerCase();
    if (str.startsWith(m_key)) {
        jList1.setSelectedIndex(i); 
        jList1.ensureIndexIsVisible(i); 
        break;
    }
}

Ответы [ 4 ]

2 голосов
/ 19 января 2012

Вероятно, самая быстрая оптимизация (для времени кодирования, а не времени выполнения) состояла бы в сортировке списка и последующем бинарном поиске.У вас есть единовременная первоначальная плата за поиск (которая, если она будет часто использоваться, будет амортизироваться), а затем вы перейдете от O (n) к O (log (n)).По моему опыту бинарный поиск относительно прост и использует те же структуры данных, которые у вас уже есть.

Конечно, отсортированная структура n-дерева будет быстрее алгоритмически, но потребует новых структур данных и больше времени на кодирование/ тестирование.Решите, где вы хотите провести время.

2 голосов
/ 19 января 2012

Я не согласен со всеми ответами, опубликованными здесь (и немного зашифрованными JB Nizet). Возможной альтернативой JList является JTable с одним столбцом (с TableHeader или без него). JTable имеет хорошую реализацию Сортировка и фильтрация .

2 голосов
/ 19 января 2012

Для быстрого изменения рассмотрим 

String str = ((String)jList1.getModel().getElementAt(i));
str.substring(1, m_key.length()).equalsIgnoreCase(m_key);

И на шаг впереди - ваша собственная реализация startsWithIgnoreCase, которая должна быть быстрой и легкой для написания.

РЕДАКТИРОВАТЬ: Это похоже на прокрутку списка до элемента, который соответствует пользовательскому вводу. Вы должны определенно рассмотреть более сложную структуру данных. Это сделано много, возможно, вы сможете найти какой-то эффективный алгоритм в сети.

0 голосов
/ 19 января 2012

Обязательно не просматривайте весь свой список на каждой итерации.Вы можете выполнить (n!) Итераций в списке, где (n) - это все, что вам нужно.

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

...