楽しんでいただければ幸いですチャレンジ 4 。 今後、何か良いチャレンジになりそうなアイデアがありましたら、ぜひお知らせください。 良い素材を常に探しています！
おめでとう、 @降下する！あなたは、1,000 桁 (9.88 秒) および最長桁 (7,150) のチャレンジの 100 ペアの両方で、最速の (スタッフ以外の) エントリーを達成しました。 これは、1,000 桁の数値の 100 組すべてを 10 秒以内に読み取ることができる唯一のスクリプト (次に近いものは 10 しか管理できない) だけでなく、次に近いエントリよりも 3.5 倍大きい 2 つの数値を乗算することもできました。 さらに、これはすべてのスクリプト (スタッフおよび非スタッフ) の中で最も短く、1,000 文字強でした。 以下のスクリプトに含めました。 4 回のチャレンジ後の合計ポイントは次のとおりです。
大きな数値の乗算について話す前に、数字の文字列のアンパックまたはベクトル化、つまり数字の文字列を数値のベクトルに変換することについて話しましょう。 先月見たように、次を使用して数字の文字列を一度に 1 つずつ解析します。サブ文字列ループ内では痛ましいほど遅いです。 これにより、一般的な代替案が 2 つ残されます: 1) 文字列を個々のユニットに分解し、それらをベクトルに変換できる形式に戻します (解析する、たとえば）または、2）パターン マッチングを使用します。 私の最初の傾向は、アプローチ 1 を使用することです。 私は何年もの間、JSL パターン マッチング関数について学ぶことに抵抗してきました。 労力が大きすぎ、情報と例が少なすぎ、そして私は怠け者でした。 必要なものはすべて揃っていると思いました正規表現機能、私はよく知っていました。 もうない。
これらの課題により、パターン マッチングのスピードと効率に目が開かれました。 私に説明したように、 @Craige_Hales 、これらの機能を担当する開発者であり、課題の定期的な参加者であり、JSL のパターン マッチング ルーチンが基礎となります。正規表現が建てられています。 その効率性を実証するには、次のコードを実行します。ベクトル化の例.JSLでは、4 つの異なるベクトル化方法を比較します。 スクリプトには乱数の長い文字列を生成する短い関数も含めました。 10,000 個の数字の文字列の場合、ループ内で数字を 1 つずつ解析するのが最も遅く、私のマシンでは約 11 秒かかります。 使用する言葉そして連結リストベクトルに解析できる文字列に数字を分解して再構築する方がはるかに優れています (0.0965 秒)。
を使用して同じことを行うと、正規表現そして解析するそれよりわずかに優れています (0.08543)。 パターン マッチングにより、この時間が驚くべき 4 倍 (0.02179) 短縮されます。 50,000 桁の時間差はごくわずかですが、5,000,000 桁を考慮すると、どちらの解析アプローチでも約 10 分かかるのに対し、パターン マッチングには 2 秒かかり、他の方法とは異なり、ほぼ直線的にスケールされます。 JSL でのパターン マッチングについて詳しく知りたい場合は、次のスクリプトを参照してください。 @Craige_Halesまたは@David_Burnham (誰が持っていますか詳しい情報と例を記載した彼自身のブログ投稿がいくつかあります。）
乗算ルーチンに進みます。 すべてのベクトル化にパターン マッチングが使用されます。 さらに、最初の例では、最後のチャレンジからの最速の加算アルゴリズムが使用されています。 最初のアプローチ ( multiplyBig Slow.JSL ）これまでのチャレンジで学んだこと以外は何も使用しません。 一度に 2 桁の数字を乗算し、被乗数と乗数の位置に応じて必ずゼロを追加します (たとえば、百の位の数字に十の位の数字を掛ける場合は、ゼロを 5 つ追加します)。 最初の入力が大きくなるように関数が入力を順序付けしているにもかかわらず、これは利点がありません。 同じ数の操作が実行されます。 ただし、最後の例ではこれが変わります。 この関数は遅く、100 個の 100 桁の数字を処理するのに 30 秒近くかかります。
でmultiplyBig Faster.JSLレジスターの桁数は 1 から 7 に増加します。これは、JSL がオーバーフローすることなく表現できる桁数の約半分です。 この選択の理由は、2 つの大きな 7 桁の数値を乗算すると明らかであり、その結果は 14 桁にもなる場合があります。 7 桁のレジスタには 14 桁が含まれる可能性があるため、最後の例で使用した加算ルーチンは、7 桁を超えるものが次のレジスタに繰り越されるように変更する必要があります。 それにもかかわらず、考慮する必要があるのは正の数のみであるため、結果として得られるコードはかなり短くなります。 さらに、100 桁の数値ペアを 100 個乗算すると、結果が大幅に向上します (0.04375 秒)。 この実装では、100 個の 1000 桁のペアを乗算する適切な処理も実行されます (1.54 秒)。
簡単な変更を 1 つ行うだけで、さらに速く進むことができます。 一度に 1 つのレジスタを乗算するのではなく、 multiplyBig Fastest.JSL JSL 行列演算を使用して、短い数値の各レジスタを大きい数値全体で乗算します。 このアプローチは以前のアプローチよりも高速で、100 個の 1,000 桁のペアで 0.3015 秒でクロックが発生し、5 倍の改善です。
さらに速く進むことができます。 ファイルmultiplyBig – Brady.JSLは、1,000 桁の数値の乗算ではわずかに遅くなりますが、数値のサイズが約 2,000 桁以上に達すると優れています。 これは、乗算と加算を同じループ内で実行できるように演算の順序を変更することで実現されました。 この背後にある詳細については私がカバーしたい範囲を超えていますが、 @brady_brady興味があれば、この投稿に追加できる短い記事を喜んで書きますと彼は言いました。 もっと早く？ 多分。 乗算演算の数を O(n から削減する) 暗号学で通常使用される 2 つの注目すべき乗算アルゴリズムがあります。 2 ） にの上1.58 )またはより低い。 大きな数値を伴う追加演算が必要になるため、JSL の方が高速かどうかを言うのは困難です。 この投稿の時点では、これらのアルゴリズムのいずれの高速 JSL バージョンも実装しようとしましたが、実装できませんでした。
2020 年 8 月 1 日:おかげで@Craige_Halesバグを捕まえるためにmultiplyBig Fastest.JSL 。 問題を修正しました。 また、Craige の multiplyBig スクリプトも追加しました。これは、実行するつもりでしたが忘れていました。 彼はアルゴリズムを高速化する方法としてルックアップ テーブルを使用しています (いくつかの注意点があります)。 彼の脚本はいつものように徹底したコメントだ。
