Ошибка пространства кучи Java при проверке очень очень длинной строки

Question

Ошибка пространства кучи Java при проверке очень очень длинной строки

У меня есть указанная строка, и мне нужно проверить эту строку на идентичные части указанной длины. Например, если String равен "abcdab", а длина указана как 2, идентичные части в этой строке - "ab" (всегда ищет наиболее повторяющуюся). Я улучшил свой алгоритм 4-5 раз для лучшей производительности, но, в конце концов, если длина строки равна 1 м +, он выдает ошибку пространства кучи Java.

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

int length = 2;
String str = "ababkjdklfhcjacajca";
ArrayList<String> h = new ArrayList<String>(); 
h.add(str.substring(0, length));
ArrayList<Integer> contains = new ArrayList<Integer>();
contains.add(1);

String c;
for (int g = 1; g < str.length()-length+1; g++) {
    c = str.substring(g, length+g);
    for (int e = 0; e < h.size(); e++) {
        if (h.get(e).charAt(0) == c.charAt(0) && h.get(e).charAt(length-1) == c.charAt(length-1)) {
            if (h.get(e).equals(c)) {
                contains.set(e, contains.get(e)+1);
                break;
            }
        }
        else if (e+1 == h.size()) {
            h.add(c);
            contains.add(1);
            break;
        }
    }

}

ArrayList h хранит каждую уникальную часть строки, ArrayList содержит количество повторений каждой уникальной части строки. строка c является главной проблемой (точки пространства Java кучи здесь). Он постепенно представляет каждую часть строки, прежде чем она будет сохранена в ArrayList h (если это c уникален). После этого я просто найду самые повторяемые, используя ArrayLists и распечатать их.

1

java string heap

Источник

user7727929 22 янв '18 в 16:30

4 ответа

Решение

Это забавное исследование для использования Map (для представления количества вхождений для каждой подстроки), Pattern а также Matcher классы.

Еще одна вещь, которая также была мне интересна, это то, что подстрока aa - например - появляется 2 раза в aaa; а не 1 раз, как я изначально рассчитывал, используя replaceAll метод (для подсчета отдельных символов).

Мое решение
(Я проверил это с длиной 10^8=100 000 000 символов String и это сработало хорошо. Единственная граница, которая, кажется, существует, это длинаString вход)

public static Map<String, Integer> getMostRepeatedSubstring(int length, String str) {
    HashSet<String> possibleSubstrings = new HashSet<>();
    Map<String, Integer> ans = new HashMap<>();
    int max = 0;

    // Create a list of all the unique substrings of "str" with a certain length
    for(int i=0; i<str.length()-length; i++) {
        String curr = str.substring(i, i+length);
        possibleSubstrings.add(curr);
        // "curr" is added only if it doesn't already appear within "possibleSubstrings"
    }

    for(String sub : possibleSubstrings) {
        Pattern pattern = Pattern.compile(sub, Pattern.LITERAL);
        Matcher matcher = pattern.matcher(str);
        int currentOccurrences = 0;
        while (matcher.find())
            currentOccurrences ++;

        if(currentOccurrences > max) {           // We have a new winner!
            max = currentOccurrences;
            ans.clear();
            ans.put(sub, currentOccurrences);
        }
        else if (currentOccurrences == max) {    // We have a tide
            ans.put(sub, currentOccurrences);
        }
    }

    return ans;
}

Редактировать: Спасибо @Holger за важные улучшения!

0

Источник

user3103891 22 янв '18 в 17:29

Вы можете попробовать использовать Map для отслеживания появления подстрок, например:

public class Test {
    public static void main(String[] args) {
        String test = "asdasdagagsjug8afhnqh3gbq29873brfuysbf78sdgy0yg7483wthsddbfahbfasfga78dftg78VGFIBDVGIUASF8928HWEAWD";
        int substringLength = 2;

        Map<String, Integer> tracker = new HashMap<>();

        for(int i = 0; i < test.length() - substringLength + 1; i ++) {
            String subString = test.substring(i, substringLength + i);
            tracker.compute(subString, (k,v) -> v == null ? 1 : v + 1);
        }

        for(String key : tracker.keySet()) {
            System.out.println("Substring: " + key + " has " + tracker.get(key) + " occurences.");
        }
    }
}

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

ababababababababababababa

вы должны хранить каждую подстроку отдельно в вашем списке h, Приведенный выше код будет отслеживать String ab в 1 отображении. Фактически, это напечатало бы:

Substring: ab has 12 occurences.
Substring: ba has 12 occurences.

Я надеюсь, что это дает вам место для начала.

0

Источник

user2704500 22 янв '18 в 16:50

Вы можете перебрать строку один раз, добавив местоположение g к g+1 в хеш-таблицу, а затем использовать if, чтобы проверить, находится ли вхождение в хеш-таблице. Например, abcab будет ab ->2, bc->1, ca->1 в таблице.

int length = 2;
String str = "ababkjdklfhcjacajca";
Hashtable<String, Integer> identicalStrings = new Hashtable<String, Integer>();
h.add(str.substring(0, length));

for (int i = 0; i < str.length() - 1; i++) {
   if(!identicalStrings.contains(str.substring(i, i+2)) {
        identicalStrings.numbers.put(str.substring(i, i+2), 1);
   } else {
       identicalStrings.put(str.substring(i, i+2), identicalStrings.get(str.substring(i, i+2)) + 1);
   }

}

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

0

Источник

user6402918 22 янв '18 в 16:51

Другие вопросы по тегам java string heap

user2711488 23 янв '18 в 16:14 2018-01-23 16:14 · Accepted Answer · 2018-01-23 16:14

Если вы хотите выполнять поиск эффективно, по времени и памяти, я предлагаю вам следующее:

Сначала создайте простую гистограмму символов, содержащую количество вхождений каждого символа. Если первый символ подстроки имеет меньше вхождений, чем самая распространенная подстрока, которую мы нашли до сих пор, мы можем пропустить эту подстроку.
Вместо создания подстрок, которые содержат копии содержимого символов, мы используем CharBufferкоторый оборачивает строку и корректирует ее position а также limit представлять подпоследовательность. Конечно, мы не должны изменять буфер после того, как он был сохранен в качестве ключа на нашей карте, поэтому мы создаем новый буфер для каждого ключа, когда он был сохранен на карте. Таким образом, мы создаем не более одного CharBuffer для каждой отдельной подстроки и эти буферы все еще только обернуть String вместо этого скопируйте любые символьные данные

public static Map<String,Integer> mostCommonSubstring(String s, int len) {
    int[] charHistogram = new int[Character.MAX_VALUE+1];
    s.chars().forEach(ch -> charHistogram[ch]++);
    int most = 0;
    HashMap<Buffer, Integer> subStrings = new HashMap<>();
    CharBuffer cb = CharBuffer.wrap(s);
    for(int ix = 0, e = s.length()-len; ix <= e; ix++) {
        if(charHistogram[s.charAt(ix)] < most) continue;
        int num = subStrings.merge(cb.limit(ix+len).position(ix), 1, Integer::sum);
        if(num == 1) cb = CharBuffer.wrap(s);
        if(num > most) most = num;
    }
    final int mostOccurences = most;
    return subStrings.entrySet().stream()
        .filter(e -> e.getValue() == mostOccurences)
        .collect(Collectors.toMap(e -> e.getKey().toString(), Map.Entry::getValue));
}

Первые две строки создают нашу гистограмму

    int[] charHistogram = new int[Character.MAX_VALUE+1];
    s.chars().forEach(ch -> charHistogram[ch]++);

В рамках цикла

        if(charHistogram[s.charAt(ix)] < most) continue;

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

Следующая строка адаптирует текущий буфер для представления подстроки и обновляет карту, связывая буфер с 1 если нет или добавить 1 на счет существующего отображения.

        int num = subStrings.merge(cb.limit(ix+len).position(ix), 1, Integer::sum);

Мы используем возвращаемое значение, чтобы определить, является ли merge Операция создала новую ассоциацию на карте, которая имеет место только в том случае, если результат равен единице. В этом случае мы не должны впоследствии изменять буфер, следовательно, создавать новый

        if(num == 1) cb = CharBuffer.wrap(s);

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

        if(num > most) most = num;

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

    final int mostOccurences = most; // needed because most is not “effectively final”
    return subStrings.entrySet().stream()
        .filter(e -> e.getValue() == mostOccurences)
        .collect(Collectors.toMap(e -> e.getKey().toString(), Map.Entry::getValue));