Словари и сортировка подсчётом

Сортировка подсчетом

Пусть необходимо отсортировать массив из N целых чисел, каждое от 0 до K. Все эти числа довольно маленькие. Например, школьные оценки от 1 до 5.

Обычная сортировка(например, из классических быстрая, слиянием, пирамидальная) займет $O(N logN)$ . Но мы не будем пользоваться классической сортировкой, если значения довольно не большие.

Будем считать количество вхождений каждого числа, а затем выводить каждое число столько раз сколько оно встречалось. Это займет $O(N+K)$ и $O(K)$ дополнительной памяти.

Интервал значений можно сдвинуть, чтобы он был не от 0 до K, а от минимального до максимального значения в массиве.

Решение

Создаем массив и заполняем его нулями. Каждому числу соответсвует ячейка соответствующего индекса в массиве. Когда встречаем число увеличиваем счетчик в соответсвуюзей ячейке на единицу.

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

Мы потратим $O(K)$ времени и $O(K)$ памяти, где К количество возможных значений.

$O(K)$ памяти - тк нам нужно завести массив из К элементов.

$O(K)$ времени - тк на создание массива тоже тратится время, пропорционально его длине. Если не на выделение памяти, то на заполнение нулями точно потратится.

$O(N)$ времени - мы за один проход заполним этот массив, тк каждая операция это прибавление единицы и она занимает $O(1)$ времени. И поскольку чисел N, в сумме это займет $O(N)$ .

В итоге на построение массива уходит $O(N+K)$ времени и $O(K)$ дополнительной памяти. Тоже самое с выводом: мы пройдемся по всем возможным значениям - это цикл до К и в сумме мы совершим N действий на вывод. То есть на вывод мы тоже потратим $O(N+K)$ времени.

Если бы мы не делали нулевой элемент в массиве этобы уменьшило количество занимаемой памяти но затруднило и усложнило вычисление, тк пришлось бы постоянно отнимать дополнительное число.

Но если нужно отсортировать числа далекие от нуля, то этот интервал лучше перенести.

public static void countSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt(); // сложность O(N)
    int min = Arrays.stream(arr).min().getAsInt(); // сложность O(N)

    int k = max - min + 1;
    int[] array = new int[k];
    Arrays.fill(array, 0);

    for (int i = 0; i < arr.length; i++) {
        array[arr[i] - min] += 1;
    }

    int nowPos = 0;
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array[i]; j++) {
            arr[nowPos] = i + min;
            nowPos += 1;
        }
    }
}

Задача 1

Дано два числа X и Y без ведущих нулей. Необходимо проверить, можно ли получить первое из второго перестановкой цифр.

Посчитаем количество вхождений каждой цифры в каждое из чисел и сравним. Цифры будем постепенно добывать из числа справа с помощью %10 и /10. Разложим цифры в массивы по аналогии с сортировкой подсчетом и сравним их.

Циклом while проходим по каждой цифре пока после деления не останется 0. Такой способ возможен только если число без ведущих нулей. Это как раз наш случай. Раскладываем цифры в массив от 0 до 9, в соответсвии со значением индекса. Пришла цифра 9 увеличиваем на один значение в ячейке с индексом 9 и тд. Делаем это для обоих чисел и сравним эти массивы по элементно. Достаточно найти всего одно несовпадение.

Сортировка подсчетом уместна, когда разница между максимальным и минимальным значением небольшая и числа с одним и тем же значением встречаются достаточно часто, тогда N > K и сложность сортировки фактически стала $O(N)$ . Если это не так, то точная оценка $O(N+K)$ , но в случаях когда K большое, а N маленькое, сортировка подсчетом не лучший выбор. Можно вычислить конкретное значение K и сравнить с $N logN$ .

public static boolean isDigitPerMutation(int x, int y) {
    int[] digitsX = countDigits(x);
    int[] digitsY = countDigits(y);
    for (int i = 0; i < 10; i++) {
        if (digitsX[i] != digitsY[i]) {
            return false;
        }
    }
    return true;
}

public static int[] countDigits(int num) {
    int[] digitCount = new int[10];
    Arrays.fill(digitCount, 0);

    while (num > 0) {
        int lastDigit = num % 10;
        digitCount[lastDigit] += 1;
        num /= 10;
    }
    return digitCount;
}

Словари

Более универсальный алгоритм, но в некоторых случаях может работать хуже чем сортировка подсчетом.

Словарь - он как множество, но к каждому ключу приписано значение. В словаре есть пара ключ - значение (key, value). И все что происходит в множестве (подсчет хеша, раскладываение и тд), оно проходит только по ключу.

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

Искать по значению в словаре нельзя.

Сложность поиска в словарях $O(1)$ . НО константа большая. Тк может происходить расширение словаря, может считаться хеш функция и тд. Работает это медленее, чем доступ по индексу, как это происходит в сортировке подсчетом.

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

Сортировку подсчетом использовать неразумно, если данные разреженные(редкие вхождения, например числа до миллиарда).

Задача 1

На шахматной доске N x N находится M ладей (ладья бьет клетки на той же горизонтали и вертикали до ближайшей занятой) Определите сколько пар ладей бьют друг друга. Ладьи задаются парой чисел I и J, обозначающих координаты клетки.

$1<= N <= 10^9, 0<=M<=2*10^5$ .

Решение

Для каждой занятой горизонтали и вертикали будем хранить количество ладей на них. Количество пар в горизонтали (вертикали) равно количество ладей минус 1. Суммируем это количество пар для всех горизонталей и вертикалей.

Чтобы оценить время работы программы мы можем посмотреть на входные данные, значение N может достигать $10^9$ или $1 000 000 000$ - 1 миллиард операций. Даже на языке C, при наличии не примитивных операций, это может быть достаточно долго, для других языков тем более. Поэтому нужно ориентироваться на значение M, оно может достигать $2*10^5$ или $200 000$ - 200 тысяч оперций.

Ладья бьет другую ладью, если они стоят на одной вертикали или горизонтали.
Ферзь бьет другого ферзя, если они стоят на одной вертикали или горизонтали или на одной диагонмали(диагональ слева направо /, диагональ справа налево \).

Обратим внимание, что если на одной линии стоит 3 ладьи то они образуют 2 пары которые бьют друг друга. Если на одной линии 4 ладьи, то они образуют 3 пары и т.д. Получается что пар ладей на 1 меньше, чем количество ладей на одной линии.

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

public static int countBeatingRooks(int[][] rookcoords) {
    Map rooksInRow = new HashMap<Integer, Integer>();
    Map rooksInCol = new HashMap<Integer, Integer>();
    for (int i = 0; i < rookcoords.length; i++) {
        addRook(rooksInRow, rookcoords[i][0]);
        addRook(rooksInCol, rookcoords[i][1]);
    }
    return countPairs(rooksInCol) + countPairs(rooksInRow);
}

public static void addRook(Map<Integer, Integer> rowOrCol, int key) {
    if (!rowOrCol.containsKey(key)) {
        rowOrCol.put(key, 0);
    }
    rowOrCol.put(key, rowOrCol.get(key) + 1);
}

public static int countPairs(Map<Integer, Integer> rowOrCol) {
    int pairs = 0;
    for (Integer key : rowOrCol.keySet()) {
        pairs += rowOrCol.get(key) - 1;
    }
    return pairs;
}

Сложность данного решения составит $O(M)$ . N - никак не участвует в оценке сложности. Если нужно будет посчитать ферзей, то нужно завести 2 словаря для диагоналей, в которых в качестве ключа для диагонали из нижнего левого угала в правй верхний (/) будет сумма между координатами (row + col или x+y), а для диагонали из левого верхнего угла в нижний правый угол (\) будет разность между координатами (row - col или x-y).

Задача 2

Дана строка S. Выведите гистограмму как в примере (коды символов отсортированы)

S = Hello, world!

      #
      ##
##########
 !,Hdelorw

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

Решение

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

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

Для того чтобы вывести символы # по условию задачи, нужно найти максимальное значение(n), когда встречается один и тот же символ и для каждого символа в цикле пройтись от 1 до n и если значение меньше того что вышло в цикле то ставим пробел иначе ставим #.

public static void printChart(String s) {
    Map<Character, Integer> symCount = new HashMap();
    int maxSymCount = 0;
    char[] charArray = s.toCharArray();
    for (int i = 0; i < charArray.length; i++) {
        char sym = charArray[i];
        if (!symCount.containsKey(sym)) {
            symCount.put(sym, 0);
        }
        symCount.put(sym, symCount.get(sym) + 1);
        if (symCount.get(sym) > maxSymCount) {
            maxSymCount = symCount.get(sym);
        }
    }
    List<Character> sortedUniqSyms = symCount
            .keySet()
            .stream()
            .sorted()
            .collect(Collectors.toList());
    for (int i = maxSymCount; i > 0; i--) {
        for (Character sym : sortedUniqSyms) {
            if (symCount.get(sym) >= i) {
                System.out.print('#');
            } else {
                System.out.print(' ');
            }
        }
        System.out.println();
    }

    String str = sortedUniqSyms.stream()
            .map(String::valueOf)
            .collect(Collectors.joining());
    System.out.println(str);
}

Этот алгоритм не самый эффективный, во-первый вместо вызова функции print луше класть символы в массив и потом выводить строку через join, во-вторых в худшем случае этот алгоритм может работать за $O(N^2)$ или $O((N/2)^2)$

Задел под оптимизацию

Преждевременная оптимизация страшный грех :). Так как иногда нужно сделать быстро и нет времени на реализацию эффективных алгоритмов. В этом случае лучше сделать таким образом чтобы если вдруг придется решать проблему со скоростью было примерно понятно как это сделать при теущей реализации.

Всегда ли асмиптотически лучшее решение лучше?

Например есть 2 алгоритма:
линейный - $1000 * N$ - $O(N)$
алгоритм $2 * NlogN$ - $O(NlogN)$

На первый взгляд первый алгоритм лучше, но константа отличается в 500 раз. Для уточнения разделим обе части на N.

$2 * logN$ или $1000$

Теперь делим на 2.

$logN$ или $500$

Теперь то какой алгоримт лучше будет зависить от N.

При $N>2^{500}$ решение за $O(N)$ лучше, чем решение за $O(NlogN)$ , но $2^{500}$ это $3*10^{150}$ , что примерно в $10^{70}$ раз больше количества атомов во вселенной. И вряд ли наш алгоритм будут запускать для таких чисел.

В реальности разница констант в 500 раз все же случается редко.

Некоторые другие критерии качества алгоритма

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

Задача 3

Сгруппировать слова по общим буквам.

Sample Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
Sample Output: ["ate", "eat", "tea"], ["nat", "tan"], ["bat"]

Отсортируем в каждом слове буквы и это будет выступать в роли ключа, а значением будет список слов.

public static List groupWords(String[] words) {
    Map<String, List> groups = new HashMap();

    for (String word : words) {
        char[] sortedWord = word.toCharArray();
        Arrays.sort(sortedWord);
        String srtWord = new String(sortedWord);
        if (!groups.containsKey(srtWord)) {
            groups.put(srtWord, new ArrayList<Character>());
        }
        groups.get(srtWord).add(word);
    }

    List ans = new ArrayList();
    for (String sortedWord : groups.keySet()) {
        ans.add(groups.get(sortedWord));
    }

    return ans;
}

Вдруг слово будет длинное (N)? Сортировка займет $O(NlogN)$ . Количество различных букв в слове $K{\leq}N$ , можем посчитать количество каждой за $O(N)$ и отсортировать за $O(KlogK)$ с помощью сортировки подсчетом, теоретически

Задел под оптимизацию

Но так как в данный момент все успешно работает и нет времени на переделывание, то можно вынести шаги с сортировкой в отдельный метод.

Будет тормозить - посмотрим на профилировщике где, и если долго считается ключ - легко поправим на что-то более эффективное.

public static List groupWords(String[] words) {
    Map<String, List> groups = new HashMap();

    for (String word : words) {
        String groupKey = keyByWord(word);
        if (!groups.containsKey(groupKey)) {
            groups.put(groupKey, new ArrayList<Character>());
        }
        groups.get(groupKey).add(word);
    }

    List ans = new ArrayList();
    for (String groupKey : groups.keySet()) {
        ans.add(groups.get(groupKey));
    }

    return ans;
}

public static String keyByWord(String word) {
    char[] sortedWord = word.toCharArray();
    Arrays.sort(sortedWord);
    return new String(sortedWord);
}

Оптимизация

public static List groupWords(String[] words) {
    Map<String, List> groups = new HashMap();

    for (String word : words) {
        String groupKey = keyByWord(word);
        if (!groups.containsKey(groupKey)) {
            groups.put(groupKey, new ArrayList<Character>());
        }
        groups.get(groupKey).add(word);
    }

    List ans = new ArrayList();
    for (String groupKey : groups.keySet()) {
        ans.add(groups.get(groupKey));
    }

    return ans;
}

public static String keyByWord(String word) {
    char[] sortedWord = word.toCharArray();
    Map<Character, Integer> symCnt = new HashMap();
    for (char sym : sortedWord) {
        if (!symCnt.containsKey(sym)) {
            symCnt.put(sym, 0);
        }
        symCnt.put(sym, symCnt.get(sym) + 1);
    }
    ArrayList<String> lst = new ArrayList<>();

    for (char sym : symCnt.keySet().stream().sorted().collect(Collectors.toList())) {
        lst.add(Character.toString(sym));
        lst.add(symCnt.get(sym).toString());
    }
    return lst.stream()
            .map(String::valueOf)
            .collect(Collectors.joining());
}

В худших случаях этот алгоритм будет работать быстрее, но в среднем будет тормозить. И в некоторых случаях этот алгоритм можно сломать :)

Сомнительная оптимизация (?)

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

Вопросы для проработки

Как сджойнить массив символов в строку?

lst.stream().map(String::valueOf).collect(Collectors.joining());

Как отсортировать массив?

symCnt.keySet().stream().sorted().collect(Collectors.toList())

Смотрите также:

Словари и сортировка подсчётом

Сортировка подсчетом

Задача 1

Словари

Задача 1

Задача 2

Задел под оптимизацию

Всегда ли асмиптотически лучшее решение лучше?

Некоторые другие критерии качества алгоритма

Задача 3

Задел под оптимизацию

Оптимизация

Сомнительная оптимизация (?)

Вопросы для проработки

On this page