Darts-clone Q&A
Q: What is the limit number of string in darts clone?
A double-array uses an array and its size must be less than 2^29 (=536M). The array size is greater than the number of keys. So, the maximum number of keys is less than 2^29.
The actual limit depends on keys and values. In general, the array size is proportional to #keys and longer keys require a larger array. Additionally, the number of distinct values affects the array size. If there are few distinct values, the array size will be small.
You can estimate the actual limit by using a part of your keys.
The following are examples (`keys`: the number of keys, `size`: the array size):
Word keys (the average length is 13 bytes).
## Unique values. $ mkdarts -t ~/corpus/1gm.zero.1m 1gm.zero.1m.darts keys: 1000000 total: 12740688 Making double-array: 100% |*******************************************| size: 1861632 total_size: 7446528
## All values are zero. $ mkdarts ~/corpus/1gm.uniq.1m 1gm.uniq.1m.darts keys: 1000000 total: 12740688 Making double-array: 100% |*******************************************| size: 4885248 total_size: 19540992
URL keys (the average length is 53 bytes).
## Unique values. $ mkdarts ~/corpus/urls.uniq.1m urls.uniq.1m.darts keys: 1000000 total: 53166751 Making double-array: 100% |*******************************************| size: 18637312 total_size: 74549248
## All values are zero. $ mkdarts -t ~/corpus/urls.zero.1m urls.zero.1m.darts keys: 1000000 total: 53166751 Making double-array: 100% |*******************************************| size: 11225344 total_size: 44901376
MacBook Pro のセットアップ
届いたので徐々にセットアップを進めています．
ソフトウェアアップデート
左上の Apple マークからソフトウェア・アップデートを選んで，アップデート可能なものはすべてアップデートしました．
キーボードの設定
システム環境設定のトラックパッドを選んで，右下にある修飾キーで Caps Lock を Control に変更しました．また，入力ソースに日本語のことえりを追加し，カタカナと英字は無効化しました．
ショートカットは以下のようにカスタマイズしました．
- Mission Control
- 「左右の操作スペースに移動」を無効化します（三本指のスワイプで移動できます）．
- 誤爆しそうなので，ほかの「Control + 矢印」も無効にします．
- ついでに「F11/F12」も無効にします．
- Spotlight
- どちらも無効化します．
- 入力ソース
- 「前の入力ソースを選択」は無効化します．
- 「入力メニューの次のソースを選択」は Control + Space に変更します．
VMWare Fusion
ダウンロードしてインストールしました．
ゲスト OS としては Ubuntu 13.10 と OSX を入れる予定です．Ubuntu 14.04 が出れば， Ubuntu 13.10 は 14.04 に移行する予定です．
MacBook Pro を注文しました
ヨドバシカメラで実機を触ってみて，キーボードが浅いとか，少し重い気がするとか，タッチパッドのクリックが少し重く感じるとか，いくつか気になるところはあるのですが，ほかに良い案がなかったので， MacBook Pro を注文しました．
MacBook Air も候補だったのですが， VMWare Fusion を使って複数の VM を動かす可能性を考えて，メモリを 16GB にできる MacBook Pro の方を選びました．デフォルトでもなかなかのお値段ですが，盛ると冷や汗が出るようなお値段になりました．大事に使っていきたいと思います．
整数除算はやはり落とし穴か
整数除算のオーバーフローに関する先日の記事（ 整数除算のオーバーフローについて - やた＠はてな日記 ）に対して思ったより多くの反応があり，自分だけじゃなかったかと安心する一方で，それってやばいような…と少しばかり不安になりました．
それから，いろいろと記事の内容にも記述不足やら誤りやら，よろしくないところがいくつかあってコメントをいただいたので，いくらか記述を足しておきました．いまだに説明不足に感じるところがいくつもあるのですが，細かいことを追求し始めると終わらなくなるので，この辺で終わりにしたいと思います．
整数の除算でオーバーフローが落とし穴だと感じるのは，整数の加算，減算，乗算ではオーバーフローしても知る限りの環境で同じ演算結果になるのに，整数の除算だけは例外が発生してプログラムごと落ちてしまうからです．そもそも C/C++ ではどちらも未定義なわけで，どんな結果になっても仕様上おかしくはないのですが…．
日本標準時と 1888 年問題
FreeBSD で mktime() に tm_year が 0 以下の struct tm を渡すと返り値が -1 になるという問題を聞いて，それくらいなら tm_year > 0 が成立するように補正した上で mktime() に渡し，後から補正した分を元に戻してやればいいんじゃないかと思ったのですが，上手く行きませんでしたという話です．
struct tm の tm_year について， Ubuntu 12.04 の manpage では以下のように説明されてます．つまり， 1900 年とそれより前の時間を指定すると失敗することになります．かなり昔になるので，普通に使っていて問題になることは稀だと思います．とはいえ，使わないとは限りませんし，困ったものです．
tm_year The number of years since 1900.
そういうわけで，この問題を回避する方法を考えてみました．
最初に思い付いたのは tm_year が 1 になるように補正するという案なのですが，閏年や夏時間に関する補正が悩みの種になりました（※1）．ちなみに，閏年になるのは西暦が 400 の倍数になるときか， 100 の倍数でない 4 の倍数になるときです（※2）．夏時間については tm_isdst で確認できます．
※1 未来の時刻について夏時間の問題を解決する方法はないので，そういうのは考えないものとします．どうしても解決したいのであれば，政治的に夏時間をなくすなり，タイムマシーンを解決するなりしなくちゃ駄目な気がします．
※2 西暦 1 年の前年が紀元前 1 年になって地味に気持ち悪いという罠がありますけど，そういうのは今回は考えないものとします．
ちなみに，夏時間が使われ始めたのは 1916 年かららしく，それより前の年代では気にしなくても大丈夫なようです．
閏年の問題を解決する手段として考えたのが， tm_year に 400 の倍数を足して 0 より大きな値にするという案です．閏年の数は一定になるため，境界条件に頭を悩ませる必要がありません．
それから，夏時間については， tm_year の補正でマシマシにして（※3），夏時間を補正するためのテーブルに引っかからないようにすることを考えました．
※3 tm_year が 401 以上になるように補正します． 401 以上にすれば 2300 年近くになるまでは問題にならないと思ったわけです．補正がテーブル以外の方法でおこなわれていたら駄目ですが…．
以上の案にもとづいて考えたのが以下の関数です．
time_t my_mktime(struct tm *tm) { if (tm->tm_year > 0) { return std::mktime(tm); } // 閏年の影響を避けるため， 400 年単位でずらします． // マシマシするために + 2 としています． long tm_year_offset = ((-tm->tm_year / 400) + 2) * 400L; tm->tm_year += tm_year_offset; std::time_t seconds_since_epoch = std::mktime(tm); tm->tm_year -= tm_year_offset; // ずらした分を元に戻します． // 400 年あたり，閏年（366 日）が 97 年とそれ以外（365 日）が 303 年です． seconds_since_epoch -= (tm_year_offset / 400) * ((303L * 365 * 24 * 60 * 60) + (97L * 366 * 24 * 60 * 60)); return seconds_since_epoch; }
そして，単純に mktime() を呼び出したときの結果を比べてみたところ（※4），一致したり一致しなかったりするという不思議な結果になりました．具体的には，正解より 1139 大きな値を返すことがありました．
※4 Ubuntu 12.04 の mktime() は tm_year <= 0 でも期待通りの結果を返してくれるので，それを正解としました．
一致しないときの誤差は常に 1139 なので意味がある数値だと判断せざるをえないのですが，中途半端な数値なので何が何やらです．「1139 秒」をウェブで検索してみましたが，有用な情報は手に入りませんでした．
仕方がないので，結果が一致しない条件を調べてみると， tm_year < -12 のときだということがわかりました．すなわち， 1888 年より前では一致せず， 1888 年以降では一致します．この情報を使えば，正確に補正できるようになりました．新たな関数は以下のようになります．
time_t my_mktime(struct tm *tm) { // ずらした分を元に戻すところまでは省略します． // 以下の補正を加えることで，結果が一致するようになりました． if (tm->tm_year < -12) { seconds_since_epoch -= 1139; } return seconds_since_epoch; }
そういうわけで， 1888 年に何かがあったのだろうと思って調べてみたところ， 1888 年 1 月 1 日のできごとに日本標準時実施と書かれていました．
さらに， 1888 年問題でウェブで検索をしてみると，以下の記事が見つかりました．時間の問題というのは，実に奥深いものです．
そういうわけで，タイムゾーンが東京の時刻については，なんとか補正できることがわかりました．一方で，補正方法はタイムゾーンによって違うことが予想されます．将来的にタイムゾーンの変更がおこなわれる可能性も否定できませんし，すべてのタイムゾーンに対処しようとすれば，面倒な問題になりそうです．
整数除算のオーバーフローについて
整数除算のエラーとしては 0 による除算が有名ですが，オーバーフローも致命的なエラーになるなりえるという話です．
（追記 2014-02-27） そもそも整数の演算におけるオーバーフロー時の動作は未定義なのですが，加算，減算，乗算のオーバーフローについては，オーバーフローした分が捨てられるという前提で使っていることがよくあります．本当はやっちゃ駄目なのでしょうが…．
- INT32-C. 符号付き整数演算がオーバーフローを引き起こさないことを保証する
具体的には，符号付き 32-bit 整数の除算で INT32_MIN / -1 となったとき，およびに符号付き 64-bit 整数の除算で INT64_MIN / -1 となったときにオーバーフローが起きます（※1）． 8-bit や 16-bit の整数については，演算時に int への暗黙的な型変換がおこなわれるため， C/C++ では問題になりません（※2）．明示的に 8/16-bit 向けの IDIV 命令を使えば，同様の問題が再現できると思います（※3）．
※1 （追記 2014-02-27） id:syohex さんがコメントにて指摘されているように，上述の組み合わせがオーバーフローになるのは， 2 の補数（ 2の補数 - Wikipedia ）を使っている環境において， INT32_MIN の絶対値が INT32_MAX より大きくなるからです． 2 の補数を使っていない環境であれば，違う結果になるかもしれません．
※2 （追記 2014-02-27） id:Assume さんがはてブで指摘されているように， int が 16-bit の環境であれば，符号付き 16-bit 整数の除算でも問題になるはずです．
※3 （追記 2014-02-27） Intel® 64 and IA-32 Architectures Software Developer's Manual で調べたことであり， x86 や x64 以外でどうなるかはわかりません．
また，同じ IDIV 命令を使う剰余算についても，上述の組み合わせでエラーになります．
ためしに，以下のようなソースコードを用意します．
#include <climits> #include <iostream> int main() { int x = INT_MIN; std::cout << (x / -1) << std::endl; return 0; }
これをコンパイルして実行すると，以下のようになりました（Ubuntu 12.04）．ただし，コンパイラが頑張ってしまうと x / -1 の演算がおこなわれない可能性があります．
$ clang++ a.cpp $ ./a.out 浮動小数点例外 (コアダンプ)
整数の除算なのに浮動小数点例外と出ているあたりは不思議（※4）ですけど，エラーになることは確認できました．
※4 （追記 2014-02-27） 整数の除算であっても FPU が使われるからだと id:syohex さんにコメントをいただきました．整数の除算より浮動小数点数の除算が速いのも納得です．
除算を使うときは除数が 0 にならないように気を付けていましたけど，上述の組み合わせによるオーバーフローは落とし穴でした．今後はオーバーフローにも注意するようにします．
後の話は蛇足ですけど， g++ を使うと以下のようになりました．
$ g++ a.cpp $ ./a.out -2147483648
そこで，ソースコードを以下のようにすると落ちるようになりました．ただし，最適化オプションを付けると再び落ちなくなります．
#include <climits> #include <iostream> int main() { int x = INT_MIN; int y = -1; std::cout << (x / y) << std::endl; return 0; }
さらに蛇足ですが， clang++ で最適化オプションを付けたときは，実行する度に違う結果が表示されました．
$ clang++ -O2 a.cpp $ ./a.out -901424984 $ ./a.out 1683933848 $ ./a.out 116451400 $ ./a.out 130056888 $ ./a.out 996577544
実験に使った g++ と clang++ のバージョンは以下の通りです．
$ g++ --version g++ (Ubuntu/Linaro 4.6.4-1ubuntu1~12.04) 4.6.4 Copyright (C) 2011 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ clang++ --version clang version 3.3 (tags/RELEASE_33/final) Target: x86_64-unknown-linux-gnu Thread model: posix
（追記 2014-02-27） clang には -fsanitize=signed-integer-overflow というオプションがあり，これを使うと以下のように出力されます．
- Clang Compiler User's Manual ― Clang 3.5 documentation
$ clang++ -fsanitize=signed-integer-overflow a.cpp $ ./a.out a.cpp:6:19: runtime error: division of -2147483648 by -1 cannot be represented in type 'int' 浮動小数点例外 (コアダンプ)
新しくない ThinkPad X1 Carbon を買い逃した件
先月末に販売が開始された新しい ThinkPad X1 Carbon があまり魅力的な製品に思えず，新しくない ThinkPad X1 Carbon の方を購入しようと考えていたのですが，どうやら手遅れだったらしく，入手することができなくなってしまいました．
一応， 2/12 に注文をして 2/17 には「生産指示済」の状態にはなっていたのですが， 2/20 に部材が確保できませんでしたという連絡があり，注文が取り消しになってしまいました．最近の ThinkPad の変化（※）が好きになれず， X1 Carbon が最後の砦だと思っていたため，とても残念です．
※ キーボードのアイソレーションタイプへの変更，タッチパッドの追加，クリックパッドへの変更（クリックボタンの廃止），アダプティブキーボードの導入（ファンクションキーの変更），キーボード配列の変更などのことを指します．
仕方がないので次に購入するノート PC を選んでいます．今のところ，有力な候補は MacBook Air と MacBook Pro です．デフォルトで Windows がインストールされていないところが魅力です．…というのはさすがに冗談ですが，初期状態で Windows に余計なソフトウェアが山盛りになっているのはうんざりします．
MacBook Air/Pro の魅力のひとつは，手頃なお値段で VMWare Fusion を手に入れられることです．新しくて高性能なハードウェアは素晴らしいのですが， Linux をネイティブで動かすのは不安があります．そのため，仮想環境を手軽に構築できることが強みになります．
なんだか Apple 万歳な内容になってしまいました．
