ナップサック問題を解いてみた
こんばんわ。
業務で組み合わせ最適化を扱う業務があったので、 ナップサック問題を解いてみました。
といっても、数学得意じゃないですし、Wikipediaに書いてる内容もほとんどわかってないですが。。。 色々調べた結果、「lpsolve」を使えば実現出来そうでしたので、これを使いました。 ※DLLは、リンク先のlp_solve_5.5.2.0_dev_win64.zipから取得しました。 ※lpsolve55のDLL読み込み部分は、lp_solve_5.5.2.0_vb.net.zipから取得しました。
lpsolveに関しては、日本語の参考サイトがほぼないので（英語読めないし）、適当に実装してるところもありますが、 たぶん、例題のサイトと同じ解になったので、あってると思います。 以下ソースです。
Module Module1
Private Structure OkasiInfo
Dim name As String
Dim price As Double
Dim kcal As Double
End Structure
Public Sub Main()
Dim okashilist = Module1.GetOkashiList()
lpsolve55.Init(".")
Dim kcal = okashilist.Select(Function(v) v.kcal).ToList
kcal.Insert(0, 0)
Dim price = okashilist.Select(Function(v) v.price).ToList
price.Insert(0, 0)
Dim lp = lpsolve55.make_lp(0, okashilist.Count)
'カロリーが高くなるように
lpsolve55.set_maxim(lp)
lpsolve55.set_obj_fn(lp, kcal.ToArray)
'合計金額は、300円以下に
lpsolve55.add_constraint(lp, price.ToArray, lpsolve55.lpsolve_constr_types.LE, 300)
'各おかしは、1度しか選択出来ないように
For i = 1 To okashilist.Count
Dim row(okashilist.Count) As Double
row(i) = 1
lpsolve55.add_constraint(lp, row, lpsolve55.lpsolve_constr_types.LE, 1)
Next
'整数のみになるように
For i = 0 To okashilist.Count
lpsolve55.set_int(lp, i, True)
Next
'算出結果
lpsolve55.solve(lp)
Dim col_cnt = lpsolve55.get_Ncolumns(lp)
Dim col(col_cnt) As Double
'算出結果を取得
lpsolve55.get_variables(lp, col)
Dim sum_kcal As Integer
Dim sum_price As Integer
Dim j As Integer = 0
For Each wk In okashilist
If col(j) > 0 Then
Console.WriteLine(String.Format("{0} \{1} {2}本", wk.name, wk.price, col(j)))
sum_kcal = sum_kcal + wk.kcal * col(j)
sum_price = sum_price + wk.price * col(j)
End If
j += 1
Next
Console.WriteLine("カロリ" & ":" & sum_kcal)
Console.WriteLine("金額" & ":" & sum_price)
Console.ReadLine()
End Sub
Private Function GetOkashiList() As List(Of OkasiInfo)
Dim okasiList As New List(Of OkasiInfo)
okasiList.Add(New OkasiInfo With {.name = "ポッキー", .price = 168, .kcal = 496})
okasiList.Add(New OkasiInfo With {.name = "うまい棒", .price = 10, .kcal = 45})
okasiList.Add(New OkasiInfo With {.name = "じゃがりこ", .price = 145, .kcal = 325})
okasiList.Add(New OkasiInfo With {.name = "ベビースターラーメン", .price = 60, .kcal = 347})
okasiList.Add(New OkasiInfo With {.name = "チロルチョコ", .price = 10, .kcal = 61})
okasiList.Add(New OkasiInfo With {.name = "かっぱえびせん", .price = 124, .kcal = 486})
okasiList.Add(New OkasiInfo With {.name = "サッポロポテト", .price = 124, .kcal = 446})
okasiList.Add(New OkasiInfo With {.name = "都こんぶ", .price = 105, .kcal = 22})
okasiList.Add(New OkasiInfo With {.name = "ヨーグレッとは入れもん", .price = 126, .kcal = 110})
okasiList.Add(New OkasiInfo With {.name = "おにぎりせんべい", .price = 184, .kcal = 475})
Return okasiList
End Function
End Module
C#の静的解析と言えばStyleCop
みなさんC#でも静的解析を行っているでしょうか。
その前に静的解析とは？ 静的コード解析 - Wikipedia
JavaだとFindbugsという有名な静的解析ツールがあります。 1年前くらいにC#開発をやってたのですが、C#にもFindbugs的な静的解析ツール無いかなぁと探してたら、 StyleCopってのがあるんですね。
静的解析をやっておけば、書き方の統一や潜在的なバグを防ぐことができます。 ということで、StyleCopの導入手順を簡単にご紹介。
StyleCopのダウンロード・インストール
以下のサイトの「Download」よりStyleCop本体をダウンロードします。
インストールはそのまま進んでいけば大丈夫です。
Visual StudioでStyleCopの実行
インストールが出来ればVisual Studioで実行ができます。 プロジェクトを右クリックすると以下のようにStyleCopの実行メニューが表示されます。 これを実行することによって、対象のプロジェクトに静的解析が実行されます。
実行結果の確認
静的解析の結果は警告として表示されます。 英語なのですが「SA1633」等でググれば日本語で解説されているサイトに行き着くと思います。
Jenkinsで実行できるともっといいかもしれませんね。
VirtualBoxでWindowsの仮想環境を作ろう
いろんなプロジェクトやってると動作検証用PC確保が問題となります。 自分のマシンで動作検証といっても既に色々なソフトをインストールしているので本来検証したい環境にするのは大変です。
プロジェクトに特化したOSがあるといいですよね！仮想マシン使えばそれが出来ます！
vagrantという環境をサクッと作れるツールも存在しますが、まだWindowsクライアント用のboxは無いみたいです（この記事執筆時点）。
ここではWindows7 64bitのマシンにVirtualBoxをインストールしてWindows7 64bitの仮想マシンを立ち上げてみましょう。
事前準備 64bitOSの仮想マシンを使用するにはBIOSの設定が必要です。 PCのBIOS画面で仮想化支援機構(VT-x/AMD-V)を有効にしてください。 BIOS画面の立ち上げ方や仮想化支援機構の設定箇所はメーカーや機種によって異なるので手助けできません。マニュアル見るかググってください。 そもそも仮想化支援機構に対応していない場合は別のマシンにするか32bitOSをインストールしましょう。以降64bitは32bitと読み替えてください。
マシンのCPUが仮想化支援機構に対応しているかは下記ページを見てみてください。 http://ark.intel.com/ja/Products/VirtualizationTechnology
１．MicroSoftがWindows7や8の試用版を用意してくれています。Windows7試用版のDVDイメージファイルをダウンロードしましょう。 http://technet.microsoft.com/ja-jp/evalcenter/dn407368 ※MicroSoftのアカウントが必要です。 私がダウンロードしたWindos7 64bitのファイル名は 7600.16385.090713-1255_x64fre_enterprise_ja-jp_EVAL_Eval_Enterprise-GRMCENXEVAL_JA_DVD.isoです（長っ！）。
２．VirtualBoxをダウンロードしてインストールします。「Windows (32-bit/64-bit)」を選んでインストールしましょう。 http://www.oracle.com/technetwork/server-storage/virtualbox/downloads/index.html?ssSourceSiteId=otnjp#vbox
最初のまとめ
- BIOS画面から仮想化支援機構(VT-x/AMD-V)を有効にしよう。
- VirtualBoxをインストールしよう。
- MicroSoftから試用版WindowsのDVDイメージをダウンロードしよう。
ではVirtualBoxを起動して始めましょう。
３．VirtualBoxで仮想マシン作成をクリックします。
４．仮想マシン名をつけましょう。バージョンはWindows64bitにします。 ここで64bitが選択できないあなた。事前準備の仮想化支援機構が有効になっていないです。
５．メモリは2GBあてましょう。最初はよくわからずに512MBのまま続けちゃってOSインストールで落ちてしまいました。 OSの最低動作要件は確保しましょう。
６．仮想マシンはOSまるまるひとつのファイルとなります。その形式を選びます。通常はそのままで良いでしょう。 ハードディスクサイズは後から増やすの面倒くさいらしいのでやや余裕を持った容量にしましょう。100GBとか。 実際のファイルサイズはそれより小さいので心配しなくてよいです。
７．作成した仮想マシンを右クリックして「設定」を選択します。ここでメモリ割り当てとかネットワーク設定とかできるんですね。 まずOSをインストールしないといけないので「ストレージ」を選択し7600.16385.0907……_DVD.isoを選択します。
８．仮想マシンを起動するとDVDイメージが読み込まれてOSインストールが始まります。なんかパソコン上でOSインストールって変な感じ。後は画面の指示に従ってインストールしてください。
９．OSのインストールが終わりましたが…、解像度がフルにならないです。そのままだと最も貧弱な状態のディスプレイになります。 ゲストOSにVBoxGuestAdditionsをインストールすると解消されます。ストレージにVBoxGuestAdditions.isoをマウントしましょう。ファイルは以下にあります。 C:\Program Files\Oracle\VirtualBox\VBoxGuestAdditions.iso
１０．VBoxWindowsAdditionsインストールはゲストOS上で行います。ゲストOSのエクスプローラーを使ってVBoxWindowsAdditions.exeを立ち上げましょう。あとはそのままインストールしましょう。 ゲストOSでもめでたく高解像度が使えるようになります。VBoxGuestAdditionsについてはこちらのサイトを参考にさせていただきました。http://exlight.net/linux/vbox_guest_additions/index.html
仮想マシンのDVDドライブにVBoxGuestAdditionsが出てきます。右クリックで「開く」
VBoxWindowsAdditionsをダブルクリックしてインストールしましょう。
そのまま「Next」で進めましょう。
１１．これで画面の解像度もマトモになりました！インストール直後はサービスパックも当たっていませんのでWindowsUpdateの嵐です。なんだかんだで半日近く要しました＿|￣|○。予めサービスパックをダウンロードしとけばよかったと後悔。いやそれよりもサービスパック適用済みのISOファイルを用意してくれ、Microsoftよ。
１２．バックアップ＆他のマシンで使えるようにクローンをとりましょう。クローンしたVHDファイルであれば他のPCのVirtualBoxでも使用できます。
１３．最初の10日は認証無しで使用できます。その後認証を求められますが認証した時点で90日間試用版として使用できます。試用版といっても機能は特に制限されていないようです。
認証してから90日っていうのがポイント。環境作ってしばらくほっておいても未認証であればそこから90日使えるんですね。 認証の猶予期間である10日間のうちに全力で必要な検証環境を用意しましょう。その状態でクローンを取っておけばいつでも同一環境で90日間利用できますよ。
１４．その他もろもろ
設定画面のネットワークは「NAT」だと同一LAN内にはアクセスできませんがインターネットにはつながります。 よくわからなければ「ブリッジ アダプター」を奨めます。同一LAN内に独立した1台のPCとして存在するようになってファイルの共有とかネットワークプリンターへのアクセスとか通常のPCのように使えます。
VirtualBoxの弱点なのですが、Windows同士ではホストOSゲストOS間でクリップボードが使用できません。ファイルを仮想マシンにコピーしたいときとか文字列コピペができないので非常に不便です。 その対策としてリモートデスクトップでの操作をおすすめします。仮想マシンのリモートデスクトップを有効にしておけば、リモートデスクトップ経由でクリップボードが利用できますので便利ですよ。
設定画面ではCPUのプロセッサー数や占有率を変更できます。あえて低スペック状態でレスポンス検証したりできます。
VirtualBoxではスナップショットという機能があり、その時点のバックアップをとれます。このソフトを試しにインストールしてみようかな？と思った時は仮想マシンで実験してダメならすぐ戻せます。
ホストOS＋ゲストOSでメモリ食うんで最低6GB積んだパソコンでやったほうがいいよ。
...実は90日試用版を延長する方法もあります。これはググってね。
まとめ
- VirtualBoxでPC上に別のWindowsを立ち上げることができる。
- OSはMicrosoftからダウンロードできる。
- 最初の10日間は猶予期間。認証した時点から90日間使用できる。
- クローン作っておけばその時点の環境をすぐに再構築できる。
PostgreSQLのインストール
最近さわったPostgreSQLの覚え書きを。
■環境 CentOS6.5 PostgreSQL9.3
パッケージではなく、ソースコードコードからインストールしました。
- インストール前の準備（PostgreSQL用ユーザー、インストール先ディレクトリの作成）
- ソースのダウンロード、展開
- インストール ※事前にreadline,zlibのインストールが必要
- 環境変数の設定 ※.bashrcに以下を追加,反映
- データベースの初期化 ※PostgreSQLを使用可能な状態にする
- 起動と停止
- PostgreSQL接続用一般ユーザーの作成とDB接続
[root@vagrant-ce65 ~]# useradd postgres [root@vagrant-ce65 ~]# cd /usr/local/src/ [root@vagrant-ce65 src]# mkdir /usr/local/src/postgresql-9.3.4 [root@vagrant-ce65 src]# chown postgres:postgres /usr/local/src/postgresql-9.3.4 [root@vagrant-ce65 src]# mkdir /usr/local/pgsql [root@vagrant-ce65 src]# chown postgres:postgres /usr/local/pgsql/
[root@vagrant-ce65 src]# su - postgres [postgres@vagrant-centos65 ~]$ wget http://ftp.postgresql.org/pub/source/v9.3.4/postgresql-9.3.4.tar.gz [postgres@vagrant-centos65 ~]$ tar zxvf postgresql-9.3.4.tar.gz -C /usr/local/src/※wgetが入ってなかったらyum install wget、ソースアーカイブの展開先指定（tar -Cオプション）
[root@vagrant-ce65 src]# yum install readline readline-devel [root@vagrant-ce65 src]# wget http://www.zlib.net/zlib-1.2.8.tar.gz [root@vagrant-ce65 src]# tar zxvf zlib-1.2.8.tar.gz [root@vagrant-ce65 src]# cd zlib-1.2.8 [root@vagrant-ce65 zlib-1.2.8]# ./configure [root@vagrant-ce65 zlib-1.2.8]# make [root@vagrant-ce65 zlib-1.2.8]# make install [root@vagrant-ce65 zlib-1.2.8]# su - postgres [postgres@vagrant-centos65 ~]$ cd /usr/local/src/postgresql-9.3.4/ [postgres@vagrant-centos65 postgresql-9.3.4]$ ./configure [postgres@vagrant-centos65 postgresql-9.3.4]$ make [postgres@vagrant-centos65 postgresql-9.3.4]$ make install
[postgres@vagrant-centos65 ~]$ vi .bashrc export PATH=$PATH:/usr/local/pgsql/bin export MANPATH=$MANPATH:/usr/local/pgsql/man export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/pgsql/lib export PGDATA=/usr/local/pgsql/data ・ ・ [postgres@vagrant-centos65 ~]$ source .bashrc
[postgres@vagrant-centos65 ~]$ initdb --encoding=UTF8 --no-locale
[postgres@vagrant-centos65 ~]$ pg_ctl -w start [postgres@vagrant-centos65 ~]$ pg_ctl stop※DB接続中のユーザーがいる場合は-mオプションを付けて停止する。 $ pg_ctl -m 停止方法 [s(mart)｜f(ast)｜i(mmediate)] stop
[postgres@vagrant-centos65 data]$ createuser kuma [postgres@vagrant-centos65 data]$ psql postgres kuma psql (9.3.4) Type <help> for help.postgres=>; \q
PostgreSQLでSQLファイルをWindowsのbatで実行する
こんちわ、堀之内です。
先日リリース作業を行った際に、DBの変更が大量でsqlを全て流すのが面倒だったのでフォルダ内のsqlを流すbatを作ってみました。
実は、sqlファイルを実行するのは簡単でpsql.exeにファイルパスを渡してあげれば実行してくれます。
しかし、実行時に毎回パスワード入力を要求されるので、これを回避するために実行ユーザのホームディレクトリにpgpassファイルを配置します。
これが有るとパスワード要求無しでpsql.exeを実行する事ができるので先にpgpassファイルを作ってやります。
ユーザーのホームディレクトリは「%APPDATA%」で取得できます。
SET HOSTNAME=HostName
SET PORT=5432
SET USERID=UserName
SET PASSWD=UserPassWord
SET DATABASE=DatabaseName
IF NOT EXIST "%APPDATA%\postgresql\pgpass.conf" (
MKDIR "%APPDATA%\postgresql"
ECHO %HOSTNAME%:%PORT%:*:%USERID%:%PASSWD% > "%APPDATA%\postgresql\pgpass.conf"
)
後は指定フォルダ内の「.sql」をファイルを取得してループ実行してやります。
FOR /F "usebackq delims==" %%i IN (`DIR /B sql\*.sql`) DO ( psql.exe -h %HOSTNAME% -p %PORT% -d %DATABASE% -U %USERID% -f sql\%%i > log\%%i.log 2>&1 )
ログをファイルに出力したりするとするとより良いのかもしれませんがここまでとします。
