参加してくださった方々に改めて感謝するとともに、この遅い投稿にお付き合いいただきありがとうございました。 全員が課題をクリアすることができました。 非 JMP スタッフによる最大追加番号 (約 200 万桁) と最大 1,000 桁リスト (約 2,000 項目) の両方の課題を克服したのは、 @David_Burnham 。 スタッフのエントリの場合、5 秒以内に加算された最大の 2 つの数字は約 2,200 万でした ( @brady_bradyそして@Craige_Hales )、最大のリストは約 61,500 要素でした (チャレンジ 3 例 3.JSL ）。 これらのスクリプトは以下に掲載されています。
3 つのチャレンジの合計ポイントは次のとおりです。
2 つの数値を含む演算から始めましょう。 課題 3 例 1 – low.JSLは、ほとんどのエントリと同様の実装を提供します。
- 数値が同じ符号 (加算) であるか反対の符号 (減算) であるかを判断します。
- 数値文字列を解析します。
- 加算/減算演算を実行します。
- 結果を連結して答えを作成します。
加算と減算の演算が 1 つの関数で実行されるか複数の関数で実行されるかはスタイルの問題であり、プログラムの明瞭さと読みやすさにのみ影響しますが、実行時間には影響しません。 ただし、大きな違いは、入力された数値がどのように解析され、元に戻されるかということです。 個々の数字をループする前に入力文字列を解析します (課題 3 例 1 – より高速な.JSL ) ループ内ではなく、演算速度が約 5 倍になります (2.28 秒、16,000 桁の数値を 2 つ追加する場合は 0.464 秒)。 結果をリストに収集し、最後に項目を連結することでループ内から個々の文字列の連結を削除すると、処理速度が 10 倍 (0.04054 秒) 以上向上します。(課題 3 の例 1 – 最速.JSL) を参照してください。
これをさらに高速化する方法について説明する前に、リストに数値を追加する方法について説明する必要があります。 ほぼ全員がこの問題に対処するために、リストを一度に 1 つずつ繰り返し、それぞれを累計に追加していました。 これは最終的に最速のアプローチではありませんでしたが、非常に高速に行うことができました (課題 3 - Hales.JSL 5 秒以内に 51,000 個の 1,000 桁の数字を追加しました)。 ほとんどの操作と同様、速度向上の鍵は、すべての条件が同じ場合に操作の数を最小限に抑えることです。 提供された例では、チャレンジ 3 例 2.JSLの場合、解決策は、桁上げ/借用操作を数値のペアごとに 1 セットから合計 3 セットに減らすことでした。 これは次のようにして実現されました。
- 入力数値を 2 つの行列 (正の数用と負の数用) にロードします。
- 次を使用して各行列を個別に追加します。 V 合計、2 つの結果行列に対して 1 セットのキャリー操作を実行します。
- 大きい数値から小さい数値を引きます。 結果に対して一連の借用操作を 1 回実行します。 最終的な減算は、上で説明した 2 つの数値アルゴリズムを使用して実行されます。
桁上げ/借用操作中に一度に複数の桁を考慮することにより、2 つの数値とリストの操作をさらに高速化できます。 これは両方で行われました課題 3 - Hales.JSLそしてチャレンジ 3 - Brady.JSL 。 自然な傾向として 1 つの数値で加算/減算/桁上げ/借用を行うことですが、オーバーフローが発生しない限り、少しの工夫でこの手順をできるだけ多くの数値に一般化することができます。 でJMP 、これは 2 つの数字の場合は 14 桁になります。 14 – フロア(ログ10(リストサイズ– 1))数字、 どこリストサイズリストの場合の入力リスト内の項目の数です。 この理由を理解するには、オーバーフローが約 9e16 で発生することを思い出してください。 15 桁の最大 2 つの数字 (9 が 15 個) を加算すると、オーバーフロー エラーが発生します。 14 桁の最大 2 つの数字を加算しても加算されません。 同様に、9,999,999,999,999 をそれ自体に加算すると、11 ～ 100 回 (正確には 91 回) 実行されるとオーバーフローが発生します。
これがどのように機能するかを示す例として、各数値が 14 個のレジスタに配置されている 3 つの数値を追加することを考えてみましょう。
11 99999999999999
22 99999999999999
33 99999999999999
最初のレジスタ (9 の 14 個) の値を合計すると、次のようになります。
2 99999999999997
2 をキャリーして 2 番目のレジスタを合計すると、次のようになります。
68
最終的な数字は
68 99999999999997
このアプローチの適用は次のとおりです。チャレンジ 3 例 3.JSL 。 200 万桁の 2 つの数値を加算する平均処理時間は 4.7 秒から 0.82 秒に短縮され、5 倍以上の速度向上が見られます。 追加の調整により、速度がさらに 2 倍向上することがわかります。課題 3 - Hales.JSLそしてチャレンジ 3 - Brady.JSL 1000 桁の数値を 10,000 個追加するのに必要な時間は、4.5 秒から 0.88 秒 (5 倍) に短縮されました。 これにより、リストを追加するアプローチが最速になります。
2020年7月20日:もう 1 つのバグ修正、今回はチャレンジ 3 例 3.JSL 。 3 つの例 1 ファイルすべてに行列引数を使用する場合の警告メッセージを追加しました (例 2 までは実装されていません)。
2020年7月17日:チャレンジ 3 の例 1 スクリプトに別のバグが見つかりました。3 つすべてが修正され、置き換えられました。
2020 年 7 月 16 日: スクリプトを置き換えました課題 3 例 1 - 遅い.JSLそして課題 3 例 1 - より高速な.JSL問題を引き起こす行が最後に含まれているためです (コードのテストに使用していたテーブルを参照しています)。 これらのファイルをダウンロードしても問題を自分で解決していない場合は、古いコピーを置き換えてください。
