Clever Geek Handbook

JavaScriptでメールフィルターをプログラミングするためにHolaコンテストで2番目（これまで）の位置を占めたソリューションの分析

昨年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つの場所で使用されます。





複数のNFA状態に一致するDFA状態の検索



最も時間をかけました。 一番下の行はこれです： Object



のセット（NFA状態）から別のObject



（DFA状態）への効果的なマッピングが必要です。 jsには文字列以外のキーを持つ通常のハッシュテーブルがないため、回避する必要がありました。



私は次のことを行いました。各状態で、NFAはNFAの作成時に一意のint .id



配置しました（単純な増分で）。 そのような状態が多数あるため、それらを.id



をBuffer



に入れ、ソートし、 .toString()



を使用して文字列キーとして解釈します 。



NFA構造の詳細を使用する



メールテンプレートから派生したNFAには次の機能があります。





メモリ割り当ての頻度を最小限に抑える





どちらの場合も、DFAを作成するときに必要な最大サイズの配列とバッファーを作成し、メモリを再割り当てせずに再利用できます。



正当性の最終評価



この時点で、私は最適化の機会を使い果たしていたので、ソリューションの正確さに完全な自信はありませんでした。 この迷惑な省略を修正するために、私は別のpythonスクリプトを作成しました。このスクリプトは 、数日間にわたって、参照実装を通じてEnronのデータセットの一部（1000ルールで約500メッセージ）を実行しました。 そして、結局のところ、無駄ではありませんでした。 結果のテストケースでは、電子メールテンプレートで2つの星が1文字で区切られている場合、エッジケースにバグが見つかりました。 見つけるのは難しいが、簡単に修正できた 。



意思決定評価方法論に関する解説



オーガナイザーベンチマークは、単純なrequire



ではなく、 vm



Node'aモジュールを介してテスト済みモジュールを実行し require



。 結局のところ、 これはパフォーマンスに予期しない影響を及ぼします。 主催者は結果を確認することにしました。



また、ソリューションの評価に使用された入力データのディメンションが比較的小さいことにも驚きました。 500,000のメッセージと1000のルールの最終バージョンを駆動し、オーガナイザーのベンチマークでさらに大きなサイズを予想しました。 このようなデータセットで、launch through require



を使用require



3人の公式リーダーが次の結果を示します。





ご希望の方のために、ベンチマークと一緒に決定を掲載しました 。 このような誤解を避けるために、入力データのさまざまな次元で結果を平均化するか、さまざまな「重みカテゴリ」で競技会を開催することを、今後提案します。


More articles:


All Articles