知ってると便利なSTL（12） reverse_iterator

基本

逆方向に進むiterator。
rbeginはend - 1と同じ場所を指す。rendはbegin - 1と同じ場所を指す。

上の説明を理解するための簡単なサンプル。

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char **argv) {
    
    vector<int> v{1,2,3,4,5,6,7,8};
    for (auto itr = v.rbegin(); itr != v.rend(); itr++) {
        cout << *itr << endl;
    }

    return 0;
}

実行すると、
8
7
6
5
4
3
2
1
と表示される。v.rbegin()はv.end()-1の場所を指しており、v.rend()はv.begin()-1の場所を指していることが分かる。また、reverse_iteratorは名前の通り逆向きに進むことが分かる。

これだけだと何が嬉しいか分からないので、以下に便利な使い方を示す。

逆順ソート

vectorを逆順にソートしたいときに、reverse_iteratorを使うと短く書ける。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char **argv) {
    
    vector<int> v{1,3,5,7,2,4,6,8};

    // functorを使って書くこともできるが、
    sort(v.begin(), v.end(), greater<int>());
    
    // reverse_iteratorを使うと、短く書ける
    sort(v.rbegin(), v.rend());

    return 0;
}

setの最小値、最大値

beginで最小値、rbeginで最大値を取得出来る。

#include <iostream>
#include <set>

using namespace std;

int main(int argc, char **argv) {
    
    set<int> s{3,2,1,4,8,7,6,5};

    cout << "min = " << *s.begin() << endl;
    cout << "max = " << *s.rbegin() << endl;

    return 0;
}

エラトステネスの定数倍高速化術

　Project Eulerのとある問題でエラトステネスの篩を高速化している人がいた。
なかなか興味深かったので、コードを読みといて自分なりにアレンジしてみた。

ローカル環境で約2倍の高速化に成功した。1e8までのふるいが0.7s程度で実行出来た。

普通のふるい

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e8;
bool pr[N];

int main(int argc, char **argv) {
    
    fill(pr + 2, pr + N, true);

    for (int i = 0; i * i < N; i++) {
        if (!pr[i])
            continue;

        for (int j = i * i; j < N; j += i)
            pr[j] = false;
    }

    int x = 0;
    int y = 0;
    for (int i = 0; i < N; i++)
        if (pr[i])
            x ^= i, y = 23 * y + i;
    
    cout << x << endl;
    cout << y << endl;

    return 0;
}

定数倍高速版ふるい

アイディアとしては、

1. 2以外の偶数は素数ではないため、ふるいの配列は奇数に対してのみ用意する。
2. 素数か合成数かのフラグをboolではなくintのビットで管理する。

というもの。

1.で約2倍高速になった。これは直感的にも理解しやすい。一番内側の処理の実行回数が半分程度になるため2倍程度速くなりそうである。

1.の後に2.を施すことで、さらに1.4倍ほど高速になった。32ビット毎に何らかの処理を纏めたというわけではなく、単純にフラグの管理をビットで行うようにしただけであるが意外と速くなった。使用するメモリがコンパクトになったためキャッシュに乗りやすくなったということだろうか。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e8;
const int BITS = 32;

#define BACKET(n) (n / 2 / BITS)
#define MASK(n) (1 << n / 2 % BITS)

int pr[BACKET(N) + 1];    // sieve arrray containing only odd numbers  [1,3,5,7,,9,....]

int main(int argc, char **argv) {
    
    fill(pr, pr + BACKET(N) + 1, -1);
    pr[0] = -2;   // 1 is not prime

    for (int i = 1; i * i < N; i += 2) {
        if (!(pr[BACKET(i)] & MASK(i)))
            continue;
        for (int j = i * i; j < N; j += 2 * i)
            pr[BACKET(j)] &= ~MASK(j);
    }

    int x = 0;
    int y = 0;
    for (int i = 0; i < N; i++)
        if (i == 2 || i % 2 && (pr[BACKET(i)] & MASK(i)))
            x ^= i, y = 23 * y + i;

    cout << x << endl;
    cout << y << endl;

    return 0;
}

Python Idioms (4) モジュールに別名をつける

import句にasを付けるとモジュールに別名をつけることが出来る。
同様に、from import句にasを付けるとモジュール内の関数に別名を付けることが出来る。

これを使って、
重複なし組み合わせ（nCk）と重複組み合わせ（nHk）を計算する関数を書いてみた。

from math import factorial as f

def c(n, k):
    return f(n) / f(k) / f(n - k)

def h(n, k):
    return c(n - 1 + k, k)

おいら、レベル4に上がったっぺ