8

大量のデータを難読化しようとしています。置き換えたい単語 (トークン) のリストを作成しました。次のように、StringBuilder クラスを使用して単語を 1 つずつ置き換えています。

 var sb = new StringBuilder(one_MB_string);
 foreach(var token in tokens)
 {
   sb.Replace(token, "new string");
 }

かなり遅いです！スピードアップするためにできる簡単なことはありますか？

tokensは、それぞれ 5 ～ 15 文字の長さの約 1,000 個の文字列のリストです。

4

4 に答える 4

5

時間がかかる理由がわかりますね。

1 MB の文字列があり、トークンごとに、replace は 1 MB を反復処理し、新しい 1 MB のコピーを作成します。見つかったトークンは新しいトークン値に置き換えられるため、正確なコピーではありません。ただし、トークンごとに 1 MB を読み取り、1 MB のストレージを新たに作成し、1 MB を書き込みます。

さて、これを行うためのより良い方法を考えることができますか? トークンごとに 1 MB の文字列を反復する代わりに、1 回ウォークします。

それを歩く前に、空の出力文字列を作成します。

ソース文字列をたどってトークンを見つけたら、token.length()文字を前方にジャンプし、難読化されたトークンを書き出します。それ以外の場合は、次の文字に進みます。

基本的に、プロセスを裏返しにして、長い文字列に対して for ループを実行し、各ポイントでトークンを探します。これを高速化するために、トークンの迅速なループアップが必要になるため、トークンをある種の連想配列 (セット) に入れます。

時間がかかる理由はわかりますが、修正についてはわかりません。置換を実行している 1 MB の文字列ごとに、置換したい tokan が 1 ～ 2,000 あります。そのため、1000 個のトークンのいずれかを探して 1 文字ずつ歩いても、それほど速くはありません。

一般的に、プログラミングで最も時間がかかるのは何ですか? メモリを新しくします。

ここで、StringBuffer を作成すると、ある程度のスペースが割り当てられる可能性があります (たとえば、64 バイトであり、現在の容量よりも多くを追加すると、おそらくそのスペースが 2 倍になります。その後、古い文字がコピーされます)。新しいものにバッファします (C の再割り当てが可能で、コピーする必要がない可能性があります)。

したがって、64 バイトから開始して最大 1 MB を取得する場合は、割り当ててコピーします: 64、次に 128、次に 256、次に 512、次に 1024、次に 2048 ... これを 20 回行い、最大 1 MB を取得します。 . そして、ここにたどり着くまでに、それを捨てるために 1 MB を割り当てました。

C++ の関数に似たものを使用して事前割り当てをreserve()行うと、少なくとも一度にすべてを行うことができます。ただし、トークンごとに一度に処理されます。トークンごとに少なくとも 1 MB の一時文字列を生成しています。2000 個のトークンがある場合、約 20 億バイトのメモリが割り当てられ、最終的にはすべて 1 MB になります。各 1 MB スローアウェイには、現在のトークンが適用された、前の結果の文字列の変換が含まれます。

そしてそれが、これが非常に時間がかかっている理由です。

はい、各キャラクターに適用するトークン (ある場合) を決定するのにも時間がかかります。最初に提案したように、セット ルックアップではなく、すべての可能性を実行するステート マシンを内部的に構築する正規表現を使用することをお勧めします。しかし、1 MB の文字列を 2000 コピーするために、そのすべてのメモリを割り当てる時間が本当にあなたを苦しめています。

ダン・ギブソンは次のように提案しています。

キャラクターごとに千個のトークンを探す必要がないように、トークンを並べ替えます。ソートには時間がかかりますが、文字ごとに何千ものトークンを検索する必要がないため、最終的にはおそらく高速になります。

これが、それらを連想配列 (Java HashSet など) に入れる理由でした。しかし、もう 1 つの問題は照合です。たとえば、あるトークンが「a」で別のトークンが「an」の場合、共通の接頭辞がある場合、つまり、どのように照合するのでしょうか?

ここで Keltex の答えが役に立ちます。彼はマッチングを Regex に委譲します。これは、Regex が既に (貪欲な一致) を定義し、これを行う方法を実装しているため、素晴らしいアイデアです。一致が確認されると、キャプチャされたものを調べてから、Java Map (連想配列でもあります) を使用して、一致した難読化されていないトークンの難読化されたトークンを見つけることができます。

これを修正する方法だけでなく、そもそもなぜ問題が発生したのかに答えを集中したかったのです。

于 2009-04-02T22:07:26.307 に答える
2

正規表現でトークンを見つけることができる場合は、次のようにすることができます。

RegEx TokenFinder = new Regex("(tokencriteria)");
string newstring = myRegEx.Replace(one_MB_string, new MatchEvaluator(Replacer));

次に、Replacer を次のように定義します。

private string Replacer(Match match)
{
    string token= match.Groups[1].Value;
    return GetObfuscatedString(token);
}
于 2009-04-02T22:06:28.850 に答える