Увеличение скорости сортировки большого списка строк по символам в Java - PullRequest
Новая
       8

Увеличение скорости сортировки большого списка строк по символам в Java

1 голос
/ 05 апреля 2020

Я написал код, который запускает список строк и возвращает список наименее часто встречающихся символов во всем списке строк.

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

Например, если задан список: ["hello", "my", "name", "is", "inigo", "montoya", "you", "killed", "my", "father", "prepare", "to", "die"]. Мой код возвращает: [s, g, u, k, f, h, d, p, n, t, r, l, m, y, a, i, o, e], где s - наименее часто встречающаяся буква в списке строк, а e - наиболее часто встречающаяся буква в списке. Результирующий список будет затем возвращать слова, содержащие наименее часто встречающиеся буквы, и так далее. Например: ["is", "inigo", "you", "killed", "father", "hello", "die", "prepare", "name", "montoya", "to", "my"]

Вот мой код, который находит наименее часто встречающиеся буквы: 

    public static void method(List<String> words)
    {
        Map<Character, Integer> elemCount = new LinkedHashMap<>();
        for (String word : words)
        {
            for (int i = 0; i  < word.length(); i++)
            {
                if (elemCount.containsKey(word.charAt(i)))
                {
                    elemCount.put(word.charAt(i), elemCount.get(word.charAt(i)) + 1);
                }
                else
                {
                    elemCount.put(word.charAt(i), 1);
                }
            }
        }
        ArrayList<Character> sortedElems = new ArrayList<>();
        LinkedList<String> sorted = new LinkedList<>();
        elemCount.entrySet().stream().sorted(
        Map.Entry.comparingByValue()).forEach(entry -> 
        { 
            for (int i = 1; i <= entry.getValue(); i++)
            {
                if (sortedElems.contains(entry.getKey()) == false)
                {
                    sortedElems.add(entry.getKey());
                }
            }
        }
        );

А вот код, в котором я пытаюсь отсортировать по наименее частым символам, найденным в строка: 

        for (int i = 0; i < sortedElems.size(); i++)
        {
            for (String word : words)
            {
                char x = sortedElems.get(i);
                CharSequence c = x + "";
                if (word.contains(c) == true && sorted.contains(word) == false)
                {
                    sorted.add(word);

                }
            }
        }
        System.out.println(sorted);

Ответы [ 2 ]

1 голос
/ 05 апреля 2020

Это, кажется, работает довольно хорошо. Я отказался от потокового подхода, так как он был слишком медленным. 

        List<String> words = new ArrayList<>(List.of("hello", "my",
                "name", "is", "inigo", "montoya", "you", "killed",
                "my", "father", "prepare", "to", "die"));

        // frequency count.
        int[] chars = new int[256];
        for (String w : words) {
            for (char c : w.toCharArray()) {
                chars[c]++;
            }
        }
        // find minimum used character
        Map<String, Integer> mins = new HashMap<>();
        for (String w : words) {
            if (!mins.containsKey(w)) {
                int v = Integer.MAX_VALUE;
                for (char c : w.toCharArray()) {
                    if (chars[c] < v) {
                        v = chars[c];
                    }
                }
                mins.put(w, v);
            }
        }

        Comparator<String> comp1 =
                (String a, String b) -> a.compareTo(b);
        Comparator<String> comp =
                (a, b) -> mins.get(a).compareTo(mins.get(b));
        comp = comp.thenComparing(comp1);

        // sort first on character then lexically
        words.sort(comp);
        words.forEach(System.out::println);

Вот подсчет частоты 

1=[f, g, k, s, u]
2=[d, h, p]
3=[n, r, t]
4=[a, l, m, y]
5=[i]
6=[o]
7=[e]

И слова в отсортированном порядке 

father
inigo
is
killed
you
die
hello
prepare
montoya
name
to
my
my
0 голосов
/ 05 апреля 2020

Это мои соображения, которые не уместились в комментарии.

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

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

Для сложной части мы можем отсканировать массив и вставить каждое слово (или указатель на каждое слово) в b-дерево, механизм разбиения которого использует Score, вычисленный по the fly, используя простую функцию, которая принимает в качестве параметров текущее слово и гистограмму.
Наконец, отсканируйте b-дерево, чтобы извлечь окончательный массив со всеми аккуратно отсортированными словами.

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

...