2012年01月03日

【数学】順列出力関数の作成(4)〜TAB区切り複数順列でメモリー対策

 全稿迄のコードでは、1つの順列を1つのオブジェクトとしてメモリー上に置く仕組みの為、単純にlistオブジェクト、tupleオブジェクト、文字列オブジェクトの生成インスタンスのメモリー上の大きさの差だけ改善しただけのことである。その結果として中でも効率の良い文字列オブジェクトにしたところで11要素11桁順列の総文字数439,084,800バイトの文字列すらpythonでは処理出来ないとすると、いくらユーザ思考にとって素直なオブジェクトデータ型のみで構成した仕様が原因とあっては寂しい限りである。
 オブジェクト型のインスタンスを保持する場合、オブジェクトの型と記憶場所をデータ本体以外に必要となるので、数が増えれば増える程メモリー効率は悪くなってしまう。PythonにC言語にある様なブリミディブな配列やポインタは存在しないのでそこは工夫が必要になる。そこで前稿迄でPythonの型の中では文字列型がもっともメモリ効率が良かったことは確認出来た訳なので、今回は文字列オブジェクト1つに複数の順列を記録する仕様に変更して試た。
 尚、今回は判り易さを優先し複数の順列をtab文字でjoin()し記録、tab文字でsplit()し復元利用する仕様とした。そのコードと実行結果は以下の通りだが、これだけでは11要素11桁順列迄が限界だった。次稿ではそれをさらに改善する予定である。



#!/usr/bin/python2.6
# -*- coding: utf-8 -*-
U"""
順列リスト作成関数(試作3号)
※ 10要素10桁の順列生成迄なら1分程度と実用になるが、11要素11桁では総メモリーが
 不足になりOS(Linux)側で強制終了してしまうことがある。
items: 順列要素のリスト
keta : 桁数(順列要素数以下である必要があります。)

"""

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

def junretsu(items=[1, 2, 3], keta=3):
u"""
順列リスト出力関数
 メモリー効率を高める為、順列生成時に各要素を文字1文字に置換行ない、
順列出力処理関数に渡し、return値では逆に要素オブジェクトに変換して
行なう様にするだけの関数
"""
idx = [ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'
, 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T'
, 'U', 'V', 'W', 'X', 'Y', 'Z', '[', '\\', ']', '^'
, '_', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'
, 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's'
, 't', 'u', 'v', 'w', 'x', 'y', 'z', '{', '|', '}'
, '~'] #置換する文字のリスト(最大で71要素迄対応)
items_dic = dict(zip(idx[:len(items)], items)) #内部処理の文字に対する要素を現す辞書生成
junretsus = _junretsu(items=idx[:len(items)] #順列リスト出力関数(本体)にidxの文字を
, keta=keta) #要素を渡し、その全順列文字列のリストを取得
for _jun in junretsus: #その全順列文字列のリストから
_juns = _jun.split('\t') # tab区切り順列文字列を取出しtab分割し
for jun in _juns: # そこから順列データを取り出し
data = [] # 順列リストを初期化
for j in jun: # その文字列の1文字について対応する文字の
data.append(items_dic[j]) # 要素オブジェクトのリストを生成し
yield tuple(data) # タプル化してイテレータで値を返す
# (メモリー不足を回避する為イテレータ)

def _junretsu(items=[1, 2, 3] #※順列リスト出力関数本体を内部関数に改名
, keta=3
, str_w=1024*1024
, kumis=[]
, pos=0):
u"""
順列リスト出力関数(本体)
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化
0.0.3 2011-12-30 順列を文字列として保持する様に変更
0.0.4 2011-12-31 複数の順列をtab区切りの文字列で保持する様に変更
"""

from time import time, localtime
fpo = open('log_c_11_%03d.txt' % (keta), 'w')
st = time() #処理開始時刻をstに代入
news = [] #新たな順列リストを空リストに初期化
if kumis==[]: #初回時は
for i in items: # 全itemsについて
news.append(i) # 要素を一つずつ含むリストを追加して行く
count = len(news)
else: #それ以外は
_news = [] # 生成順列追加用リストの初期化
for _kumis in kumis: # 生成済の上位桁数の全順列について
_kumi = _kumis.split('\t') # tab区切り文字列をtab分割したリストを生成
n = 0 # 個数カウンタを0に初期化
for kumi in _kumi: # その中身の順列を一つずつ取り出して
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(
''.join(k)) # _newsリストに順列を登録
n += 1 # _newsリストに追加した個数カウント
if n>=str_w: # その個数がstr_w以上になったら
news.append( # 新たな順列リストにtab区切り
'\t'.join(_news)) # 文字列で追加して、
_news=[] # _newsを初期化
n = 0 # 個数を0に初期化
fpo.write('%s\n' % (''.join(k)))
count = len(news) * str_w + len(_news)
if not len(_news)==0: # _newsにnewsへの未追加分があるなら
news.append('\t'.join(_news)) # newsにそれをtab区切り文字列にして追加

kumis = news #処理完了に付、生成済順列を新たな順列リストに置換

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

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

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', 'K'] #順列生成用要素をリスト指定し
# items = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'] #順列生成用要素をリスト指定し
keta = len(items) #全要素数を順列桁数として
junretsus = junretsu(items=items, keta=keta) #順列出力関数を実行し順列リストを取得
fmt_str = ''
for jun in junretsus: #全順列を一つずつコンソール出力
if fmt_str=='': # fmt_strが未生成なら、
fmt_str = format_str(len(jun)) # 要素数分format文字列の生成
print fmt_str % jun # 順列をコンソール出力

10要素10桁の全順列の生成



[mire@localhost ~]$ python junretsu_pre5c.py
10: 10 [ 0.000 sec]
9: 90 [ 0.000 sec]
8: 720 [ 0.003 sec]
7: 5040 [ 0.024 sec]
6: 30240 [ 0.152 sec]
5: 151200 [ 0.826 sec]
4: 604800 [ 3.511 sec]
3: 1814400 [ 11.544 sec]
2: 3628800 [ 26.402 sec]
1: 3628800 [ 38.187 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 ~]$

11要素11桁の全順列の生成



[mire@localhost ~]$ python junretsu_pre5c.py
11: 11 [ 0.000 sec]
10: 110 [ 0.001 sec]
9: 990 [ 0.005 sec]
8: 7920 [ 0.038 sec]
7: 55440 [ 0.281 sec]
6: 332640 [ 1.725 sec]
5: 1663200 [ 9.155 sec]
4: 6652800 [ 40.250 sec]
3: 19958400 [ 131.794 sec]
2: 39916800 [ 320.692 sec]
1: 39916800 [ 446.043 sec]
[A, B, C, D, E, F, G, H, I, J, K]
[A, B, C, D, E, F, G, H, I, K, J]
[A, B, C, D, E, F, G, H, J, I, K]
[A, B, C, D, E, F, G, H, J, K, I]
[A, B, C, D, E, F, G, H, K, I, J]
[A, B, C, D, E, F, G, H, K, J, I]
[A, B, C, D, E, F, G, I, H, J, K]
[A, B, C, D, E, F, G, I, H, K, J]
[A, B, C, D, E, F, G, I, J, H, K]
[A, B, C, D, E, F, G, I, J, K, H]
[A, B, C, D, E, F, G, I, K, H, J]
[A, B, C, D, E, F, G, I, K, J, H]
[A, B, C, D, E, F, G, J, H, I, K]

<中略>

[K, J, I, H, G, F, E, B, D, C, A]
[K, J, I, H, G, F, E, C, A, B, D]
[K, J, I, H, G, F, E, C, A, D, B]
[K, J, I, H, G, F, E, C, B, A, D]
[K, J, I, H, G, F, E, C, B, D, A]
[K, J, I, H, G, F, E, C, D, A, B]
[K, J, I, H, G, F, E, C, D, B, A]
[K, J, I, H, G, F, E, D, A, B, C]
[K, J, I, H, G, F, E, D, A, C, B]
[K, J, I, H, G, F, E, D, B, A, C]
[K, J, I, H, G, F, E, D, B, C, A]
[K, J, I, H, G, F, E, D, C, A, B]
[K, J, I, H, G, F, E, D, C, B, A]
[mire@localhost ~]$

12要素12桁の全順列の生成ではOS側でOut of Memoryで強制終了されてしまう。



[mire@localhost ~]$ python junretsu_pre5c.py
12: 12 [ 0.000 sec]
11: 132 [ 0.001 sec]
10: 1319 [ 0.006 sec]
9: 11860 [ 0.074 sec]
8: 94788 [ 0.533 sec]
7: 662869 [ 3.743 sec]
6: 3973334 [ 23.408 sec]
5: 19847288 [ 127.696 sec]
4: 79311700 [ 548.993 sec]
強制終了
[mire@localhost ~]$
posted by Mire at 19:53 | 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年以上新しい記事の投稿がないブログに表示されております。