カテゴリーアーカイブ 未分類

著者:杉浦

マージソート

 ソートアルゴリズムの一つであるマージソートの紹介です。このソートはコンピュータに比べて残念な記憶力の人間でも身一つで大規模な相手に対して実行可能な高速ソートアルゴリズムです。実際、ボードゲーム、TCGなどでカードを整理する時に便利です。コンピュータにソートをやらせるならメモリをあまり食わず高速な賢い備え付けのソート(多分大体クイックソートの変形)を使った方がよいと思います。コンピュータ的な利点は、同値の項目でも並び替え前の関係を維持する安定ソートである点、データを分割して実行してもそれほど遅くならない点(メモリに乗りきらないくらい巨大なデータ相手に強い)でしょうか。
 マージソートの手順は以下の通りです。
(日本語wikipediaより引用)

  1. データ列を分割する(通常、二等分する)
  2. 分割された各データ列で、含まれるデータが1個ならそれを返し、2個以上ならステップ1から3を再帰的に適用してマージソートする
  3. 二つのソートされたデータ列(1個であればそれ自身)をマージする

 下のGIFはデモです。
 このソートは安定して塊を置くスペースがあるならば、デモ中で赤く示されているわずかな部分に注目するだけで実行できます。このためソート対象が巨大になってもデモと同様のことが人間の手で十分やれます。塊が目印になるので途中で放置しても再開が簡単な点、小さな塊を柔軟に好き勝手並びかえるのが有利な点(アルゴリズムによっては最終的に変わらなかったり、遅くなったり)も人の手で行うのにおすすめです。

  • この記事いいね! (0)
著者:杉浦

文字の出現頻度

 言語にはよく使われる文字と使われない文字の偏りがあります。アルファベットの母音と子音の使用頻度の違いは分かりやすいですし、調査結果もググれば出てきます。下図はアルファベットの出現頻度です。自分の覚えとも近かったので大体こんな感じです。

この出現頻度の偏りを用いた二つの技術を紹介します。
 一つは単純な換次式暗号の解読です。これはA→え、B→あ、C→さ、…のように1対1で本来の文字と別の記号を割り当てる暗号です。文中に出てくる語の頻度とある言語の使用頻度が近い場合、それは重要な手掛かりになり、十分な量の暗号文があれば暗号文のみで解読まで可能です。
 また、通信量の減少にも用いることができます。文字の出現頻度を考慮して01符号にアルファベットを割り当てることを考えると
0->e
1->a
00->t
01->i
10->o
11->s
000->n

と頻出する語に短い符号を割り当てることで雑な割り当てに比べて通信量を少なくすることができます。

  • この記事いいね! (0)
著者:杉浦

二進法

二進法は01、ビットなどと連想されるようにコンピュータに縁の深い言葉です。現代のコンピュータの計算速度はこれでもかというくらい小型化を続けるハードの貢献といかにうまくビットを扱うかというソフトの貢献に大きく支えられています。二進法は0,1,10,11,100,101,110,111,1000,⋯ と数えていく方式です。雑な言い方で二進法、十進法の関係を言葉にすると、二進法のn桁目の値が十進法でいうところの2^nにあたり、その変換の各桁の和が十進法表記になります。二進法表記と十進法表記の関係は次式の様に見るとわかりやすいはずです。
 コンピュータでは十進法でいうm^nをm=2^a、n=2^bと表現することで巨大な数や微小な数を表す浮動小数点方式、一度の状態変化で値を多彩に処理する補数表現、シフト演算、論理演算などの工夫がされています。
物事を覚えるには何度も繰り返すのが堅実です。二進法にはものを数える時に二進法を使うというで即物的に役に立ち、繰り返し使える方法があります。手の指をビットに見立て、折った状態を0、立てた状態を1とすることで片手で0から2^5-1=0~31、両手で2^10-1=1023までを数えることができるのです。さすがに32以上のものを手で数える事は珍しいでしょうが、片手で31まで数えられるというのは案外便利です。二進法に親しんでみましょう。

  • この記事いいね! (0)
著者:ym

コンプライTS500

ジムやジョギング用に bluetooth のヘッドセットを持っているのですが、付属の大イヤーピースでもサイズが合わず、困っていたんですよね。

でも、良い製品を発見しました。まさかイヤーピースだけで販売しているとは。

X3Tに対応した型番はなかったので、試しに TS500 の L をつけてみたところ、これがジャストフィット。いや結構無理やり差し込みましたけど。
でも、耳はジャストフィット。ウレタンの低反発枕のような素材なので握ってつぶしてから耳に差し込めば徐々に大きくなって抜けなくなります。
ただ素材的には消耗品なので、いずれは買い直しが必要、これはやむを得ないかな。
これで、何か食べて落ちるとか、下向いて落ちるとかが改善されたのでよしとします。

  • この記事いいね! (0)
著者:杉浦

ウィキメディア・コモンズの紹介

 ウィキメディア・コモンズはコモンな素材を集めたサイトです。少なくとも公的な立場で何かを書くことになり、そのために使う画像を集めるに際し、権利関係で悩むのが面倒な人(私とか)の役に立ちます。(最近フリー素材でググっても大勢のおもちゃにされているだけで、全然フリーじゃない素材がけっこうでてきて厄介です)
 ウィキメディア・コモンズは一見、創造的であったりなんだりで著作権が付随していそうな硬いメディアが多岐にわたり豊富なことが他のフリー素材集との大きい違いです。ポップなアイコンなら、いらすとや、ピクトグラムなんかもおすすめできます。また、このメディアがどのくらいの範囲で、どういう理由でフリーなのかの説明も付随してくるというのも権利関係にお手軽に安心できて良いです。
 ウィキメディア財団はウィキペディア、ウィキメディア・コモンズのみならず様々な活動活動を行っています。英語版wiki関係の充実っぷりはとんでもない(wikipediaは500万を超える記事、10万人以上のアクティブな編集者)のでいろいろ探してみるのも面白いです。

  • この記事いいね! (0)
著者:杉浦

量子三目並べの紹介

 三目並べは〇×ゲームとして知られています。私の地元では〇×ゲームと呼ばれていました。googleで三目並べと検索すれば検索結果画面で三目並べを遊ぶこともできます。お互いが最善の行動をした〇×ゲームが引き分けで終わることは簡単にわかると思います。単純な三目並べの手筋は探索アルゴリズムを考えるより、総当たりをした方が早いぐらいの探索範囲で済みますしね。この記事では三目並べに量子力学の発想を加えた量子三目並べの紹介をします。
 量子力学の世界では量子重ね合わせ(複数の状態を同時に持つ。ビットは0と1を同時に取れる)、量子もつれ(他の量子の状態の確定によって他の量子の状態も確定した状態になる)という法則が存在します。量子三目並べはこの量子重ね合わせ、量子もつれらしいものを導入した〇×ゲームです。量子三目並べはQuantum Tic-Tac-Toeというタイトルでiphone、android両方でアプリとしてプレイすることが可能です。石関匠, & 松浦昭洋. (2010). 量子三目並べの必勝法解析.なんて論文もあります。
 ルール(wikipediaより引用。図は石関・松浦(2010)より引用)

盤は通常の三目並べと同様に3×3の9つのマスを使用する。マークは先手を○、後手を×として、順に○1、×2、○3、…、×8、○9とする。
各手番でプレイヤーは、9つのマスのうちの2つに確定していないマーク(石関・松浦(2010)では量子マークと呼んでいるのでここではこれに倣う)を置く。マークした時点ではこのマークは確定せず、ゲームの進行によって後から確定することになる。量子マークは他の量子マークがすでに置かれているマスにも置くことができる。特例として、○9の手番ですでに他の8マスが確定している場合のみ、残りの1マスを即座に○に確定させる。

プレイヤーの新たな量子マークによって、同じ番号の2つずつ量子マークをそれぞれ結んだときに輪ができる状態になったとき(これを「”cyclic entanglement”が発生した」と言う。)、この輪を完成させた方ではない方のプレイヤーが、この輪に関わるマークの確定のしかたを選ぶ。なお、cyclic entanglementが発生したとき、この輪を形成するいずれかの番号の量子マークをどちらかのマスに確定させると、連鎖的にこの輪に関わる全てのマークが確定するため、有りうる確定の結果は2通りである。ここで、「この輪に関わるマーク」とは、直接に輪を形成しているマークのみでなく、ペアのうち一方が輪の上あり、もう一方が輪に関係ないマスにある量子マークのペアも含む(このようなペアの量子マークは、輪に関係ない方のマスに確定する。)。

通常の三目並べと同様に、確定した自分のマークを一列に3つ並べたプレイヤーが勝利である。しかし、量子三目並べでは、cyclic entanglementを確定させた結果、先手と後手が同時にラインを完成させる場合がある。この場合は、ラインを形成する確定したマークの番号のそれぞれの最大値を比べて、これが小さい方が優位であるとされる。

 図3の(b)は7対6で×が勝ちです。このゲームは既に必勝法を解析されてしまいしたが、常人の頭の許容量を超える程度には深く、十分楽しむ余地がありお勧めできるゲームです。余談ですが英語wikipediaの目並べ系項目は異様に充実しています。目並べ研究会でもあるのでしょうか。

  • この記事いいね! (0)
takahashi 著者:takahashi

FuelPHPでNotice例外の表示を消す方法

FuelPHPはデフォルトで、すべてのPHPエラーを表示するように設計されています。

FuelPHP は、古い手続き型の関数からの(例外でなない)PHP エラーに遭遇した場合、デフォルトの PHP の振る舞いを変更します。 FuelPHP は、致命的でない PHP エラーに遭遇した場合、処理を継続せず、これらのすべてのエラーに対し PhpErrorException をスローします。 すると、以前は無視していたような E_NOTICE といったエラーもすべて解決することを求められます。 非プログラマが作成したビューファイル中の構文エラーといった、PHP のエラーを捕らえることも同時に可能になります。

つまり、PHP上で作法通り(例えば空の変数を参照しない、など)プログラムしていないとNoticeエラーでバシバシ怒られます。
綺麗なプログラムを描きたい場合は非常に有用です(し、可能な限り修正すべきです)が、既成のライブラリを用いたり、開発期間が短かかったり、などといった場合はNoticeエラーが表示されるのは非常に困ることがあります。

そういう場合にNoticeエラーを無効化する方法を紹介します。

自分の知る限り、無効化する方法は2通りあります。

一つ目は、.htaccessでPHPのNoticeエラーを無効化する方法です。
fuelの場合、ドキュメントルート/public/.htaccess に次の設定を加えることで設定できます。

php_value "error_reporting" "E_COMPILE_ERROR|E_RECOVERABLE_ERROR|E_ERROR|E_CORE_ERROR"

この一行を、.htaccessの末尾に追加すれば設定完了です。
もう一つの方法は、fuelPHPの設定ファイル fuel/app/config/config.php に設定を記述することでnoticeを無効化できます。

アプリケーション設定 – FuelPHP

FuelPHPは”規定より設定”という思想で開発されており、かなり自由にコーディングすることができます。
最低限のルールの土台はfuel、それ以降の細かい部分は自分で作りこむことができるのがfuelの魅力ですね。

フレームワーク何を使うか悩んでいる方は是非一度試してみてはいかがでしょうか。

  • この記事いいね! (1)
村上 著者:村上

【MySQL】SELECT文で取得したデータを外部ファイルに書き込む方法

気付けばこの投稿が記念すべき100記事目でした。
いつも必死に書いていましたが、案外100記事ってあっという間ですね。

 

さて今回は、MySQLでSELECT文で取得したデータを ○○○.csv のような形式で、外部ファイルに書き込む方法です。
すぐやり方を忘れる or 定型文としてメモしてあるのをコピーして使っているだけなので、私のための備忘録としてまとめます。

select * from [テーブル名] INTO OUTFILE '[ファイル名]' FIELDS TERMINATED BY ',' OPTIONALLY ENCLOSED BY '"';

こちらを実行すると、指定したファイル名(例えば data.csv など)で新しくファイルが作られ、そこに抽出したデータが書き込まれます。

具体的には、まず「INTO OUTFILE [ファイル名]」でデータをファイルに書き込みます。
なお、既にあるファイル名を指定することはできません。
次に「FIELDS TERMINATED BY ‘,’」で、抽出したデータをカンマ区切りに変更します。
OPTIONALLY ENCLOSED BY ‘”‘」では囲み文字を指定でき、抽出したデータを指定した文字で囲むことができます。
今回は、「”(ダブルコーテーション)」でデータを囲みます。

また、サンプルコードでは指定しておりませんが、改行コードを指定することもでき、「LINES TERMINATED BY ‘\r\n’」を使います。
が、エクセルなどで開くと、いい感じに整形してくれるので、あまりこのオプションを使うことは少なそう。

 

データベースのデータをCSVファイルとして抽出できると、あとから表でまとめるときにとても楽なので、このオプションはとても重宝しています。
が、初めて使ったときは変な風に指定してしまい、おかしな形式になってしまったので、慣れるまではサンプルコードをコピー&ペーストした方が無難ですね。

  • この記事いいね! (0)
著者:杉浦

NMEAについてざっくり

NMEAを詳しく知りたい方のための資料として私がおすすめする資料はu-bloxの公開しているu-blox 8 / u-blox M8 Receiver Description Including Protocol Specificationのpp.105~127あたりです。このふんわりした小話よりもそちらでがっつり読み込んだ方がためになると思います。私は検索がうまくできませんでしたがtrimbleのhelpなども詳しいです。
NMEAとはGNSSの受信したデータを出力する複数のプロトコルをまとめた呼称です。NMEAは正式にはNMEA0183といい、団体であるNMEA(この記事中に出てくるこれ以外のNMEAはプロトコルNMEA0183のことを指した語です)が制定したプロトコルです。GNSS受信機はGNSS衛星から送られてきた信号を元に自らの位置などを推定しています。この推定された位置などの便利そうな情報をいい感じにまとめるプロトコルがNMEAになるわけです。ほとんどのGNSS受信機はこのNMEAに従ってデータを出力します。このNMEAには様々な種類があります。その中でも使われる頻度の高いGGA、GSA、GSV、RMCについてほんのり紹介します。実際に受信機から送られてくるデータを読んだことがある人はGGA、GSAでなく$GPGGA、$GNGSAなどの頭文字を持ってデータが送られてくることを知っているでしょう。NMEAは受信機によってGPGGA、GNGGAと頭文字が変わります。この頭文字は受信機が対応する衛星に従って付けられています。
GGAはざっくりと今の受信機の状態が分かるプロトコルです。位置、使用衛星数、精度低下率などがわかります。

$xxGGA,time,lat,NS,long,EW,quality,numSV,HDOP,alt,M,sep,M,diffAge,diffStation*cs<CR><LF>

GSAは誤差について詳しく記述されたプロトコルです。使用衛星、精度低下率について詳しく記述されています。

$xxGSA,opMode,navMode{,sv},PDOP,HDOP,VDOP,systemId*cs

GSVはGNSS Satellites in Viewの略称であり可視状態にある衛星について詳しく記述されています。

$xxGSV,numMsg,msgNum,numSV,{,sv,elv,az,cno},signalId*cs

RMCはRecommended Minimum dataとされています。RMCに大体のGPSに時刻、位置、速度といったGNSSに要求されている結果が記されています。

$xxRMC,time,status,lat,NS,long,EW,spd,cog,date,mv,mvEW,posMode,navStatus*cs
  • この記事いいね! (2)
著者:杉浦

組み合わせ爆発の話

 巨大な数を表す方法にはいろいろあります。掛け算、乗数、n乗のn乗の…数(乗数に乗数が含まれている)と順に大きくなっていきます。この中で2番目の乗数なんかは組み合わせ爆発と合わせてプログラマに縁があると思います。組み合わせ爆発とは機械学習などのアルゴリズムを考える時に考える必要のあることであり、碁や将棋のコンピュータが強くなることが難しいとされていた理由の一つです。多数の項目を組み合わせることで組み合わせ爆発を起こせます。[a-z]と[A-Z]と[0-9]を組み合わせれば26*26*10になります。雑に作ったアルゴリズムになんかはループ中ループ中を含み、こんなことになります。
 囲碁や将棋の手を進めることはどうしようもなく組み合わせ爆発になります。このため良い手を見つけることはとても難しいとされていました。組み合わせ爆発が起きるか否かはアルゴリズムを図示する際、フローチャートか状態遷移図かの基準なんかにもできます。

  • この記事いいね! (0)