C++プログラムにおいて、関数呼叫やループ、回路上的の最適化だけでなく、定数レベルでコードを高速化する手法があります。以下では、実際に効果が期待できる定数最適化の手法を解説します。

共用体（union）の活用

基本的な定義

共用体は複数のメンバーが同一のメモリ領域を共有する特殊なクラスです。定義は以下のようになります（関数内 maupun 関数外どちらでも定義可能）

union DataBlock {
    int num;
    double rate;
    char flag;
};
DataBlock data;

排他的ストレージ的特性

共用体の全メンバーは同一アドレスに配置されるため、いずれかのメンバーが有効な値を持つ場合、他のメンバーは未定義となります以下のコードは誤った使用例です

data.num = 27;
data.rate = 6.7;
cout << data.num;

この特性により、メモリの節約になるだけでなく、CPUキャッシュの効率向上期待できます。複数の変数を頻繁に切り替えながら使用する場合に特に有効です。

オブジェクトを伴う共用体の定義

共用体内にクラスオブジェクトを含めることができます

class Item {
    int value;
};
union DataUnion {
    Item record;
    int key;
};

共用体を通じてクラスのメンバーにアクセスする場合、そのメンバーはpublicである必要があります以下のコードは正常に動作します

#include<bits/stdc++.h>
using namespace std;
class Item {
public:
    int value;
};
union DataUnion {
    Item record;
    int key;
};
DataUnion data;
int main() {
    data.record.value = 114;
    cout << data.record.value;
    return 0;
}

4行目のpublicをprivateやprotectedに変更すると、コンパイルエラーが発生します。

ループの複数経路展開

以下の2つのコードを比較してみましょう

int sum = 0;
for(int i = 1; i <= n; i++) {
    sum += a[i];
}

int sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;
for(int i = 1; i <= n; i += 4) {
    sum1 += a[i];
    sum2 += a[i + 1];
    sum3 += a[i + 2];
    sum4 += a[i + 3];
}
sum = sum1 + sum2 + sum3 + sum4;

前者の実行時間と後者の実行時間を比較すると前者の方が約2倍かかります、ループ展開による並列化効果が顕著に表れています。

ビット演算の活用技法

条件分岐なしの絶対値計算

int absolute(int x) {
    int mask = (x >> 31);
    return (x + mask) ^ mask;
}

条件分岐なしの最大値取得

int maximum(int x, int y) {
    int diff = (x - y) >> 31;
    return y & diff | x & (~diff);
}

除算を用いない平均値計算

int average(int x, int y) {
    return (x & y) + ((x ^ y) >> 1);
}

一時変数なしの変数交換

void swap(int &x, int &y) {
    x ^= y;
    y ^= x;
    x ^= y;
}

値の置換（aからbへ）

x ^= a ^ b;

多次元配列の効率的なアクセス

多次元配列の要素アクセスは.Address計算のオーバーヘッドが大きくなるため、十分な注意が必要です。

以下のコードについて

if(a[i][j][k][l] > a[i][j][k - 1][l] + a[i][j][k][l - 1]) {
    a[i][j][k][l] += a[i][j][k - 1][l] + a[i][j][k][l - 1];
}

以下のように参照で代理変数を用いることで、配列アドレスの再計算を減らせます

int &current = a[i][j][k][l];
int temp = a[i][j][k - 1][l] + a[i][j][k][l - 1];
if(current > temp) {
    current += temp;
}

特に動的計画法（DP）の実装において、この最適化の効果は顕著です。

また，某一の次元が非常に小さい場合

dp[10000000][2]

構造体を用いるか、2つの独立的配列として定義するのが推奨されます

struct DPState {
    int first;
    int second;
} dp[10000000];

// または
int dp0[10000000];
int dp1[10000000];

上記の2つの写法では、構造体を使用する方法がよりメモリ効率的に优于れています。

多次元配列はメモリアクセス順序に配慮する

多次元配列を使用不可避免な場合、メモリ配置に沿ったアクセスパターンを心掛けることが重要です。

以下の2つのコードを検討します

int a[10000][10000], sum = 0;
for(int i = 0; i < 10000; i++) {
    for(int j = 0; j < 10000; j++) {
        sum += a[i][j];
    }
}

int a[10000][10000], sum = 0;
for(int i = 0; i < 10000; i++) {
    for(int j = 0; j < 10000; j++) {
        sum += a[j][i];
    }
}

後者の実行時間は前者と比較して约3倍になります。さらに、配列の各维のサイズが2のべき乗である场合、后者の実行时间は前者の10倍以上となる实测结果があります。

2のべき乗の次元サイズを避ける

实验结果表明、2048×2048の配列の走査は2049×2049の配列と比較して约4倍低速になります。このため、多次元配列の各维のサイズを2のべき乗避けることが推奨されます。可能な限り、各维のサイズを奇数に设定するか、または2のべき乗plus1にすることで、キャッシュalinealignmentによる 성능低下を防ぐことができます。

特に状态圧縮DPなような配列を使用する場合、各维のサイズを+1することをお勧めします。