2017-03-19

SQLite3でちょっと複雑なソート

SQL

studies.hatenablog.com
studies.hatenablog.com

応用情報の勉強をしなければならない。
といっても、なかなか腰が上がらないものである。
気づけば日曜日の夜である。

今回は普段触らないSQLで例の問題を解く。
きっと、応用情報の役に立つはずだ（？）

今、city_tableの中身はこんな感じ。

sqlite> SELECT *
   ...> FROM city_table;
city_id|city_name|pref
1|京都市|京都府
2|千代田区|東京都
3|高岡市|富山県
4|松本市|長野県
5|宮津市|京都府
6|川崎市|神奈川県
7|諏訪市|長野県
8|渋谷区|東京都
9|滑川市|富山県
10|新宿区|東京都
11|臼杵市|大分県
12|稚内市|北海道
13|氷見市|富山県
14|いわき市|福島県
15|長野市|長野県
16|横須賀市|神奈川県
17|宇治市|京都府

これをソートして出力する。

次のようなSQL文でいける。

sqlite> SELECT city_table.*
   ...> FROM city_table
   ...> INNER JOIN ( SELECT pref, MIN(city_id) AS  pref_id
   ...>              FROM city_table
   ...>              GROUP BY pref ) AS pref_table
   ...> ON city_table.pref = pref_table.pref
   ...> ORDER BY pref_table.pref_id, city_table.city_id;
city_id|city_name|pref
1|京都市|京都府
5|宮津市|京都府
17|宇治市|京都府
2|千代田区|東京都
8|渋谷区|東京都
10|新宿区|東京都
3|高岡市|富山県
9|滑川市|富山県
13|氷見市|富山県
4|松本市|長野県
7|諏訪市|長野県
15|長野市|長野県
6|川崎市|神奈川県
16|横須賀市|神奈川県
11|臼杵市|大分県
12|稚内市|北海道
14|いわき市|福島県

まず、サブクエリを使って、pref_tableを作る。
pref_tableは県名と、県の優先度が書かれている。
こんな感じのテーブルだ。

sqlite> SELECT pref, MIN(city_id) AS  pref_id
   ...> FROM city_table
   ...> GROUP BY pref;
pref|pref_id
京都府|1
北海道|12
大分県|11
富山県|3
東京都|2
神奈川県|6
福島県|14
長野県|4

続いて、city_tableとpref_tableを県名をキーにinner join。
pref_idを第一キー、city_idを第二キーにしてorder by。
最後にcity_tableの要素だけを出力。

これでいい…。
と思ったけど、相関サブクエリでスカラを返させたほうがかっこいいかもしれない。

sqlite> SELECT *
   ...> FROM city_table AS XX
   ...> ORDER BY ( SELECT MIN(city_id)
   ...>            FROM city_table AS YY
   ...>            WHERE XX.pref = YY.pref ),
   ...>          city_id;
city_id|city_name|pref
1|京都市|京都府
5|宮津市|京都府
17|宇治市|京都府
2|千代田区|東京都
8|渋谷区|東京都
10|新宿区|東京都
3|高岡市|富山県
9|滑川市|富山県
13|氷見市|富山県
4|松本市|長野県
7|諏訪市|長野県
15|長野市|長野県
6|川崎市|神奈川県
16|横須賀市|神奈川県
11|臼杵市|大分県
12|稚内市|北海道
14|いわき市|福島県

慣れないことをすると頭を使う。

2017-03-18

pythonとhaskell, perl6で加重平均

python haskell perl6

python。
最後はnumpyの内積（ドット積）を使っている（ずるい？）

>>> weight = [ 0.22, 0.14, 0.04, 0.12, 0.22, 0.26 ]
>>> record = [ 64, 51, 132, 24, 19, 11 ]
>>> sum( a * x for (a, x) in zip(weight, record) )
36.42
>>> sum(map(lambda a, x: a * x, weight, record))
36.42
>>> import operator as op
>>> sum(map(op.mul, weight, record))
36.42
>>> import numpy as np
>>> np.dot(weight, record)
36.420000000000002

haskell。

Prelude> let weight = [ 0.22, 0.14, 0.04, 0.12, 0.22, 0.26 ]
Prelude> let record = [ 64, 51, 132, 24, 19, 11 ]
Prelude> sum $ zipWith (*) weight record
36.42

perl6も面白い。

> my @weight = 0.22, 0.14, 0.04, 0.12, 0.22, 0.26
[0.22 0.14 0.04 0.12 0.22 0.26]
> my @record = 64, 51, 132, 24, 19, 11
[64 51 132 24 19 11]
> [+] @weight >>*<< @record
36.42

2017-03-12

void *p = &p : 自分自身を参照する初期化の問題

C/C++

久しぶりの投稿はちょっと変な話。

次のように、自分自身を参照するポインタを作ってみる。

#include <stdio.h>

int main(void)
{
    void *p = &p;
    printf("%p\n", p);
    return 0;
}

自分の環境では、普通にコンパイルが通る。
そして、実行するたびに結果が変わる（実行のたびに別のアドレスにpが配置される）。

こんなプログラムは何の意味もないと思うかもしれないが、次のような場合はどうだろうか？

typedef struct List {
    char value;
    struct List *next;
} List;

static List terminator = {0, &terminator};
List * const tail = &terminator;

terminatorは自分自身を参照するセルである。
つまり、tailは要素数1の環状リストである。

ふつう、線形リストの最後はNULLを指すことで終端を示すが、このような要素数1の環状リストで最後を「結んで」やると、簡潔にコードをかける場合がある（と思う）。
というのは、こうすることで、NULLのnextを参照してしまう恐れがなくなるからだ。

しかし、この書き方には疑問が残る。
つまり、宣言と同時に初期化する場合、実行順序として、「左辺のメモリの確保」→「右辺の評価」となっていることは保証されているのか、という問題である。

    void *p = &p;

が許されるということは、私のコンパイル環境ではその実行順序で正しいようだが、これには一般性があるだろうか？
つまり、規格的にはどうだろうか？
少しネットを探してみたが、それらしい記事を見つけることはできなかった。

もし、この実行順序が保証されないとすると、少し厄介なことも起こる。

static List terminator;
List * const tail = &terminator;

void initialize_tail(void)
{
    tail->value = 0;
    tail->next = tail;
}

terminatorとtailを宣言した後で、ユーザにtailの初期化関数initialize_tail()を呼び出してもらわなければならなくなる。
（関数の「外」に代入文はかけないため）。
C#とかなら、terminatorやtailをListクラスの静的メンバとして、静的コンストラクタを用いて初期化すればよさそうだが、Cではそうもいかない。
これはけっこう厄介だと思う。

2017-02-07

無名共用体を見かけた

C/C++

無名共用体(anonymous union)を久しぶりに見た。

無名共用体というのは、こんなやつ。

#include <iostream>
using namespace std;

static struct {
    char dummy;
    union {
    // これが無名共用体よ
        long data_double_word;
        struct {
        // これは無名構造体だ
        // リトルエンディアンを想定
            short data_word_low;
            short data_word_high;
        };
    };
} foo;

int main() {
    foo.data_word_low = 8;
    foo.data_word_high = 1;
    cout << foo.data_double_word << endl; // 65544 = 1 << 16 + 8
}

しかし、気になったことには、今回見かけたソースは上のようなC++のソースではなく、Cで書かれていた。
Cでanonymous unionとか、anonymous structなんて使えるのか？？

Cで書くならこうだろうと思っていた（というか、こういうコードしか見たことがなかった）ので、少し意外な感じ。

#include <stdio.h>

static struct {
    char dummy;
    union {
    /* dataという名前のタグのない共用体 */
        long double_word;
        struct {
        /* wordという名前のタグのない構造体 */
        /* リトルエンディアンを想定 */
            short low;
            short high;
        } word;
    } data;
} foo;

int main(void)
{
    foo.data.word.low = 8;
    foo.data.word.high = 1;

    /* 65544 = 1 << 16 + 8 */
    printf("%ld\n", foo.data.double_word);
}

調べてみると、どうやら、無名共用体も、無名構造体も、C11から使えるようになったらしい。
しかし、C99標準では使えないらしく、可搬性を意識しているソースでは導入が進んでいないようだ。
（もちろん、C11リリース以前に書かれたソースでは、皆無。もしかしたらコンパイラの独自拡張機能としてあったかもしれないけど）。
やはり、今回見かけたCの無名共用体は今のところはまだレアキャラのようです。

www.buildinsider.net
www.kijineko.co.jp

2017-02-03

pythonで順序を保つグルーピング

python

恒例の？問題をpythonでやってみる。
使うアルゴリズムは、perlで最後にやったのと同じ（いちおうバケットソートといえるだろうか？）
studies.hatenablog.com

pythonのcollectionモジュールにあるOrderedDict（順序付き辞書）を使うと楽に書ける。
OrderedDictについての説明は以下にある。
8.3. collections — コンテナデータ型 — Python 3.6.1 ドキュメント

通常の dict メソッドをサポートする、辞書のサブクラスのインスタンスを返します。 OrderedDict は、キーが最初に追加された順序を記憶します。新しい項目が既存の項目を上書きしても、元の挿入位置は変わらないままです。項目を削除して再挿入するとそれが最後に移動します。

さて、書いたコードは以下の通り。

#! /usr/bin/python3
import fileinput
from collections import OrderedDict

pref_to_cities = OrderedDict()

for city in fileinput.input():
    pref = city.split()[1]
    if pref not in pref_to_cities.keys():
        pref_to_cities[pref] = list()
    pref_to_cities[pref].append(city)

for cities in pref_to_cities.values():
    print(*cities, sep="", end="")

以前perlで書いたコードと比べると、ダイヤモンド演算子や組み込みの変数が少ないのと、インデント強制のため、少し長いコードになっている。
しかし、以前は順序を覚えておくためだけに無駄な配列を作っていたのに比べれば、問題に最適なデータ構造を選択できていて、よい。

2017-01-31

pythonとhaskellで素数のリストを作ってみる

python haskell

今回はメモ程度。
リスト内包表記と、filter, mapを使った書き方。

python。

>>> [n for n in range(2,100) if 0 not in [n%d for d in range(2,n)]]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>>> list(filter(lambda n: 0 not in map(lambda d: n%d, range(2,n)), range(2,100)))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

haskell。

Prelude> [n | n <- [2..100], not $ 0 `elem` [n `mod` d | d <- [2..n-1]]]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
Prelude> filter (\n -> not $ 0 `elem` map (n `mod`) [2..n-1]) [2..100]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

pythonはリスト内包表記のほうがすっきり。
というか、lambdaキーワードが長すぎて…。
haskellはどっちも似たようなものかな～。

pythonにはこんなことできないかな？

Prelude> take 30 $ filter (\n -> not $ 0 `elem` map (n `mod`) [2..n-1]) [2..]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113]

2017-01-26

フィボナッチ数をたくさん出力すると放物線が現れる件

python 数学

前回、pythonを使ってフィボナッチ数の第n項を返す関数をいくつかのバリエーションで実装した。
ところで、pythonではメモリが許す限りいくらでも大きな整数を扱うことができる。
調子に乗って、前回作った関数でフィボナッチ数を（各項の間にスペースを一個入れながら）、大量に出力してみていると、面白いことに気づいた。
放物線が現れるのである。

f:id:developingskills1110:20170126194748p:plain

おお。
なんだこれは。

若干の感動を覚えつつ、少し考えてみると理由が分かった。

おおざっぱに説明してみよう。

フィボナッチ数列を $\{F_n\}$ とかく。
フィボナッチ数列の漸化式を解くと、一般項は、

　　　 $F_n = \frac{\phi^{n} - (1 - \phi)^{n}}{\sqrt{5}}$

である。ここで $\phi$ は黄金比である。
$1 < \phi < 2$ であり、したがって $-1 < 1 - \phi < 0$ であるから、

　　　 $\begin{eqnarray}\lim_{n\to\infty}(1-\phi)^{n} = 0\end{eqnarray}$

ゆえに、nが十分大きいとき、

　　　 $F_n \sim O\left(\frac{\phi^{n}}{\sqrt{5}}\right) \sim O(\exp(n))$

と評価される。
つまり、nが十分大きくなると、その挙動は「指数関数的」になる。

いま、各項は10進数でコマンドラインに表示しているので、各項の桁数は $1 + \lfloor\log_{10} F_n\rfloor$ である。
先の評価も考慮すれば、第n項の桁数は

　　　 $O(\log_{10} \exp(n)) \sim O(n)$

で評価されることが分かる。
つまり、フィボナッチ数の各項の桁数はおおよそ「線形」に増えていく。

ところで、上のコマンドラインに放物線が現れたのは、スペースがある適当な間隔で表示されたことが直接の原因である。
ここで、「適当な間隔」というのは、ここまでで議論してきたフィボナッチ数の各項の桁数であり、それはおおむね線形に増加しているのだった。
そこで、長さが $O(n)$ の文字列を繰り返し表示すれば（そして、各文字列のあいだに適当な文字を挟めば）、別にフィボナッチ数列でなくても、同じように放物線が現れそうだと予想がつくだろう。
以下のコードで試してみると、確かにそうなっている。

for i in range(200):
    print(" "*i, end="*")

f:id:developingskills1110:20170126202727p:plain

では、なぜこのような状況で放物線が現れるのか。

次の図で説明する。

f:id:developingskills1110:20170126202835p:plain

コマンドライン下に向かってx軸を、右に向かってy軸をとる。
コマンドラインの左端が $y=0$ で、右端が $y=C$ である。

各*はxが整数である点に現れていると考え、その座標を、 $(n, y_n)$ とする。
上で定義した状況は、図に示した赤色の線の長さの合計が線形に増加する、という状況だから、次のように言い換えられる。

　　　数列 $\{L_n = (C-y_n) + y_{n+1}\}$ は、等差数列である

これは、Cという定数を抜きにして考えることで、すぐに次のように言い換えられる。

　　　数列 $\{y_n\}$ の階差数列は、等差数列である

したがって、

　　　 $y_n \sim O(n^{2})$

が分かり、これにより、放物線が現れることが説明される。
（ほんとうは、離散的な点集合のみで、線は一つも現れてないですけどね）。

あまり、正確には議論していないですが、今日のところはTeXを初めて書いた面倒くささなどもあり、これで

Q.E.D.

ということで許してください。