Есть массив строк (String[]
) размером в один миллион, и надо найти те строки, которые повторяются.
Но при поиске стандартным методом (цикл в цикле) все это занимает очень много времени.
Как лучше это реализовать? И можно ли уложиться в 10 секунд?
2 ответа
Очень просто, но с дополнительными расходами памяти:
- Взять set (множество) – контейнер, обеспечивающий быстрый (логарифм..константа) поиск по значению и не допускающий (возможно, игнорирующий) вставку одинаковых значений.
- При обходе массива (в одном цикле, без вложенности) поддерживать два множества (изначально пустых): одно со строчками что встречались ранее, второе со строчками что встретились больше одного раза (иначе говоря, с ответом).
Что будет происходить на каждой итерации в процессе обхода, предлагаю установить самостоятельно.
Увеличение расхода памяти вы можете почти и не ощутить, если хранить в множестве прямо те же строчки, что в массиве (а не копии) по ссылкам (как в Java хранятся все объекты). Если, конечно, у вас не совсем мелкие строки, но чем больше в массиве дублирования, тем меньше попадёт в множества, так что даже с мелкими может быть всё не так плохо.
-
А разве
Set
подойдет? При каждой вставке он будет проверять есть ли такой или нет. Под конец операции вставки будут очень медленными– user194625Commented 12 мар. 2017 в 6:02 -
2@Flippy при использовании реализации Hashset поиск, вставка удаление выполняются за константное время не зависимо от размера.– temqCommented 12 мар. 2017 в 6:29
-
@temq, спасибо буду знать– user194625Commented 12 мар. 2017 в 6:30
-
1Гарантированное надежное решение, которое не зависит от функции хеширования, это положить все строки в бор.– pavelCommented 12 мар. 2017 в 8:18
-
@pavel да, это одна из реализаций множества для строк. Но операции с ним логарифмические, хэшсет может оказаться пошустрее. Но алгоритму, в целом, пофиг, можно всё забенчмаркать и решить :)– user181100Commented 12 мар. 2017 в 8:24
Тестовые данные. Х строк, первые У из которых уникальны, а оставшиеся Х-У - копии этих У. Все строки одинаковой длины и состоят из символов с 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());
}
Результаты тестирования.
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
).
-
тут на самом деле есть проблема - вы не делаете копии строки. У вас просто копируется указатель. Используете честное копирование с созданием новой строки. Иначе даже хеш закешируется в самой строке. (Они тупо по == будут равны). Да и код dfa работает как-то сильно долго в случае 2 (явно что-то не так). Вот пример ideone.com/ZPTUoK на С++, я не использовал Map а просто массив, но вроде бы код одинаковый.– pavelCommented 12 мар. 2017 в 15:48
-
@pavel про жутко сомнительные результаты работы варианта с ДКА я писал ещё в комментариях к ответу D-side, но от первой версии реализации получилось повысить производительность только процентов на 10. Использование массива вместо
Map
не внушает оптимизма, ибо нужно будет рассчитывать алфавит, да и charcode-ы в нём не обязаны идти подряд: например, могут быть латинские буквы и кириллица. Насчет не использования настоящих копий строк - попробую с настоящими, но, надеюсь, результаты от этого не сильно изменятся.– RegentCommented 12 мар. 2017 в 16:19 -
-
@etki а что насчет ложных срабатываний? Получается, в случае положительного результата всё равно придётся сравнивать строку с уже просмотренными (например, как в третьем варианте).– RegentCommented 12 мар. 2017 в 20:42
-
1@Lugovets всё сводится к замерам времени начала и конца работы алгоритма с помощью
System.currentTimeMillis()
и вычислению разницы между конечным временем и начальным. Конкретно в этой задаче ДКА (дерево) себя почему-то плохо показал, однако зачастую этот вариант работает быстрее других. Так было, например, в этом случае и в этом.– RegentCommented 18 мая 2017 в 12:36