レガシ アプリ プログラムには巨大な文字列バッファー (サイズが 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で始まる行を削除する必要があります。文字列バッファを文字列に分割し、行を処理し、再度文字列を結合して文字列バッファを作成すると、少しコストがかかります。可能な解決策を教えてください。
ありがとう
文字列バッファを文字列に分割し、行を処理し、再度文字列を結合して文字列バッファを作成するには、少しコストがかかります。
行を削除すると、削除する行ごとに残りのバッファーをコピーすることになるため、実際にははるかにコストがかかります。
最速の方法は、おそらくjava.util.regex.Matcher.replaceAll()を使用して、不要なすべての行を除いてバッファーのコピーを取得することです。
これをインプレースで効率的に行うことができます。適切な間隔でバッファ内の文字を上書きする必要があり、論理的にバッファをsetLength. かなり複雑になりますが、インプレースでO(N).
delete/を使用する代わりに上書きしたい理由insertはO(N^2)、物事を不必要に移動する必要があるためです。
このアウトオブプレースを実行するのは非常に簡単O(N)ですが、2 次バッファーが必要になるため、必要なスペースが 2 倍になります。
簡単な概念実証を次に示します。とremoveIntervalsを取ります。それぞれが値のペア(半分の範囲、排他的な上限) であると想定されます。線形時間とインプレースでは、これらの間隔は単純な によってから削除されます。これは、間隔がソートされていて重複していない場合に機能し、左から右に処理されます。StringBufferint[][] intervalsint[]{ start, end }StringBufferoverwrite
次にバッファは で短縮され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);
}
これは出力します ( 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プロセス全体を 1 つのパスで実行できます。ポイントは、これは間違いなく線形時間でインプレースで実行できることです (絶対に必要な場合は、シングルパスで実行できます)。
これは、セカンダリ バッファーと正規表現を使用する場違いです。そのシンプルさから検討のために提供されます。さらなる最適化が必要であることが証明されていない限り (証拠のプロファイリング結果の後)、これで十分です。
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);
これは出力します ( ideone.com で見られるように):
<deleted!>
KEP: line2
<deleted!>
KEP: line4
<deleted!>
<deleted!>
KEP: line7
<deleted!>
stringbuffer の行が改行で区切られている場合、それを読み込んで新しいバッファを作成できます。1 メガバイトのバッファの場合、これは数十ミリ秒で完了し、正規表現よりも高速です。StringReader のカスタム バージョンを作成して、文字列に変換するのではなく StringBuffer を直接読み取ることで、時間を少し節約できます。
final String NEWLINE = System.getProperty("line.separator");
StringBuffer nuBuffer = new StringBuffer();
BufferedReader br = new BufferedReader(new StringReader(sbData.toString()));
String line;
while ( (line = br.readLine()) != null) {
if (!line.startsWith("DEL:")) { // don't copy lines starting with DEL:
nuBuffer.append(line).append(NEWLINE);
}
}
br.close();