質問: i; } } cout << maxi << endl; } 速度を向上させるためのコンパイラーの最適化、その他すべてを知っていますが、私のassemblyソリューションをさらに最適化する方法はあまり多くありません(プログラム的には数学的にではありません)。c++コードには、用語ごとにモジュラス、偶数用語ごとに除算があります。アセンブリは、偶数用語ごとに1つの除算しかありません。しかし、総会はc++ソリューションよりも平均1秒長くかかります。どうしてこれなの?私は主に好奇心から頼みます。実行時間私のシステム:1.4 ghz intel celeron 2955u(haswell microarchitecture)上の64ビットlinux。 g++(最適化されていない):平均1272ミリ秒 g++ -o3 avg 578ミリ秒 元のasm(div)平均2650ミリ秒 asm (shr) avg 679ミリ秒 @johnfound asm 、nasm avg 501ミリ秒でアセンブル @hidefromkgb asm avg 200ミリ秒 @pideter cordesによって最適化された@hidefromkgb asm avg 145ミリ秒 @veedrac c++ avg -o3で81ミリ秒、-o0で305ミリ秒
回答: どちらかといえば無関係なメモとして:より多くのパフォーマンスハック! [最初の「予想」は@shreevatsarによってようやくデビューされました。削除] シーケンスをたどるとき、現在の要素nの2近傍にある3つの可能なケースだけを得ることができます(最初に示されています): [偶数] [奇数] [奇数] [偶数] [偶数] [偶数] これら2つの要素を飛び越えることは、それぞれ(n >> 1) + n + 1、((n << 1) + n + 1) >> 1およびn >> 2を計算することを意味します。 (1)と(2)のどちらの場合でも、最初の式(n >> 1) + n + 1を使用できることを証明しましょう。 ケース(1)は明らかです。ケース(2)は(n & 1) == 1を意味しているので、(一般性を失うことなく)nが2ビット長でそのビットが最上位から最下位までbaであると仮定すると、a = 1が成り立つ。 (n << 1) + n + 1: (n >> 1) + n + 1: b10 b1 b1 b + 1 + 1 ---- --- bbb0 bbb b = !b。最初の結果を右にシフトすると、正確に欲しいものが得られます。 q.e.d .: (n & 1) == 1 ⇒ (n >> 1) + n + 1 == ((n << 1) + n + 1) >> 1。 証明されているように、単一の3項演算を使用して、一度に2要素のシーケンスをトラバースすることができます。さらに2倍の時間短縮。 結果のアルゴリズムは次のようになります。uint64_t sequence(uint64_t size, uint64_t *path) { uint64_t n, i, c, maxi = 0, maxc = 0; for (n = i = (size - 1) | 1; i > 2; n = i -= 2) { c = 2; while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2) c += 2; if (n == 2) c++; if (c > maxc) { maxi = i; maxc = c; } } *path = maxc; return maxi; } int main() { uint64_t maxi, maxc; maxi = sequence(1000000, &maxc); printf("%llu, %llu\n", maxi, maxc); return 0; } ここで、n > 2を比較します。シーケンスの全長が奇数の場合、プロセスは1ではなく2で停止する可能性があるためです。[編集:]これを議会に翻訳しましょう!mov rcx, 1000000; dec rcx; and rcx, -2; xor rax, rax; mov rbx, rax; @main: xor rsi, rsi; lea rdi, [rcx + 1]; @loop: add rsi, 2; lea rdx, [rdi + rdi*2 + 2]; shr rdx, 1; shrd rdi, rdi, 2; ror rdi,2 would do the same thing cmovl rdi, rdx; note that shrd leaves of = undefined with count>1, and this doesn't work on all cpus. cmovs rdi, rdx; cmp rdi, 2; ja @loop; lea rdx, [rsi + 1]; cmove rsi, rdx; cmp rax, rsi; cmovb rax, rsi; cmovb rbx, rcx; sub rcx, 2; ja @main; mov rdi, rcx; add rcx, 10; push rdi; push rcx; @itoa: xor rdx, rdx; div rcx; add rdx, '0'; push rdx; test rax, rax; jne @itoa; push rcx; lea rax, [rbx + 1]; test rbx, rbx; mov rbx, rdi; jne @itoa; pop rcx; inc rdi; mov rdx, rdi; @outp: mov rsi, rsp; mov rax, rdi; syscall; pop rax; test rax, rax; jne @outp; lea rax, [rdi + 59]; dec rdi; syscall; これらのコマンドを使ってコンパイルします。nasm -f elf64 file.asm ld -o file file.o cと、peter cordesによるasmの改良/バグ修正版 on godbolt を参照してください。 (編集者注:あなたの答えに私のものを入れてすみませんが、私の答えはgodboltリンク+テキストからの30,000文字の制限を打ちました!)