Tociyuki::Diary RSSフィード

tociyuki による Perl・Ruby・C++・C で書き散らしたコードを中心に、日常雑記も混在 : B  F  twitter  GitHub  CPAN  本館  公開鍵
 

2016年08月05日

[]Least Recently Used 用リング

Least Recently Used (LRU) を、 一つのリングで書いてみます。 つまり、 Baker のトレッドミルからぱくって、 リングの途中に 2 つの番兵項目を置き、 リングを 2 つのリストに分割します。 リストの一方を使用中項目リストに使い、 もう一方をフリー・リストに使います。 なお、 項目数上限固定の LRU では本質的にガベージ・コレクションは不要で、 Baker のトレッドミルで運用するのはオーバー・ヘッドが無駄にかかるだけです。 ぱくるのはリングのつなぎかただけとします。

ちなみに、 これまでここで書いてきた LRU では、 使用中リストとフリー・リストを、 それぞれ別の番兵項目につないで、 2 つのリングにしてきました。 それぞれのリングは、 教科書のリングそのもののふるまいをします。 それを今回は 1 つのリングにするようにつなぎかたを変更してみようというわけです。

書いてみた結果、 つなぎかたを変更した相違点はリストの空判定と末尾判定に吸収されて、 他はまったく同じ済みました。 ベンチマークにも違いはでません。 そうなるのが当然です。 つなぎかたが変わるだけでリストとしての本質は同じですから。 さらに、 単体テストのリング内部のふるまい記述が変わりますが、 どちらでもメンテナンスのしやすさに大差はありません。

ということで、 結論。 どちらのつなぎかたでも大差はありません。 教科書のリングのふるまいに合わせたいか、 Backer のトレッドミル風にするかの違いだけです。

#include <vector>

class least_recently_used_type {
public:
    explicit least_recently_used_type (std::size_t numentry);
    void set (int key, int value);
    int get (int key, int default_value);
    void erase (int key);

private:
    bool empty (void) const;
    bool full (void) const;
    void move (std::size_t from, std::size_t to);
    std::size_t find (int key) const;

    struct ring_type {
        int key;
        int value;
        std::size_t prev, next;
    };
    std::size_t m_latest, m_ring_free;
    std::vector<ring_type> m_ring;
};

お試しなので、 下部構造のキャッシュされるデータ部分を簡略にして整数の key と value だけとします。 それをリングの項目に一体化します。 リングの 2 つの番兵の添字を m_latest と m_ring_free にします。 コンストラクタには、 番兵を除く項目数の上限を与えます。 リング中でのリストの順方向を両方共 next で辿る方向とします。 番兵以外のすべての項目をフリー・リスト側に並べるようにリングを初期化します。

least_recently_used_type::least_recently_used_type (std::size_t numentry)
{
    numentry += 2;
    m_ring.resize (numentry);
    for (std::size_t i = 0; i < m_ring.size (); ++i) {
        m_ring[i].prev = i - 1;
        m_ring[i].next = i + 1;
    }
    m_ring[0].prev = m_ring.size () - 1;
    m_ring.back ().next = 0;
    m_ring_free = 0;
    m_latest = m_ring[m_ring_free].prev;
}

使用中リストが空かどうかを判定します。

                       m_latest  m_ring_free
                         ↓      ↓
 → [6] → [7] → [8] → [9] → [0] → [1] → [2] → [3] → [4] → [5] →

具体的には、 番兵 m_latest の直後が番兵 m_ring_free のとき、 使用中リストが空になっています。

bool
least_recently_used_type::empty (void) const
{
    return m_ring[m_latest].next == m_ring_free;
}

使用中リストが満杯かどうかを判定します。 言い換えると、 フリー・リストが空かどうかを判定すれば良いわけです。

         m_ring_free   m_latest   
                  ↓     ↓
 → [7] → [8] → [0] → [9] → [1] → [2] → [3] → [4] → [5] → [6] →

具体的には、 番兵 m_latest の直前が番兵 m_ring_free のとき、 フリー・リストが空になっています。

bool
least_recently_used_type::full (void) const
{
    return m_ring[m_latest].prev == m_ring_free;
}

使用中リストから key を探します。 戻り値は ring ベクタの添字です。 見つからないときは、 番兵の添字 m_ring_free を返します。

std::size_t
least_recently_used_type::find (int key) const
{
    std::size_t p = m_ring[m_latest].next;
    while (p != m_ring_free) {
        if (m_ring[p].key == key) {
            return p;
        }
        p = m_ring[p].next;        
    }
    return m_ring_free;
}

使用中リストに key と value のペアをセットします。 まず、 使用中リストに既に存在しているかどうかを find メンバ関数で調べます。 見つかったときは、 value を書き換えた上で、 使用中リストの先頭へ項目をつなぎかえます。 見つからなかったときは、 m_latest を一つ前へ動かします。 さらに、 フリー・リストが空のときは、 m_ring_free も一つ前へ動かします。

void
least_recently_used_type::set (int key, int value)
{
    std::size_t const p1 = find (key);
    if (p1 != m_ring_free) {
        m_ring[p1].value = value;
        move (p1, m_latest);
        return;
    }
    if (! full ()) {
        m_latest = m_ring[m_latest].prev;
    }
    else {
        m_latest = m_ring_free;
        m_ring_free = m_ring[m_ring_free].prev;
    }
    std::size_t const p2 = m_ring[m_latest].next;
    m_ring[p2].key = key;
    m_ring[p2].value = value;
}

使用中に項目があるときは、 それの値をとりだして項目を先頭へ移動します。 ないときは、 引数の default_value を返します。

int
least_recently_used_type::get (int key, int default_value)
{
    std::size_t const p = find (key);
    if (p != m_ring_free) {
        move (p, m_latest);
        return m_ring[p].value;
    }
    return default_value;
}

項目を削除します。 使用中リストに見つかった場合に、 それをフリー・リストへ移動します。

void
least_recently_used_type::erase (int key)
{
    std::size_t const p = find (key);
    if (p != m_ring_free) {
        move (p, m_ring_free);
    }
}

項目を移動します。 from は移動対象項目の添字です。 to は移動先の添字で、 それの next が from になるようにつなぎかえます。 つなぎかえは、 from を削除し、 to の next になるように挿入をします。

void
least_recently_used_type::move (std::size_t from, std::size_t to)
{
    if (from == m_latest || from == m_ring_free || m_ring[to].next == from) {
        return;
    }
    m_ring[m_ring[from].prev].next = m_ring[from].next;
    m_ring[m_ring[from].next].prev = m_ring[from].prev;
    m_ring[from].prev = to;
    m_ring[from].next = m_ring[to].next;
    m_ring[m_ring[from].prev].next = from;
    m_ring[m_ring[from].next].prev = from;
}

2016年07月22日

[]Unicode の文字数カウント

一年半前に C++11 に慣れるために GNU coreutils の wc (1) コマンドを書き直したときに、 wc (1) に合わせて文字数をワイド文字の個数としていました。 ところで、 LC_CTYPE が ja_JP.UTF8 のとき、 UTF-8デコードしたコード・ポイント一つずつがそのままワイド文字に変換されるだけです。 そのため、 複数のコード・ポイント列が一文字になる合成文字や異字体漢字が入力に含まれている場合、 出力は文字の個数ではなくなります。 ここは、 やはり文字数を表示するように改善したいものです。

合成文字を一文字に数えるのは簡単で、 結合クラスがゼロでないコード・ポイントを無視すればことたります。 異字体漢字も同様で、 異字体セレクタを無視すれば良いだけです。 他に、 無視するべきは、 既に使ってはいけないことになっている幽霊コード・ポイントの言語タグと、 UTF-8 では出現してはならないサロゲートも無視することにします。 これで、 だいたい表示される見た目の文字数に近い個数が文字数として出力されることになります。 扱いに迷うのは書式文字で、 左右上下の方向指定コード・ポイントやグリフ結合指定コード・ポイントは無視した方が良いのかもしれないと考えつつも、 今回は文字として扱って個数にいれています。

namespace ucd {

int canonincal_combining_class (char32_t codepoint);
bool is_surrogate (char32_t codepoint);
bool is_variation_selector (char32_t codepoint);
bool is_language_tag (char32_t codepoint);

}//namespace ucd

static inline bool
is_character_base_code (char32_t codepoint)
{
    return ! ucd::is_surrogate (codepoint)
        && ! ucd::is_variation_selector (codepoint)
        && ! ucd::is_language_tag (codepoint)
        && ucd::canonincal_combining_class (codepoint) == 0;
}

結合クラスには UnicodeData Canonical Combining Class のダブル配列トライ を使います。 他は、 コード範囲に含まれているかどうか調べるようにします。

namespace ucd {

bool
is_surrogate (char32_t codepoint)
{
    return 0x00d800L <= codepoint && codepoint <= 0x00dfffL;
}

bool
is_variation_selector (char32_t codepoint)
{
    return (0x180bL <= codepoint && codepoint <= 0x180dL)
        || (0xfe00L <= codepoint && codepoint <= 0xfe0fL)
        || (0xe0100L <= codepoint && codepoint <= 0xe01efL);
}

bool
is_language_tag (char32_t codepoint)
{
    return 0xe0001L <= codepoint && codepoint <= 0xe007fL;
}

}//namespace ucd

これで文字を数えるように修正することができます。 以前はワイド文字列の長さを足していたのを止めて、 文字の個数を数えるのに使うコード・ポイントを数えるようにします。

void wordcount_counter::countline (std::string& octets)
{
    auto line = t42::decode (octets);
    bc += octets.size ();
    bt += octets.size ();
    if (! octets.empty () && octets[octets.size () - 1] == '\n') {
        lc++;
        lt++;
    }
    enum {OUTWORD, INWORD} state = OUTWORD;
    std::locale loc (std::locale::classic (), "", std::locale::ctype);
    for (auto c : line) {
        if (is_character_base_code (c)) {
            cc++;
            ct++;
        }
        if (std::isspace (c, loc)) {
            state = OUTWORD;
        }
        else if (state == OUTWORD) {
            state = INWORD;
            wc++;
            wt++;
        }
    }
}

2016年07月12日

[][]UnicodeData Canonical Combining Class のダブル配列トライ

Unicode の合成文字は、 UnicodeData.txt の第 3 欄 Canonical Cobining Class の数値がゼロでないものを抽出します。 以前は狭い範囲で収まっていて単純なテーブル参照で済んでいたのですけど、 広い範囲にばらけながら増える一方なので、 ダブル配列のトライを作ることにしました。

コードポイントの下 3 バイトを使い、 それぞれのバイトでトライ木の枝分かれをしていくようにします。

int
canonincal_combining_class (char32_t codepoint)
{
    static const short base[] = {
        // Perl で生成
    };
    static const short check[] = {
        // Perl で生成
    };
    int const ncheck = sizeof (check) / sizeof (check[0]);
    int const k0 = (codepoint >> 16) & 0xff;
    int const k1 = (codepoint >>  8) & 0xff;
    int const k2 = (codepoint      ) & 0xff;

    int state = 1;
    int next_state = base[state] + k0;
    if (0 < next_state && next_state < ncheck && check[next_state] == state) {
        state = next_state;
        next_state = base[state] + k1;
        if (0 < next_state && next_state < ncheck && check[next_state] == state) {
            state = next_state;
            next_state = base[state] + k2;
            if (0 < next_state && next_state < ncheck && check[next_state] == state) {
                return base[next_state];
            }
        }
    }
    return 0;
}

ダブル配列は Perl で生成します。

#/usr/bin/env perl
use strict;
use warnings;
use List::Util qw(any shuffle);

my %trie;
#@<UnicodeData.txt を読んで、第 0 欄をキー、第 3 欄を値とするトライ木を作ります@>

my @base = (0);
my @check = (-1, -1);
#@<トライ木からダブル配列を作ります@>

print "static const short base[] = {\n    ";
for my $i (0 .. $#check) {
    printf "%4d,%s", defined $base[$i] ? $base[$i] : 0,
        $i % 10 < 9 ? " " : "\n    ";
}
print "\n};\nstatic const short check[] = {\n    ";
for my $i (0 .. $#check) {
    printf "%4d,%s", defined $check[$i] ? $check[$i] : 0,
        $i % 10 < 9 ? " " : "\n    ";
}
print "\n};\n";

Unicode 8.0 での対象コードポイントは 751 個にすぎないので、 トライ木を作って、 それから静的にダブル配列を作ることにします。

#@<UnicodeData.txt を読んで、第 0 欄をキー、第 3 欄を値とするトライ木を作ります@>=
while (<>) {
    my @f = split /;/, $_, -1;
    next if $f[3] == 0;     # Start コードポイントは対象外
    my $codepoint = hex($f[0]);
    my $k0 = ($codepoint >> 16) & 0xff;
    my $k1 = ($codepoint >>  8) & 0xff;
    my $k2 = ($codepoint      ) & 0xff;
    $trie{$k0}{$k1}{$k2} = $f[3];
}

初期状態を 1 として、 ダブル配列を作ります。 トライ木からダブル配列を作るには、 分岐の節のキーをストアップし、 それを check 配列の隙間にはめ込んでいきます。 深さ優先と幅優先の両方で動かしてみて、 どちらが小さなダブル配列になるか比較してみたのですが、 優位差は生じなかったので、 深さ優先の方を書いておきます。

#@<トライ木からダブル配列を作ります@>=
my $s0 = 1;
my @key0 = sort { $a <=> $b } keys %trie;
$base[$s0] = 2 - $key0[0];
for my $k0 (@key0) {
    $check[$base[$s0] + $k0] = $s0;
}
for my $k0 (@key0) {
    my $s1 = $base[$s0] + $k0;
    my @key1 = sort { $a <=> $b } keys %{$trie{$k0}};
    $base[$s1] = 1 - $key1[0];
    while (any { defined $check[$base[$s1] + $_] } @key1) {
        ++$base[$s1];
    }
    for my $k1 (@key1) {
        $check[$base[$s1] + $k1] = $s1;
    }
    for my $k1 (shuffle @key1) {
        my $s2 = $base[$s1] + $k1;
        my @key2 = sort { $a <=> $b } keys %{$trie{$k0}{$k1}};
        $base[$s2] = 1 - $key2[0];
        while (any { defined $check[$base[$s2] + $_] } @key2) {
            ++$base[$s2];
        }
        for my $k2 (@key2) {
            $base[$base[$s2] + $k2] = $trie{$k0}{$k1}{$k2};
            $check[$base[$s2] + $k2] = $s2;
        }
    }
}

key1 をシャッフルして、 割り当て順をランダムに変えています。 これで、 なんどかスクリプトを走らせて、 一番行数が少ないものを選んで利用しています。 1 行 10 個ずつで折り返して、 base と check あわせて少ない方は 2100 行前後になります。