4

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

0

2 ответа 2

6

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

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

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

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

11
  • А разве Set подойдет? При каждой вставке он будет проверять есть ли такой или нет. Под конец операции вставки будут очень медленными
    – user194625
    Commented 12 мар. 2017 в 6:02
  • 2
    @Flippy при использовании реализации Hashset поиск, вставка удаление выполняются за константное время не зависимо от размера.
    – temq
    Commented 12 мар. 2017 в 6:29
  • @temq, спасибо буду знать
    – user194625
    Commented 12 мар. 2017 в 6:30
  • 1
    Гарантированное надежное решение, которое не зависит от функции хеширования, это положить все строки в бор.
    – pavel
    Commented 12 мар. 2017 в 8:18
  • @pavel да, это одна из реализаций множества для строк. Но операции с ним логарифмические, хэшсет может оказаться пошустрее. Но алгоритму, в целом, пофиг, можно всё забенчмаркать и решить :)
    – user181100
    Commented 12 мар. 2017 в 8:24
5

Тестовые данные. Х строк, первые У из которых уникальны, а оставшиеся Х-У - копии этих У. Все строки одинаковой длины и состоят из символов с 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<String> 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<String, Integer> map = new HashMap<>();
    for (String str : data)
    {
        if (!map.containsKey(str))
        {
            map.put(str, 1);
        }
        else
        {
            map.put(str, map.get(str) + 1);
        }
    }
    List<String> 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<String> foundStrings = new HashSet<>();
    Set<String> 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<Character, State> 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<String> 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<String> 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());
}

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

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

    compare    n/a ms
    oneMap     290 ms
    twoSets    280 ms
    dfa        670 ms
    sort       840 ms
    
  2. 1000k, 500k, 20

    compare    n/a ms
    oneMap     860 ms
    twoSets    770 ms
    dfa       2060 ms
    sort      1300 ms
    
  3. 1000k, 500k, 10

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

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

11
  • тут на самом деле есть проблема - вы не делаете копии строки. У вас просто копируется указатель. Используете честное копирование с созданием новой строки. Иначе даже хеш закешируется в самой строке. (Они тупо по == будут равны). Да и код dfa работает как-то сильно долго в случае 2 (явно что-то не так). Вот пример ideone.com/ZPTUoK на С++, я не использовал Map а просто массив, но вроде бы код одинаковый.
    – pavel
    Commented 12 мар. 2017 в 15:48
  • @pavel про жутко сомнительные результаты работы варианта с ДКА я писал ещё в комментариях к ответу D-side, но от первой версии реализации получилось повысить производительность только процентов на 10. Использование массива вместо Map не внушает оптимизма, ибо нужно будет рассчитывать алфавит, да и charcode-ы в нём не обязаны идти подряд: например, могут быть латинские буквы и кириллица. Насчет не использования настоящих копий строк - попробую с настоящими, но, надеюсь, результаты от этого не сильно изменятся.
    – Regent
    Commented 12 мар. 2017 в 16:19
  • предложу еще блум фильтр
    – etki
    Commented 12 мар. 2017 в 18:55
  • @etki а что насчет ложных срабатываний? Получается, в случае положительного результата всё равно придётся сравнивать строку с уже просмотренными (например, как в третьем варианте).
    – Regent
    Commented 12 мар. 2017 в 20:42
  • 1
    @Lugovets всё сводится к замерам времени начала и конца работы алгоритма с помощью System.currentTimeMillis() и вычислению разницы между конечным временем и начальным. Конкретно в этой задаче ДКА (дерево) себя почему-то плохо показал, однако зачастую этот вариант работает быстрее других. Так было, например, в этом случае и в этом.
    – Regent
    Commented 18 мая 2017 в 12:36

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.