java - 从 StringBuffer 中删除某些行

Question

遗留应用程序有一个巨大的字符串缓冲区(大小有时高达 1 Mb)，并且会按顺序处理以修改内容。我必须实现一项更改，其中我需要更新字符串缓冲区以删除以某些特定单词开头的一些行。有哪些可能的实现方式？

例如:

ABC:djfk kdjf kdsjfk#
ABC:jfue eijf iefe# 
DEL:kdjfi efe eei # 
DEL:ieeif dfddf dfdf#
HJU:heuir fwer ouier# 
ABC:dsf erereree ererre #

我需要删除以 DEL 开头的行。将字符串缓冲区拆分为字符串、处理行并再次连接字符串以创建字符串缓冲区会有点昂贵。请让我知道可能的解决方案。

谢谢

Answer 1

它是可以有效地就地执行此操作。您必须以适当的时间间隔覆盖缓冲区中的字符，然后使用 setLength 从逻辑上缩短缓冲区。这将非常复杂，但它会就地进行并且 O(N)。

之所以要覆盖而不是使用 delete/insert 是因为那将是 O(N^2)相反，因为事情需要不必要地转移。

在异地执行此操作非常简单且 O(N) 但需要辅助缓冲区，从而使空间需求加倍。

---

概念验证

这是一个简单的概念验证。 removeIntervals 采用一个 StringBuffer 和一个 int[][] 间隔。每个 int[] 被假定为一对 { start, end } 值(半开范围，独占上限)。在线性时间和就地中，这些间隔通过简单的覆盖从StringBuffer中删除。这适用于间隔已排序且不重叠且从左到右处理的情况。

然后使用 setLength 缩短缓冲区，切断尽可能多的被删除的字符。

static void overwrite(StringBuffer sb, int dst, int srcFrom, int srcTo) {
    for (int i = srcFrom; i < srcTo; i++) {
        sb.setCharAt(dst++, sb.charAt(i));
    }
}
static int safeGet(int[][] arr, int index, int defaultValue) {
    return (index < arr.length) ? arr[index][0] : defaultValue;
}
static void removeIntervals(StringBuffer sb, int[][] intervals) {
    int dst = safeGet(intervals, 0, 0);
    int removed = 0;
    for (int i = 0; i < intervals.length; i++) {
        int start = intervals[i][0];
        int end   = intervals[i][1];
        int nextStart = safeGet(intervals, i+1, sb.length());
        overwrite(sb, dst, end, nextStart);
        removed += end - start;
        dst += nextStart - end;
    }
    sb.setLength(sb.length() - removed);
}

那么我们可以这样测试:

    String text = "01234567890123456789";
    int[][][] tests = {
        { { 0, 5, },
        }, // simple test, removing prefix
        { { 1, 2, }, { 3, 4, }, { 5, 6, }
        }, // multiple infix removals
        { { 3, 7, }, { 18, 20, },
        }, // suffix removal
        {
        }, // no-op
        { { 0, 20 },
        }, // remove whole thing
        { { 7, 10 }, { 10, 13 }, {15, 15 }, 
        }, // adjacent intervals, empty intervals
    };

    for (int[][] test : tests) {
        StringBuffer sb = new StringBuffer(text);
        System.out.printf("> '%s'%n", sb);
        System.out.printf("- %s%n", java.util.Arrays.deepToString(test));
        removeIntervals(sb, test);
        System.out.printf("= '%s'%n%n", sb);
    }

这会打印 ( as seen on ideone.com ):

> '01234567890123456789'
- [[0, 5]]
= '567890123456789'

> '01234567890123456789'
- [[1, 2], [3, 4], [5, 6]]
= '02467890123456789'

> '01234567890123456789'
- [[3, 7], [18, 20]]
= '01278901234567'

> '01234567890123456789'
- []
= '01234567890123456789'

> '01234567890123456789'
- [[0, 20]]
= ''

> '01234567890123456789'
- [[7, 10], [10, 13], [15, 15]]
= '01234563456789'

---

获取间隔

在这种特定情况下，间隔可以在初步传递中构建(使用 indexOf)，或者如果绝对需要，整个过程可以在一次传递中完成.关键是这绝对可以在线性时间内就地完成(如果绝对必要，可以一次性完成)。

---

一个不合适的解决方案

这不适合使用辅助缓冲区和正则表达式。由于它的简单性，它被提供以供考虑。除非证明需要进一步优化(在证据分析结果之后)，否则这应该足够好:

    String text =
        "DEL: line1\n" +
        "KEP: line2\r\n" +
        "DEL: line3\n" +
        "KEP: line4\r" +
        "DEL: line5\r" +
        "DEL: line6\r" +
        "KEP: line7\n" +
        "DEL: line8";
    StringBuffer sb = new StringBuffer(text);
    Pattern delLine = Pattern.compile("(?m)^DEL:.*$");
    String cleanedUp = delLine.matcher(sb).replaceAll("<deleted!>");
    System.out.println(cleanedUp);

这会打印 ( as seen on ideone.com ):

<deleted!>
KEP: line2
<deleted!>
KEP: line4
<deleted!>
<deleted!>
KEP: line7
<deleted!>

引用资料

• regular-expressions.info
• java.util.regex.Pattern