No Such Blog or Diary

«Prev || 1 | 2 | 3 |...| 884 | 885 | 886 |...| 1247 | 1248 | 1249 || Next»

写真をBDRに焼いた

片面を6枚分,思いのほかjpegも大きいということを認識.

まあ,失敗写真というか残しておいてもしょうのない写真ばかりなので整理してやればメディア節約できるだろうけど面倒なので気にしない.

たまにはプリントしてみるか.

BDを初めて焼く

研究室のサーバの定期バックアップということで,初めてBD焼いた.大容量なのに意外と焼く時間が短く感じた.初めてのCD-RドライブはCD一枚焼くのに15分かかったというに…

でも一枚の片面BDRには25GBしか入らないのでRAWで撮った写真の全データを保存しておくには枚数がかさみすぎるんだよなぁ… 二回出かけたらBDR一枚なわけで.明らかな失敗写真を捨てれば問題ないのだろうか? とりあえずそのうち整理してみよう.

そういやVMのディスクイメージもデカすぎて片面だと入らないっけなぁ… あと10倍入るようになってくれるとありがたい.

飛んだなぁ

今年の実験を見た限りでは制御用のドライバ回路をゼロから組ませるのは大変だなぁと.それでも空飛んだので今年の連中はよくやった.そして発表に編集した動画を持ち出したのも良かったかもしれん.実験の発表なら面白くなければいけない.もう少しテンポよく行けるとよかったけど.

さて,来年の実験のネタは何にするかね.SunSOPTひとつお亡くなりになったけど来年もSunSPOTネタで動くものにするが,はたまたFPGAでリダクションマシン作って遊んでみるか.FPGAの方が工作量が少なくて楽かもしれないが… 派手さに欠けるよなぁ.

とりあえず余ってる部品でそのうち空中に停止するように作り変えるか.あとは適宜重心をとれるような制御と.駆動系のパワー自体も一度測定しておいた方が良いなぁ.

謝金

わーお,思ったよりだいぶ多いぜぇ.まあ,普通には交通費か.

保護回路は敵なのだろうか?

充電できないリチウムイオン電池を保護回路バイパスして充電してみた.充電器にも保護回路入っているので問題ないと思うけど,一方でやっぱりちょっと怖かったりする.まあ,本番は明後日なのでそれまでもてば問題ないから良しとしよう.

Ukkonen's algorithm

Suffix tree を線形時間で作るアルゴリズム.しかも文字列を先頭から処理できるオンラインアルゴリズムになっている.なぜかその元論文を読んだのでここにメモっておく.

とりあえず,二乗コストで suffix trie をオンラインに作るアルゴリズムがベース.この suffix trie は,各リーフが suffix に対応し,中間ノードは部分文字列に対応する.このアルゴリズムは,空文字列に対応する suffix trie から始め,それを逐次的に更新していくことで文字列全体に対する suffix trie を構成する.1文字追加することに対応する suffix trie の更新は,各ノードに持たせた suffix link を辿って行われる.suffix link は,そのノードの表現する部分文字列から先頭の一文字を取り去った文字列に対応するノードへのリンク(つまりは,suffix を取る操作に対応した状態遷移のこと).

このベースとなるアルゴリズムは1文字分の更新にtrieの大きさに比例したコストがかかるため,二乗のコストがかかる.

Ukkonen のアルゴリズムのアイデアは,分岐せずに一列につながった suffix trie のノード達をその根元のノード一つで代表させること.実際のところ,ベースアルゴリズムで構成する suffix trie にはこういった一列に並んだだけのノード列が多く現れ,それらの suffix link の更新が非常に無駄だと感じる.

一文字追加する際の更新で少々面倒なのは,一纏めにされたノード達を適宜分割する操作が必要なこと.これ以外はベースと同じで,一纏めになっているノードに対して suffix link を保持していく.この作業は順次大きくなっていく木を下から上に辿るように行うだけなので(横に飛んだりするけれど概ね全部の分岐で上に向かうイメージ),結局のところならし計算量で線形コストになっている.あとは頭のいいインデックスを使っていて,その更新作業中にループが出てくるが,こちらもならしでループ本体が線形回しか呼ばれないので問題ない.そのならし計算量の見積りは,インデックシングに使われている文字列上のポインタ二つが常に大きくなる方向にしか動かないことによる.

まあ,並列化できそうにないね.

«Prev || 1 | 2 | 3 |...| 884 | 885 | 886 |...| 1247 | 1248 | 1249 || Next»
Search
Feeds

Page Top