読者です 読者をやめる 読者になる 読者になる

woshidan's loose leaf

ぼんやり勉強しています。

C言語の値渡しとアドレスを知る引数、配列のアドレスについて

C 値渡し

C言語の関数の引数はすべて値渡しだそう。

関数の中で、引数で渡された構造体などの中身を変更したい時は、&演算子でその変数のアドレスを求めて、そのアドレスを値渡しで渡す。 そして、関数の中でアドレスに対応するメモリの値を書き換えることで、&演算子をつけて渡された変数の中身を書き換える。

C言語を読んでいく時は、配列名が配列の0番目の要素の変数のアドレスを指していることを合わせて読んでいくと理解しやすいかも。

char str[256]:
scanf("%s", str);
// これは上記と同じ
scanf("%s", &str[0]);

また、配列の各要素のアドレスは、配列の型が取るバイト数だけずれた連番になるそうで、array[n]は、配列名のアドレス + 要素番号 * 1要素分の大きさのアドレスがさすメモリから参照できる変数をさしていることになるそうで。

int array[10];
&array        2345678
&array[0]   2345678
&array[1]  2345682
&array[2]  2345686

苦しんで覚えるC言語

苦しんで覚えるC言語

数学ガール6章まで読んだ

数学ガール
  • 定数はa, b, c... 変数は x, y, z... が多い
  • 相加相乗平均の例、a=+2, b=-2だと絶対値が同じな特殊なケースなのでは、と思ってb=-1にして計算したりした
  • 離散的な世界での差分 <=> 連続的な世界での微分
    • 差分を求めるために下降階乗冪を使うのが計算の都合上にしか見えなくてよくわからない
    • h->0の極限つけて(x-0)(x-h)(x-2h)(x-3h)... としていく所は納得できるけど、h->1で使っていいというのは計算の都合なのかもしれない(元々のxのn乗からの差分の差が10n違わないだろうか的な意味で納得いかない)
      • 計算しやすい

蟻本の1-6の続き

蟻本

のーみそこねこね。

  • 衝突して折り返していく -> 蟻を区別しなければ、蟻全体の動きとしては、そのまま進んでいく状態と一緒
    • 最短 -> それぞれの位置の蟻が最短で着く方法
    • 最長 -> それぞれの位置の蟻が最長で着く方法
  • 4枚のくじを引いた時、4枚の合計値がmになるか
    • 2枚のくじを引いた時(この組み合わせは2重ループで表現 -> n2)、残りの2枚を引いてこれとの合計値がmになるような値があるか
    • 残りの2枚を引いて合計値がmになるような値この探索は
      • 残りの2枚については、残りの2枚を引いた値の取りうる組み合わせを列挙してその中から(m-最初の2枚)になるものを探す
        • この探す方法は2分探索(binary search) log(n)
    • O(n)に耐えうる必要のある値を入れて必要に応じて変えていくっぽい

2分探索雑に書いた。

n = 4
a = [2, 3, 4, 5, 10]

def binary_search(target, data)
  range_min = 0
  range_max = data.size
  while range_max - range_min >= 1
    i = ((range_max + range_min)/2).to_i
    if (data[i] == target)
      return true
    elsif data[i] < target
      range_min = i + 1
    else
      range_max = i
    end
  end
  return false
end

if binary_search(n, a)
  puts "found"
else
  puts "not_found"
end

蟻本の三角形をrubyで書いた

蟻本

三角形

n本の棒があります。棒iの長さはa_iです。あなたは、それらの棒から3本を選んでできるだけ周長の長い三角形を作ろうと考えています。最大の周長を求めなさい。ただし、三角形が作れない際には0を答えとしなさい。

一番大きな辺が他の2つの長さの合計よりも長かったらいけないのですが、

  • 辺を大きい順か小さい順に並べて、大きい方から条件を満たすものを探せばいいのでは?
  • 大きい方から辺を3つ探していったとき、「他の2つの長さの合計が一番大きな辺より大きい」を満たす、一番大きな辺より短い2本の辺って常に一番大きい辺の次とその次に大きい辺なのでは?
    • 未検証... orz

と思って書いた。反例見つかったら修正します。

n = 5
a = [2, 3, 4, 5, 10]
a.sort! # 昇順にソート

if n < 3
  puts "the number of bars is less than 3."
  puts 0
  return
end

def make_triangle(n, a)
  longest_bar_index  = n - 1
  middle_bar_index   = n - 2
  shortest_bar_index = n - 3

  while is_too_long_longest_bar?(longest_bar_index, middle_bar_index, shortest_bar_index, a) do
    longest_bar_index -= 1
    middle_bar_index -= 1
    shortest_bar_index -= 1
    if shortest_bar_index < 0
      puts "cannot make any triangle in this set."
      return 0
    end
  end

  return "#{a[longest_bar_index] + a[middle_bar_index] + a[shortest_bar_index]}(#{a[longest_bar_index]}, #{a[middle_bar_index]}, #{a[shortest_bar_index]} の3本を選んだ時)" unless shortest_bar_index < 0
end

def is_too_long_longest_bar?(longest_bar_index, middle_bar_index, shortest_bar_index, a)
  a[longest_bar_index] >= (a[middle_bar_index] + a[shortest_bar_index])
end

puts make_triangle(n, a)

mp4ヘッダーのボックスとは

mp4 ファイル形式

mp4 ヘッダー でぐぐったらボックスって出てくるのですが

refs. http://matsu623a.blogspot.jp/2013/12/mpeg4ftyp.html

mp4 ヘッダー ででてくるのは引用元が少なくてあれなのですが、

  • だいたいファイル冒頭にあるファイルのメタデータ持ったバイト群およびハッシュなどの類
  • mp4の場合、ファイル形式がボックスで構成されており、ボックスの中でもヘッダーと呼ばれる部分があるのでややこしく感じる

という認識で良さそう。

そのボックスとはなんぞや

refs. https://unoh.github.io/2007/09/12/mp43gpp3gpp2.html

MP4や、その派生である携帯電話向けの3GPP3GPP2などのファイルフォーマットはボックス(あるいはその基になったQuickTimeでの用語のAtom)と呼ばれるデータブロックで構成され

 

ボックスによってはその内部にさらにボックスが入れ子になるツリー構造になっています

 

各ボックスはその先頭8バイト(オクテット)がボックスを識別するためのヘッダで、最初の4バイト(オクテット)がボックスのサイズ、続く4バイトがそのタイプです。

  • 動画を表すmp4や3gppなどのファイルフォーマットはボックス単位で構成
  • ボックスはボックスの大きさ + ボックスのタイプの部分がボックス識別用のヘッダから始まる
  • ボックスはボックスの大きさの部分で宣言した大きさの分だけ続く。入れ子の場合は入れ子になったボックスの分の大きさも親側のボックスが宣言する(っぽい((いつかまた調べる)))
    • cf. moov以下にmvhdなどがあるが、moovの大きさはこれを含んでいると思われる
  • ボックスの種類(一部)
    • ftyp
      • そのファイルが準拠している規格を表す4文字の「ブランド」が列挙
      • 一番良く使われる形式 ... 4バイト ... それ以外に利用可能な形式 の順で並ぶ
    • moof
      • 3gpp2用のボックス
      • HTTPストリーミングを想定したもので、文字通りデータを分割し小分けに受信することで、全データのダウンロードを完了しなくても再生が開始できるというもの (参考ページより引用まま)
  • mp4box, mp4dump などのツールで確認可能

数学ガール(無印)4章まで

数学

最近本体ブログと使い分けに悩んでるんですが、本の読みかけで表に出せそうな感想やメモはこっちに書きましょうか。

昔から数学がたいそうできずに数式に怯えて生きてきて、大量にインターネットに流れてくる「数学ガールいいよ」の声に負けてとうとう手に取った感じです。

感想が続かないので、雑目に続けます。

1章 ~ 4章まで全般的に

ミルカさん萌え。テトラさんもいじらしさがあります(そういう本ではありません)。

知り合いにたいそう数学ができる人がいて、その人に線形代数を教えてもらった時、同じように自分がうんうんうなるのを待ちながら根気強く教えてもらったことがあって、うんうんうなること一晩、基本的な線形代数の演算ができるようになった時に「できたー」といったらたいそう嬉しそうに爆笑されたものでした。

あと、主人公の小さな数学者の話が好きです。

自分の場合は数学じゃなくてコードや技術書、教科書に対して苦労話を聞いたり一緒に悩んだり楽しんだりするような姿勢で読むことが多いです。けれど、周りにそういった人をあまり見たことがなく変態扱いされることが多くて寂しかったので、ニュアンスがずれているかもしれないのですが、他にもそういう人がいるのかーと思って嬉しかっ... あれ、これ2次元では...(ry

プログラミングに対してそういった印象を持っているのは最初の頃から結城先生のデザインパターンの本やリファクタの本を読んで学ぶことが多かったので、影響を受けているのかもしれないですね*1

2章

恒等式、方程式を一つ一つの式が何かをテトラさんが説明しているのがすごい印象的でした。

変形する時には、恒等式(=どんなxを入れても、この式は成り立つ)を使って、方程式(=ある数xを入れると、この式は成り立つ)を解いていて、おおおおぉ...。

項と因子(因数)の定義については自分もテトラさんと同レベルだったので、ひたすらうなずいていました...。

3章

行列の掛け算さえ分かっていれば、倍角の公式なんて覚える必要がなかったんや!!

と思うのですが、これ、角θの回転の式をなんだかんだ頭に入れてたから馴染んだのかな、と思うところがあったり。

ド・モアブルの定理の式がなんだか納得できない気がしたのでn=いくらかまで書こうとして、 そもそも回転行列から納得いかなくて、三角関数の加法定理から回転行列(といって0<α(回転前のx軸からの角度),θ(回転の角度),α+θ<90の一番単純な場合)証明しようとしていました。

f:id:woshidan:20170103233141p:plain

その時、回転行列の項は4つなのに、ド・モアブルの定理で出てくる項が2つなのに納得できなかったのだけど、証明の過程で出てくる恒等式の中で回転前の点のx座標にかかる係数で、回転行列の定義から、n回θ回転させたときの座標を計算するときはそこだけ見れば十分なので、それでいいんだろう、とまぁ、ゆるゆると(おい)納得したりしました。

本当はだいぶ違っていて、ド・モアブルの定理の左辺のカッコの中身は複素数表示で複素数平面上で座標を現した時の単位円上の一点であり、同時に、それを乗ずるという操作はその点が持つのと同じ角度だけ回転させるのと同じなんだろう、みたいな感じです。

厳密とはなんだったのか。

4章

大学時代何やっていたかよくわからないんですが、母関数がなんであるかを知らなくて、フィボナッチ数列の一般項を求める段階で使い方が分かって嬉しかったです。

数列の各項を係数として持つxの累乗が並んだ関数 -> 母関数, 母関数の閉じた式を求める -> 無限級数を利用して、数列の一般項をお返しする流れが、あ、計算方法だけ知ってる!! みたいな残念な感じだったのですが、おかげで話の流れに集中できてよかったです。

それでも 1/(1 - rx)の式が自信なくて残念が尽きないんですが...。

(正直なんで関数なんだろう、というところがまだ疑問...)

*1:個人的には自分みたいな趣味読みより、緑の方のデザパタ本はしばらく現場で書いてから、紫の方は最初によむとよさそうです (マルチスレッド処理の流れや用語を学ぶのに現場で手ごろな例はあまりない気がするので、覚えきれなくても用語の雰囲気だけindex頭に作ってからだと、ライブラリのAPIドキュメント読みがはかどりそう)

ObjectiveCのソースコードをclangでコンパイルした時Undefined symbols for architecture x86_64: "_OBJC_CLASS_$_NSObject", referenced from: ... のようなメッセージが出てくる

ObjectiveC clang

症状

#import <Foundation/NSobject.h>
#import <stdio.h>

int main() {
  id obj = [[NSObject alloc] init];
...
}
$ clang -o ref1 ref1.m
Undefined symbols for architecture x86_64:
  "_OBJC_CLASS_$_NSObject", referenced from:
      objc-class-ref in ref1-62be76.o
  "_objc_msgSend", referenced from:
      _main in ref1-62be76.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

原因

Foundation/NSobject.hのヘッダファイルが含まれるFoundationフレームワークを読み込む指定がない。

$ clang -o ref1 ref1.m -framework Foundation

ならいける。