Поиск повторяющихся элементов в большом массиве

#java

Есть массив строк (String[]) размером в один миллион, и надо найти те строки, которые
повторяются.
Но при поиске стандартным методом (цикл в цикле) все это занимает очень много времени.
Как лучше это реализовать? И можно ли уложиться в 10 секунд?
    

Ответы

Ответ 1

Очень просто, но с дополнительными расходами памяти:


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


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

Увеличение расхода памяти вы можете почти и не ощутить, если хранить в множестве
прямо те же строчки, что в массиве (а не копии) по ссылкам (как в Java хранятся все
объекты). Если, конечно, у вас не совсем мелкие строки, но   чем больше в массиве дублирования,
тем меньше попадёт в множества, так что даже с мелкими может быть всё не так плохо.


Ответ 2

Тестовые данные. Х строк, первые У из которых уникальны, а оставшиеся Х-У - копии
этих У. Все строки одинаковой длины и состоят из символов с charcode-ами от 32 до 127.

private static final Random random = new Random();

private static String[] generateArray(int stringsTotalCount, int uniqueStringsCount,
        int stringLength)
{
    String[] array = new String[stringsTotalCount];
    for (int i = 0; i < uniqueStringsCount; i++)
    {
        array[i] = generateString(stringLength);
    }
    for (int i = uniqueStringsCount; i < array.length; i++)
    {
        int index = random.nextInt(uniqueStringsCount);
        array[i] = new String(array[index]);
    }
    return array;
}

private static String generateString(int stringLength)
{
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < stringLength; i++)
    {
        int charCode = random.nextInt(96) + 32;
        sb.append((char)charCode);
    }
    return sb.toString();
}


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

Первый алгоритм. Сравнение строк с помощью цикла в цикле. Несмотря на оптимизацию
(j = i + 1, break, duplicates.contains), алгоритм всё равно работает "за квадрат" (O(n^2)),
что приводит ко времени работы в несколько минут.

private static void compare(String[] data)
{
    Set duplicates = new HashSet<>();
    for (int i = 0; i < data.length; i++)
    {
        if (duplicates.contains(data[i]))
        {
            continue;
        }
        for (int j = i + 1; j < data.length; j++)
        {
            if (data[i].equals(data[j]))
            {
                duplicates.add(data[i]);
                break;
            }
        }
    }
    System.out.println(duplicates.size());
}


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

private static void oneMap(String[] data)
{
    Map map = new HashMap<>();
    for (String str : data)
    {
        if (!map.containsKey(str))
        {
            map.put(str, 1);
        }
        else
        {
            map.put(str, map.get(str) + 1);
        }
    }
    List duplicates = map.entrySet().stream()
            .filter(e -> e.getValue() > 1)
            .map(e -> e.getKey())
            .collect(Collectors.toList());
    System.out.println(duplicates.size());
}


Третий алгоритм. Использование двух HashSet: одного для уже найденных строк, второго
- для хранения дубликатов.

private static void twoSets(String[] data)
{
    Set foundStrings = new HashSet<>();
    Set duplicates = new HashSet<>();
    for (String str : data)
    {
        if (foundStrings.contains(str))
        {
            duplicates.add(str);
        }
        else
        {
            foundStrings.add(str);
        }
    }
    System.out.println(duplicates.size());
}


Четвёртый алгоритм. Построение префиксного дерева / использование ДКА для определения,
встречалась ли данная строка ранее.
! Возможно, реализация не является оптимальной. Отдельное хранение первой пары "символ
- состояние" (firstChar и firstState) ощутимо ускоряет работу при случайных строках.
При менее случайных строках прирост производительности может быть меньше.

private static class State
{
    private Map transitions;
    public boolean isFinal = false;
    private char firstChar = 0;
    private State firstState = null;

    public State get(char c)
    {
        if (firstState != null && firstChar == c)
        {
            return firstState;
        }
        if (firstState == null)
        {
            firstState = new State();
            firstChar = c;
            return firstState;
        }
        if (transitions == null)
        {
            transitions = new HashMap<>();
        }
        State state = transitions.get(c);
        if (state == null)
        {
            state = new State();
            transitions.put(c, state);
        }
        return state;
    }
}

private static void dfa(String[] data)
{
    State root = new State();
    Set duplicates = new HashSet<>();
    for (String str : data)
    {
        State state = root;
        for (int i = 0; i < str.length(); i++)
        {
            char c = str.charAt(i);
            state = state.get(c);
        }
        if (state.isFinal)
        {
            duplicates.add(str);
        }
        else
        {
            state.isFinal = true;
        }
    }
    System.out.println(duplicates.size());
}


Пятый алгоритм. Сортировка массива с последующим сравнением соседних элементов.

private static void sort(String[] data)
{
    Arrays.sort(data);
    Set duplicates = new HashSet<>();
    for (int i = 1; i < data.length; i++)
    {
        if (data[i - 1].equals(data[i]))
        {
            duplicates.add(data[i]);
        }
    }
    System.out.println(duplicates.size());
}


Результаты тестирования.


1000k строк, 100k уникальных, длина строки 20

compare    n/a ms
oneMap     290 ms
twoSets    280 ms
dfa        670 ms
sort       840 ms

1000k, 500k, 20

compare    n/a ms
oneMap     860 ms
twoSets    770 ms
dfa       2060 ms
sort      1300 ms

1000k, 500k, 10

compare    n/a ms
oneMap     320 ms
twoSets    240 ms
dfa       2020 ms
sort       810 ms



Указанные значения являются приблизительными средними значениями.
n/a означает, что программа работала больше минуты (>60k ms).