３種類の設計に挑戦

プログラムはその設計思想によりいろいろなタイプがある。今回その代表的な３つのタイプでプログラムを組んでみた。ひとつが手続き型、もう一つがオブジェクト指向、そしてもう一つが関数型である。他にもいろいろな言語があるが私が扱えそうなのはこれだけなので他は別の人に頑張ってもらう(誰
題材はナップザック問題。NP困難の代表的な問題であるがまあ詳しくはいつものごとく他に譲ります。

さて、まずは手続き型です。コンピュータのデータや演算をそのまま流した形の言語ですね。C++でC言語風に書いてみた。

struct Item
{
	int weight;
	int value;
};

int main()
{
	const int knapsackLimit = 20;
	Item items[] = {
		{ 10, 7 },
		{ 4, 2 },
		{ 5, 9 },
		{ 1, 4 },
		{ 7, 9 },
		{ 3, 7 },
		{ 6, 4 },
		{ 3, 5 },
	};
	const int itemSize = sizeof(items)/sizeof(items[0]);

	int maxValue = 0;
	unsigned int bestConbination;

	unsigned int conbinationSize = (1 << itemSize);
	for( unsigned int conbination = 0; conbination < conbinationSize; ++conbination ){
		int weightSum = 0;
		int valueSum = 0;
		for( int item = 0; item < itemSize; ++item ){
			if( ( (conbination >> item) & 1 ) != 0 ){
				weightSum += items[item].weight;
				valueSum += items[item].value;
			}
		}
		if( weightSum < knapsackLimit ){
			if( maxValue < valueSum ){
				maxValue = valueSum;
				bestConbination = conbination;
			}
		}
	}

	for( int item = 0; item < itemSize; ++item ){
		if( ( (bestConbination >> item) & 1 ) != 0 ){
			std::cout << item << ",";
		}
	}
	std::cout << std::endl;
	std::cout << "value sum : " << maxValue << std::endl;

	return 0;
}

ちと反則(？)してビット演算を使ったがまあ本質的には変わらないので。荷物が32個超えたら破綻します（＾＾；　再帰使えばもうちょっとスマートに書けると思うがそれはまた後で取っておきます（何

次にオブジェクト指向。規模が小さいのであまりメリットがないし寧ろ作りにくいのだがやってみました。クラス候補は「荷物」と「ナップザック」と「問題解決部分」かな？「荷物」は重さと価値を参照でき、「ナップザック」は荷物を入れたり出したり出来、重さに上限があり、中の価値の合計がわかる。まあざっとそんな設計でC++で書いてみた。

class Item
{
public:
	Item( int weight, int value, int number ):
	  m_weight(weight),m_value(value),m_number(number){}
	~Item(){}

	int GetWeight()const{ return m_weight; }
	int GetValue()const{ return m_value; }
	int GetNumber()const{ return m_number; }
private:
	const int m_weight;
	const int m_value;
	const int m_number;
};

class Knapsack
{
public:
	Knapsack():m_limit(0),m_weightSum(0),m_valueSum(0){}
	Knapsack( int limit ):m_limit(limit),m_weightSum(0),m_valueSum(0){}

	bool insertItem( Item* pItem ){
		if( m_weightSum + pItem->GetWeight() < m_limit ){
			m_weightSum += pItem->GetWeight();
			m_valueSum += pItem->GetValue();
			m_pItems.push_back( pItem );
			return true;
		}else{
			return false;
		}
	}
	void removeItem( Item* pItem ){
		std::deque< Item* >::iterator pFindItem =
			std::find( m_pItems.begin(), m_pItems.end(), pItem );
		if( pFindItem != m_pItems.end() ){
			m_weightSum -= (*pFindItem)->GetWeight();
			m_valueSum -= (*pFindItem)->GetValue();
			m_pItems.erase( pFindItem );
		}
	}
	int GetValueSum()const{ return m_valueSum; }

	size_t GetItemSize()const{ return m_pItems.size(); }
	const Item* GetItem( size_t i )const{ return m_pItems[i]; }

	Knapsack& operator=( const Knapsack& napsack ){
		m_limit = napsack.m_limit;
		m_pItems = napsack.m_pItems;
		m_weightSum = napsack.m_weightSum;
		m_valueSum = napsack.m_valueSum;
		return *this;
	}
private:
	int m_limit;
	std::deque< Item* > m_pItems;
	int m_weightSum;
	int m_valueSum;
};

class KnapsackProbrem
{
public:
	KnapsackProbrem():m_pNapsack(0),m_pResultNapsack(0){}
	virtual ~KnapsackProbrem(){
		if( m_pNapsack != 0 ){ delete m_pNapsack; }
		if( m_pResultNapsack != 0 ){ delete m_pResultNapsack; }
		for( std::deque< Item* >::iterator pItem = m_pItems.begin(); pItem != m_pItems.end(); ++pItem ){
			delete *pItem;
		}
	}

	void SetKnapsack( Knapsack* pNapsack ){ m_pNapsack = pNapsack; }
	void AddItemList( Item* pItem ){ m_pItems.push_back( pItem ); }

	int Execute(){
		m_pResultNapsack = new Knapsack();
		Next( 0 );
		return m_pResultNapsack->GetValueSum();
	}

	const Knapsack* GetResultKnapsack()const{ return m_pResultNapsack; }
protected:
	void Next( size_t item ){
		if( item < m_pItems.size() ){
			Next( item + 1 );
			if( m_pNapsack->insertItem( m_pItems[item] ) ){
				Next( item + 1 );
				m_pNapsack->removeItem( m_pItems[item] );
			}
		}else{
			if( m_pResultNapsack->GetValueSum() < m_pNapsack->GetValueSum() ){
				*m_pResultNapsack = *m_pNapsack;
			}
		}
	}
private:
	Knapsack* m_pNapsack;
	std::deque< Item* > m_pItems;

	Knapsack* m_pResultNapsack;
};

int main()
{
	KnapsackProbrem* pKnapsackProbrem = new KnapsackProbrem();

	pKnapsackProbrem->SetKnapsack( new Knapsack( 20 ) );
	pKnapsackProbrem->AddItemList( new Item( 10, 7, 0 ) );
	pKnapsackProbrem->AddItemList( new Item( 4, 2, 1 ) );
	pKnapsackProbrem->AddItemList( new Item( 5, 9, 2 ) );
	pKnapsackProbrem->AddItemList( new Item( 1, 4, 3 ) );
	pKnapsackProbrem->AddItemList( new Item( 7, 9, 4 ) );
	pKnapsackProbrem->AddItemList( new Item( 3, 7, 5 ) );
	pKnapsackProbrem->AddItemList( new Item( 6, 4, 6 ) );
	pKnapsackProbrem->AddItemList( new Item( 3, 5, 7 ) );

	const int maxValue = pKnapsackProbrem->Execute();
	const Knapsack* pResultNapsack = pKnapsackProbrem->GetResultKnapsack();

	for( size_t item = 0; item < pResultNapsack->GetItemSize(); ++item ){
		const Item* pItem = pResultNapsack->GetItem( item );
		std::cout << pItem->GetNumber() << ",";
	}
	std::cout << std::endl;
	std::cout << "value sum : " << maxValue << std::endl;

	delete pKnapsackProbrem;
}

書いてみてからC#あたりにすればよかったと思ってしまった。ライブラリなしだとC++でOOP組むのは結構めんどうだなやっぱり。ちなみにナップザックをコピーできたりとちょっとおかしな設計になっているので少々失敗orz

最後に関数型。言語としてhaskellを利用。ぶっちゃけ、関数型言語の設計思考って実はあんまり分かっていなかったり（＾＾；ていうか、動くプログラムを書くのが精一杯で設計まで頭が回りませんorz

itemlist = [(10,7),(4,2),(5,9),(1,4),(7,9),(3,7),(6,4),(3,5)]
weight = 20
main = print $ knapsack_probrem itemlist weight

knapsack_probrem :: (Integral a) => [(a,a)] -> a -> ( a, [(a,a)] )
knapsack_probrem ns w = knapsack_sub ns [] [] w

knapsack_sub :: (Integral a) => [(a,a)] -> [(a,a)] -> [(a,a)] -> a -> ( a, [(a,a)] )
knapsack_sub [] ms best w = knapsack_better ms best w
knapsack_sub (n:ns) ms best w =
    let better1 = knapsack_sub ns ms best w
        better2 = knapsack_sub ns (n:ms) (snd better1) w
    in better2

knapsack_better :: (Integral a) => [(a,a)] -> [(a,a)] -> a -> ( a, [(a,a)] )
knapsack_better l1 l2 w =
    let v1 = knapsack_value l1 w
        v2 = knapsack_value l2 w
    in if (fst v1) > (fst v2) then v1 else v2

knapsack_value :: (Integral a) => [(a,a)] -> a -> (a,[(a,a)])
knapsack_value ns w =
    let tuple_sum = knapsack_sum ns
    in if (fst tuple_sum) > w then (0,[]) else ((snd tuple_sum),ns)

knapsack_sum :: (Integral a) => [(a,a)] -> (a,a)
knapsack_sum = foldr tuple_sum (0,0)
    where tuple_sum (n1,m1) (n2,m2) = (n1+n2,m1+m2)

今回ひょっとしたら初めてletを使ったかもしれないけどなんだか関数型言語っぽくなくなるなぁ。手続き型みたいなプログラムになってしまった。まあ何をもって関数型言語っぽいプログラムかはよくわかっていないけど。

とりあえず、久々に真面目にプログラム書いてみた結果でした。オチ無し。