昨年11月、Holaは
jsで
メールフィルタをプログラミングするための
コンテストを発表し、最近
その結果を発表し
ました 。
2位はイリヤマカロフと共有しました。
どうでしたか
コンテストに参加することを決めてタスクについて考えると、
'*'を
'.*'および
'?'置き換えるだけで、指定されたメールテンプレートを正規表現に変換できることにすぐに気付きました
'.*' '.' すべての特殊文字をエスケープします。
最短のソリューションで特別賞を受賞し
た Nadav Ivgiのように、これに落ち着くことができ
ます 。
しかし、このソリューションには致命的な欠陥があります-複雑さ
O（（ルールの数）*（メッセージの数）） 、各メッセージは各ルールへの準拠をチェックする必要があるためです。
より良い方法があります。 まず、
.fromフィールドと
.toフィールドの2つの正規
.fromを1つに
結合し、未使用の文字でそれらを分離します（たとえば、
'\x20'から
'\x7F'まで
'\x7F'文字のみ
'\x7F' ）、対応するメッセージフィールドで同じ操作を行います。
{from: 'john.doe@foo.org', to: '*@hola.*', action: 'act1'} -> {signature: 'alex@foo.org\x1F*@hola.*', action: 'act1'}
これにより、必要なテストの数が半分になります。
第二に、これらのレギュラーは1つの
確定的な有限状態マシン（DFA）にコンパイルでき、その複雑さはその数に依存しません。 ここでは、標準の
RegExpはもはや役に立ちません。
これはまさに私のソリューションの
最初のバージョンがしたことです。
タスクからのデータでテストを成功させたので、プロセスを自動化し
、ソースデータジェネレーターを実装
し、結果をリファレンス実装と比較することにしました 。 無駄ではないことが判明したため、DFAの最小化手順で
バグが発見され
、アルゴリズムから一時的に除外しました （その存在は正確性には影響せず、パフォーマンスのみに影響します）。
私のスクリプトは、可能な限り最大の頻度で参照実装で破損し、2、3日後にHolaはリクエストの頻度の制限を導入しました。 へえ。 私は肩をすくめ、
リクエスト間の遅延を
導入しました 。 テストはよりゆっくりと始まり始めましたが、生きることは可能でした。
ここで最適化が始まりました。 最初のアイデアは、
lexや他の同様のツールと同様に、
DFAをjsの巨大なswitchにコンパイルすることでした。
このようなコードジェネレーターを実装した結果、結果が改善されたかどうかを評価する方法がなく、そのためにはより広範なテストデータが必要であることに気付きました。 私は、健全な統計特性を持つデータセットをそれほど簡単に生成できないと判断しました。実際のデータセットを使用するのは良いことです。 すぐに
Enron Email Datasetが見つかりました。これは、適切な名前の破産した会社のメールアーカイブです。
いくつかのPythonスクリプトがアドレスからメッセージを抽出し、ルールを生成し、ベンチマークの準備が整いました。
私はそれを立ち上げて...
コンビナトリアル鉱山で爆発した 。 事実
、DFA構築アルゴリズムには指数関数的な複雑さ（
O（2 ^（非決定性有限状態マシン（NFA）の状態数） ）があり、これがどれほどひどいものかを過小評価していました。 20のルールだけで、機械の建設が終わるのを待つことができませんでした。 このアルゴリズムの問題を解決する代わりに、システムの既に高性能な部分の最適化に時間を費やしました。 本当に、
時期尚早の最適化はすべての悪の根源です 。
啓発を感知して、私が最初にしたことは
.fromと
.to backを分割した
.from 、すべてのルールに対して
.fromのみで動作するオートマトンと、ルールの各グループに対して
.toで動作するオートマトンを
.fromました。最初のオートマトンの最終状態：
これにより、各NFAのサイズが少なくとも半分に削減されたため、対応するDFAのサイズが大幅に削減されました。 生産性は桁違いに上昇し、今ではすでに数百のルールのオートマトンの構築を待つことが可能でした。
しかし、それでも長すぎました。 概念を変更する必要があるという理解は得られましたが、1週間のうちに洞察が得られました。決定論的オートマトン全体を一度に構築する必要はなく、ステップごとに1つの状態で遅延的に構築できます。
この概念の実装は、私を非常に驚かせました。同じ入力データで以前のバージョンよりも数倍高速であり、さらに、より大きな次元の入力データを簡単に噛むことができました。 どうやら、完全なDFA州のほとんどは訪問されていません。 さらに多くのデータを抽出するために、エンロンのデータセットを再解析しました。
これが必要だと判断し、最適化を開始しました。
最適化
さまざまなことを試しましたが、具体的な結果をもたらしたものについて説明します。
メモ化
私はそれを測定しませんでしたが、時間は他の何よりも節約すると信じる理由があります。 2つの場所で使用されます。
- 遅延DFAビルドは、一度渡された状態を記憶し 、各パスを再作成しません。
- 各電子メールのマシンの最終状態が記憶されるため、DFAグラフを再度確認する必要がなくなります。 通常のメッセージの電子メールアーカイブには、転送先のアドレスよりもはるかに多くの場合があるため、そのメリットは非常に大きくなります。 特に、これは、
filter結果として、アクションによって同じ配列を持つメッセージが実際に同じ配列オブジェクトを参照するという事実につながります。 アクションの配列は、新しいメッセージごとに再作成されません。
複数のNFA状態に一致するDFA状態の検索
最も時間をかけました。 一番下の行はこれです：
Objectのセット（NFA状態）から別の
Object （DFA状態）への効果的なマッピングが必要です。 jsには文字列以外のキーを持つ通常のハッシュテーブルがないため、回避する必要がありました。
私は次のことを行いました。各状態で、NFAはNFAの作成時に一意のint
.id配置しました（単純な増分で）。 そのような状態が多数あるため、それらを
.idを
Bufferに入れ、ソートし、
.toString()を使用
して文字列キーとして解釈します 。
NFA構造の詳細を使用する
メールテンプレートから派生したNFAには次の機能があります。
- 各頂点状態には、最大2つの出力アーク遷移があります。 当初、これは任意の数の要素の配列として実装されていました。 これをプロパティのペアとして実装すると、ランタイムが20％減少しました。
- 作成時に、将来構築されるこれらのセットが既にソートされるように、 NFA状態に番号を
.id ことができます （ .id ）。文字列キーを構築するためのソートの必要性を排除します（上記）
メモリ割り当ての頻度を最小限に抑える
- DFAを構築すると、NFA状態配列が常に作成されます。NFA状態配列は、文字列キーが構築され、対応するDFA状態が見つかった後にスローされることがよくあります（見つからない場合、新しい配列が作成され、配列がその一部になります）
- 文字列キーを構築するとき、
.id NFA状態を含むバッファは常にまったくスローされます。
どちらの場合も、DFAを作成するときに
必要な最大サイズの配列とバッファーを作成し、メモリを再割り当てせずに再利用できます。
正当性の最終評価
この時点で、私は最適化の機会を使い果たしていたので、ソリューションの正確さに完全な自信はありませんでした。 この迷惑な省略を修正するために、私は
別のpythonスクリプトを作成しました。この
スクリプトは 、数日間にわたって、参照実装を通じてEnronのデータセットの一部（1000ルールで約500メッセージ）を実行しました。 そして、結局のところ、無駄ではありませんでした。 結果のテストケースでは、電子メールテンプレートで2つの星が1文字で区切られている場合、エッジケースにバグが見つかりました。 見つけるのは難しい
が、簡単に修正できた 。
意思決定評価方法論に関する解説
オーガナイザーベンチマークは、単純な
requireではなく
、 vm Node'aモジュールを介してテスト済みモジュールを実行し require 。 結局のところ、
これはパフォーマンスに予期しない影響を及ぼします。
主催者は結果を確認することにしました。また、ソリューションの評価に使用された入力データのディメンションが比較的小さいことにも驚きました。 500,000のメッセージと1000のルールの最終バージョンを駆動し、オーガナイザーのベンチマークでさらに大きなサイズを予想しました。 このようなデータセットで、launch through
requireを使用
require 3人の公式リーダーが次の結果を示します。
- ユーリキロチェク〜2300ms（I）
- デニス・クレシキン〜2850ms
- イリヤ・マカロフ〜7500ms
ご希望の方のため
に、ベンチマークと一緒に決定を
掲載しました 。 このような誤解を避けるために、入力データのさまざまな次元で結果を平均化するか、さまざまな「重みカテゴリ」で競技会を開催することを、今後提案します。