Toy problemsは役立たずか(Floydの問題・ネタバレ)


U = {√1, √2, …, √50}を2つのグループに分け、グループ毎の和を求める。和の差がなるべく小さくなるようなグループ分けを、制限時間10秒で見つけよ。

1881526917先日紹介したFloyd問題です。

10秒という制限時間で、2の49乗個の候補の中から最良のものを見つけ出すのは、1977年当時のコンピュータでは難しかったはずです。そこでKnuthは、以下のような工夫をしました。

  1. まず小数部分を近づけることを目指し、その後で整数部分を近づける。(この問題では結果オーライ。√40までの場合はうまくいかない。)
  2. I = {√1, √4, √9, √16, √25, √36, √49}は、和の整数部分にしか関与しないから後で考えることにする。
  3. Uを2つのグループAとBに分け、Aの部分集合とBの部分集合の合計の小数部分を、全体の合計の半分の小数部分に近づける。
  4. Aの部分集合の小数部分をすべて記録しておき、Bの部分集合に対して、上の条件に会うようなAの部分集合がすぐに見つかるようにする。
  5. 部分集合の生成にはグレイコードを使う。
  6. X = {√2, √8, √18, √32, √50}の組み合わせでできる和は16通りしかないことを利用する。同様に、Y = {√3, √12, √27, √48}の組み合わせでできる和は11通りしかないことも利用する。
  7. 集合をA = X ∪ Y ∪ {√5, √6, √7, √10, √11, √13, √14, √15}、B = U – I – Aとする。

今日のコンピュータは当時と比べればはるかに強力なので、これらの工夫のうちの1から4を採用するだけで、あとは富豪的なプログラムでも最良解を見つけるのに5秒とかかりません(コード)。本稿執筆時点のideone.comで約2.5秒(double)あるいは約2.8秒(long double)、私のデスクトップ(Core i7 950 3.07Ghz)のVisual C++で約1.3秒でした(いずれもシングルスレッド)。

4774157155Aの部分集合の記録には、C++11で導入されたunordered_multimapを使いました。キーAのサブセット和の小数部分8桁を、値はサブセットを表現する整数とサブセット和のpairです(この実装では、mapよりunordered_mapのほうがかなり速いです)。sizeAを20にしたり、keyを小数点以下8桁にすると速いのは、動かしてみてわかったことです。

OpenCLに対応するデバイスの列挙(C言語・Mathematica)


GPUをグラフィック処理ではなく汎用計算に利用しようというGPGPUのためには、CUDAかOpenCLを利用するのが一般的です。NVIDIA的には、CUDAはGPGPUの開発環境であり、プログラミング言語としてC for CUDAかOpenCLを選べる、つまりCUDAはOpenCLの上位概念らしいのですが、一般にはCUDAとOpenCLは対立するものとして認識されているような気がします。

CUDAはNVIDIAのGPUにしか対応していないのに対して、OpenCLはNVIDIAのGPUとAMDのGPU、IntelとAMDのCPUにも対応しているので便利です(対応していないGPUやCPUもあります)。

IntelのCPUとHD GraphicsでOpenCLを利用できるようにする、Intel SDK for OpenCL Applicationsの新版(2013)が出たので、ちょっと使ってみます。

OpenCLに対応したデバイスを列挙することで、複数のデバイスに対応しているというOpenCLの特徴を確認してみましょう。規格で定まっているわけではないようですが、複数のOpenCL環境をインストールしているときには、複数のOpenCLプラットフォームがOpenCLのAPIから認識できるようになるようです(後述の参考書p.71)。

実行するためには、以下のいずれかが必要です。

4844331728開発は、WindowsとGNU/Linux、Macのいずれでも可能です。株式会社フィックスターズ『OpenCL入門 1.2対応 マルチコアCPU・GPUのための並列プログラミング』(インプレスジャパン, 改訂新版, 2012)サポートサイト)などを参考にすると、開発環境を比較的簡単に構築できます。(参考:Visual Studio + Intel SDK for OpenCL

適当な開発環境を用意したら、以下のプログラムをビルド・実行します(RSSリーダーでは見られないかもしれません)。

OpenCLの実装は複数のプラットフォームを認識できるものになっているので、上のコードでは、プラットフォームを列挙しつつ、各プラットフォームが持つデバイスを列挙しています。

私のデスクトップPCでの実行結果はこんな感じです。プラットフォーム毎にデバイスが1つあるというわかりやすい構成です。

Platform: NVIDIA CUDA
CL_PLATFORM_VERSION: OpenCL 1.1 CUDA 4.2.1

  Device: GeForce GTX 580
  CL_DEVICE_VERSION: OpenCL 1.1 CUDA
------------------------------------------------------------------------------
Platform: Intel(R) OpenCL
CL_PLATFORM_VERSION: OpenCL 1.2

  Device: Intel(R) Core(TM) i7 CPU         950  @ 3.07GHz
  CL_DEVICE_VERSION: OpenCL 1.2 (Build 63463)
------------------------------------------------------------------------------

私のノートPCでの実行結果はこんな感じです。2番目のプラットフォームにはデバイスが2つあり、そのうち1つは1番目のプラットフォームのデバイスと同じという、わかりにくい構成になっています。

Platform: AMD Accelerated Parallel Processing
CL_PLATFORM_VERSION: OpenCL 1.2 AMD-APP (923.1)

  Device:       Intel(R) Core(TM) i7-3612QM CPU @ 2.10GHz
  CL_DEVICE_VERSION: OpenCL 1.2 AMD-APP (923.1)
------------------------------------------------------------------------------
Platform: Intel(R) OpenCL
CL_PLATFORM_VERSION: OpenCL 1.2

  Device:       Intel(R) Core(TM) i7-3612QM CPU @ 2.10GHz
  CL_DEVICE_VERSION: OpenCL 1.2 (Build 63463)

  Device: Intel(R) HD Graphics 4000
  CL_DEVICE_VERSION: OpenCL 1.1
------------------------------------------------------------------------------

プラットフォームについて得られる情報は、http://www.khronos.org/registry/cl/sdk/1.0/docs/man/xhtml/clGetPlatformInfo.htmlにまとまっています。

デバイスについて得られる情報は、http://www.khronos.org/registry/cl/sdk/1.0/docs/man/xhtml/clGetDeviceInfo.htmlにまとまっています。

Mathematicaなら、すべての情報を以下の2行で得られて便利です(参考:OpenCLInformation)。

Needs["OpenCLLink`"]
OpenCLInformation[]

マンデルブロ集合をOpenCLで描く(Mathematica)


CUDAを使ってマンデルブロ集合の描画を3桁速くする方法を以前紹介したのですが、同じことをOpenCLでやってみます。NVIDIAのGPUを搭載していないノートPCを使うことが多くなった自分用のメモでもあります。書き換え方は、OpenCLLink プログラミングで紹介されています。

書き換えたコードは以下の通りです(RSSリーダーでは表示されないかもしれません)。

最初に作成したコードをCore i7-3612QM 2.1GHz上で実行するのと比べて、ここで作成したコードをIntel HD Graphics 4000上で実行すると、3桁くらい速くなります。

Manipulateを使ってインタラクティブに描くコードは以下の通りです(RSSリーダーでは表示されないかもしれません)。

似たような話がMathematicaのマニュアルにも載っていますが、ここで書いたコードなら、描画の中心もインタラクティブに変わります。

realtime

OAuth認証でTwitterを利用するWebアプリケーション(PHP PECL/oauthの場合)


以前、OAuth認証でTwitterを利用するWebアプリケーション(PHP twitteroauthの場合)をいう記事を書いたのですが、状況がいろいろ変わってきたので、PECL/oauthを使う方法を紹介します。

TwitterのAPIが変わっても、Twitter専用ライブラリがそれに対応するとは限らないので、汎用のOAuthライブラリを使っておいた方がいいかもしれない、という話です。

PECL/oauthを導入してから先に進んでください(参考:PECL/oauthの導入方法)。

アプリの登録

Twitterにアプリを登録し、Consumer KeyとConsumer Secretを取得します。

アプリを一度許可したユーザが確認画面をスキップできるように、つまり「oauth/authorize」ではなく「oauth/authenticate」を使いたい場合は、下のように、「Allow this applicetion…」を有効にしてください。

OAuth認証してつぶやく

3つのファイルに分けて説明します(RSSリーダーではコードが表示されないかもしれません)。

  1. twitter-oauth-start.php: OAuth認証開始
  2. twitter-oauth-end.php: OAuth認証完了
  3. twitter-oauth-post.php: つぶやき投稿

あとで1つのファイルにまとめます。

OAuth認証開始(twitter-oauth-start.php)

「Consumer Key」と「Consumer Secret」、callbackUrlは環境に合わせて書き換えてください。

実験時には、「$oauth->disableSSLChecks();」としておいてもいいでしょう。XAMPPでは、何もしないと「Peer certificate cannot be authenticated with given CA certificates」というエラーになります。Ubuntuでは、自動的に「/etc/ssl/certs/ca-certificates.crt」が読み込まれます。

OAuth認証完了(twitter-oauth-end.php)

つぶやき投稿(twitter-oauth-post.php)

ログアウト

ブラウザを再起動すればはじめに戻りますが、次のようなtwitter-oauth-logout.phpを作っておいてもいいでしょう。

1つのファイルでつぶやく

OAuth認証をしてつぶやく処理を1つのファイルにまとめると次のようになります。

MathematicaのAgglomerateのバグ


Mathematica 8.0, 9.0, 10.0, 10.1, 10.2, 10.3, 10.4.1, 11, 11.1 for Microsoft Windows (64-bit)と10.0.0, 10.3.1 for Linux ARM (32-bit)でのことです。

Mathematicaには、階層的クラスタリングができる関数が3つ用意されています。FindClustersAgglomerateClusteringComponentsです。3つもあるのが問題な気もしますが、とりあえずそれはよしとして・・・

FindClustersにはバグがあることを以前報告しました。

ですから、階層的クラスタリングをしたいときは、AgglomerateかClusteringComponentsを使わなければなりませんが、残念なことに、Agglomerateにもバグがあります。FindClustersの場合と同様、このデータと次のコードで再現できます(RSSリーダーでは表示されないかもしれません)。Assertによる警告は表示されませんが、UMMでも動きます。

クラスタリング結果にはすべての要素(この例では63個)が入っていなければなりませんが、結果を数えてみると足りません(この例では38個)。このバグは報告済みですが、解決方法はわかっていません。バグが修正されたバージョンを受け取るために、プレミアユーザになっています。

FindClustersとAgglomerateが使えないとなると、残るはClusteringComponentsだけになるわけですが、これにもちょっと問題があります(MathematicaのClusteringComponentsの困ったところ)。

というわけで、階層的クラスタリングをしたいときはRを使うのがよさそうです(参考)。