近況

ご無沙汰してます。
Javaおじさんです。

以前に書いたお仕事の話は残念ながら諸事情でぽしゃりました。
やー残念残念。
まあどっかに拾う神がいてくれればいいんだけどねー。

そしてちょっと最近白背景の黒文字が目につらくなってきたのは老眼進んできたのかしら。

でまあしばらく若干抜け殻っぽくなってましたが、例の「日本の技術者の90%はブログを書くな」たらいうクソはてなーのおかげでちょっと開き直りましたよ。
長々言及する気はないけど一言だけいえば、そんなもんまずお前のその駄文から消せやって話ですよ。
まあ、大体主語の大きいやつって自分も含まれてるの気がつかずに「技術者はブログ書くな」とか「人類滅べ」とか言っちゃうんだよな。
まず隗より始めよって言うじゃないの。自分から実践して見せなさいって。無理だと思うけど。

技術的近況

Djangoのアプリケーションを作って挫折したり、「Python言語によるプログラミングイントロダクション第2版」（以下、テキストと呼称）を読んで色々考えたりしてます。

Djangoの何に挫折したかといえば、要求された仕様がちょっと特殊で、たぶんMiddleware使わないと実現できない、もしくは使ってもうまくいかない感じだったのがすべての原因だったのかなー。
まあその辺、あとでまた別の記事にしてみよう。

テキストは12章のナップサック問題とグラフ最適化問題まで読み進んでいて、特にナップサック問題を読むうえでちょっと思うところがあるのでつらつら書いてみようと思います。

対象読者はおれです。つまりただの備忘録。

ナップサック問題とPython実装

そもそもナップサック問題とは何かというと「容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題」（Wikipedia）で、テキストではなんでか「空き巣がどの品物を選んで持っていくか」という話になっている。
空き巣てw

で、この時に「貪欲アルゴリズム」をベースとして最適解を求めていくことになるのだが、まずは貪欲アルゴリズムを使ったPython実装を見てみよう。基本テキストの写経だけど、ちょっとここはこう書かないとダメなんじゃないの的なことやら日本語で書いてあるところはほぼおれのオリジナルです。

item.py

"""貪欲アルゴリズムで使用するItemクラスとそれにまつわる関数の定義"""

class Item(object):
    """ナップサックに詰める対象の品物"""
    def __init__(self, n, v, w):
        """初期化。weightについては割り算の分母になるのと質量なので０以下の値は入れない"""
        self.__name = n
        self.__value = v
        if float(w) <= 0.0:
            raise ValueError(w)
        self.__weight = w

    def getName(self):
        """名前取得"""
        return self.__name

    def getWeight(self):
        """質量取得"""
        return self.__weight

    def getValue(self):
        """価値取得"""
        return self.__value

    def __str__(self):
        """文字列表現"""
        return '['+self.__name+'] weight = '+str(self.__weight)+', value = '+str(self.__value)

def value(item):
    """「価値の高いもの」を基準に取る場合"""
    return item.getValue()

def weightInverse(item):
    """「重量の軽いもの」を基準に取る場合"""
    return 1.0/item.getWeight()

def density(item):
    """「価値/重量比」を基準に取る場合"""
    return item.getValue()/item.getWeight()

greedy.py

"""貪欲アルゴリズム本体の実装"""

def greedy(items, maxWeight, keyFunction):
    """品物のリスト、ナップサックの最大容量、ソート用の基準を提供する関数を与えて貪欲アルゴリズムを実行するための関数"""
    copiedItems = sorted(items, key=keyFunction, reverse=True)
    result = []
    totalValue, totalWeight = 0.0, 0.0
    for item in copiedItems:
        if (totalWeight + item.getWeight()) <= maxWeight:
            result.append(item)
            totalWeight += item.getWeight()
            totalValue += item.getValue()
    return result, totalValue

test.py

"""貪欲アルゴリズムのテスト実行用モジュール"""
from item import Item, value, weightInverse, density
from greedy import greedy

def buildItems():
    """データ初期化"""
    names = ['時計', '絵画', 'ラジオ', '花瓶', '本', 'PC']
    values = [175, 90, 20, 50, 10, 200]
    weights = [10, 9, 4, 2, 1, 20]

    items = []
    for i in range(len(names)):
        items.append(Item(names[i], values[i], weights[i]))
    return items

def testGreedy(items, maxWeight, keyFunction):
    """各ソート基準を使ったアルゴリズム実行のテスト"""
    taken, val = greedy(items, maxWeight, keyFunction)
    print('取得した品物の総価値 : ', val)
    for item in taken:
        print(' ', item)

def testGreedys(maxWeight = 20):
    """テストのエントリポイント"""
    items = buildItems()
    print('価値を基準としたアルゴリズム実行の結果 ...')
    testGreedy(items, maxWeight, value)
    print('重量を基準としたアルゴリズム実行の結果 ...')
    testGreedy(items, maxWeight, weightInverse)
    print('価値/重量比を基準としたアルゴリズム実行の結果 ...')
    testGreedy(items, maxWeight, density)

testGreedys()

で、実行結果はこうなる。

価値を基準としたアルゴリズム実行の結果 ...
取得した品物の総価値 :  200.0
  [PC] weight = 20, value = 200
重量を基準としたアルゴリズム実行の結果 ...
取得した品物の総価値 :  170.0
  [本] weight = 1, value = 10
  [花瓶] weight = 2, value = 50
  [ラジオ] weight = 4, value = 20
  [絵画] weight = 9, value = 90
価値/重量比を基準としたアルゴリズム実行の結果 ...
取得した品物の総価値 :  255.0
  [花瓶] weight = 2, value = 50
  [時計] weight = 10, value = 175
  [本] weight = 1, value = 10
  [ラジオ] weight = 4, value = 20

ここでポイントになるのはモジュールgreedy.pyである。
greedy関数に与える第1引数は実はItemのリストでなくてもよい。
getWeightとgetValueという2つのメソッドの定義されているすべてのオブジェクトについて、この関数は有効に使用できる。
ちょっと試しに別のクラスを作って試してみる。

another.py

"""Itemではないクラスでもgreedy.pyが有効であることを検証するためのクラス"""
class Another(object):
    """中身はItemと基本同じ"""
    def __init__(self, n, v, w):
        """初期化。weightについては割り算の分母になるのと質量なので０以下の値は入れない"""
        self.__name = n
        self.__value = v
        if float(w) <= 0.0:
            raise ValueError(v)
        self.__weight = w

    def getName(self):
        """名前取得"""
        return self.__name

    def getWeight(self):
        """質量取得"""
        return self.__weight

    def getValue(self):
        """価値取得"""
        return self.__value

    def __str__(self):
        """文字列表現"""
        return '['+self.__name+'] weight = '+str(self.__weight)+', value = '+str(self.__value)

そしてtest.pyを以下のように書き直す。

test2.py

"""貪欲アルゴリズムのテスト実行用モジュール"""
from item import value, weightInverse, density
from greedy import greedy
from another import Another

def buildItems():
    """データ初期化"""
    names = ['時計', '絵画', 'ラジオ', '花瓶', '本', 'PC']
    values = [175, 90, 20, 50, 10, 200]
    weights = [10, 9, 4, 2, 1, 20]

    items = []
    for i in range(len(names)):
        items.append(Another(names[i], values[i], weights[i]))
    return items

def testGreedy(items, maxWeight, keyFunction):
    """各ソート基準を使ったアルゴリズム実行のテスト"""
    taken, val = greedy(items, maxWeight, keyFunction)
    print('取得した品物の総価値 : ', val)
    for item in taken:
        print(' ', item)

def testGreedys(maxWeight = 20):
    """テストのエントリポイント"""
    items = buildItems()
    print('価値を基準としたアルゴリズム実行の結果 ...')
    testGreedy(items, maxWeight, value)
    print('重量を基準としたアルゴリズム実行の結果 ...')
    testGreedy(items, maxWeight, weightInverse)
    print('価値/重量比を基準としたアルゴリズム実行の結果 ...')
    testGreedy(items, maxWeight, density)

testGreedys()

変更したのはimport文の修正と下記の1行だけ。

        items.append(Another(names[i], values[i], weights[i]))

Itemクラスの代わりにAnotherクラスを使っただけである。

これ、Javaの場合はinterfaceを切ってgetWeightおよびgetValueが存在することを確定しなければならないところなので、Pythonの方がより柔軟であると言える。
例えばこんな感じ。

HasWeightAndValue.java

public interface HasWeightAndValue {
    public float getValue();
    public float getWeight();
}

Item.java

/**
 * 貪欲アルゴリズムの品物に関するJava実装
 */
public class Item implements HasWeightAndValue{
    private String name;
    private int value;
    private float weight;

    /**
     * コンストラクタ。Immutable Objectにするのでここでしか値はセットされない。
     * @param name 名称
     * @param value 価値
     * @param weight 重さ
     */
    public Item(String name, int value, int weight) {
        this.name = name;
        this.value = value;
        this.weight = weight;
    }

    /**
     * 名称を取得する。
     * @return 名称
     */
    public String getName() {
        return this.name;
    }

    /**
     * 価値を取得する。
     * @return 価値
     */
    @Override
    public float getValue() {
        return (float)this.value;
    }

    /**
     * 質量を取得する。
     * @return 質量
     */
    @Override
    public float getWeight() {
        return (float)this.weight;
    }    
}

ただし、柔軟であることが必ずしも良いことばかりとは限らない。
Javaでinterfaceを切るのはクラスの構成として特定のメソッドが存在することを確約するためだが、これによってコンパイル時にコーディングミスを発見することが容易になるというメリットがある。
ところがPythonだと実際に動かしてみるまではこのあたりのチェックができない。
そうすると、コンパイラで文法やインターフェースがある程度チェックされるJavaよりも、Pythonの方がテストコードを書いて検証する有用性が高くなると言えるし、むしろテストコードのないPythonコードは一切信用してはいけないんじゃなかろうかとも思えてしまうがさすがにパラノイアっぽいだろうか。

さて、ここからナップサック問題における最適アルゴリズムについてみていくのだが、長くなったので次の記事に回そう。