studies

いろいろ勉強用備忘録的な感じ

英語、UML、git、バイナリ操作、オブジェクト指向

久しぶりの投稿だ。

というのも、仕事であまり新奇なものに触れる機会もなく、ちょっと腐り気味だったのである。

タイトルは、最近なんとなく勉強しといたほうがいいだろうかと思っていることを列挙したものである。

英語は結構勉強している。
あまりそれ自体は楽しいものではないので辛いのだけれども、しかし、英語を使えると世界が広がるということは否定できない事実である。
英語を使って記された情報量 >>> 日本語を使って記された情報量
が現実だ。
日本の某企業のマイコンのハードウェアマニュアルでも、英語版はあるけど日本語版はなかったりする。

とりあえず、9月10日のTOEICで900点を突破することを目標にしているが、最近英語について思うのは、やはりほかの言語を学ぶというのはそれなりに時間のかかることなのだろうなということだ。
私は、試験勉強とかいうと、だいたい短期突破である。
短い間でガッと集中し、合格ラインすれすれを突破するというやり方が身についている。
しかし、言葉というのには合格ラインというものが(当然ながら)存在しないし、人や状況にもよりけりだ。
そのすべてを勉強することは、日本語でだって不可能だし、しかしだからといって、とても限られた状況や主題でしか物事を語れない/読めない、というのであれば、それはその人の教養の低さを示すことになる。
言葉とは教養だ。

そして、突き詰めれば言葉とは単語だ。
単語が英語学習の基本だ。
あまりいろいろなことを一度にできない自らの能力が恨めしいが、
~9月10日:TOEICの勉強に専念
~10月15日:情報処理の勉強に専念
10月16日~年末:ボキャブラリーを5000ほど増やす!

という感じでやっていこうと思う。

いろいろ環境設定(主にvim)

ソースコードが読めない(絶望)。

あまりにダメダメだから、環境を色々試してみることにした。

やったこと↓

とりあえず、今は

Ctrl-Aでtmuxのコントロール(Actionのつもり)。
Ctrl-Tでファイルツリー表示(Treeのつもり)。
Ctrl-Gでカーソル位置の関数定義/参照にジャンプ(Goのつもり)。
Ctrl-JでQuickFixの選択を下に(vimに合わせて)。
Ctrl-KでQuickFixの選択を上に(vimに合わせて)。
Ctrl-Lでファイル内関数一覧表示(Listのつもり)。
Ctrl-Oでジャンプ元に戻る(デフォルト通り)。
Ctrl-Iで進む(デフォルト通り)。

という感じにキーバインドしてみた。

vimプラグイン大杉ワロタ。
設定項目も多すぎ。
しんどい。

でもなんかかっこよくなったぞ(見た目だけ)。
f:id:developingskills1110:20170423235836p:plain

とりあえず、ネットでパクりまくったvimrcをメモ。

"""""""""""
"dein
""""""""""""
if &compatible
    set nocompatible
endif
set runtimepath+=~/.vim/dein.vim
call dein#begin(expand('~/.vim/'))
call dein#add('scrooloose/nerdtree')
call dein#add('Shougo/vimproc.vim')
call dein#add('Shougo/neocomplete.vim')
call dein#add('justmao945/vim-clang')
call dein#add('Shougo/neoinclude.vim')
call dein#end()


""""""""""""
"nerdtree
""""""""""""
noremap <C-t> :NERDTreeToggle<CR>
let g:NERDTreeDirArrows = 1
let g:NERDTreeDirArrowExpandable = '+'
let g:NERDTreeDirArrowCollapsible = '-'


""""""""""""
"neocomplete
""""""""""""
let g:neocomplete#enable_at_startup = 1
"let g:neocomplete#enable_auto_select = 1
if !exists('g:neocomplete#force_omni_input_patterns')
        let g:neocomplete#force_omni_input_patterns = {}
endif
let g:neocomplete#force_overwrite_completefunc = 1
let g:neocomplete#force_omni_input_patterns.c = '[^.[:digit:] *\t]\%(\.\|->\)'
let g:neocomplete#force_omni_input_patterns.cpp = '[^.[:digit:] *\t]\%(\.\|->\)\|\h\w*::'

" disable auto completion for vim-clanG
let g:clang_auto = 0
let g:clang_complete_auto = 0
let g:clang_auto_select = 0
let g:clang_use_library = 1

" default 'longest' can not work with neocomplete
let g:clang_c_completeopt   = 'menuone'
let g:clang_cpp_completeopt = 'menuone'

if executable('clang-3.8')
    let g:clang_exec = 'clang-3.8'
elseif executable('clang-3.7')
    let g:clang_exec = 'clang-3.7'
elseif executable('clang-3.6')
    let g:clang_exec = 'clang-3.6'
elseif executable('clang-3.5')
    let g:clang_exec = 'clang-3.5'
elseif executable('clang-3.4')
    let g:clang_exec = 'clang-3.4'
else
    let g:clang_exec = 'clang'
endif

if executable('clang-format-3.8')
    let g:clang_format_exec = 'clang-format-3.8'
elseif executable('clang-format-3.7')
    let g:clang_format_exec = 'clang-format-3.7'
elseif executable('clang-format-3.6')
    let g:clang_format_exec = 'clang-format-3.6'
elseif executable('clang-format-3.5')
    let g:clang_format_exec = 'clang-format-3.5'
elseif executable('clang-format-3.4')
    let g:clang_format_exec = 'clang-format-3.4'
else
    let g:clang_exec = 'clang-format'
endif

let g:clang_c_options = '-std=c11'
let g:clang_cpp_options = '-std=c++11 -stdlib=libc++'

inoremap <expr><CR>  pumvisible() ? "\<C-y>" : "\<CR>"   
inoremap <expr><TAB>  pumvisible() ? "\<Down>" : "\<TAB>"   
inoremap <expr><S-TAB>  pumvisible() ? "\<Up>" : "\<S-TAB>" 
inoremap <expr><Space> pumvisible() ? "\<C-y><Space>" : "\<Space>"
inoremap <expr>( pumvisible() ? "\<C-y>(" : "("
inoremap <expr>) pumvisible() ? "\<C-y>)" : ")"
inoremap <expr>[ pumvisible() ? "\<C-y>[" : "["
inoremap <expr>] pumvisible() ? "\<C-y>]" : "]"
inoremap <expr>< pumvisible() ? "\<C-y><" : "<"
inoremap <expr>> pumvisible() ? "\<C-y>>" : ">"
inoremap <expr>* pumvisible() ? "\<C-y>*" : "*"
inoremap <expr>& pumvisible() ? "\<C-y>&" : "&"
inoremap <expr>" pumvisible() ? "\<C-y>\"" : "\""
inoremap <expr>' pumvisible() ? "\<C-y>'" : "'"
inoremap <expr>: pumvisible() ? "\<C-y>:" : ":"
inoremap <expr>; pumvisible() ? "\<C-y>;" : ";"
inoremap <expr>` pumvisible() ? "\<C-y>`" : "`"

"""""""""""
"gtags
"""""""""""
function! GtagsCursor_()
  execute "GtagsCursor"
  if (len(getqflist()) <= 1)
    cclose
  endif
endfunction

nnoremap <C-g> :call GtagsCursor_()<CR>
noremap <C-l> :Gtags -f %<CR>
noremap <C-j> :cn<CR>
noremap <C-k> :cp<CR>

""""""""""""
"general
""""""""""""
set tabstop=4
set shiftwidth=4
set expandtab

set number
set nowrap

set cindent
set cinoptions+=g0
set showmatch

syntax on

set ignorecase
nnoremap / /\v

set list
set listchars=tab:^-,eol:$

set clipboard=unnamed,autoselect

colorscheme darkblue

出力変換指定子の修飾子とか、整数拡張とか

仕事でビット演算を使って、結構知らないことが多かった。

まずは、signed charの場合。

#include <stdio.h>

int main(void)
{
    /* 以下いずれも右辺の定数はintで解釈される。右辺の値が左辺の型で表現できる範囲を超えている場合の動作は処理系定義。 */
    signed char c = 0xf7; // 多くの処理系で0xf7は内部表現として解釈される。gccの場合、特にWarningは出ない。
    c = 247;              // これも同じ。gccの場合、特にWarningは出ない。
    c = 0x123456f7;       // 多くの処理系で下二桁が内部表現として代入される。gccの場合、overflow Warningが出る。

    /* 出力指定子:size_t型はzで修飾。intが4バイトなら、charはhhで修飾。 */
    printf("sizeof(c) = %zu, c = %hhd = %#hhx\n", sizeof(c), c, c); // 1, -9, 0xf7

    /* signedの負数に対する右シフトは処理系定義。 */
    c >>= 1;
    printf("c = %hhd = %#hhx\n", c, c); // 算術右シフトの処理系では、-5, 0xfb
    
    /* signedに対して論理右シフトさせたければ、キャストするかマスクをとる必要がある。 */
    c = 0xf7;
    c = (unsigned char)c >> 1;
    printf("c = %hhd = %#hhx\n", c, c); // 123, 0x7b

    c = 0xf7;
    c = (c >> 1) & 0x7f;   // 上位7ビットを読む。0x7f = 0b0111_1111
    printf("c = %hhd = %#hhx\n", c, c); // 123, 0x7b

    return 0;
}


次にunsigned charの場合。

#include <stdio.h>

int main(void)
{
    
    unsigned char uc = 0x12345680;  // 右辺の値を(UCHAR_MAX+1)で除した剰余が代入されることが保証されている。gccの場合、overflow Warningが出る。

    printf("sizeof(uc) = %zu, uc = %hhu = %#hhx\n", sizeof(uc), uc, uc); // 1, 128, 0x80

    /* unsignedに対する右シフトは値にかかわらず論理右シフト(0埋め)。 */
    uc >>= 1;
    printf("uc = %hhu = %#hhx\n", uc, uc); // 64, 0x40

    /* しかし整数拡張(integer promotion)に嵌る可能性がある。 */
    uc = ~uc >> 1;  // 右辺のucはint型に暗黙にキャストされて、0x00_00_00_40となっている。
    printf("uc = %hhu = %#hhx\n", uc, uc); // 223, 0xdf
    
    /* 回避するにはキャストするか、マスクをとる。 */
    uc = 0x40;
    uc = (unsigned char)~uc >> 1;
    printf("uc = %hhu = %#hhx\n", uc, uc); // 95, 0x5f

    uc = 0x40;
    uc = (~uc >> 1) & 0x7f;   // 上位7ビットを読む。0x7f = 0b0111_1111
    printf("uc = %hhu = %#hhx\n", uc, uc); // 95, 0x5f

    return 0;
}

教訓を列挙する。
ビット演算を行う変数は、unsigned指定をつけたものに限る。なぜならば、型の表現できる範囲を超えた値が代入された時の挙動について、unsignedについては仕様によって定義されているが、signedの場合は処理系定義だから。左シフトやビット反転と整数拡張によって容易に型の表現できる範囲を超えてしまう。
ビット演算を行った後は必ず、最後にマスクをかける。右シフトを行う場合、unsignedであっても整数拡張により1が埋められてしまうことがある。
・char型の変数をprintfでダンプする場合のフォーマット指定子にはhhをつける(int4バイトの場合)。

ややこしいことは考えず、この程度で面倒な問題を回避できるなら安いものである。

C言語のdigraphsを使ってみる

完全に小ネタ。

ISO/IEC 9899:1999によると、

In all aspects of the language, the six tokens(67

<:    :>    <%    %>    %:    %:%:
behave, respectively, the same as the six tokens
[    ]    {    }    #    ##
except for their spelling.(68



67) These tokens are sometimes called ‘‘digraphs’’.
68) Thus [ and <: behave differently when ‘‘stringized’’ (see 6.10.3.2), but can otherwise be freely interchanged.

なので、こんなソースもOKだ。

%:include <stdio.h>
%:define GLUE(x,y) x%:%:y

/* おなじみhello, world */
int main(void)
<%
    char hello<::> = "hello, world\n";
    int i;

    for (i=0; i<sizeof GLUE(hell,o); i++) <%
        putchar(hello<:i:>);
    %>
    return 0;
%>

trigraphsもある。

5.2.1.1 Trigraph sequences
1 All occurrences in a source file of the following sequences of three characters (called trigraph sequences(12 ) are replaced with the corresponding single character.

??= #        ??( [        ??/ \
??) ] ??' ^ ??< {
??! | ??> } ??- ~
No other trigraph sequences exist. Each ? that does not begin one of the trigraphs listed above is not changed.
2 EXAMPLE The following source line

printf("Eh???/n");

becomes (after replacement of the trigraph sequence ??/)

printf("Eh?\n");

12) The trigraph sequences enable the input of characters that are not defined in the Invariant Code Set as described in ISO/IEC 646, which is a subset of the seven-bit US ASCII code set.

??=include <stdio.h>
??=define GLUE(x,y) x??=??=y

int main(void)
??<
    char hello??(??) = "hello, world??/n";
    int i;

    for (i??'=i; ??-i>??-sizeof GLUE(hell,o); i++) ??<
        putchar(hello??(i??));
    ??>
    return 0;
??>

しかし、gccの場合、-trigraphsオプションをつけないとコンパイルされない。

tokens.c:1:1: warning: trigraph ??= ignored, use -trigraphs to enable [-Wtrigraphs]
??=include
^

これは、仕様書のEXAMPLEにあるように、trigraphは文字列の中にあっても展開されるという危険な動きをするからだ。

ぐるぐるとまだ回る君の影 どこにも行けずに春が来る

社会人になって一年が経過した。

同時に、プログラマになって一年だ。

今自分の職業について思っていることを徒然に書いてみる。

プログラマはプログラムを作る人

プログラムとは予定表の意味だ。
だから、プログラマとは予定表を作る人に他ならない。

プログラマナチュラリスト

予定表を作るためにはナチュラリストである必要がある。
といっても、別に山や野原に出る必要はない。
あるプログラムの振る舞いを決めるうえで、「何が自然か」ということを知っていなければならない、ということだ。
これはたとえば、数列が与えられたとき、そのルールを見抜く(自ら設定する)ような力だ。
有限数列が与えられて、自分の好きな数値をそのあとにもう一項加えてよいのなら、どうするだろうか。
自分の誕生日を入れる?
それとも、好きな人の誕生日だろうか?
しかし、プログラマなら、次の項は何が自然かを必死になって考えるはずだ。

プログラマアルゴリズムアプリケータか、アルゴリズムエンジニア

プログラマが作る予定表は誰でも意味が分かるように書かれている必要があるので、必然的に何らかのアルゴリズムがそこには記述されることになる。
もし幸いにも予定表の目指している「目的」と同じモノに向かって既に歩いた人がいるなら、プログラマはその人のレガシーを用いて予定表を作る。
その場合はプログラマアルゴリズムアプリケータだ。
しかしさらに幸いなことに、人類にとっての大きな一歩を踏み出すことを余儀なくされるのであれば、プログラマアルゴリズムエンジニアだ。

プログラマトランスレータ

プログラマが作り上げる予定表は、残念ながら最終的には「誰か」に渡さなければならない。
そうしないとだれもその予定表の存在を認識できない。
認識できないものは存在しないので、そうするしかないのだ(プラグマティズムですよ)。
実のところプログラマはまず最初に、内言語で予定表を作り上げる。

ここをああして、あれをこうして、そこでそうすれば、目的地にたどり着きそう…。

それから、この内言語を外言語に翻訳するのだ。
外言語はプログラミング言語が一般的だが、フローチャートだったりUMLだったりすることもある。
もしかしたら、自然言語かもしれないし、ハードウェア的な実装かもしれない。
このとき、プログラマトランスレータだ。

システムはプログラムを必ず含む

実は社会人になった当初はプログラマではなくSEになったと思っていた。
今では自分はプログラマだと思っている。
というか、「私はSEです」という人をかなり胡散臭いと思っている。

しかし、システムという言葉が周りでよく使われているのは確かだ。
システムという言葉は難しい。
今、私なりに理解しているシステムとは、こうだ。
複数の構成物が一つの目的に向かって、ある特定のやり方で協調して働いているような構造体。
この「ある特定のやり方」というのは予定表で書けるところだ。
つまり、システムは必ずプログラムを含む。

エンジニアリングはアーキテクチャとインプリメンテーションに分けられる

グラデーションはあるが、プラトンイデア説のように、設計と実装に分けるのはとても分かりやすい。
たとえば、プログラミング言語イデア界の住人だ。
私たちは直接見ることはできない。
言語仕様書はこのイデア界の住人を理性によって描写したものだ。
プログラミング言語のインプリメンテーション=現実界の住人は、コンパイラだ。
私たちは通常コンパイラを通してプログラミング言語を見ることになる。

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)

高速化フィボナッチの計算量の理想と現実

前回書いた高速化フィボナッチでは、計算量を O(\log{n})と見積もった。
今回はこの見積もりの妥当性を検討する。

まず、

>>> 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時間半くらい。

f:id:developingskills1110:20170325074303p:plain:h300

ここで、x軸の単位は 2^{18}、y軸の単位は秒である。

グラフを観察してみると、xが23から24に変わるときと、47から48に変わるとき、94から96に変わるときでギャップがあるのに気が付く。
これはこれで気になるが、今回検討するのはそこではない。
今回は、グラフが下に凸であることに着目したい。

もし、計算量が前回の理想的な見積もり、 O(\log{n})であるなら、グラフは上に凸であるはずだ。
しかし、実際にはグラフは下に凸になっている。
これはなぜだろう?

ちょっと考えれば当然だが、これは巨大な整数を扱っていることに起因している。
フィボナッチ数は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として、 O(k^{\log_2{3}})だ。

フィボナッチ数列ではnが大きくなるにしたがって、数そのものは指数関数的に大きくなるから、桁数はnに対して線形に増加する。
(これは前に、フィボナッチ数をたくさん出力すると放物線が現れる件 - studiesでみたことだ)。

高速化したフィボナッチ数列の計算では多倍長整数の演算(特に乗算)がボトルネックとなり、その計算量は
 O(n^{\log_2{3}} + (\frac{n}{2})^{\log_2{3}} + (\frac{n}{4})^{\log_2{3}} + …) \sim O(n^{\log_2{3}})
となる。