Оптимизация строк и вложенных поисков

Question

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

public NestLink<String> searchsubs(String input, NestLink<String> searchTags) {

// parameter tests

int startIndex = 0; // start of the resultant subsection
int endIndex = 0; // end of the resultant subsection
String openTag = searchTags.elem1; // start of the string I need
String closeTag = searchTags.elem2; // end of the string I need
String subString = null; // stores the result in between
NestLink<String> node = null; // temp variable
NestLink<String> out = null; // output variable

while (true) {
    // find the opening string
    startIndex = input.indexOf(openTag, endIndex);
    if (startIndex == -1) {
    break; // if no more are found, break from the loop
    } else {
    }
    endIndex = input.indexOf(closeTag, startIndex);
    if (endIndex == -1) {
    break; // if tag isn't closed, break from the loop
    } else {
    }

    // we now have a pair of tags with a content between
    subString = input.substring(startIndex + openTag.length(), endIndex);

    // store what we found, method unimportant

    // search this content for each subsearch in the heirarchy
    for (NestLink<String> subSearch : searchTags.subBranches) {
    // recurse
    node = subBlockParser(subString, subSearch);
    // do stuff with results
    }       
}

//final do stuff
return out;
}

примечание: NestLink - это настраиваемая древовидная структура, однако формат не имеет значения.

В результате получается, что для каждого уровня поиска создается копия подстроки, иногда размером до 1 мегабайта, что, очевидно, далеко не эффективно.

Чтобы попытаться решить эту проблему, я подумал о следующем:

public NestLink<String> searchsubs(String input, int substringStart, int substringEnd,
NestLink<String> searchTags) {

// parameter tests

int startIndex = substringStart; // start of the resultant subsection
int endIndex = substringStart; // end of the resultant subsection
String openTag = searchTags.elem1; // start of the string I need
String closeTag = searchTags.elem2; // end of the string I need
String subString = null; // stores the result in between
NestLink<String> node = null; // temp variable
NestLink<String> out = null; // output variable

while (true) {
    // find the opening string
    startIndex = input.indexOf(openTag, endIndex);
    if (startIndex == -1 || startIndex >= substringEnd) {
    break; // if no more are found, break from the loop
    } else {
    }
    endIndex = input.indexOf(closeTag, startIndex);
    if (endIndex == -1 || endIndex >= substringEnd) {
    break; // if tag isn't closed, break from the loop
    } else {
    }

    // we now have a pair of tags with a content between
    // store what we found, method unimportant

    // search this content for each subsearch in the heirarchy
    for (NestLink<String> subSearch : searchTags.subBranches) {
    // recurse, this time sharing input, but with a new substring start and end to serve as bounds
    node =
        subBlockParser(input, startIndex + openTag.length(), endIndex, subSearch);
    // do stuff with results
    }
}

// final do stuff
return out;
}

На этот раз вместо создания подстроки я отправляю входные данные и набор границ. Возникает вопрос: как JRE справится с этим? Будет ли он копировать входную строку (что приведет к снижению производительности при копировании еще большей строки) или просто передаст объект-указатель, как это было бы с другими объектами, и все рекурсии совместно используют один и тот же строковый объект (значительное повышение производительности как нет копирования)

В качестве альтернативы, есть ли другие концепции, которые могут быть применимы к поиску по иерархии? и heirarchal результат?

K.Barad

Answer 1

substring не создает новую строку, содержащую копию символов в исходной строке. Он просто возвращает объект String, использующий тот же массив символов, что и исходная строка, но с другим смещением и длиной.

Итак, ваша вторая реализация похожа на первую, но более сложна (потому что она делает то, что делает String внутри).

Answer 2

Боюсь, что стандартный API Java уже реализует эту оптимизацию, поэтому от нее нечего извлечь.

A java.lang.String состоит из базового char[], смещения и длины.substring() повторно использует char[] и просто регулирует смещение и длину.

Я предлагаю использовать профилировщик в вашем коде, чтобы узнать, где он фактически проводит большую часть времени, до васдумать о любых оптимизациях.Это не позволит вам тратить свои усилия таким образом, и я почти гарантирую, что вы будете удивлены результатом.