优化字符串和嵌套搜索

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 MB），这显然效率不高。

为了尝试解决这个问题，我考虑了以下内容：

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 将如何处理这个问题？它会复制输入字符串（导致性能下降，因为现在正在复制更大的字符串），还是会像其他对象一样简单地传递指针对象，并且所有递归共享相同的字符串对象（性能显着提高）因为没有复制）

或者，是否有任何其他概念可能适用于层次搜索？和继承结果？

巴拉德

Answer 1

substring 不会创建包含原始字符串中字符的副本的新字符串。它只是返回一个与原始字符串共享相同字符数组的 String 对象，但具有不同的偏移量和长度。

因此，您的第二个实现与第一个实现类似，但更复杂（因为它执行 String 内部的操作）。

Answer 2

恐怕Java标准API已经实现了这种优化，所以从中没有什么好处。

java.lang.String 由底层 char[]、偏移量和长度组成。 substring() 重用 char[] 并仅调整偏移量和长度。

我建议在您考虑任何优化之前，在您的代码上使用分析器来找出它实际花费大部分时间的地方。这将防止你像这样浪费你的努力，我几乎可以保证你会对结果感到惊讶。