ちょこっとメモ

コラム１

コラム１を読んでてビットの話で早速躓いてしまった。 ネットで解説読んで理解したのでまとめてみる。 http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q13100650348

問題

7桁の数値が10^8個あり、これらをソートしたい。 ただしメモリは1MBまでしか使えない。

考え方

数値nを右からn番目のビットを立てる事で全ての状態を一度に表現する。 (例えば全てのビットを立てれば1~9999999までの数値全てを表している事になる）。 そうすると、今扱いたいのは10^8個の数値なので、 0000 0000 0000 0000 0000 ............ 0000 (0を10^8個並べる) と一列に並べる事が出来れば良い。 このようにすれば、 10000000[bit]=1250000[byte]=1.25[MB]≒1[MB] となるのでメモリの問題も発生しない。

次に問題となるのは、実際には10^8個の数値を一列に並べる事が出来ないという点。 intは4[byte]=32[bit]なので、一度に扱えるのは32桁分まで。 そこで、32桁ずつ分けて表現する事を考える。 10000000 / 32 = 312500 なので全ての数値を表現するためには312500個分のintを確保する必要がある。 よってint a[312500+1]という配列を用意し、入力nが配列のどのindexになるかを計算して収めていく。 (+1するのは余りがある場合を考慮してるためだと思う。今回はぴったり収まるけど。） a[0] = 0~31までの数字を全て表現出来る: 0000 0000 0000 0000 0000 0000 0000 0000 a[1] = 32-63までの数字を全て表現出来る: 0000 0000 0000 0000 0000 0000 0000 0000 a[2] = 64~95までの数字を全て表現出来る: 0000 0000 0000 0000 0000 0000 0000 0000 ... a[312499] = 9999967~9999999までの数値を全て表現出来る: 0000 0000 0000 0000 0000 0000 0000 0000

プログラムで表現する

解答にはビット操作をふんだんに利用しているが、上記の背景の理解が不十分だったのではじめ本を読んでも理解する事ができなかった。 例えば以下のコードの場合。

void set(int i) { a[i>>SHIFT] |= (1 << (i & MASK)); }

入力として i = 50を考える。 今、SHIFT = 5, MASK = (11111)なので、 50 >> 5 = 1 (右に５シフトするとは、2^5=32で割ることと同じ。） 次に i & MASKについて。 50 & 111111(2) => 0011 0010(2) & 1 1111(2) => 1 0010 => 2^4 + 2^1 = 18 = (※ 32 + 18 = 50) 最後に、i << (18) で、これは右から18桁目にビットを立てる事になる。

以上を踏まえ、理解しやすいようにbitsetで考えると以下のようになる

alfredからdayoneに書き込む方法を調べた。 ネットの情報そのままにやっても、applescirptのruby実行時にchronicがないとか怒られてハマった。 やってうまく行った方法をメモしておく。

~/.bashrcに以下を追加

eval "$(/usr/local/bin/rbenv init -)"

dayoneのコマンドラインツールを落とす

スクリプトを落とす

logtodayone.rb

gem install chronic

workflowを落としてダブルクリック

Day-One-Alfred-Tools

ただしそのままではうまく動かなかったので、中身を開いて、do the shellsciptの部分を

do shell script "source ~/.bashrc; ruby ~/Documents/Scripts/logtodayone.rb \"" & q & "\""

とすることで動かす事が出来た。 lwの方が動かす事ができず諦めた。

また、ターミナルからもlog hogeで記録出来るように、~/.bashrcに以下を追記した。

bitbucket上にmarkdownで画像をする場合の画像のパスを調べてみた。

myfolder/ | |---image/ | |---hoge.jpg

という構成の場合、画像のパスは

https://bitbucket.org/ユーザー名/レポジトリ名/raw/master/myfolder/image/hoge.jpt

とすることで画像表示出来た。 画像パスは絶対パスでないとダメみたい。

qtのバージョンを5.2.1に上げたら直ってると思ったらまだダメだったのでメモ。

opencv使ってビルドしようとするとundefined-symbolsというエラーが出る。

動かすためには、

../Qt5.2.0/5.2.0-rc1/clang_64/mkspecs/macx-clang/qmake.conf

ファイル内を以下のように書き換える

#MAKE_MACOSX_DEPLOYMENT_TARGET = 10.6 MAKE_MACOSX_DEPLOYMENT_TARGET = 10.9

根本的な解決ではないらしいけど、とりあえず動くようになるのでOKとする。

TypeError: list indices must be integers, not float というエラーでハマった。 python3以降は割り算の挙動が変わるらしい。/ではなく、//とすれば整数になるようだ。

middle = (first + last) // 2 The // indicates floor division in Python 3.x.

Tree コマンドで-Lオプションで階層指定した時に日本語の文字化けが発生。-Nオプションを指定することで回避出来た。

python

# -*- coding: UTF-8 -*- from matplotlib import pyplot as plt from sklearn.datasets import load_iris import numpy as np data = load_iris() features = data['data'] feature_names = data['feature_names'] target = data['target'] for t, marker, c in zip(xrange(3), ">ox", "rgb"): #scatter(xの値を格納したリスト、Yの値を格納したリスト、色） plt.scatter(features[target == t, 0], features[target == t, 1], marker = marker, c=c) print plt.show()

メモ

zipは組み合わせを作る

features[target == t, 0]はtarget == tとなる要素のうち、第０列の値を取ってきている

実行結果

; 最初に書いたもの

(define (print-point p) (newline) (display "(") (display (x-point p)) (display ",") (display (y-point p)) (display ")")) (define (make-segment stt end) (cons stt end)) (define (start-segment x y) (make-point x y)) (define (end-segment x y) (make-point x y)) (define (make-point x y) (cons x y)) (define (x-point x) (car x)) (define (y-point y) (cdr y)) (define (midpoint-segment seg) (make-point (/ (+ (car (car seg))) (car (cdr seg)) 2) (/ (+ (cdr (car seg))) (cdr (cdr seg)) 2))) (print-point (midpoint-segment (make-segment (make-point 1 2) (make-point 3 4))))

; 修正版

pythonのループはなるべく除く。この場合は、sum

import timeit normal_py_sec = timeit.timeit('sum(x*x for x in xrange(1000))', number=10000) native_np_sec = timeit.timeit('sum(na*na)', setup="import numpy as np; na=np.arange(1000)", number=10000) good_np_sec = timeit.timeit('na.dot(na)', setup="import numpy as np; na=np.arange(1000)", number=10000) print("Normal Python: %f sec" % normal_py_sec) print("Native Numpy: %f sec" % native_np_sec) print("Good Numpy: %f sec" % good_np_sec)

実行結果

$ brew install pip

うまくインストール出来なかったので、

$ brew doctor

で指摘される箇所を修正 その後

$ pip install numpy

続いて

$ pip install scipy error: library dfftpack has Fortran sources but no Fortran compiler found

fortranが必要みたいなので、

$ brew install gfortran

http://blog.f13.jp/post/21714276427/pybrain

$ pip install matplotlib

これも失敗したので、 ここを参考にしたら上手くインストールできた。 http://yukisakamoto.hatenablog.com/entry/2013/08/24/030205

これが実行出来れば成功

c++で何度も標準入力をさせたい場合

inoremap {} {}<LEFT> inoremap [] []<LEFT> inoremap () ()<LEFT> inoremap "" ""<LEFT> inoremap '' ''<LEFT> inoremap <> <><LEFT>