M.Hiroi's Home Page

Memorandum

プログラミングに関する覚え書や四方山話です。
[ Home | 2019年 1月, 2月, 3月, 4月, 6月, 9月, 12月 ]

2019 年 12 月

12月21日

●ウィンドウマネージャ (window manager)

X Window System の続きです。X の場合、サーバー側はユーザーの入力処理とクライアントが要求したグラフィックをディスプレイに描画するだけで、ウィンドウの外観や操作方法などのユーザーインターフェース (UI) を担当しているわけではありません。UI を担当しているのはクライアント側のプログラムで、これを「ウィンドウマネージャ (window manager)」といいます。

Cygwin/X には 4 つのモードがあります。

  1. Multiple windows
  2. Fullscreen
  3. One window
  4. One window without titlebar

1 は Windows 10 の画面の中で X クライアントのウィンドウが描画されますが、これは X サーバーに Multiple windows 用のウィンドウマネージャが用意されていて、それが動作することで実現しています。それ以外のモードでは何かしらのウィンドウマネージャが必要になります。たとえば、3. One Window で Cygwin/X を起動した場合、コンテンツが黒い大きなウィンドウが一つ表示されます。この状態では、コンテンツ上でマウスカーソルは表示されません。

また、Cygwin や WSL の端末で xeyes を実行すると、コンテンツの左上隅に xeyes は表示されますが、ウィンドウのタイトルや枠などは表示されません。ウィンドウを閉じたり、最大化、最小化、移動などの操作もできません。表示する位置も左上隅からしかできないので、xeyes のあとに xclock を実行すると、xeyes の上に xclock が上書きされてしまいます。

X サーバーを起動したあとウィンドウマネージャを実行すると、いわゆる GUI での操作が可能になります。いちいちウィンドウマネージャを実行するのは面倒なように思えますが、ウィンドウマネージャを入れ替えることで、ユーザーが自分の好みに合わせて自由に GUI 環境を構築することが可能になります。

Cygwin/X (X11 カテゴリ) にはいろいろなウィンドウマネージャが同梱されています。

Fluxbox, FVWM, Openbox, WindowMaker は スタートボタン -> Cygwin-X から起動できますが、いわゆる「ディスクトップ環境」ではないので、その操作方法に戸惑われるかもしれません。

たとえば、Openbox にはパネル (タスクバー) がありません。マウスの右クリックでメニューが表示されるのはいいのですが、ウィンドウを最小化すると画面から消えてしまいます。M.Hiroi は元に戻す方法がわからず、途方に暮れてしまいました。ネットで調べてみると、Openbox は tint2 などのパネルと組み合わせて使うのが一般的なようです。

ところで、Cygwin には GNOME, KDE, LXDE, Xfce といったカテゴリも用意されています。M.Hiroi はまだ試していませんが、それらをインストールすればディスクトップ環境を利用できると思います。興味のある方は試してみてください。

ウィンドウマネージャは X クライアントの一つなので、WSL 側で実行することもできます。ネットを検索すると、LXDE や Xfce などをインストールする記事も見つかりますが、ここでは twm を使ってみましょう。twm は X11 の初期からある小さくて軽量なウィンドウマネージャです。古風な UI なので、初めて使う方は面食らうのではないでしょうか。

Ubuntu の場合、twm は次のコマンドでインストールすることができます。

sudo apt install twm

あとは One Window モードで X サーバーを起動して、WSL から次のコマンドを入力するだけです。

$ twm &

twm はユーザーによるカスタマイズが可能です。設定はファイル ~/.twmrc に記述します。ファイルが存在しない場合、デフォルトのファイル (Cygwin ならば /usr/share/X11/twm/system.twmrc, Ubunts ならば /etc/X11/twm/system.twmrc-menu) が参照されます。Ubunts の場合、デフォルトの設定が非常に使いにくいので、M.Hiroi は Cygwin の設定ファイルを ~/.twmrc にコピーしました。この設定で参考 URL 3 を読むと、twm の基本的な使い方がよくわかると思います。作者様に感謝いたします。

マウスの右ボタンを押したままにするとメニューが表示されます。xterm を立ち上げて xeyes や xclock を実行する、または WSL 側から GUI アプリを実行することもできます。拙作の Tcl/Tk ミニゲームも動作します。興味のある方はいろいろ試してみてください。

●参考 URL

  1. Twm - ArchWiki, (Arch Linux JP Project)
  2. Bash on Ubuntu on Windowsでウィンドウマネージャを起動, (野村さん)
  3. twmウィンドウマネージャの使い方, (kabe さん)
  4. ウィンドウマネージャ - Wikipedia
  5. twm - Wikipedia

12月14日

●X Window System

WSL の続きです。Unix 系 OS では GUI の構築に X Window System を使うのが一般的です。X とか X11 (X Version 11) と呼ばれることもあります。X はクライアントサーバーモデルになっています。ユーザーが使うキーボード、マウス、ディスプレイなどを管理するサーバー (X サーバーという) があり、それを複数のアプリケーション (X クライアントという) が利用する方式になります。

1 台の PC で Linux (たとえば xubuntu など) を動かす場合、X サーバーと X クライアントは同じマシンで動作することになります。X サーバーと X クライアントはネットワークを経由して通信することもできます。たとえば、遠隔地にあるマシンでアプリを実行し、手元のマシンで結果をグラフィック表示したり、アプリを GUI で操作することも可能です。この場合、手元のマシンがサーバーになるので、一般的なクライアントサーバーモデルと同じように考えるとちょっと混乱するかもしれません。

WSL の場合、基本的には CUI (Character User Interface) ですが、Windows 上で動作する X サーバーを用意すれば、WSL でも GUI アプリケーションを動かすことができます。フリーで利用できる X サーバーには Xming, Cygwin/X, VcXsrv などがあります。これらの X サーバーについては X Windowの利用について (農林水産研究情報総合センター) が参考になると思います。

インターネットで検索すると、WSL と VcXsrv で GUI 環境を構築する記事が多いようですが、ここでは Cygwin/X を使うことにします。なぜならば、M.Hiroi は Cygwin で Tcl/Tk や Python/Tkinter などを動かすため Cygwin/X を導入済みだからです。Cygwin/X は Cygwin がないと動作しません。Cygwin と Cygwin/X をインストールするのはけっこう時間がかかります。Cygwin は不要という方は、Cygwin/X 以外の X サーバーを選択することをおススメします。

Cygwin と Cygwin/X のインストールについては、拙作のページ Tcl/Tk GUI Programming: インストール方法, Cygwin で簡単に説明しているので参考にしてください。起動方法ですが、WSL で使用するときはサーバーの起動時にオプション -listen tcp の指定が必要になります。スタートボタン -> Cygwin-X -> XWin Server を実行しても、WSL と X サーバーを接続することはできません。ご注意くださいませ。

X サーバーを Cygwin Terminal で起動する場合、次のコマンドを実行してください。

run xwin -multiwindow -listen tcp

いちいち Cygwin Terminal でコマンドを入力するのは面倒という方は XLaunch を使いましょう。スタートボタン -> Cygwin-X -> XLaunch を実行します。

最初の Select display settings と次の Select how to start clients はそのままでいいでしょう。3 番目の Extra settings の項目 Additional parameters for X sever に -listen tcp を追加します。そして、最後の Configuration complete で Save Confiuration をクリックすると、今まで設定した内容がファイル (デフォルトは config.xlaunch) に保存されます。このファイルをダブルクリックすると、その設定で X サーバーが起動されます。

あとは WSL 側で環境変数 DISPLAY の設定が必要になります。

$ export DISPLAY=:0.0

bash の設定ファイル .bashrc に書き込んでおくとよいでしょう。

動作確認のため、パッケージ x11-apps をインストールして xeyes や xclock を動かしてみてください。ちなみに、WSL と Cygwin の両方で GUI アプリケーションを動作させることもできます。たとえば、WSL で xeyes を実行し、Cygwin で xclock を実行すれば、同じ画面上に xeyes と xclock が表示されます。Tcl/Tk と Noto フォントをインストールすれば、拙作のゲーム (Mini Games, Mini Games 2) も動作します。興味のある方はいろいろ試してみてください。

●参考 URL

  1. X Windowの利用について, (農林水産研究情報総合センター)
  2. WSLからCygwin/XにX転送する, (tpcbtw さん)
  3. X Window System - Wikipedia

12月7日

●Windows Subsystem for Linux (WSL)

最近、M.Hiroi は Tcl/Tk の再入門みたいなことをやっています。Tcl/Tk の場合、C言語で書かれた関数をリンクするのは簡単で、その動作確認を xubuntu (VirtualBox) や Cygwin で行っています。VirtualBox はとても便利なのですが、以前に比べて動作がちょっと重くなったような気がしたので、たらい回し関数で実行時間を計測してみました。

リスト : たらい回し関数 (C言語)

int tak( int x, int y, int z )
{
  if (x <= y) return z;
  return tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y));
}
tak(22, 11, 0) の実行時間 
gcc -O2 (ver 7.3.0): 1.24 (バージョン 5 詳細は不明 2018/10)
gcc -O2 (ver 7.4.0): 2.99 (バージョン 6.0.14)
実行環境: xubuntu 18.04 on VirtualBox, Intel Core i5-6200U 2.30GHz

結果を見てびっくりしました。バージョン 6 になってから遅くなったのか、それとも M.Hiroi の設定に何か問題があるのかもしれません。設定はいろいろ試してみたのですが、現バージョンではこれより速くすることはできなかったので、残念ながらあきらめました。そこで、前から興味があった Windows Subsystem for Linux (WSL) を使ってみることにしました。

WSL は Linux の実行ファイル (ELF フォーマット形式) を Windows で動かすための仕組みです。Windows で Linux カーネルが動いているわけではなく、LXCore と呼ばれる「サブシステム」が Linux カーネルへのファンクションコールを Windows カーネルへのファンクションコールに変換することで動作します。なお、LXCore はすべてのカーネルファンクションコールに対応しているわけではありません。WSL では動作しないコマンドもあるようですが、多くのコマンドはそのまま実行することができます。

Windows 10 に WSL をインストールするのは簡単です。

  1. コントロールパネル -> プログラム -> Windows の機能の有効化または無効化 を開く
  2. 項目 Windows Subsystem for Linux をチェックする
  3. Windows を再起動する
  4. Microsoft Store で WSL を検索
  5. 好みのディストリビューションを選ぶ (M.Hiroi は Ubunts を選択)
  6. インストールをクリックする
  7. 終了すると起動ボタンが表示されるので、それをクリックする
  8. 選択したディストリビューションがインストールされる (少々時間がかかる)
  9. 最後にユーザー名とパスワードを入力する

2 回目以降の起動はスタートから Ubunts を選択する、またはコマンドプロンプトや PowerShell でコマンド wsl を実行します。あとは必要なパッケージを apt でインストールしてください。gcc は入っていなかったので、さっそくインストールしました。

たらい回し関数の実行時間は次のようになりました。

tak(22, 11, 0) の実行時間 
gcc -O2 (ver 7.4.0): 1.28
実行環境: Windows 10 WSL, Intel Core i5-6200U 2.30GHz

WSL も速いですね。I/O 処理が絡むと実行速度は遅くなると思いますが、Linux やプログラミング言語の学習には十分すぎる速度です。Linux の学習には Cygwin という選択肢もあるのですが、パッケージのインストールは apt に慣れると Ubuntu のほうが簡単です。しばらくは WSL でいろいろ試してみたいと思います。

●参考 URL


2019 年 9 月

9月15日

●M.Hiroi's Home Page の転送について

ジオシティーズの転送サービスは 2019 年 9 月 30 日で終了します。10 月以降になるとジオシティーズ (http://www.geocities.jp/m_hiroi/ と http://www.geocities.co.jp/SiliconValley-Oakland/1680/) にアクセスしても、今のホームページ (http://www.nct9.ne.jp/m_hiroi/) に転送されることはありません。よろしければブックマークの変更をお願いいたします。


2019 年 6 月

6月9日

●整数計画法

PuLP の続きです。数理計画法において、変数の値が整数値しかとらない場合を「整数計画法 (integer programing)」といいます。特に、変数の値が 0 と 1 しかとらない場合を「0-1 整数計画法 (0-1 integer programming)」といいます。PuLP は変数に Integer (整数) や Binary (0 or 1) を指定できるので、整数計画法の問題を解くことも可能です。ただし、整数計画法は NP 問題になるので、変数の数や変数の領域 (domain) が大きくなると、現実的な時間で解を求めるのは困難になる場合があります。ご注意くださいませ。

今回は「ナップザック問題」を取り上げます。拙作のページ 制約論理プログラミング超入門 ナップザック問題 で取り上げた問題を PuLP を使って解いてみましょう。

[問題1]

下表に示す品物をサイズ 15 のナップザックに入れるとき、金額が最大となる入れ方を求めてください。

品物金額サイズ
A43
B54
C65
D87
E109

出典 : Coprisによる制約プログラミング入門, (田村直之さん)

リスト : 問題1の解法 (test2.py)

import pulp

problem = pulp.LpProblem('sample', pulp.LpMaximize)

a = pulp.LpVariable('a', cat='Binary')
b = pulp.LpVariable('b', cat='Binary')
c = pulp.LpVariable('c', cat='Binary')
d = pulp.LpVariable('d', cat='Binary')
e = pulp.LpVariable('e', cat='Binary')

problem += 4*a + 5*b + 6*c + 8*d + 10*e

problem += 3*a + 4*b + 5*c + 7*d + 9*e <= 15

status = problem.solve()
print("Status", pulp.LpStatus[status])

print(problem)

print("Result")
print("a", a.value())
print("b", b.value())
print("c", c.value())
print("d", d.value())
print("e", e.value())
print(problem.objective.value())
C>python test2.py
Status Optimal
sample:
MAXIMIZE
4*a + 5*b + 6*c + 8*d + 10*e + 0
SUBJECT TO
_C1: 3 a + 4 b + 5 c + 7 d + 9 e <= 15

VARIABLES
0 <= a <= 1 Integer
0 <= b <= 1 Integer
0 <= c <= 1 Integer
0 <= d <= 1 Integer
0 <= e <= 1 Integer

Result
a 1.0
b 0.0
c 1.0
d 1.0
e 0.0
18.0
[問題2]

下表に示す品物をサイズ 10 のナップザックに入れるとき、金額が最大となる入れ方を求めてください。なお、同じ品物を何個入れてもかまいません。

品物金額サイズ
A64
B43
C11
リスト : 問題2の解法 (test3.py)

import pulp

problem = pulp.LpProblem('sample', pulp.LpMaximize)

a = pulp.LpVariable('a', cat='Integer', lowBound=0)
b = pulp.LpVariable('b', cat='Integer', lowBound=0)
c = pulp.LpVariable('c', cat='Integer', lowBound=0)

problem += 6*a + 4*b + c

problem += 4*a + 3*b + c <=10

status = problem.solve()
print("Status", pulp.LpStatus[status])

print(problem)

print("Result")
print("a", a.value())
print("b", b.value())
print("c", c.value())
print(problem.objective.value())
C>python test4.py
Status Optimal
sample:
MAXIMIZE
6*a + 4*b + 1*c + 0
SUBJECT TO
_C1: 4 a + 3 b + c <= 10

VARIABLES
0 <= a Integer
0 <= b Integer
0 <= c Integer

Result
a 2.0
b 0.0
c 2.0
14.0
[問題3]

下表に示す品物をサイズ W のナップザックに入れるとき、金額が最大となる入れ方を求めてください。なお、同じ品物を何個入れてもかまいません。

品物金額サイズ
A913
B1204
C61020
D93030
リスト : 問題3の解法 (test4.py)

import pulp

def solver(w):
    problem = pulp.LpProblem('sample', pulp.LpMaximize)

    a = pulp.LpVariable('a', cat='Integer', lowBound=0)
    b = pulp.LpVariable('b', cat='Integer', lowBound=0)
    c = pulp.LpVariable('c', cat='Integer', lowBound=0)
    d = pulp.LpVariable('d', cat='Integer', lowBound=0)

    problem += 91*a + 120*b + 610*c + 930*d
    problem += 3*a + 4*b + 20*c + 30*d <= w

    status = problem.solve()
    print("Status", pulp.LpStatus[status])
    print(problem)

    print("Result")
    print("a", a.value())
    print("b", b.value())
    print("c", c.value())
    print("d", d.value())
    print(problem.objective.value())
>>> import test4
>>> test4.solver(400)
Status Optimal
sample:
MAXIMIZE
91*a + 120*b + 610*c + 930*d + 0
SUBJECT TO
_C1: 3 a + 4 b + 20 c + 30 d <= 400

VARIABLES
0 <= a Integer
0 <= b Integer
0 <= c Integer
0 <= d Integer

Result
a 2.0
b 1.0
c 0.0
d 13.0
12392.0
>>> test4.solver(500)
Status Optimal
sample:
MAXIMIZE
91*a + 120*b + 610*c + 930*d + 0
SUBJECT TO
_C1: 3 a + 4 b + 20 c + 30 d <= 500

VARIABLES
0 <= a Integer
0 <= b Integer
0 <= c Integer
0 <= d Integer

Result
a 0.0
b 0.0
c 1.0
d 16.0
15490.0
>>> test4.solver(1000)
Status Optimal
sample:
MAXIMIZE
91*a + 120*b + 610*c + 930*d + 0
SUBJECT TO
_C1: 3 a + 4 b + 20 c + 30 d <= 1000

VARIABLES
0 <= a Integer
0 <= b Integer
0 <= c Integer
0 <= d Integer

Result
a 2.0
b 1.0
c 0.0
d 33.0
30992.0

どの問題も一瞬で解を求めることができました。SWI-Prolog のライブラリ clpfd を使って問題3を解く場合、サイズ w を増やすと少し時間がかかるようになりますが、PuLP ではあまり変わらないようです。興味のある方はいろいろ試してみてください。


6月2日

●線形計画法

「数理計画法 (Mathematical Programing)」 (または数理最適化) は、変数に関する不等式や等式で表される制約の条件下で、目的の関数を最小 (あるいは最大) にする変数の値を求める問題です。特に、制約条件と目的関数が線形方程式で表される「線形計画法 (liner programming)」 (線形最適化) の分野では、「単体法 (simplex method)」という高速な解法アルゴリズムがあって、非常に広範囲な分野で使用されています。

最近は線形計画法を解くソルバーがいろいろ開発されているので、それらを利用するのが簡単です。数理モデル (変数、制約条件、目的関数など) の記述には標準フォーマット (LP ファイルや MPS ファイルなど) があるようですが、それらを自分で書くのは大変なので、モデリング言語を使うのが一般的です。

たとえば、Python のモジュール PuLP を使うと、Python で変数や数式を記述することができます。PuLP には CBC という無料で利用できるソルバーが同梱されているので、PuLP をインストールするだけで線形計画法を解くことができます。PuLP は次のコマンドでインストールすることができます。

pip install pulp

それでは実際に PuLP を使って線形計画法を解いてみましょう。問題は 参考文献・URL 1 の線形計画法の例題をお借りしました。

目的関数:
    z = x + y + 1
制約条件:
    3*x + 5*y <= 15
    2*x + y >= 4
    x - y == 1
    x >= 0
    y >= 0

上記の条件で z の最小値を求めます。プログラムは次のようになります。

リスト : 線形計画法 (test1.py)

import pulp

problem = pulp.LpProblem('sample', pulp.LpMinimize)

x = pulp.LpVariable('x', lowBound = 0)
y = pulp.LpVariable('y', lowBound = 0)

problem += x + y + 1

problem += 3*x + 5*y <= 15
problem += 2*x + y >= 4
problem += x - y == 1

status = problem.solve()
print("Status", pulp.LpStatus[status])

print(problem)
print("Result")
print("x", x.value())
print("y", y.value())
print("z", problem.objective.value())

PuLP の使い方は 参考文献・URL 2, 3 をお読みくださいませ。

実行結果は次のようになります。

C>python test1.py
Status Optimal
sample:
MINIMIZE
1*x + 1*y + 1
SUBJECT TO
_C1: 3 x + 5 y <= 15

_C2: 2 x + y >= 4

_C3: x - y = 1

VARIABLES
x Continuous
y Continuous

Result
x 1.6666667
y 0.66666667
z 3.33333337

数式を入力するだけで、簡単に解を求めることができました。PuLP の変数はデフォルトで実数ですが、Integer (整数) や Binary (0 or 1) を指定することもできるようです。そこで、次回は PuLP を使って「ナップザック問題」を解いてみましょう。

-- 参考文献・URL --------
1. 奥村晴彦,『C言語による最新アルゴリズム事典』, 技術評論社, 1991
2. Optimization with PuLP, (本家ドキュメント, 英語)
3. PuLPによるモデル作成方法, (PyQ ドキュメント)

2019 年 4 月

4月7日

●Noto フォント

Noto フォントは Google によって開発されたオープンソースのフォントです。Linux ディストリビューションの 1 つである Ubuntu は、今まで日本語フォントに Takao フォントが用いられてきましたが、Ubuntu 18.04 からは Noto フォントになりました。Noto Sans CJK JP がゴシック体で、Noto Serif CJK JP が明朝体になります。

もちろん、Windows にインストールすることも可能です。そこで、実際にインストールして Python/Tkinter で表示してみました。プログラムと実行結果を示します。

リスト : 游ゴシックと Noto Sans CJK JP の表示

import tkinter as tk
import tkinter.font as font

root = tk.Tk()
str = 'Hello, world, こんにちは世界'

for x in ["Light", "Regular", "Medium", "Bold"]:
    tk.Label(root, text=str, font=('游ゴシック {}'.format(x), 20)).pack()

for x in ["Thin", "Light", "DemiLight", "Regular", "Medium", "Bold", "Black"]:
    tk.Label(root, text=str, font=('Noto Sans CJK JP {}'.format(x), 20)).pack()

root.mainloop()

上の 4 つが游ゴシックで、残りの 7 つが Noto フォントです。游ゴシックと Noto フォント、どちらも綺麗なフォントだと思います。M.Hiroi's Home Page のメインフォントとして、Noto フォントを使ってみるのも面白いかもしれません。なお、Noto フォントは Web フォントとして利用する方法もあるようです。Web フォントはよくわかっていないので、これから勉強しようと思っています。

●参考 URL

  1. Google Noto Fonts, (本家)
  2. Noto - Wikipedia
  3. Webフォント - Wikipedia

2019 年 3 月

3月3日

●M.Hiroi's Home Page は移転しました

昨日、M.Hiroi' Home Page の転送設定を行いました。http://www.geocities.jp/m_hiroi/ と http://www.geocities.co.jp/SiliconValley-Oakland/1680/ のアクセスは移転先 (http://www.nct9.ne.jp/m_hiroi/) に転送されます。なお、転送サービスの期限は 2019 年 9 月 30 日までです。よろしければブックマークの変更をお願いいたします。また、メールアドレスに変更はありません (アドレスは Profile をご覧ください)。何か不具合などありましたら、メールでご連絡いただけると助かります。

ジオシティーズ様には長い間大変お世話になりました。厚くお礼申しあげます。そして、ここまで長い間続けることができたのも M.Hiroi's Home Page に来てくださる皆様のおかげです。本当にありがとうございました。これからもがんばりますので、よろしくお願い申しあげます。


2019 年 2 月

2月17日

●M.Hiroi's Home Page の移転について

M.Hiroi's Home Page の移転先は こちら です。ジオシティーズでの更新は今月末で停止しようと思っています。来月になりましたら、ホームページの転送設定を行う予定です。移転先でも M.Hiroi's Home Page をよろしくお願い申し上げます。


2019 年 1 月

1月1日

あけましておめでとうございます

旧年中は大変お世話になりました
本年も M.Hiroi's Home Page をよろしくお願い申し上げます


Copyright (C) 2019 Makoto Hiroi
All rights reserved.

[ Home ]