2020-01-01から1年間の記事一覧
あまりしゃべらないと調子よくない気がする ちゃんと調整していきたいです
std::make_index_sequence<N>は、std::index_sequence<0, 1, 2, ..., N-1>に展開される、メタプログラミングを行う場合や最適化に便利なエイリアステンプレートです。 しかし、以下の問題点があります。 C++14で追加されたため、C++11環境では使えない*1 多くの</n>…
バーチャルっていろいろときれいなのがいいね
容量に上限があるキューを実現するためには、リングバッファを用いるのが最も効率的です。 しかし、ポインタの操作を含むコードを自分で書くのは間違いのもとです。効率を最優先する場合以外は、ライブラリを使うほうが良いです。 C++の場合、std::deque*1を…
gshare分岐予測器について - よーるの補足です。 分岐命令の上位アドレスとグローバル分岐履歴をxor、について 吉瀬 謙二, 片桐 孝洋, 本多 弘樹, 弓場 敏嗣:「高性能プロセッサのための代表的な分岐予測器の実装と評価」Technical Report UEC-IS-2003-2, Ve…
gshare分岐予測器というのは、単純な構造の分岐予測器の中では最も性能が良い分岐予測器であり、1993年に発表されました。 このgshare分岐予測器について、あまり教科書に書いていないことを調べたので、まとめておきます。 この記事には、以下のものが含ま…
いつも通りの日々の連続?
概要 クイックソートは一般に高速なソートアルゴリズムとして知られています。 アルゴリズム中にはピボットを選択する部分がありますが、ここでなるべく中央値に近い値を選択すると、総比較回数を少なくすることができます。 しかし、最近の高性能プロセッサ…
リモートマシンにsshログインしようとしたところ、パスフレーズの入力後に何も反応しなくなることがありました。 正しくない公開鍵を使った場合や、正しくないパスフレーズを入力した場合はログインできないと応答が返ってくるので、リモートマシンの側の問…
輻輳が発生しています……
64bit符号なし整数を素因数分解するため、事前に32bit符号なし整数で表せる素数をリストアップしておくとします。 方法1: 素数のリストをビットベクトルで保持し、試し割り 32bit符号なし整数で表せる奇数が素数であるかを、0, 1で表した列(ビットベクトル…
以下にはABC152のE問題 Flatten のネタバレが含まれます。 この問題は多倍長整数を使用できる言語であれば愚直解が通ります。Haskellで書かれた愚直解のコードは、例えばSubmission #9632460 - AtCoder Beginner Contest 152が簡潔で読みやすいです。 foldr …
Karatsuba乗算、あるいはToom–Cook2乗算とは、入力a0、a1、b0、b1が与えられたとき、a0*b0、a0*b1+a1*b0、a1*b1の三つを出力する際、必要な乗算を四回から三回に減らせるアルゴリズムです。ただし、減算ができることを要求します。 長乗法(筆算と同様の手順…
RISC系の命令セットでは、一命令でレジスタに書き込める即値と、一命令では書き込めない即値が存在する設計になっています。 一命令では書き込めない即値の場合、二命令以上かけて即値を生成することになるわけですが、そこに存在する罠に引っかかった記録で…
今年もよろしくお願いします。 2020ってちょっと不思議な感じのする数字です。 今年は、きっかけを待つのではなくて、自分で行動を起こせる年にしたいです。 あと、お酒飲むのやめます。心身の健康に悪いので……。