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

Я получаю String a и b и проверяю, содержат ли b точные символы a. Например: «ABBA» и «BAAAAA» возвращают false, «ABBA» и «ABABAB» возвращают true. Я вставляю и массиву с каждым значением String и проверяю, содержит ли b это значение, удаляя значение, если оно делает так, что оно не находит его дважды.Какой самый быстрый способ проверить, содержит ли одна строка символы другого?

Однако, метод слишком медленный, по-видимому, на 12 секунд для некоторых больших строк. Я пытался, но не нашел более быстрого решения. Пожалуйста, помогите мне, если вы можете!

public static boolean inneholdt(String a, String b) 
{ 
    int k = 0; 
    String[] Inn = a.split("(?!^)"); 

    for (int i = 0; i < Inn.length; i++) 
    { 
     if(b.contains(Inn[i])) 
     { 
      b = b.replaceFirst(Inn[i], ""); 

      k++; 
     } 
    } 

    if(k >= Inn.length) 
    { 
     return true; 
    } else return false; 
}

источник

2015-10-03 Magnus Minor

Основываясь на первом взгляде без дальнейшего чтения, но: 'a.split (" (?! ^) ");' Если вы используете Java 8, вы можете просто использовать 'a.split (" ");' или, a.toCharArray() '. – Pshemo

В любом случае избегайте замены, которая является дорогостоящей, если это делается для каждой буквы из первой строки. - Как насчет подсчета символов в первой строке отдельно? Если вы знаете, что вам нужно найти 2 As и 2 Bs, (самое большее), достаточно пройти один проход над другой строкой. – laune

Я бы использовал 'int [] counter = new int [256]' и начал добавлять 1 в каждое значение 'int' каждого символа, найденного в кратчайшей строке из этих двух, а затем пересекать вторую строку и вычитать 1 за каждый' int' каждого символа. –

Если я понял проблему, есть два основные способ сделать это:

сортировать полукокс массивы обоего строк и проверить кратчайший массив является префиксом самого длинного
заполняется Map<Character, Integer>, в котором подсчитывается количество вхождений каждого символа в кратчайшие строка. Затем, итерация по самой длинной строке и уменьшение количества каждого встреченного символа. Если один счетчик достигает 0, удалите его с карты. Верните true, если карта пуста. Если после употребления всех символов самой длинной строки карта не была пуста, верните false.

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

Я покажу вам код второго решения:

// in Java 8. For older versions, it is also easy but more verbose 
public static boolean inneholdt(String a, String b) { 
    if (b.length() > a.length()) return false; 

    Map<Character, Integer> countChars = new HashMap<>(); 
    for (char ch : b.toCharArray()) countChars.put(ch, countChars.getOrDefault(ch, 0) + 1); 
    for (char ch : a.toCharArray()) { 
     Integer count = countChars.get(ch); 
     if (count != null) { 
      if (count == 1) countChars.remove(ch); 
      else   countChars.put(ch, count - 1); 
     } 
     if (countChars.isEmpty()) return true; 
    } 
    return false; 
}

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

В ответ на тест Макса я попытался сравнить производительность. Вот что я нашел:

My version : 
Mean time of 3 ms with lenA = 50000, lenB = 50 
Mean time of 1 ms with lenA = 50000, lenB = 500 
Mean time of 1 ms with lenA = 50000, lenB = 5000 
Mean time of 1 ms with lenA = 50000, lenB = 50000 
Mean time of 10 ms with lenA = 5000000, lenB = 5000 
Mean time of 18 ms with lenA = 5000000, lenB = 50000 
Mean time of 93 ms with lenA = 5000000, lenB = 500000 
Mean time of 519 ms with lenA = 5000000, lenB = 5000000 
Mean time of 75 ms with lenA = 50000000, lenB = 50000 
Mean time of 149 ms with lenA = 50000000, lenB = 500000 
Mean time of 674 ms with lenA = 50000000, lenB = 5000000 
Mean time of 9490 ms with lenA = 50000000, lenB = 50000000 

Max's parallel solution : 
Mean time of 89 ms with lenA = 50000, lenB = 50 
Mean time of 22 ms with lenA = 50000, lenB = 500 
Mean time of 23 ms with lenA = 50000, lenB = 5000 
Mean time of 36 ms with lenA = 50000, lenB = 50000 
Mean time of 2962 ms with lenA = 5000000, lenB = 5000 
Mean time of 2021 ms with lenA = 5000000, lenB = 50000 
Mean time of 2200 ms with lenA = 5000000, lenB = 500000 
Mean time of 3988 ms with lenA = 5000000, lenB = 5000000 
Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded 
    at java.util.concurrent.ForkJoinTask.recordExceptionalCompletion(Unknown Source) 
    at java.util.concurrent.CountedCompleter.internalPropagateException(Unknown Source) 
    at java.util.concurrent.ForkJoinTask.setExceptionalCompletion(Unknown Source) 
    at java.util.concurrent.ForkJoinTask.doExec(Unknown Source) 
    at java.util.concurrent.ForkJoinPool$WorkQueue.pollAndExecCC(Unknown Source) 
    at java.util.concurrent.ForkJoinPool.externalHelpComplete(Unknown Source) 
    at java.util.concurrent.ForkJoinTask.externalAwaitDone(Unknown Source) 
    at java.util.concurrent.ForkJoinTask.doInvoke(Unknown Source) 
    at java.util.concurrent.ForkJoinTask.invoke(Unknown Source) 
    at java.util.stream.ReduceOps$ReduceOp.evaluateParallel(Unknown Source) 
    at java.util.stream.AbstractPipeline.evaluate(Unknown Source) 
    at java.util.stream.ReferencePipeline.collect(Unknown Source) 
    at Stack.inneholdt(Stack.java:34) 
    at Stack.test(Stack.java:61) 
    at Stack.main(Stack.java:12)

Это показывает, что реализация Collectors.groupingBy довольно требовательно к памяти. Решение Max в принципе неплохое, даже если оно делает больше работы, чем могло бы быть, это решение высокого уровня, поэтому он не может контролировать некоторые детали реализации, такие как группировка записей. Рассматривая код стандартной библиотеки Java, похоже, что сортировка выполняется, поэтому требуется некоторая память, особенно потому, что несколько потоков сортируются в одно и то же время. Я запускал это с настройкой по умолчанию -Xmx2g. Я переделал его, используя -Xmx4g.

My version : 
Mean time of 3 ms with lenA = 50000, lenB = 50 
Mean time of 1 ms with lenA = 50000, lenB = 500 
Mean time of 2 ms with lenA = 50000, lenB = 5000 
Mean time of 5 ms with lenA = 50000, lenB = 50000 
Mean time of 7 ms with lenA = 5000000, lenB = 5000 
Mean time of 17 ms with lenA = 5000000, lenB = 50000 
Mean time of 93 ms with lenA = 5000000, lenB = 500000 
Mean time of 642 ms with lenA = 5000000, lenB = 5000000 
Mean time of 64 ms with lenA = 50000000, lenB = 50000 
Mean time of 161 ms with lenA = 50000000, lenB = 500000 
Mean time of 836 ms with lenA = 50000000, lenB = 5000000 
Mean time of 11962 ms with lenA = 50000000, lenB = 50000000 

Max's parallel solution : 
Mean time of 45 ms with lenA = 50000, lenB = 50 
Mean time of 18 ms with lenA = 50000, lenB = 500 
Mean time of 19 ms with lenA = 50000, lenB = 5000 
Mean time of 35 ms with lenA = 50000, lenB = 50000 
Mean time of 1691 ms with lenA = 5000000, lenB = 5000 
Mean time of 1162 ms with lenA = 5000000, lenB = 50000 
Mean time of 1817 ms with lenA = 5000000, lenB = 500000 
Mean time of 1671 ms with lenA = 5000000, lenB = 5000000 
Mean time of 12052 ms with lenA = 50000000, lenB = 50000 
Mean time of 10034 ms with lenA = 50000000, lenB = 500000 
Mean time of 9467 ms with lenA = 50000000, lenB = 5000000 
Mean time of 18122 ms with lenA = 50000000, lenB = 50000000

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

Код here.

источник

2015-10-03 15:15:20 Dici

Спасибо! Это было очень полезно, даже если оно немного выше моего уровня. –

Нет проблем, не стесняйтесь задавать вопросы, если вам что-то неясно – Dici

Java 8 + выражения лямбда.

Как это работает?

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

Это решение использует параллельное выполнение и работает с любыми литералами, поскольку оно подсчитывает кодовые точки. Однако решение @ Dici будет намного быстрее для случая, который он описывает.

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

Alphanumeric N=50000: 26ms vs 10ms vs 16ms 
Alphanumeric N=5000000: 425ms vs 460ms vs 162ms 
Alphanumeric N=50000000: 3812ms vs 3297ms vs 1933ms

Первый номер для @ решения Dici, в второй для моего решения с обычными потоками, а третий для версии от этого ответа.

источник

2015-10-03 16:05:23

Как насчет случая, когда 'get' возвращает' null'? Здесь вы должны использовать 'getOrDefault'. Кроме того, он работает – Dici

Спасибо, что указали ошибку! Починил это. –

Я немного удивлен, что ваше потоковое решение без параллелизма быстрее, чем мое, поскольку потоки, как известно, имеют небольшие накладные расходы, а также потому, что вы делаете немного больше работы, чем я. Распараллеленный результат интересен. Как вы это оценили? – Dici

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

ответ

Смежные вопросы