2013年01月

CodeIQ の「グループを作ろう!」にチャレンジ

目次

現役のエンジニア・企業がプログラミングの問題を出してくれる CodeIQ というサイトがある。問題を解くと、正解不正解の判定や、フィードバックなどを行ってくれる。ジャンルや言語などはさまざまある。

グループを作ろう!

今回は結城浩さんの「グループを作ろう!」という問題に挑戦してみた。アルゴリズムの問題で、プログラムを使って解いても使わずに解いても構わない。プログラムを使う場合、言語は何でも良い。解答(とコメントなど)を送ると、フィードバックをもらえる。

問題の概要は以下。

Bill=Billy
Mick=Michael
Billy=William
というように、同じ人物を表すニックネームのペアが 444 個与えられる。同じ名前をすべて連結し、
Bill=Billy=Will=William=Willie=Willy
Michael=Mick=Micky=Mike=Mikey
というようにグルーピングする。ただし、各行の順番および、同一行内の名前は ASCII 順に並べなければならない。

自分の解答:STEP 1 グループ番号割り振り

C++ でプログラムを組む前提で。

どうやってグループを寄せ集めていくかと考えたとき、グループ毎の配列(vector)を用意してしまう、というのは最初に思いつくが、さすがに効率が悪い(名前を読み込む度に、すべてのグループ配列を見て、すでにグループ化されているか調べる必要がある)。

漠然と、木を使えばできるのではないかとイメージしたが、残念ながら、木を簡単に実装する方法を思いつかなかった。

CodeIQ_グループ割り振りそこで代わりに、グループ番号を割り当てていく方法を採った(右はイメージ図)。

ペアの両辺を読み込み、それぞれの名前に既にグループ番号が割り当てられているか調べる。両辺とも未割り当てであれば、新しいグループ番号を割り振る。いずれかが割り当て済みであれば、もう片方に同じグループ番号を割り当てる。

CodeIQ_グループ変更両方とも割り当て済みで、かつ、違うグループ番号であれば、今までは別のグループとして扱ってきたが、実は同じグループであることが分かったということなので、片方のグループ番号をすべて書き換える。

名前→グループ番号の対応を格納するのは、STL の map を用いた。

自分の解答:STEP 2 結合

すべてグループ分けできたら、同じグループ同士を連結していく。string 型の vector を用意しておき、1 行に 1 グループを突っ込んでいく。

CodeIQ_行番号割り振りmap を先頭から読み込んでいき、同じグループ番号の文字列が既に vector にあるか調べる。あれば、文字列の末尾に新しい名前を追加する。無ければ、新しい行の先頭に名前を追加する。

グループ番号と行番号の対応も、やはり map で覚えておく(……が、今から思えば、配列の方が高速だった)。

map を使うことにより。キーが自動的に ASCII 順になっているので、新しい行ができた時は、単純に配列の末尾に加えれば良く、ソートの必要は無い。また、1 つの行に名前を追加する際も、末尾に追加するだけで良く、ソートの必要は無い。

注意点

注意すべきはグループの統合で、最初はこれを見逃していた。できあがった解答を眺めていて偶然気づいた。グループ統合のコードを後から付け加えたので、これだけ異質な感じがする。

計算量は、入力のペア数を N として、グループ統合がなければ恐らく O(NlogN) だが、グループ統合があると最悪 O(N^2) になるのだろう。

ソースコードの抜粋

// グループ番号割り当て
while ( aInFile && getline(aInFile, aLine) ) {
    get_names(aLine, &aName1, &aName2);

    // 名前のペアをマップに登録していく
    p1 = aGroupMap.find(aName1);
    p2 = aGroupMap.find(aName2);
    if ( p1 == aGroupMap.end() && p2 == aGroupMap.end() ) {
        // 新規登録
        aGroupMap[aName1] = aGroupIndex;
        aGroupMap[aName2] = aGroupIndex;
        aGroupIndex++;
    } else if ( p1 != aGroupMap.end() && p2 == aGroupMap.end() ) {
        // aName1 が登録済み→aName2 を同じグループに登録
        aGroupMap[aName2] = p1->second;
    } else if ( p1 == aGroupMap.end() && p2 != aGroupMap.end() ) {
        // aName2 が登録済み→aName1 を同じグループに登録
        aGroupMap[aName1] = p2->second;
    } else {
        // 両方登録済み
        if ( p1->second != p2->second ) {
            // 違うグループとして登録されているのでグループを統合
            change_group(&aGroupMap, p1->second, p2->second);
        }
    }
}

// A=B=C=D というような結合行を作成していく
while ( aGItr != aGroupMap.end() ) {
    aRItr = aResultMap.find(aGItr->second);
    if ( aRItr == aResultMap.end() ) {
        // 新規に結果行に登録
        aResult[aResultIndex] = aGItr->first;
        aResultMap[aGItr->second] = aResultIndex;
        aResultIndex++;
    } else {
        // 既存の行に追加
        aResult[aRItr->second] += "="+aGItr->first;
    }
    aGItr++;
}


模範解答

CodeIQ_木模範解答では、やはりグルーピングに木を使っていた。

面白かったのは木の実装方法。木を map で実装していた(模範解答は perl と思われる言語で実装されていたので、実際には連想配列)。

map のキーに、葉っぱの名前を入れ、値に、根っこの名前を入れる。根っこの名前は、値を空文字列にでもしておく。

こうすることで、数回 map を探索すれば、一番根っこの名前にたどりつける。1 つの根っこから出てくる名前はみな同じグループで、グループの数だけ、根っこ(空文字列)があることになる。

木をこうやって実装するのは定石なのだろうか。シンプルでいいな。

木の良い点は、グループの結合が楽ちんなこと。2 つのグループの根っこのうち、片方の空文字列をやめて、もう片方の根っこの名前を入れるだけで良い。どんなにグループが巨大でも、1 つの書き換えで済む。

感想

単にグルーピングするだけというシンプルな問題なのに、やってみるといろいろ考えることがあって面白かった。Union Find アルゴリズムとか Union Find Tree データ構造などという問題らしい。

実装言語を問わないこともあり、いろんな解答があったと聞く。なかにはエクセルで解いた人もいるとか。

他の人がどんな解答をしているのか気になっているのだが、残念ながら、ググっても自分の解答を公開している人はほとんどいないようだ。

結城さんがせっかく公開 OK に設定してくれているのだから、自分の解答を公開する人が増えてくれればいいなと思う。


鼻歌採譜プラグイン Ver 2.13 β を公開

歌声から音符を取得する SS_SaiLis_Main_Ver205BetaUTAU 用のプラグイン「鼻歌採譜プラグイン(Humming to Score Plugin)」をバージョンアップ。Ver 2.13 β をテスト公開。

ドラッグ&ドロップインストールに対応しているので、ダウンロードしたアーカイブを UTAU のウィンドウにドラッグ&ドロップすればインストール可能。

今回はマイナーバージョンアップで、配布サイトの URL の修正を実施。また、ミチコラさんに送って頂いた簡体字中国語の言語ファイルを収録した。謝謝!

引き続き、他の言語の辞書ファイルもお待ちしております。

鼻歌採譜プラグインの使い方などについては、新しく公開した動画をご覧ください

鼻歌を録音する際は、ノイズの少ない高音質の機材で行う方が良い結果が得られる。自分は、オリンパスのリニア PCM ボイスレコーダー、DS-800 で行っている。



WiMAX は将来どうなるんだろ?

いつでもどこでもインターネットができる WiMAX。

契約してかれこれ 3 年目になろうとしているが、ここにきて WiMAX の将来に暗雲が立ちこめている気がする。

勿論原因は LTE。速度だけの問題ならまだしも、世の中総 LTE 的な雰囲気になっているのが気がかりだ。

そもそも、WiMAX の何が好きかというと、
  • 安くて(月々 3,880 円程度、キャンペーン次第でもっと安く)
  • 実用十分なスピードで(5~15Mbps くらい)
  • 帯域制限が無く(真の意味でのパケホーダイ)
  • 縛りが緩い(いろんなプロバイダ&機器を選べる)

というようなメリットがあるから。安くて自由に使える広域無線は WiMAX しかない。


一方の LTE、特に日本で流行り始めている携帯各社の LTE は、速度が速い代わりに、

  • 高くて(月々 5,000~6,000 円くらい)
  • 帯域制限があって
  • 縛りだらけ(キャリア代えたら機器使い回せない、そもそも携帯電話という端末がほとんど)

と、デメリットが大きい。


携帯 LTE に押されて、WiMAX が無くなってしまったら……というのは心配だ。


WiMAX の次の手としては、WiMAX 2+ がある。


単に高速になるだけではなく、LTE 規格を一部取り込むことで、量産効果のある LTE の恩恵を受けてコストダウンに繋げるらしい。サービスインまでは遠そうだが……。


個人的には、WiMAX という規格自体にはこだわりはないので、最初の 4 つのメリットを実現してくれるなら、LTE で全く問題ない。ただ、携帯各社のサービスである限り、その実現はないので、UQ が LTE をやってくれたら面白いのでは、と思う。


まだ見ぬ WiMAX 2 を主体にした WiMAX 2+ ではなく、LTE の中に過去の WiMAX 1 も収容しますよ、という LTE+ の方がわくわくする感じ(技術的に実現できるのかは知らないけど)。


3 規格(WiMAX 1/2/LTE)を扱うよりもコストダウンできそうだし、LTE ならいろんな半導体会社がチップ作っているので、WiMAX 2 PC よりも LTE PC(LTE 内蔵 PC)の方が実現しやすそう。


便利で快適なモバイルライフが送れますように!








マシンベンチマークまとめ(メインマシン:Core i7)

新しい Core i7 マシン(Core i7-3770S/RADEON HD 5570 他、詳細スペックはこちら)の性能を見てみた。

Windows 7 エクスペリエンスインデックス

Windows7エクスペリエンスインデックス前世代の Core i5 マシンからパーツを使い回しているグラフィックス以外はスコアが上がり、上限値(7.9)にほぼ貼り付いている。
  • プロセッサ:7.7
  • メモリ:7.8
  • グラフィックス:6.8
  • ゲーム用グラフィックス:6.8
  • プライマリハードディスク:7.9
初回測定時はプライマリハードディスクが 5.9 という異様に低い値になったんだけど、何かあったのだろうか……。

Windows 7 の起動

Windows の起動(コールドブート)に要する時間を測定してみた。
  • 電源を入れてから Windows 7 を読み込み始めるまで:22 秒
  • Windows 7 を読み込み始めてからユーザー選択画面が出るまで:19 秒
  • 合計:41 秒
読み込み始めるまで(BIOS POST)が長いのは、SATA→eSATA に変換して接続している外付け RAID ユニットがあるため。RAID ユニットがなければこの時間が半分くらいになるかも。

読み込み始めてからの時間はもう少し短くならないものか……と思ってしまう。

なお、Windows 7 インストール時は、UEFI DVD ブートにて行った。

なお、スリープからの復帰は 4 秒。

CrystalDiskMark

CrystalDiskMarkResult_1000MBPLEXTOR M5 Pro 512GB(PX-512M5P)の速度を測定。さすが SATA 3(6Gbps)SSD、高速だ。


シーケンシャルリードは、公称値(540MB/s)に若干及ばないものの、521MB/s と、とても高速。以前の東芝 SSD(209MB/s)の 2.5 倍近くの速度だ。


シーケンシャルライトは、ほぼ公称値(450MB/s)通りの、443MB/s。こちらも以前(171MB/s)2.5 倍。


4K ランダムは 32MB/s と、これまた以前(13MB/s)の 2.5 倍。

CrystalDiskMarkResult_100MB参考に、100MB での測定結果も。


1000MB の時と大きなずれはなく、安定して性能が出ている印象。

PCMark7

Ver 1.0.4.0
総合スコア 4035

MHF ベンチマーク【大討伐】

MHF_Result_i71920x1080 フルスクリーン
スコア 2356

前世代とグラボが代わっていないのにスコアが伸びているので、CPU の演算も効いてるベンチなのか。

マシンスペックまとめ(メインマシン:Core i7)

更新

パソコンをリニューアル。

今までのマシンはまだ 3 年弱しか使っていなくて、なかなか快適ではあったのだけど、メモリ 8GB というのがちょっと少なく感じられるようになっていた。しかしメモリスロットが埋まっているので増設できない。それならいっそ……ということで新調して、メモリを 32GB に。

ただ、新しいマザボにはいくつか不満点がある。
  • ATX としてはやや小さなサイズのため、端っこをケースにねじ止めできない。なので、端の方のコネクタをはめる際にたわんでしまうのが気になる。
  • UEFI(BIOS)の画面がモニターからはみ出ていること。画面の右側や下側が見えないので設定が行えない。
光学ドライブがやたら高いのは、近所のヤマダ電機で買ったから。当初は代えるつもりがなく、秋葉で買わなかったのだが、ふと、光学ドライブだけ P-ATA であることに気づき、この際レガシーフリーにしよう、と思いつきで買ったので高くなってしまった。計画性大事。

全体としては満足のいく内容。

PX-512M5PSSD が 512GB になったので、データも SSD に置ける。バックアップ体制を変えないといけないけど。SSD って QUO カード大の大きさと USB メモリよりも薄い厚さしかないのに、よく 512GB もデータを貯められるよねぇ。

T2501(III)UAASSD におまけで付いてきた、SATA→USB 3.0 ケース(T2501(III)UAA)がなかなか良い。SSD を手軽に外付けできる。先代の東芝 SSD もプレクスターの SSD と同じくらいの大きさだったようで、ケースにぴったり入った。

【2013/01/12 追記】

スリープからの復帰後、一部アプリが外付け HDD(SATA→eSATA 変換 HDD)を見失っているような症状が出た。
の 2 点を実施したところ、治ったように見える。恐らく、SATA のタイムアウトだけ直せば大丈夫なのではないか。

パーツ型番購入価格(税込み)
名称Core i7 - P8 マシン(Rev. 2013-01-05)
※初出:2013-01-05
91,051 円
マザーボードASUS P8H77-V8,441 円
CPUIntel Core i7-3770S
※4 コア 8 スレッド、実クロック 3.1GHz(Turbo Boost 3.9GHz)、TDP 65W、22nm プロセス
26,300 円
CPU クーラーCPU 付属品
0 円
セラミックグリスCPU 付属品0 円
メモリ32GB、DDR3-1600(PC3-12800) DIMM 8GB×4
SMD-32G28NP-16K-Q
※SanMax 製、Elpida チップ、CL11、ヒートスプレッダ無し
14,780 円
ビデオカードSAPPHIRE HD5570 1G DDR3 PCI-E HDMI/DVI-I/VGA
※RADEON HD 5570、DDR3 1GB、128bit、PCI-e x16、40nm プロセス
※Core i5 マシンからの使い回し
0 円
サウンドカードCreative Sound Blaster Digital Music Premium HD (SB-DM-PHD)
※USB 接続
※Core i5 マシンからの使い回し
0 円
LANオンボード
※ギガビット
0 円
SSD512GB、PLEXTOR M5 Pro
PX-512M5P (3C01140039)
※S-ATA 3 (6Gbps)、2.5 インチ、7mm 厚、BGA
36,800 円
マウンタSSD 付属品0 円
RAID ユニット筐体……コレガ CG-HDC4EU3500
HDD……1TB×3 の RAID 5 で 2TB。いずれも Seagate Barracuda 7200.12、S-ATA
※eSATA 接続、GPT
※Core Duo マシンからの使い回し
0 円
光学ドライブ
(DVD スーパーマルチ)
アイ・オー・データ機器 DVR-SN24GE
4,730 円
ケーススカイテック SKⅡ-201W
※Core Duo マシンからの使い回し
0 円
電源Owltech AU-500
※500W
※Core i5 マシンからの使い回し
0 円
ディスプレイ21.5 インチワイド液晶、IO DATA LCD-MF223XS
※HDMI 接続
※Core i5 マシンからの使い回し
0 円
スピーカーONKYO WAVIO GX-70HD
※Core Duo マシンからの使い回し
0 円

マシンベンチマークまとめ(メインマシン:Core i5)その 2

Core i5-750s/RADEON HD 5570 等のマシンにて、追加でベンチマークを実施したのでその結果を。

  • PCMark 7 1.0.4.0……3257
  • MHF ベンチマーク【大討伐】(1920x1080)……2164

マシンスペック詳細はこちら

その他のベンチマーク結果はこちら

鼻歌採譜プラグイン Ver 2.12 β を公開

歌声から音符を取得する SS_SaiLis_Main_Ver205BetaUTAU 用のプラグイン「鼻歌採譜プラグイン」をバージョンアップ。Ver 2.12 β をテスト公開

ドラッグ&ドロップインストールに対応しているので、ダウンロードしたアーカイブを UTAU のウィンドウにドラッグ&ドロップすればインストール可能。

今回のバージョンアップ内容は、
  • 音長解析のさらなる改善。
  • 多言語対応のさらなる改善。
  • 細かなバグ修正。
また、Maplestyle さんに送って頂いた繁体字中国語(台湾)の言語ファイルを収録した。謝謝 Maplestyle!

引き続き、他の言語の辞書ファイルもお待ちしております。

以下の組み合わせで動作を確認。

鼻歌採譜プラグインOSUTAU音源
鼻歌採譜プラグイン
Ver 2.12 β
Windows 8 Pro
64 ビット版
UTAU
Ver 0.4.14
淡水ウパ淡水ウパ
鼻歌採譜プラグイン
Ver 2.12 β
Windows 7 Professional
64 ビット版
UTAU
Ver 0.4.16
槌音ずも
槌音ずも
鼻歌採譜プラグイン
Ver 2.12 β
Windows XP Professional
SP1 32 ビット版
UTAU
Ver 0.2.75
実音とわの(100404)実音とわの100404

なお、Windows 2000 では動作しない。

鼻歌採譜プラグインの使い方などについては、新しく公開した動画をご覧ください

鼻歌を録音する際は、ノイズの少ない高音質の機材で行う方が良い結果が得られる。自分は、オリンパスのリニア PCM ボイスレコーダー、DS-800 で行っている。



月別アーカイブ
記事検索
最新コメント
  • ライブドアブログ