Geekly Articles each Day

Hola JavaScriptコンテストの11ステップ3位

確かにあなたの多くは、あなたの目の前ですでにHolaのコンテストで記事の見出しをフラッシュしている、それは最近その論理的結論に達した。 最終結果では、幸運にも3位になりました。 このため、私は自分の決定の説明と、それまでの経緯を共有できるようにしました。

1.なぜ私が悪いのですか？


もちろん、最初の決定は「額に」です。 ルールごとに正規表現のペアを作成し、ルールに従ってネストされたループでメッセージループを開始します。 コードはいシンプルです（そして、すでにわかっているように、この恐ろしい数の666バイトに簡単に収まります）。ここでは、その点についてはわかりません。

2.ダイナミック機能を長持ちさせる！


次のステップでは、内側のループを拡張することにしました。 これを行うには、まず、ルールに基づいてgetActions（from、to）関数を動的に形成し、各メッセージに対してループで呼び出します。 フィルターは次の形式を取ります。

function filter(messages, rules) { //   var builder = []; builder.push('var actions = [];'); for ( var i = 0; i < rules.length; i++ ) { var rxFrom = createRegex(rules[i].from); if ( rxFrom ) builder.push(escapeRegex(rxFrom), '.test(from) && '); var rxTo = createRegex(rules[i].to); if ( rxTo ) builder.push(escapeRegex(rxTo), '.test(to) && '); builder.push('actions.push(\'', escapeString(rules[i].action), '\');'); } builder.push('return actions;'); var getActions = new Function('from, to', builder.join('')); //   var result = {}; for ( var key in messages ) { var message = messages[key]; result[key] = getActions(message.from, message.to); } return result; }

また、生成されたgetActions関数の例を以下に示します。

 function getActions(from, to) { var actions = []; /^.*@work\.com$/.test(from) && actions.push('tag work'); /^.*@spam\.com$/.test(from) && actions.push('tag spam'); /^jack@example\.com$/.test(from) && /^jill@example\.org$/.test(to) && actions.push('folder jack'); /^jill@example\.com$/.test(to) && actions.push('forward to jill@elsewhere.com'); return actions; }

このアプローチの利点は、関数内で特定のルールに必要な条件を事前にプログラムできることです。 具体的には、上記の例では、ルールでfromまたはtoプロパティが指定されていない場合、このルールに対応するメッセージプロパティのチェックを関数本体に追加する必要はありません。 これらのプロパティのいずれもルールで指定されていない場合、ルールで指定されたアクションは、チェックなしで結果の配列に書き込まれます。

通常のネストされたループを使用してこの動作を実現する場合、各反復で計算されるループの本体に追加のチェックを挿入する必要があり、もちろん追加のコストがかかります。

3.自分自身、すべて自分で！


さらに、正規表現から逃れ、アドレスが特定のパターンに一致するかどうかを判断する一致（値、パターン）関数を作成し、それぞれtrueまたはfalseを返しました。 最初は、私の関数は文字/文字列で動作しましたが、このアプローチはあまり効果的ではなかったため、主にString.charCodeAt（インデックス）から取得されるASCIIコードになりました（String.codePointAt（インデックス）を使用する試みもありましたが、有効性の観点から正当化されない）。 この関数は面倒であまり面白くないので、ここでは紹介しません。

getActionsからmatch関数を呼び出すために、fromおよびtoの後に追加のパラメーターを渡しました。

4.申し訳ありませんが、あなたは間違いなく私たちには適していません。


生産性をさらに向上させる方法を探して、私は自分の機能はもちろん素晴らしいと判断しましたが、それでも呼び出し回数は少なく、再びgetActionsに焦点を当てるべきです。 実際、この段階でのタスクは、いくつかの兆候に基づいて、いくつかのルールを意図的に除外し、それらのリソースを集中的に使用する機能を呼び出さないことでした。これらの兆候の定義自体もそれほど時間を要しません。

これらの兆候の1つは、テンプレートの最初の文字にすぎません。 「？」でない場合にのみ使用できます。 または「*」。 2番目の記号である長さは、テンプレートに「*」記号がない場合に使用できます（その時点では、住所の最小長を確認できるという考えがまだ届いていませんでした）。

各ルールをチェックするときに、処理されたメッセージのfromおよびtoプロパティで一連のメソッドを呼び出さないようにするために、getActions関数の開始時に追加の変数を計算し、必要に応じて使用します。

 function getActions(from, to, match) { var actions = []; var fb = from.charCodeAt(0), fb61 = fb == 0x61, fb74 == 0x74 /*, ... */; var tb = to.charCodeAt(0), tb66 = tb === 0x66 /*, ... */; var fl = from.length, fl14 = fl == 14, fl15 = fl == 15 /*, ... */; var tl = to.length, tl16 = tl == 16 /*, ... */; fb61 && tb66 && fl15 && tl16 && match(from, 'abc@example.com') && match(to, 'fake@example.com') && actions.push('action 1'); fb74 && fl14 && match(from, 'test@gmail.com') && match(to, '*@any.net') && actions.push('action 2'); // ... return actions; }

この変更により、生産性が著しく向上しました。 しかし、シンボル「*」で始まるパターンでは、最初の文字または長さでナビゲートすることは不可能であることがわかります。 そして、そのようなパターンは間違いなく見つかりました。

5.さらにいくつかの質問


したがって、次のステップでは、テンプレートもドメイン別に分類しようとすることにしました。 「*」はドメイン内のどこでも発生する可能性があるため、ドメインの最大レベルを3番目まで取得することにしました。 したがって、getActions関数の開始時に、fromおよびtoメッセージプロパティからレベル1、2、および3ドメインを選択し、メッセージアドレスが特定のドメインに属していることを通知する変数の大きな束を形成する必要があります。

私が思い出す限り、この方法は完全に機能しないということではなく、さまざまなテストデータを使用して、さまざまな方法で現れました。 ドメインをアドレスから分離し、各反復で変数を予備計算するのに多くの時間がかかりました。 その後、多くの異なるオプションを試しました。 たとえば、最初に計算された変数の数を減らすために、めったに出会わないドメインをグループ化し（ちなみに、最初の文字と長さで同様のグループ化を行いました）、ドメインハッシュを計算して比較しようとしました。 しかし、ドメイン比較の結果、私はまだ拒否しました。

6.近くのどこか


その間、思考は頭の中に浮かんできました。そして、テンプレートの最初から（そして最後から）最初の「*」記号まで単一のツリーを構築し、それにチェックすべきルールのリストを入れようとしませんか？ 私はこの方法が本当に好きではなく、無意識にそれを非効率的に構築したか、構築に非常に長い時間がかかりましたが、最初の実験の後、この構造の作成はかなり遅いものであると判断し、混乱させたくありません

7.なぜ車輪を再発明するのですか？


前のオプションに戻りましたが、ドメインで分類する代わりに、テンプレートの最後の文字のチェックを追加しました。

すべてがうまくいくようですが、あまり良くありません。 一致関数を呼び出す前に各ルールをチェックすると、最大6個の変数をチェックでき（最初からチェックの回数を減らしたいと思っていました）、さらにメッセージごとに計算する必要があることがわかりました。 好きじゃなかった。 さらに、各ルールのチェック数とそのシーケンスを試してみたところ、このような長いチェックでは、2つのサインよりも3つのサインのほうが多くの利点はないという結論に達しました。 したがって、次のステップ。

8. Cr屈だが、犯罪はない


アドレスとパターンの長さを比較することは最も役に立たない症状であると判断し、ルールを除外する兆候を除外しました。 残っているのは、最初の文字と最後の文字の対応を確認することだけです。 競合の条件から、行には0x20から0x7Fの範囲のコードを持つ文字しか存在できないことを覚えています。つまり、パターンの最初と最後のすべての文字は、整数型の1つの変数に簡単に収まり、各ルールが一致を呼び出す前に1つの比較のみを行うことができます。 残ったのは、一部のテンプレートに「？」文字が先頭または末尾にあるという問題だけでした および「*」は、比較に参加すべきではありません。 しかし、値を比較する前に、余分なオクテットをリセットするマスクをそれらに適用すると、この問題は簡単に解決されます。 次のことを取得します。

 function getActions(from, to, match) { var actions = []; var hash = (from.charCodeAt(from.length-1)<<24) | (from.charCodeAt(0)<<16) | (to.charCodeAt(to.length-1)<<8) | to.charCodeAt(0); (hash & 0xFFFFFFFF) == 0x6D616D66 && match(from, 'abc@example.com') && match(to, 'fake@example.com') && actions.push('action 1'); (hash & 0xFFFFFF00) == 0x6D747400 && match(from, 'test@gmail.com') && match(to, '*@any.net') && actions.push('action 2'); // ... return actions; }

そしてもちろん、ハッシュをマスクすることは、各ルールに対してこの操作を実行しないように、関数の開始時に変数（16個を超えることはできません）に事前計算することも論理的です。

9.分割して征服しよう！


マッチ機能は非常にうまく機能しましたが、すべてのテンプレートに共通しており、これが欠点でした。 記号「*」を含まないテンプレートの場合、これらの追加手順をすべて実行する必要はありませんが、記号「？」の特徴を考慮して、文字ごとに2行を比較するだけで十分です。 テンプレート内。 同じことは、「*」文字を1つだけ含むパターンにも当てはまりました。 この場合、「*」の前後のテンプレートのセクションをチェックするのが論理的です。

その結果、1つの一致関数ではなく、5つの関数が表示されます。


さらに、文字列としてではなく、文字コードを含む配列の形式でこれらの関数にテンプレートを既に渡します（String.charCodeAt（インデックス）メソッドを再度プルしないように、実際、これが恩恵を受けているかどうかはわかりません）。

したがって、その形成の過程で、getActions関数は必要な関数の呼び出しに置き換えられます（これらの関数はまだ追加のパラメーターを介して渡されます）。 同時に、連続した「*」文字はテンプレートから削除されます。これは結果に影響しませんが、それでも比較関数の選択であるためです。 （最終ソリューションでは、このプロセスの実装はcreatePatternMatchFunc関数内にあります。）

10. shhhのみ...


この決定には1つの弱点があります。 最悪の場合、すべてのテンプレートが突然同じ文字で始まり、さらに同じ文字で終わる場合、すべてのテンプレートは同じハッシュを持ち、getActions内のテンプレートチェック関数は絶対にすべてのルールに対して呼び出されます（メッセージ内のアドレス、もちろん、フィット）。

この場合、最初の文字ではなく、パターンの最初と最後から2番目または3番目の文字を比較することは論理的です（ただし、「*」が前にない場合）。 しかし、どのオプションが最も最適であるかを判断する方法は？

私は次の方法で行った：

  1. パターンの最初と最後の3つの位置について、特定の文字コードの発生頻度を計算しました。
  2. 各位置について、これらの周波数の標準偏差を計算しました。
  3. 最小標準偏差で位置の最初と最後に選択されます（ただし、文字コードが1つしかない場合は選択されません）。

原則として、これはすべて機能しましたが、getActions関数の形成プロセスが遅くなり、フィルターの全体的な速度に影響しました。 さらに、同じ周波数のコードの2つのバリアントを持つ位置と同じ周波数のコードの8つのバリアントを持つ位置は同じ標準偏差を持つという考えに悩まされましたが、2番目のバリアントが使用に適していることは論理的に明らかです。 小さなパフォーマンス障害を考慮して、私はこのすべてのバランスをとろうとしませんでしたが、最初と最後のキャラクターの分析に戻りました（実際のデータが約束されました）。

11.実用的な魔法だけでなく



この段階で、ソリューションは検証のために送信されました。

12.満たされていない


ソリューションのパフォーマンスをテストするために、600,000のメッセージと1,000のルールを含むテストデータを準備しました。 また、メッセージの中には、重複したアドレスのペアを持つ単一のメッセージはありませんでした。 これがおそらく、結果をキャッシュすることを考えたことがなかった理由です。

コンテストで使用されるデータを使用してgetActions結果キャッシュを追加することにより、私のマシンでは、大きなデータで15％、xlargeデータで2％のパフォーマンスの向上が得られました（データでは、パフォーマンスが13％低下しました）。 つまり、この形式でソリューションを送信すると、おそらく最終テーブルでは、私の結果はそれぞれ292ミリ秒と2351ミリ秒ではなく約248ミリ秒と2303ミリ秒になり、記事は「12段階で2位」と呼ばれます。 しかし、悲しいかな！

オーガナイザーのおかげで、新しいコンテストを待っています！

Source: https://habr.com/ru/post/J275343/

More articles:


All Articles