2011年12月29日

【数学】順列出力関数の作成(2)〜tuple化でメモリー対策

 前稿では、再帰関数で定義した単純な順列出力関数を掲載させて頂いた。本稿では出来るだけ少ない修正で9要素9桁の順列迄しか出来なかった点を改善して試ようと思う。
 当方のPythonコーディングではデータ要素の配列を扱う方法としてはlistを多用することが多い。listオブジェクトなら、append(), remove(), sort(), reverse()等多彩なメソッドが使えてとても使い勝手が良いからである。しかし、今回の順列出力関数の様に大量のlistオブジェクトを含むリストを生成し返す関数の場合の様に実メモリー空間を越えてメモリー消費が膨大に増やしてしまう原因となってしまうことがある。それを小手先で回避するにはtuple化することが考えられる。tupleオブジェクトの場合、一切変更不可のオブジェクトの為使い勝手は悪いものの、その分シンプルな為、メモリー消費が抑えられる様だ。
 本稿のコードでは、オブジェクトの構造は別としても10要素10桁の全順列、3628800個×19バイト以上のデータ実体の収納が必要だが計算してもまだ20倍迄なら大丈夫そうである。そうであればlistで作成している順列の並びをtupleに変更することで僅かでも改善の可能性がある筈なので、その点を変更して試た次第だ。
 変更箇所は極めて少ないが変更後のコードは以下の通りだ。



#!/usr/bin/python2.6
# -*- coding: utf-8 -*-
U"""
順列リスト作成関数(試作2号)
※ 10要素10桁の順列迄なら実用になるが、11要素11桁では仮想メモリー領域を大量に使う為、実用にならない。
items: 順列要素のリスト
keta : 桁数(順列要素数以下である必要があります。)
kumis: 追記する先頭要素

"""

__author__ = "Mire in Japan"
__version__ = '0.0.2'
__copyright__ = 'Copyright (c) 2011-12-28 Mire'
__license__ = 'GPL'
__url__ = 'http://pythonlife.seesaa.net/article/243207369.html '

def junretsu(items=[1, 2, 3], keta=3, kumis=[]):
"""
順列リスト出力関数本体
items: 順列要素のリスト
keta : 桁数(順列要素数以下である必要があります。)
kumis: 追記する先頭要素
"""

history = u"""
0.0.1 2011-12-26 初版
0.0.1a 2011-12-28 コメント附記, clean up
0.0.2 2011-12-28 加工しないlistデータを全てtuple化
"""

from time import time, localtime
st = time() #処理開始時刻をstに代入
news = [] #新たな順列リストを空リストに初期化
if kumis==[]: #初回時は
for i in items: # 全itemsについて
news.append([i]) # 要素を一つずつ含むリストを追加して行く
else: #それ以外は
for kumi in kumis: # 生成済の上位桁数の全順列について
loop=items[:] # 全itemsをloopにコピーし
for item in kumi: # 配置済の全要素について
loop.remove(item) # loopから取り除いた上で
for i in loop: # 残りの未配置の全要素について
k = list(kumi[:]) # kに順列をlist化しコピーした上で ※
k.append(i) # そのリストkに要素を一つずつ追加後
news.append(tuple(k)) # 新たな順列リストにTupleで追加して行く ※
kumis = news #処理完了に付、生成済順列リストを新たな順列リストに置換

et = time() #処理終了時刻をetに代入
print '%2d:%15d [%12.3f sec]' % (keta #処理桁位置と
, len(news) #全生成順列の数に
, et - st) #処理時間をコンソール表示

if keta<=1: #既に再帰終了条件最終桁に達していたら
return kumis #全順列リストを返し再帰終了する
else: #未処理桁があるなら
return junretsu(items=items #同じitemsに対し、
, keta=keta-1 #桁数を一つ減らし
, kumis=kumis) #生成済の前桁迄の順列リストを指定して自関数に再帰


def format_str(n):
u"""
要素数分format文字列の生成
"""
spaces = ' '
return '[%s]' % (spaces.replace(' '
, '%s, '
, n).strip()[:-1])


#### コードの実行開始 ####
if __name__ == "__main__":
items = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'] #順列生成用要素をリスト指定し
keta = len(items) #全要素数を順列桁数として
junretsus = junretsu(items=items, keta=keta) #順列出力関数を実行し順列リストを取得
fmt_str = format_str(len(junretsus[0])) #要素数分format文字列の生成
for jun in junretsus: #全順列を一つずつコンソール出力
print fmt_str % jun # ※

 このコードでは、10要素10桁の処理用に変更させて頂いたが、想定通り、実メモリー不足で12時間かかっていたものがtuple化で4分以内に実行出来る様になった。実行結果は以下の通り。



[mire@localhost ~]$ python junretsu_pre3.py
10: 10 [ 0.000 sec]
9: 90 [ 0.000 sec]
8: 720 [ 0.001 sec]
7: 5040 [ 0.016 sec]
6: 30240 [ 0.130 sec]
5: 151200 [ 0.499 sec]
4: 604800 [ 2.413 sec]
3: 1814400 [ 14.951 sec]
2: 3628800 [ 63.240 sec]
1: 3628800 [ 120.585 sec]
[A, B, C, D, E, F, G, H, I, J]
[A, B, C, D, E, F, G, H, J, I]
[A, B, C, D, E, F, G, I, H, J]
[A, B, C, D, E, F, G, I, J, H]
[A, B, C, D, E, F, G, J, H, I]
[A, B, C, D, E, F, G, J, I, H]
[A, B, C, D, E, F, H, G, I, J]
[A, B, C, D, E, F, H, G, J, I]
[A, B, C, D, E, F, H, I, G, J]
[A, B, C, D, E, F, H, I, J, G]
[A, B, C, D, E, F, H, J, G, I]
[A, B, C, D, E, F, H, J, I, G]
[A, B, C, D, E, F, I, G, H, J]

<中略>

[J, I, H, G, F, E, B, D, C, A]
[J, I, H, G, F, E, C, A, B, D]
[J, I, H, G, F, E, C, A, D, B]
[J, I, H, G, F, E, C, B, A, D]
[J, I, H, G, F, E, C, B, D, A]
[J, I, H, G, F, E, C, D, A, B]
[J, I, H, G, F, E, C, D, B, A]
[J, I, H, G, F, E, D, A, B, C]
[J, I, H, G, F, E, D, A, C, B]
[J, I, H, G, F, E, D, B, A, C]
[J, I, H, G, F, E, D, B, C, A]
[J, I, H, G, F, E, D, C, A, B]
[J, I, H, G, F, E, D, C, B, A]
[mire@localhost ~]$
posted by Mire at 00:06 | Comment(0) | TrackBack(0) | Pythonプログラミング | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック
月額見放題1,000円開始キャンペーンバナー(画像ありver)
紺碧の艦隊 ルパン三世 GREAT CHASE クリックプロモーション
<< 2013年01月 >>
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    
カテゴリ
タグクラウド
ファン
利用中のオープンソース
最近のコメント
最近の記事
過去ログ
QRコード
レガシーなアプリはいかが?
Dell 法人のお客様ページ
  • 【法人様向け】デル、お得なキャンペーン情報
  • 法人のお客様向け ストレージソリューション
  • 法人のお客様向け ネットワークソリューション
  • 【SOHO法人様向け】デル・オンライン広告限定ページ
  • デル-個人のお客様ページ
  • 【個人のお客様向け】デル・オンライン広告限定ページ
  • オンライン広告限定キャンペーンページ
  • ソフトウェア&周辺機器 パソコン工房
    ツートップインターネットショップ(twotop.co.jp) マウスコンピューター/G-Tune
  • ×

    この広告は1年以上新しい記事の投稿がないブログに表示されております。