GIFのバイトオーダはリトルエンディアンです!ビッグエンディアンじゃありません!
ふーんという感じですが、specificationにも記述があります。
https://www.w3.org/Graphics/GIF/spec-gif89a.txt
Multi-byte numeric fields are ordered Least Significant Byte first.
『入門 Python3』のp216の記述は誤植ですね(とても混乱するので、エンディアンで誤植してほしくない…)。
7-14 GIFファイルの幅(単位ピクセル)は、バイトオフセット6からの16ビット
ビッグエンディアンの整数で、高さはオフセット8からの同じサイズの整数になっている。gifのこれらの値を抽出して表示しよう。どちらも1になっているか。
答え(p524)はあってる。
>>> import struct >>> width, height = struct.unpack('<HH', gif[6:10]) >>> width, height (1, 1)
高速化フィボナッチの計算量の理想と現実
前回書いた高速化フィボナッチでは、計算量をと見積もった。
今回はこの見積もりの妥当性を検討する。
まず、
>>> from my import fib >>> from timeit import timeit >>> from matplotlib import pyplot as plt >>> x = range(2**7) >>> y = [ timeit('fib({} * 2**18)'.format(n), ... number=1, globals=globals()) for n in x ] >>> plt.plot(x,y, '.') >>> plt.show()
とやって、実際にfib(x)を計算するのに要した時間を可視化してみる。
(もちろん、私の環境固有の値である。またコード中のmyはfib関数を実装した自作モジュールの名前だ)。
計測時間の総計はだいたい1時間半くらい。
ここで、x軸の単位は、y軸の単位は秒である。
グラフを観察してみると、xが23から24に変わるときと、47から48に変わるとき、94から96に変わるときでギャップがあるのに気が付く。
これはこれで気になるが、今回検討するのはそこではない。
今回は、グラフが下に凸であることに着目したい。
もし、計算量が前回の理想的な見積もり、であるなら、グラフは上に凸であるはずだ。
しかし、実際にはグラフは下に凸になっている。
これはなぜだろう?
ちょっと考えれば当然だが、これは巨大な整数を扱っていることに起因している。
フィボナッチ数はnが大きくなるにしたがって、指数関数的に大きくなる。
扱う整数の値が大きくなれば、それに伴って四則演算の計算コストもそれに伴い増加するのは当然だ。
前回の見積もりでは、「任意の桁数の四則演算は同じ計算コストを持つ」という非現実的な仮定を置いていた。
今回はこれを修正して、多倍長整数の計算コストも考慮して、評価してみよう。
しかし、残念ながら、この評価をするには(もちろん)、pythonの多倍長整数演算の実装を知らなければならない。
今回は標準的なpythonの実装の一つであるCPythonを考えてみる。
CPythonのソースをgithubからゲットしよう。
github.com
これを少し読むと、Karatsuba法を用いた実装のようであることが分かる。
/* Karatsuba multiplication. Ignores the input signs, and returns the * absolute value of the product (or NULL if error). * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295). */ static PyLongObject * k_mul(PyLongObject *a, PyLongObject *b)
(cpython/Objects/longobject.c)
Karatsuba法なら、乗算の計算コストは桁数をkとして、だ。
フィボナッチ数列ではnが大きくなるにしたがって、数そのものは指数関数的に大きくなるから、桁数はnに対して線形に増加する。
(これは前に、フィボナッチ数をたくさん出力すると放物線が現れる件 - studiesでみたことだ)。
pythonでフィボナッチ高速化
激しく既出という気がするけど、行列を使ってフィボナッチを高速化する。
その前に、の計算を高速化するアルゴリズムを確認しておく。
def my_pow(x, n): if n == 0: return 1 elif n % 2: return x * my_pow(x, n-1) else: half_pow = my_pow(x, n/2) return half_pow * half_pow
このアルゴリズムでは、例えば、は次のように展開されて、計算される。
半分ずつにして計算するため、真っ先に考えてしまう次の展開よりも早くなる。
さて、行列を使ったフィボナッチ数の一般項の表現は次のようになる。
実は、
である。
この公式と先ほどのアルゴリズムを組み合わせればよい。
計算量は、素朴な実装が なのにたいして、となる。
あとは、行列の乗算を実装して完成。
from itertools import product def mat2_mul(X, Y): Z = [ [0, 0], [0, 0] ] for (i,j,k) in product(range(2),range(2),range(2)): Z[i][j] += X[i][k] * Y[k][j] return Z def mat2_pow(X, n): if n == 0: return [ [1, 0], [0, 1] ] elif n % 2: return mat2_mul(X, mat2_pow(X, n-1)) else: half_pow = mat2_pow(X, n/2) return mat2_mul(half_pow, half_pow) def fib(n): if n == 0: return 0 else: F = [ [0, 1], [1, 1] ] return mat2_pow(F, n-1)[1][1]
なお、ここでは(n-1)乗までの計算でとどめている。
先ほども書いたように、(n-1)乗までで、すでに第n項は出ている。
SQLite3でちょっと複雑なソート
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|いわき市|福島県
慣れないことをすると頭を使う。
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
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
void *p = &p : 自分自身を参照する初期化の問題
久しぶりの投稿はちょっと変な話。
次のように、自分自身を参照するポインタを作ってみる。
#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ではそうもいかない。
これはけっこう厄介だと思う。
無名共用体を見かけた
無名共用体(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の無名共用体は今のところはまだレアキャラのようです。