Почему производительность хешсета намного выше, чем список? - PullRequest
Новая
       8

Почему производительность хешсета намного выше, чем список?

0 голосов
/ 14 января 2019

Эта проблема из кода leetcode (https://leetcode.com/problems/word-ladder/)!

Учитывая два слова (beginWord и endWord) и список слов словаря, найдите длину кратчайшей последовательности преобразования от beginWord до endWord, такую ​​что:

Одновременно можно изменить только одну букву. Каждое преобразованное слово должно существовать в списке слов. Обратите внимание, что beginWord не является преобразованным словом. Примечание:

Вернуть 0, если такой последовательности преобразования нет. Все слова имеют одинаковую длину. Все слова содержат только строчные буквенные символы. Вы можете предполагать, что в списке слов нет дубликатов. Вы можете предположить, что beginWord и endWord не пусты и не совпадают.

Это мой код, выполнение которого занимает 800 мс: 

class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList){
    if(!wordList.contains(endWord))
        return 0;
    int ret = 1;
    LinkedList<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<String>();
    queue.offer(beginWord);
    queue.offer(null);
    while(queue.size() != 1 && !queue.isEmpty()) {
        String temp = queue.poll();
        if(temp == null){
            ret++;
            queue.offer(null);
            continue;                
        }
        if(temp.equals(endWord)) {
            //System.out.println("succ ret = " + ret);
            return ret;
        }
        for(String word:wordList) {           
            if(diffOf(temp,word) == 1){
                //System.out.println("offered " + word);
                //System.out.println("ret =" + ret);
                if(!visited.contains(word)){
                visited.add(word);
                queue.offer(word); 
                }
            }
        }
    }
    return 0;
}
private int diffOf(String s1, String s2) {
    if(s1.length() != s2.length())
        return Integer.MAX_VALUE;
    int dif = 0;
    for(int i=0;i < s1.length();i++) {
        if(s1.charAt(i) != s2.charAt(i))
            dif++;
    }
    return dif;    
}
}

Вот еще один код, для запуска которого требуется 100 мс: 

class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> set = new HashSet<>(wordList);
    if (!set.contains(endWord)) {
        return 0;
    }

    int distance = 1;
    Set<String> current = new HashSet<>();
    current.add(beginWord);

    while (!current.contains(endWord)) {
        Set<String> next = new HashSet<>();

        for (String str : current) {
            for (int i = 0; i < str.length(); i++) {
                char[] chars = str.toCharArray();

                for (char c = 'a'; c <= 'z'; c++) {
                    chars[i] = c;
                    String s = new String(chars);

                    if (s.equals(endWord)) {
                        return distance + 1;
                    }

                    if (set.contains(s)) {
                        next.add(s);
                        set.remove(s);
                    }
                }
            }
        }
        distance++;

        if (next.size() == 0) {
            return 0;
        }
        current = next;
    }

    return 0;
}
}

Я думаю, что второй код менее эффективен, потому что он проверяет 26 букв для каждого слова. Почему это так быстро?

1 Ответ

0 голосов
/ 15 января 2019

Короткий ответ: Ваш поиск в первом дыхании на несколько порядков больше сравнивается на «единицу расстояния до слова» (далее - итерация).

  • Вы сравниваете каждого кандидата с каждым оставшимся словом. Временная сложность T (N × n) за итерацию,
  • Они сравнивают каждого кандидата с искусственно созданными «следующими» кандидатами. И поскольку они строят кандидатов, им не нужно «вычислять» расстояние. Для простоты я предполагаю, что оба (создание или проверка) имеют одинаковое время выполнения. Сложность по времени составляет T (26 × l × n) за итерацию.

(N = размер списка слов, n = количество кандидатов на эту итерацию, l = длина слова)

Конечно, 26 × l × n намного меньше, чем N × n, потому что длина слова мала, но список слов огромен.

Я попробовал вашу процедуру на ("and","has",[List of 2M English words]) и через 30 секунд я убил ее, потому что думал, что она разбилась. Это не разбилось, это было просто медленно. Я перешел к другому списку слов, состоящему из 50 КБ, и теперь у вас 8 секунд, вместо 0,04 с.

В моем списке слов N = 51306 есть 2167 трехбуквенных слов. Это означает, что на каждое слово в среднем приходится 3 × cbrt (2167) возможных кандидатов, что составляет n≈38,82.

  • Их ожидаемая производительность: T (26 × l × n) ≈ T (3027) работа за итерацию,
  • Ожидаемая производительность: T (N × n) ≈ T (1991784) работы на одну итерацию.

(при условии, что список слов не становится короче; но при таком количестве слов разница незначительна)

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

...