子供の落書き帳 Remix

15/4/13:ひと月に一度更新するブログになってしまっている

音声処理ソフトAudacityでのディザ適用の条件とビット深度について
2018/01/28(日) 23:52:58


そもそもディザとは何か


ディザとは、ディジタル音声信号を処理するときに、信号に人工的に付加される微小なノイズのことである。
ビットの深度が減少する処理の際に、量子化エラー(丸め誤差)が起きるのを防止する。量子化エラー(丸め誤差)が周期的に発生すると、特定の種類の音が現れる可能性があり、それを防ぐために微小なノイズを付加する。

audacityにおけるビット深度 (bit depth)


audacityに特有の話に移る。
audacityで音声の取り扱うときに、ビット深度(bit depth)をいくつにして処理するか。これは32bit float, 24bit, 16bitの3つの選択肢がある。
[編集]→[設定]の画面を開いて、「品質」タブを選択する。「サンプル形式」という選択項目がビット深度を表わしている。
設定値は以下の画像がデフォルトである。
Audacity設定画面デフォルト

Audacityのヘルプでは下記の通り、32bit floatを推奨している。32bitだけがfloat(浮動小数点数)なのがポイントである。他の2つは固定小数点数であり、小さな数を表現するときに精度が大幅に落ちる危険性がある(詳しい説明は省く)。

The Audacity default quality settings are Sample Format 32-bit float (and Sample Rate 44100 Hz). It is strongly recommended that you use these settings unless you have good reasons to deviate from these. 32-bit float is chosen to give an extremely low noise floor and to provide good headroom to avoid sound distortion even when performing heavy editing and manipulation of the audio.
拙訳:Audacityのデフォルトの品質設定は、32-bit float(とサンプリング周波数44100Hz)である。これらの設定から逸脱する正当な理由が無い限り、これらの設定を使用することを強く推奨する。 音声を何度も編集し操作したときでも、非常に低いノイズフロアと充分なヘッドルームが得られるため、32-bit floatが選択されている。

ノイズフロアは特定の量子化の方式を使用する上で発生するノイズを指す模様、下記リンクを参照。
偏ったDTM用語辞典 - ノイズフロア:Noise Floorとは - DTM / MIDI 用語の意味・解説 | g200kg Music & Software

Audacityではどのようなときにディザが実行されるか?


基本的には、音声信号のビット深度が下がるときには、設定に従ってディザリングが実行される。
「ビット深度が下がるとき」というのは、具体的には以下の3つの場合だ。

・音声を再生するとき (正確には、再生時にAudacity内のデータと、再生時のサウンドカードのビット深度を比較して、後者が少ない場合)
・音声をエクスポートする際にビット深度が下がるとき (例えば、32-bit floatや24bitのプロジェクトで処理をしていて、16bit形式でファイルにエクスポートするとき)
・16bitもしくは24bitのプロジェクトで、音声の編集処理を実施する場合

3番目については説明が必要だろう。例えば16bit信号に対して編集を行う場合、

16bit信号→編集→16bit信号

であるから、一見するとビット深度の低下は起こらない。しかしながら、Audacity内部では編集時に32bit floatに一旦数値を変換している。したがって、編集処理はこうなる。

16bit信号→32bit float信号→編集→32bit float信号→★16bit 信号

最後の★のところで、信号のビット深度が下がっているため、ディザリングが実行されているというわけだ。
16bit信号に対して何度か編集処理をすると、そのたびにディザリングが実行されてしまう。ディザリング自体は微小なノイズだが、何度も実行していると「ちりも積もれば山となる」で大きなノイズになり、音声品質の劣化につながるだろう。Audacity公式が「32bit floatを使うのを推奨」と言っている理由は、このあたりであると推測される。

実例 ~矩形波~


ディザの実例を見てみよう。
「品質」の設定はデフォルトのままである。
ジェネレータで「矩形波、エイリアス成分なし」を選んで、振幅0.001、周波数440Hzの矩形波を生成した。縦軸を適度に拡大すると以下のようになる。矩形波の上下の部分が一直線になっていることに注意。
2018-01-28_2317.png

[書き出し]→[Export as wav]で「WAV 16bit PCM 符号あり」形式で保存。この時、エクスポートする際にビット深度が下がったので、ディザリングが実行されたはずである。保存したwavファイルを再度開いてみると、以下のようになる。
2018-01-28_2319.png

上下の線がギザギザになってしまった! これは、ディザが実行されたためである。各サンプルに微小なノイズを加算したので、一直線にはならない。サンプルが見える程度まで拡大すると、以下のようになる。サンプルごとにノイズが付加されて、違う値になっていることが分かる。
2018-01-28_2336.png

(ディザのノイズレベルは一定なので、もとの信号が小さいときにはS/N比が悪くなる。今回はディザリングの影響を分かりやすくするため、矩形波のレベルをわざと小さくしている)

ディザリングが実行されないようにしたい場合はどう設定するか?



音声処理をする上で、特定の16bit PCM音源(例えば正弦波とか……)が必要になってAudacityで作成するという場合もあるだろう。
気をつけるべきは、デフォルトの設定だとディザによるノイズが重畳されるということである。
例えば「16bit PCM形式で、周波数880Hzの正弦波を生成したい」と言っても、完璧に正確な正弦波は生成不可能だ(量子化によるエラーが生じるため)。量子化に対して「周期的な量子化エラー(丸め誤差)が生じてもよいから、16bitにおいて一番近い数にしたい」という場合もあるだろう。この場合はディザを避けなければならない。あるいは「周期的な量子化エラー(丸め誤差)は嫌なので、ディザを乗せよう」という場合もあるだろう。上記のうちどちらの音声を生成したいのかを考えて、適切な設定を選ぶ必要がある。
デフォルトの設定のままだとディザが実行されるので、後者の音ができあがる。

では前者の「周期的な量子化エラー(丸め誤差)が生じてもよいから、16bitにおいて一番近い数にしたい」場合はどうすれば良いのだろうか?
[編集]→[設定]の画面を開いて、「品質」タブを選択する。「高品質変換」の中の「ディザリング」を「無し」に変更すれば良い。
デフォルトから先ほどのサンプル形式を「16bit」に変更するのは良い方法ではない。第一に、音声を編集する時に量子化エラーによる音声歪みが大きくなる危険性がある。第二に、「ディザリング」の設定項目を変更しないと、結局目的は達成されない。殆どの音声処理は内部的に32bitで実行されるので、前述したとおり処理のたびにディザが実行される。音声を生成する際もこれに該当するので、生成した時点ですでにディザが乗ってしまうことになる。

それでは。

最後に:
画像はクリックすると全体が見られる。
今回の記事はAudacity公式の以下のページを参考にした。
Dither - Audacity Wiki
Bit Depth - Audacity Wiki
  1. 2018/01/28(日) 23:52:58|
  2. プログラミング
  3. | トラックバック:0
  4. | コメント:0

GMOエンジニアトーク -先端IT技術を学ぶ会- 深層学習、ブロックチェーン、AR/VR 参加レポート
2017/05/13(土) 14:56:23


2017年5月11日GMOエンジニアトーク -先端IT技術を学ぶ会- 深層学習、ブロックチェーン、AR/VR
にブログ執筆枠で参加してきたので、記事を書きます。

資料は後日公開される予定です。
(講演のうち一つはスライド見つけたのでリンクを貼りました)

会場はこんなところ。(講演終了後の写真です)
GMO170511.jpg

IoT領域でのブロックチェーン実践



ブロックチェーン技術の実用例として色々なアプリケーションを開発している。
そのサンプルアプリの1つが、今回紹介するスマート宅配ボックスである。
受け取り本人だけが解錠できる。

紹介動画:「本人のみが受け取れる宅配ボックス」の実証実験 - YouTube
プレスリリース:
GMOインターネット・GMOグローバルサイン・セゾン情報システムズの3社の共同実験。
セゾン情報システムズって、小野和俊さんがCTOをしている会社で、モダンなSIerになろうとしているというイメージだった。ブロックチェーンの実証実験に協力しているとは知らなかった。

ブロックチェーンの最大の特徴は、
ただそこにデータが記録されてるだけで「いつ・誰が・何を記録したか」が、第三者による証明なしに記録される
ということである。
なぜ客観的な事実の証明ができるのか?

技術としては、ハッシュ関数、公開鍵と秘密鍵を使っている。

例えば仮想通貨のやり取りの場合、Aさんは「私はBさんに100コイン渡す」という内容を自分の秘密鍵で暗号化する。
他の人は誰でもAさんの公開鍵を用いて暗号を復号することができる。
このとき「Aさんの秘密鍵で暗号化したものである」ことが確認できるので、内容が間違いなくAさんの書いたものであると確認できる。

前のブロックのハッシュ値が、次のブロックの入力に含まれている。
もしも内容を改竄すると、後続のブロックのハッシュが一致しなくなり整合性が崩れるので、改竄ほぼ不可能。

スマートコントラクトとは
ソースコードそのものを暗号化して通信する……らしいが、ちょっとついて行けなかった。
詳しくはブロックチェーンサービス利用ガイド · ブロックチェーンサービス(Ethereum)利用ガイドを見てくれと言っていたので、リンクを貼ってごまかすことにする。

■世界の事例
ゲームのカードの所有権を管理する
「ujo music」音楽の直接販売

不動産登記 新興国だと土地の登記が信用できないから、ブロックチェーンで正しさを担保する。
議決権の行使

ドバイはブロックチェーンのナンバーワンになろうとして、開発に多額の金を投じている。

■GMOの取り組み
やってみたこと
(1)ゲームのコンテンツ管理
そこまで厳密な所有権管理は必要ないのでは。やめた。

(2)個人所有データを管理する
→今ある共有サービスで良いと感じた。
「ブロックチェーンじゃないとできない」ではない。

(3)GMOポイントをブロックチェーン管理?
一企業の責任範囲ならでーびーでいいや

(4)KYC (Know Your Customer:顧客確認)
銀行に口座を開設するときに必要な書類手続きのこと。
金融の口座開設ては本人確認に数千円のコストがかかる。
検索したところ、2016年8月に楽天証券が開発開始してるな。これから競争激化するのだろうか。
日本初!ブロックチェーン技術を利用した本人確認(KYC)システム共同開発開始|楽天証券のプレスリリース

検討中:
特許のアイデア保管
内容を誰にも伝えずにアイデア発生日時を保証する

■Q&A

Ethereum使用で使用料金かかるけど、ほかのブロックチェーンにすることで手数料が無料にできないか?
お金かからない設定もできる、が、金がかかるようにしてある
DDoS攻撃をしようにも、お金を払わないと攻撃できないので、攻撃されづらいという利点がある。

国を動かすことについて?
スマートコントラクトは色々な企業を巻き込むので、必然的に国レベルの話になります
国のほうも、アイデア募集してる場面があるので(詳細は言えないけど)、意見を言えば国は聞いてくれると思う

モバイルAR技術の最先端 Google Tangoを活用してバーチャル道案内スタッフを実現してみた



発表資料
モバイルAR技術の最先端 Google Tangoを活用してバーチャル案内スタッフを実現してみた from bmkhuong


■概要
スマホのカメラ画面の上に道案内スタッフ(ユニティちゃん)を登場させる。
でユニティちゃんが画面内で歩いて、目的地までの誘導をしてみる。
スマホの画面の向きや位置を変えると、それに応じてユニティちゃんの映り方が変わる。

ショッピングモール……行きたい店は?美味しいご飯は? 行き方がわからない
地下鉄や駅……道がわからない

■内容
GoogleTangoとは
AR(Augmented Reality : 拡張現実)/MR(Mixed Reality : 複合現実)のプラットフォーム。
奥行き知覚、モーショントラッキング、領域学習という3つのコア技術を持つ。

スマホはLenovo phab 2 proを使った。
(現在、Tangoに対応している唯一の端末。ASUSが「ZenFone AR(ZS571KL)」を日本で2017年夏に発売予定。)

ランドマーク=特徴的な物体をいくつか記憶する
カメラの視野が広ければたくさんのランドマークを取得できて認識精度があがる。

■Q&A
空港だと広くて通路が取りづらく、人が通ることで学習したときと環境が変わって難しいのではないか?
変わりやすい環境だと学習や認識は難しい。Tangoの弱点

ビーコンによる誘導はできたりする?
現手法であまり頻繁に変わらない環境なら認識は簡単。ビーコンより経済的なのでは

目的地までプロットするの大変だから、目的地指定したら経路案内するようにできるか?
先にマーカーを付与しておけば経路探索アルゴリズムを適用することは可能。

■感想
案内の前に一度対象となる空間を歩き回って認識させ、経路案内用のマーカーを(スマホ上で)配置する必要があるのがちょっと面倒そうに感じた。
Tango自体は近未来感があって楽しそう。

高橋ゆうこう

深層学習は金融市場をシミュレーションすることができるか?



■イントロ
2016年のヘッジファンドの成績を見ると、AIを使ったファンドだけ利益を上げている
最終的な目標は人工知能による資産運用を確立すること
今回はそのためのシミュレーション方法の開発、環境の構築を取り上げる
シミュレーション用のデータを増やしたいので、GANを用いて為替(ドル円)のデータを生成する。

イントロ、がんとは何か、実験計画、シツケン、まとめ、

■GANとは何か
Generative Adversarial Network
generator(データを生成するもの)とdiscriminator(真贋を見分けるもの)を同時に学習させる手法。
詳しい解説を見つけたので参照。はじめてのGAN
今回は深層学習のDCGAN(Deep Convolutional GAN)を使った。

CelebA という、世界のセレブの写真20万枚のデータセットを使って、新たな顔を生成するデモ。
Large-scale CelebFaces Attributes (CelebA) Dataset
フレームワークはTensorFlow。

■実験

2001~2015年のドル円相場のグラフから連続する100日分を切り出し、
100×100のpng画像に直す。合計3000枚程度のデータでDCGANを実行した

人工的なデータ(一直線のグラフとか、明らかに違うもの)をdiscriminator(判別器)に入れた
→判別成功

もう少しホンモノに近いデータを、モンテカルロ・シミュレーションで人工的に生成する
日々の差分がガウス分布(?)に従うように生成した? データをdiscriminator(判別器)に入れた
→判別成功


■Q&A
シミュレーションでデータ増やそう、という動機は何か? 値動きのシグナルを学習させる手法で上手くいくので、データを増やす必要はないのではないか?
根本にあるのは「値動きを的確に当てて大儲けするというよりは、環境の変化に強い安定したロジックを開発したい」というもの。
最終的にはほったらかしでAIに任せるやつを作りたい


画像でやる動機は? 最初に数値データがあるので数値のほうが扱いやすいし、画像にするとデータ量が増えるのでは?
(私の質問。100日分の終値の数値は100次元だが、100×100のpngだと10000次元データなのでわざわざデータの次元を上げる理由が気になった)
人間の視覚的な見た目による直感を取り入れるとどうなるのかを見てみたかった
ある程度ギャンブルで、試しにやってみた感じ。上手く行ったので結果オーライ。

2001年より前のデータでテストしたか?
今回はデータを入手できなかった。


以上。GMOの皆さんありがとうございました。

  1. 2017/05/13(土) 14:56:23|
  2. プログラミング
  3. | トラックバック:0
  4. | コメント:0

ザ・黒帯 ~ Yahoo! JAPANのエンジニアの働き方とキャリアを語る 内容メモ #devsumi
2017/02/24(金) 01:14:52

Developers Summit 2017に初参加してきたのでレポートなど。この記事では下記のカンファレンスの内容をまとめています。
【16-A-7】 ザ・黒帯 ~ Yahoo! JAPANのエンジニアの働き方とキャリアを語る | Developers Summit 2017
システム上は満員になっていたけど、実際の会場では結構空席があった。申し込んだけど聞きに行かなかった人が多いのかな。

注意事項
聞きながらガーッとメモを書いたので、内容が完璧に正しい保証はありません。

登壇者 (詳しい経歴はdevsumiの公式ページを参照)
楠 正憲 (黒帯 プライバシー・セキュリティ @masanork)
伊藤 宏幸 (黒帯 アジャイル開発プロセス @hageyahhoo)
倉林 雅 (黒帯 認証技術(ID連携) @kura_lab )
里山 南人 (黒帯 Androidアプリ )
司会者:斉木 崇 (CodeZine編集長 斉木 崇(編集部)について:CodeZine(コードジン))

黒帯制度:実績を上げている優秀な人材を正しく評価するという目的で設立された。約50人が任命されている。Yahooのエンジニアの中の、トップ2%に位置する。6代目が21人。今日登壇しているのはそのうちの4人である。

【 】の中は、斉木さんの質問文の要約である。


【事前に話を聞くと、現在のIT業界に対して懸念があるということだったが?】
ある業務を電子化しようとする際、昔はできる技術が限られてたから、仕様は決まっていた。しかし、今では技術が進歩したし、ユーザーもHTML5の新しい技術をFacebookやTwitterなどで普通に使っている。技術が複雑化している。それを言葉に表して仕様に落とすのが難しくなってきている。結果として、受託開発で回せる難易度と内製で回せる難易度の差が広がっている。
また、事前に仕様を決めきれないシステムは、ビッグデータ解析に関係するシステムなどでますます増えるだろう。そのようなシステムは、内製じゃないと構築できないと思う。Yahooはエンジニアをたくさん抱えているから良いが、日本全体で見ると内製で全部できる会社は多くないだろう。

【黒帯との関係は?】
困りましたね。そこまで関係ないかな。ただ、いろいろな人に会い、国際会議に出たりできると、日本のやり方が必ずしも当たり前じゃないことが分かる。日本の社会構造の中で何ができるんだろう、ということは、外での活動の中で発見できるかと思う。


里山
【プロダクトのスピード感、意志決定の速度について】
2010年以降、CyberAgentやDeNAなどを経由して今に至る。Yahoo!はこれらの企業に比べると、職務の階層が多い。SIerほどとは言わないが、それに近いかな。ボトムアップで変えていきたいという現場の思いが上に届きづらい。どこかでトップダウンの話に変換できないといけない。トップダウンに変換するためには、大義名分が必要になる。大義名分を持っていて、ちゃんと背景が分かる人が介入していく必要がある。

【今後はどういう活動がしたい?】
弊社はアプリ開発数が多い。小規模で開発運用してるアプリが多い。リソースのバランスが上手く行ってない部分がある。人を採用できるように、Yahoo社として技術のブランディングをしていきたい。


伊藤
【組織横断的なことをしたいという話だが?】
アジャイルは「アジャイル開発」という名前で呼ばれることが多い。そのため、開発だけに閉じたものではないかと思われがちである。しかし、開発が上手くいっても、マネジメント層や経営層に否定されれば、そこで終わってしまう。以前の経験で、取締役にアジャイルOKのゴーサインをもらって、それを受けてアジャイルを推進した経験がある。だからYahoo!でも同様に、アジャイルな考え方を社内に浸透させていきたい。

【黒帯は単なる認定制度なのか、権限があるのか?】
活動資金は年100万円支給される。上司の決裁も不要なので裁量がある。
その他、書籍執筆、対外講演など、外で活動する機会を多めに与えてもらえる。


倉林
【担当業務とのしがらみとか】
黒帯になると、社内外の人が課題を抱えていていろいろと相談されることが増えた。
技術の導入にはハードルがあって、ID技術はYahoo!のいろいろなサービスにつながるから、社内調整が大変。コスト面、ビジネスのメリットを全社に説明できれば社内導入できるので、そういうやりがいを感じて取り組んでいる。


伊藤
【プレイヤーとして輝き続けたい。マネジメントにいくラットレースからの脱却】
前職では、アジャイルのコーチとして4年ほど活動してきて、現場に入って一緒に仕事をして改善活動をする、を続けてきた。しかし、前職でそれができなくなった。なぜならアジャイルの施策をやる自分の部署が廃止されたから。それと、技術者で上に行くキャリアパスがなかった。マネージャーの狭き門を目指して他の人と競争しなければいけない。社内改善活動で貢献したいのに、マネージャーに行かなきゃいけない。それはやだなといって転職した。Yahoo!ではエンジニアのまま技術を極めて、黒帯を取ることも可能。

【居心地は?】
良いところ:
黒帯だから、といろいろな人からコンタクトをもらえる。取締役まわりとのコネクションも増える
悪いところ:
自分の言動に対して、周りがしっかり注目しているので厳しい。有名税みたいな感じかな。


倉林
【プレイヤーとして黒帯】
新卒で入社して丸6年たつ。チームの中でも中堅、ベテランに近い立場になり、マネジメントも求められる。マネージャーとしてではなく、黒帯として技術を追求している。現場で実際に開発をして気づけることがたくさんあるので、経験値を貯めて次に向けて充電している感じ。

里山
【企業の対外的なブランディング】
Yahoo!って、企業ブランディングではWEBの会社という印象が強く、アプリを作っている会社という印象は薄い。渋谷や六本木の会社がアプリエンジニアをブラックホールみたいに吸い込んでるけどw、アプリの技術に関しても発信していって、Yahooのブランドを確立していけたらと思う。

【紀尾井町に本社が移転して、良かったという話を聞いたが?】
17階にコワーキングスペース「LODGE」ができました。
外部の人を招いて勉強会を開催して、弊社との交流を進めていこうとしている



【ブランディング】
会社のブランドとしては、自分はとてもリスキーな行動をしていると思う。会社に言われないのに勝手にビットコイン調べまくってるし。国の立場かYahoo!の立場なのかよく分からなくなってくる。
標準化も含めて国際会議に出ていったりとか、Yahoo!としての場をつくっていこうとしている。

【黒帯について英語で説明するの?】
おまえ空手やるのか? とか言われたw 海外企業にもdistinguished engineerという制度があるのだろうが、黒帯制度について海外勢に伝えるのが大変だったりする。


里山
【コミュニティ】
以前、Android黒帯の全員で書籍を出したんだけど、そこでの話として、エンジニアの中級者以降って本を買わないよね、というのがあった。
初心者向けの本は売れるけど、中級者以上の人は、本を買わずにQiitaとかWEBを見て情報を得る。
参考:「黒帯エンジニアが教えるプロの技術 Android開発の教科書」を執筆しました - Yahoo! JAPAN Tech Blog
コミュニティ運営に関与する中で色んなエンジニアと出会うことがあって、自分の状況を見たときに会社に対してどういう風に貢献できるのか、どんなノウハウを伝えられるのか、ということを考えさせられた。


倉林
【OpenIDのほうとの関係は?】
黒帯の前は OpenID ファウンデーション・ジャパンのエバンジェリストだった。
黒帯になってからはYahoo!内の専門家として発信する機会も増えた。もともとYahoo!は社外の技術を吸収しやすい文化。黒帯のおかげで社外発信の機会は増えてきて、活動しやすくなってきた。
後継者をどう育成していくかは課題だと思う。活動自体はやりやすいので、自分の得意技術についてがんがん発信したい人はYahoo!に来るといいと思う。


伊藤
アジャイルというのは、教育方法として優秀だなと思っている。アジャイルだと、メンバーにすごく高速に失敗を経験させて、問題発見・解決・改善を積み重ねていく。その結果、メンバーが自分で動いて考えていく。自走性が育めるいい手段だと思う。
黒帯をうまく利用して、多くのプロダクトチームに、よりよく失敗を経験させて成長をさせていこうとしている。気づかせるために厳しく当たることもある。
【厳しく当たった例などある?】
何でも他人に丸投げしてしまう人の集団がいた。彼らが丸投げをしたら、投げた先にたくさん仕事を振って、仕事をパンクさせて「丸投げしたら仕事が立ち行かなくなる」という状態にした。リリースが遅れそうになる程度まで、それをやったことはある。それでも結果的にはうまく行った。
  1. 2017/02/24(金) 01:14:52|
  2. プログラミング
  3. | トラックバック:0
  4. | コメント:0

LPIC レベル1 101試験にボーダーギリギリで合格。勉強方法と反省を書くよ
2017/01/24(火) 00:55:17

1/22(日)に受けて、1回目で合格しました。

勉強の方法と内容 問題集は専らPing-tに頼った


勉強方法について。
参考書(問題集)は、定評のある「Linux教科書 LPICレベル1 Version4.0対応(中島 能和)」の紙版を購入した。
通称、あずき本(小豆本)。カバーがあずき色をしているからこのあだ名になったんだろうが、誰がこの名前をつけたんだろうw


問題を解いて覚えていかなければいけない。しかし、Ping-tという素晴らしいサイトがあるので使い倒すと良い。
101試験の問題は会員登録すれば無料で使えるので、これを使った。
(102試験の問題は有料)

仕事後や休日にPing-tの問題をチョコチョコ解いていって、分からないところは適宜あずき本で勉強した。
あずき本の章末練習問題・模擬試験は、パラパラ眺めることはあったが、解かなかった。

Ping-tの問題集のうち、銅を20%、銀を70%、金を10%くらいにしたところで試験日を迎えた。
Ping-tでは、問題ごとの回答状況に応じて「この問題は銅」「この問題は銀」などと自動的に分類される。
「銅」は未出題もしくは直前不正解の問題である。

あずき本によれば、合格ラインの正答率は65%(非公式)である。
80%の問題は一度正解できているから、少し間違えても65%は解けて、合格できるだろう。
俺はそう楽観的に考えていたが、その考えがロイヤルミルクティーなみに甘すぎたことを思い知ることになる。


試験感想 ギリギリで合格、試験最中にかなり焦った


試験開始。
あれ、見たことの無い問題があるぞ。それもかなりたくさんあるぞ。
ヤバい!! これは落ちるかもしれない!!
と思いながら、無理矢理全部の問題に解答した。

解答を終えるとすぐに採点され、自分の得点と合否が画面に表示される。
ボーダーラインちょうどの500点で合格した。
あずき本によれば合格ラインは約65%(非公式)らしい。
俺の正答率もその程度だろう。

受験料は15000円 + 消費税8% = 16200円。今まで受けてきた情報技術者試験(5700円)と比べても3倍近い値段である。あと1問でもミスってたら、高い金を払って不合格になっていただろう。危ない危ない。


反省点 なぜこんなに危ない成績だったのか?


なぜこんなに危ない成績だったのか?

■選択式の問題ばかり解いていた
Ping-tの問題集は、条件に当てはまる項目を選ぶ選択式問題であった。
俺はひたすらPing-tをやり続けていたので、選択式問題ばかり解いて勉強していたことになる。
しかし、あずき本の最初のほうをみると、択一式(1つの答えを選ぶ)・複数選択式(複数の答えを選ぶ)の
ほかにも入力式問題があることが分かる。
この本の練習問題には、コマンド名・オプション・ディレクトリ名などを答えさせる問題がある。
これらの問題に対処できなかったのが原因だろう。

なお、Ping-tにはコマ問という、「正しいコマンドを入力させる」問題がある。
これは入力式問題の対策になるだろう。
コマ問をさっき試しにやってみたらボロボロだった。コマ問もやる必要があったんだ……

■実機で練習しなかった
家で使っているのはWindows 7だが、それにLinuxを入れず、ネットと本だけで勉強してしまった。
早いところ仮想化を使ってLinuxを入れておこう。
LPICの試験は実機を触って確かめておけば慣れて覚えやすくなると思うし、
また、合格できても実機で実際に使えるようになっておかないとダメだろう。


102試験に向けて 合格のための勉強方法を考えた


■Ping-tで有料会員の申し込み
■参考書(問題集)のあずき本の102試験範囲を一度軽く流し読みして、「だいたいどんなことが聞かれるの?」を把握する
■Ping-tの問題集を解いていく
■Ping-tのコマ問を解いていく
■仕上げにあずき本の章末問題・模擬試験を解く
■特に覚えられない問題は、Ankiにも入力し、解いていく

Ankiは暗記用のソフト & Androidアプリ。現在はLPICの問題を一部Ankiに入れている。


目的 そもそも何のために受けたのか


試験でLinuxサーバ使うし、Linuxの知識を深めて行ければ良いと思って受験を決意したのだが。
いざ勉強すると、コマンド覚えたりオプション覚えたりと、細かい知識が多い。
「nlコマンドはデフォルトだと空白行にも行番号をつけます、空白でない行だけに行番号をつけるには
何のオプションが必要でしょうか? (答え:-bt)」みたいな問題が出てくると
「いやnlとか使わんし、それ調べたくなったらmanを見ればいいじゃん。覚える必要ないじゃん」と思ってしまう。
もうちょいLinuxの全体像みたいのを習得したいんだけど、いい方法無いかなぁ。

102試験だとネットワーク系のコマンドも出てくるし、
将来「あれ、なんかサーバのネットワークが不調だぞ」ってときに役立つかな。
役立つといいな。

それでは。
  1. 2017/01/24(火) 00:55:17|
  2. プログラミング
  3. | トラックバック:0
  4. | コメント:0

AtCoder Beginner Contest 036 木の独立集合の個数を求める
2016/06/11(土) 17:48:42

珍しく技術系っぽい記事を書く。

AtCoder Beginner Contest 036のD問題について。
D: 塗り絵 - AtCoder Beginner Contest 036 | AtCoder

問題の内容



グラフ理論の言葉で言い換えると
「与えられた木に対して、独立集合(independent set)の個数を求めよ。」となる。
独立集合 - Wikipedia

一般のグラフに対して、最大独立集合を求める問題はNP完全問題らしい。
そして独立集合の個数を数えるのも難しいらしい。↓の資料に書いてあった。
PowerPoint資料:木分解とグラフ・アルゴリズム(最適化と数え上げ)


ということは、グラフが「木であること」を利用しないと上手く解けないはずだ。
資料の中にも根付き木を利用して考える方法があったし、適当な頂点を根として計算するんだろう。

逐次的に(DPを用いて)処理するんだろうなぁ……
f(G)を与えられたグラフに対する独立集合の総数とすると、
・一点からなるグラフから始めて頂点を次々と追加し、f(G)を求めていく
・根付き木の部分木から順に、f(G)を求めていく
の2通りが思いつく。

競技時間中は前者かと思っていたけど、正解は後者。

AtCoder解説(※pdf)を見ると「根から遠い順に求めていけば良い」と書いてある。

プログラミング


なるほど、アルゴリズムとしては理解できた。
でもコードにできそうに無い。

深さ優先探索か何かをして、木の構造を入力する……??
各頂点に対して「この頂点の親はコレで、子はコレとコレです」みたいなデータを用意するの??
……?????

と、ワケが分からなくなったので皆の提出したコードを見ることにした。
言語はRuby。
Rubyで書かれた正答のソースコード一覧は以下から見られる。
All submissions - AtCoder Beginner Contest 036 | AtCoder

Rubyは初心者なので、読むのにだいぶ苦労したが、正解のコードは以下の2つの段階からなっている。

(1) 頂点どうしの関係性を配列に入力する
(2) 配列を元に、再帰的にf(x), g(x)を計算する

f,gは以下の通り。解説文から引用。
・f(x):頂点 x を親とする部分木に含まれる頂点をすべて白または黒で塗り,両端が黒で塗られた辺が存在しないようにする方法は何通りか?
・g(x): 頂点 x を親とする部分木に含まれる頂点をすべて白または黒で塗り,両端が黒で塗られた辺が存在しないようにする方法は何通りか?ただし,頂点 x は必ず白で塗らなければならない.


(1) 頂点どうしの関係性を配列に入力する



これは例を用いたほうが分かりやすいだろう。問題に載っていた入力例で考える。

5
2 5
1 5
2 4
3 2


5つの頂点からなるグラフである。

頂点1と繋がっているのは頂点5、頂点2と繋がっているのは頂点3,4,5、……という情報を順に配列に入れて
[[5], [3, 4, 5], [2], [2], [1, 2]]
というデータを作る。
ただし、実装する際はインデックスが0から始まるので、全ての要素から1を引いて
[[4], [2, 3, 4], [1], [1], [0, 1]]
という結果にする必要がある。

このデータの作り方はそんなに難しくない。枝のデータを1行ずつ読み込みながら配列に要素を追加すれば良い。

(2) 配列を元に、再帰的にf(x), g(x)を計算する



問題の解説文では、関数を定義するときはf(x)と書いてあり、xを引数にしていた。
しかし、実際のコードではf(x,p)と書かれているので「xとp」が引数である。
ではpとは何か。皆のコードを見てもしばらく分からずに悩んでいて、やっと分かった。
pは、xの親のノードである。
頂点xと繋がっている頂点の一覧は(1)の段階で作成した。
根ではない頂点を考えると、繋がっている頂点のうち1つは親、残りは子である。
関数の再帰では「頂点xの子それぞれに対して、値を求める」という操作をする。
これを言い換えると「xの隣接点の全てに対して、値を求める。ただし親pに対しては無視する」となる。

こうすると、各頂点に対して「頂点xの親は頂点pです」というデータを(例えば連想配列で)用意する必要はない。関数を呼び出す段階で、pを引数に入れればよい!
yをxの子とすると、f(x,p)を計算するにはf(y,yの親)が必要である。ここでyの親はxなので、関数呼び出しの際にはf(y,x)とすればよい。


アルゴリズムとコードの間のギャップ



解説文のアルゴリズムを読んで「納得した、確かにそのとおりだ」と思った。
しかし、コードを書こうとしても、どうすれば良いのか全然分からなくなってしまった。
つまり、解説文とソースコードとの間にギャップがあり、それを越えられなかったと言える。理論から実践までは案外遠いものである。
解説文とソースコードとのギャップは、まとめると次の2点だろう。

・「根から遠い頂点から順に求めていけばよい」と言っても、末端(グラフ理論では「葉」)を実際に指定する必要はない。根を指定して、子に対して再帰的に関数を呼び出せばよい
・そして「この点の親はどれか」という情報も明示的に保持しなくて良い。関数の引数に親の情報を入れ、子に対して呼び出す際にその点自身をパラメータに入れる

分かれば納得するけど、言われなきゃ気づかないぞ、これ。このギャップをどう埋めていけば良いんだろう。

ソースコード


そして俺が書いたコードがこちらです。
Submission #761133 - AtCoder Beginner Contest 036 | AtCoder
後学のために色々コメント書いといた。変数名もちゃんとしたものにした。時間制限があったらもっと適当な名前にすると思うw

あー。もっとrubyかけるようになろう。
それでは。
  1. 2016/06/11(土) 17:48:42|
  2. プログラミング
  3. | トラックバック:0
  4. | コメント:0
次のページ

FC2Ad