2012年01月07日

【数学】順列出力関数の作成(6)〜最終要素確定時処理で高速化

 前稿では、zlib.compress()による文字列圧縮を使うことで、そのままなら処理中に全メモリー空間を超過し (生成文字列12バイト×479001600+11桁迄の参照文字列11バイト×479001600の11,017,036,800バイトを超えるメモリーがreturn前に消費し)OUT OF MEMORY となることを回避したが、予告通りメモリー対策は一先ずこの程度で放置して本稿からは処理速度の改善をしていく。
 本稿での対策は極めてシンプルで限定的なものであるが前稿の12要素12桁順列生成に4時間も費やしていたものを100分程度で生成出来る様にした成果面はとても大きいと思う。実のところ、本稿の改善部分は早々と組み込んでいたのだが、メモリー対策の効果比較面で邪魔になったので、ここ迄省いたコードを示させて頂いた次第だ。
 発想は簡単で残り1桁の要素を埋める作業自体は、その一つ前にまとめて行なっても構わないだろうと言うもので、これにより、最後の479001600回分のループ処理を不要にしただけである。コードは以下の通りだが、同時にここ迄なるとコード自体がかなり混雑して来て本体部分が何処か判り辛くなって来たのでdebug用の画面出力とlogファイル出力を関数の引数次第でif文制御する様に記述し判り易くさせて頂いた。そのソースコードは以下の通りだ。



#!/usr/bin/python2.6
# -*- coding: utf-8 -*-
U"""
順列リスト作成関数(試作6号)
※ 10要素10桁の順列生成迄なら40秒程度、11要素11桁の順列生成でも8分程度と
かなり実用になるが、12要素12桁では状況により総メモリーが不足になりDISK SLEEP
状態に陥る可能性もある。その場合は引数str_wを大きくすることで回避可能である。
でも13要素13桁以上ではどう逆立ちしてもOS(Linux)側で強制終了してしまう筈だ。
items: 順列要素のリスト
keta : 桁数(順列要素数以下である必要があります。)

"""

__author__ = "Mire in Japan"
__version__ = '0.0.6'
__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, debug=0, log=''):
u"""
順列リスト出力関数
 メモリー効率を高める為、順列生成時に各要素を文字1文字に置換行ない、
順列出力処理関数に渡し、return値では逆に要素オブジェクトに変換して
行なう様にするだけの関数
"""
from zlib import decompress

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 #要素を渡し、その全順列文字列のリストを取得
, debug=debug) #
for _jun in junretsus: #その全順列文字列のリストから
try:
_jn = decompress(_jun) # 圧縮済の筈の文字列の復元を試みる
except: # 失敗なら
_jn = _jun # そのままで
s = 0 # 順列文字列の先頭アドレスを0に初期化し
while len(_jn[s:])>=keta: # 文字列の残りが生成済順列長以上なら
jun = _jn[s:s+keta] # 先頭アドレスsで長さposの順列文字列を取得
s += keta # 次処理の為、先頭Adressを次に進めて置く
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 #720
, kumis=[]
, pos=0
, debug=0
, log=''):
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区切りの文字列で保持する様に変更
0.0.5 2012-01-02 その文字列を固定長化&zip圧縮し保持する様に変更
0.0.6 2012-01-05 要素数と同じ桁数の順列出力の最終桁を一つ前にまとめて処理
"""

from time import time
from zlib import compress, decompress

#DEBUG用の変数確認用コンソール出力(始め)
if debug>=2:
#print kumis
if kumis==[]:
lst = []
else:
lst = [kumis[0], kumis[-1]]
#print lst
for _k in lst:
try:
k = decompress(_k)
except:
k = _k
s = n = 0
while len(k[s:])>=pos:
print k[s:s+pos],
s += pos
n += 1
if (pos+1)*n+pos>80:
print
n = 0
if not n==0:
print
print u'処理済順列文字列圧縮率%3.2lf%%\n' % (1.0*len(k)/len(_k)),
print 'param: keta=%d, str_w=%d, pos=%d' % (keta, str_w, pos)
#DEBUG用の変数確認用コンソール出力(終り)

if keta<1: #既に再帰終了条件最終桁に達したら
return kumis # 全順列リストを返し再帰終了する
else: #でなく未処理桁があるなら
if not log=='':
fpo = open('%s_%03d-%03d.txt' % (log, keta+pos, keta), 'w')
if ( keta==2 # 順列桁指定が2になり
and len(items)-pos==2): # 且つ、残り要素が2の時
if not log=='':
fpo1 = open('log6b_%03d-%03d.txt' % (keta+pos, keta-1), 'w')
k = ''
st = time() #処理開始時刻をstに代入
news = [] #新たな順列リストを空リストに初期化
if kumis==[]: #初回時は
for i in items: # 全itemsについて
news.append(i) # 要素を一つずつ含むリストを追加して行く
if not log=='':
fpo.write('%s\n' % (i)) # logファイルに生成順列を追記
count = len(news)
else: #それ以外は
_news = [] # 生成順列追加用リストの初期化
for _kumis in kumis: # 生成済の上位桁数の全順列について
n = 0 # 個数カウンタを0に初期化
s = 0 # 順列文字列の先頭アドレスを0に初期化し
try:
_ks = decompress(_kumis) # 圧縮文字列の復元を試みる
except: # 処理に失敗したら
_ks = _kumis # そのままの文字列を宛てる
while len(_ks[s:])>=pos: # 文字列の残りが生成済順列長以上なら
kumi = list(_ks[s:s+pos]) # 先頭アドレスsで長さposの文字列をリスト化

loop=items[:] # 全itemsをloopにコピーし
for item in kumi: # 配置済の全要素について
try:
loop.remove(item) # loopから取り除いた上で
except:
print item, loop, kumi
loop.remove(item) # loopから取り除いた上で

for i in loop: # 残りの未配置の全要素について
k = list(kumi[:]) # kに順列をlist化しコピーした上で
k.append(i) # そのリストkに要素を一つずつ追加後
if not log=='':
fpo.write('%s\n' % (''.join(k)))

#要素数と同桁数の順列出力の最終桁を1つ前にまとめて処理(要:再帰終了条件変更)
if ( keta==2 # 順列桁指定が2になり ※
and len(loop)==2): # 且つ、残り要素が2の時 ※
lp = loop[:] # 残り要素をコピーして ※
lp.remove(i) # 追加済要素を削除した ※
k.append(lp[0]) # 残りの要素を追加 ※

_news.append(
''.join(k)) # _newsリストに順列を登録
n += 1 # _newsリストに追加した個数カウント
if n>=str_w: # その個数がstr_w以上になったら
news.append( # 新たな順列リストに
compress(''.join(
_news))) # 圧縮した固定長文字列で追加して、
_news=[] # _newsを初期化
n = 0 # 個数を0に初期化

if ( keta==2 # 順列桁指定が2になり ※
and len(loop)==2): # 且つ、残り要素が2の時 ※
if not log=='':
fpo1.write('%s\n' % (''.join(k))) # 最終桁のlogファイルに順列追記 ※

s += pos
count = len(news) * str_w + len(_news)
if not len(_news)==0: # _newsにnewsへの未追加分があるなら
_str = ''.join(_news)
try:
str = compress(_str)
except:
str = _str
news.append(str) # newsにそれをtab区切り文字列にして追加

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

if debug>0: #デバック時なら
et = time() #処理終了時刻をetに代入
ft_str = u'%2d要素%2d桁 :x%2d= %15d [%12.3f sec]'
print ft_str % (len(items) #要素数
, pos+1 #処理桁数
, keta #処理桁位置と
, count #全生成順列の数に
, et - st) #処理時間をコンソール表示

if not log=='':
fpo.close()

if keta==2 and len(k)==keta+pos: #最終桁を早期処理済なら ※
if not log=='':
fpo1.close() # 最終桁のlogファイルを閉じる ※
keta -= 1 # その分処理桁を一つ先に進め ※
pos += 1 # 処理済桁数を増やして同期する ※
if debug>0: # デバック時なら ※
print '%2d要素%2d桁 :x%2d= %15d ' % ( len(items)
, pos+1
, keta # 処理桁位置と ※
, count) # 全生成順列の数を表示する ※


return _junretsu(items=items # 同じitemsに対し、
, keta=keta-1 # 桁数を一つ減らし
, kumis=kumis # 生成済の前桁迄の順列リストを指定して自関数に再帰
, pos=pos+1 # 現処理桁アドレスを指定
, debug=debug # 指定debugモード
, log=log) #

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', 'L'] #12 順列生成用要素をリスト指定し
# items = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'] #11 順列生成用要素をリスト指定し
# items = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'] #10 順列生成用要素をリスト指定し
# items = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'] # 9 順列生成用要素をリスト指定し
# items = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] # 8 順列生成用要素をリスト指定し
# items = ['A', 'B', 'C', 'D', 'E', 'F', 'G'] # 7 順列生成用要素をリスト指定し
# items = ['A', 'B', 'C', 'D'] # 4 順列生成用要素をリスト指定し
keta = len(items) #全要素数を順列桁数として
#keta = 3
log = 'log6b'
log = ''
junretsus = junretsu(items=items, keta=keta
, debug=1, log=log) #順列出力関数を実行し順列リストを取得
fmt_str = ''
for jun in junretsus: #全順列を一つずつコンソール出力
if fmt_str=='': # fmt_strが未生成なら、
fmt_str = format_str(len(jun)) # 要素数分format文字列の生成
print fmt_str % jun # 順列をコンソール出力
 このソースコードの実行結果は以下の通り。



[mire@localhost ~]$ python junretsu_pre6b.py
12要素 1桁 :x12= 12 [ 0.000 sec]
12要素 2桁 :x11= 132 [ 0.001 sec]
12要素 3桁 :x10= 1320 [ 0.003 sec]
12要素 4桁 :x 9= 11880 [ 0.033 sec]
12要素 5桁 :x 8= 95040 [ 0.272 sec]
12要素 6桁 :x 7= 665280 [ 2.100 sec]
12要素 7桁 :x 6= 3991680 [ 13.766 sec]
12要素 8桁 :x 5= 19958400 [ 77.831 sec]
12要素 9桁 :x 4= 79833600 [ 350.105 sec]
12要素10桁 :x 3= 239500800 [ 1299.264 sec]
12要素11桁 :x 2= 479001600 [ 4289.828 sec]
12要素12桁 :x 1= 479001600
[A, B, C, D, E, F, G, H, I, J, K, L]
[A, B, C, D, E, F, G, H, I, J, L, K]
[A, B, C, D, E, F, G, H, I, K, J, L]
[A, B, C, D, E, F, G, H, I, K, L, J]
[A, B, C, D, E, F, G, H, I, L, J, K]
[A, B, C, D, E, F, G, H, I, L, K, J]
[A, B, C, D, E, F, G, H, J, I, K, L]
[A, B, C, D, E, F, G, H, J, I, L, K]
[A, B, C, D, E, F, G, H, J, K, I, L]
[A, B, C, D, E, F, G, H, J, K, L, I]
[A, B, C, D, E, F, G, H, J, L, I, K]
[A, B, C, D, E, F, G, H, J, L, K, I]
[A, B, C, D, E, F, G, H, K, I, J, L]

<後略>
 11桁目の処理ループで残る1桁の要素も付加する仕様の為、11桁目ではその分のCPU付加は増えたものの、logファイル出力を引数log=''として渡すことで抑制した為、全般的に高速化出来た。前稿では4時間もかかっていたのでほぼ実用にはならないが、100分程度の今回のコードであれば使う機会もゼロではないだろう。
 この様に桁毎のルーフ処理をまとめて行なうことで処理時間は大きく改善出来るし、同時に前桁迄の順列文字列保持に費やすメモリー量も削減出来ることになる。コード自体はif文による分岐の為解読し辛くなるものの、この切り口もなかなか捨てたものではない。次回からはこの切り口での実用先ずは60分以内の処理を目指して行く予定だ。
 尚、後の比較の為、このコードによる11要素11桁と10要素10桁での実行結果も以下に掲載しておく。



[mire@localhost ~]$ python junretsu_pre6b.py
11要素 1桁 :x11= 11 [ 0.000 sec]
11要素 2桁 :x10= 110 [ 0.001 sec]
11要素 3桁 :x 9= 990 [ 0.003 sec]
11要素 4桁 :x 8= 7920 [ 0.021 sec]
11要素 5桁 :x 7= 55440 [ 0.168 sec]
11要素 6桁 :x 6= 332640 [ 1.130 sec]
11要素 7桁 :x 5= 1663200 [ 6.300 sec]
11要素 8桁 :x 4= 6652800 [ 29.738 sec]
11要素 9桁 :x 3= 19958400 [ 105.208 sec]
11要素10桁 :x 2= 39916800 [ 341.086 sec]
11要素11桁 :x 1= 39916800
[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]

<後略>



[mire@localhost ~]$ python junretsu_pre6b.py
10要素 1桁 :x10= 10 [ 0.000 sec]
10要素 2桁 :x 9= 90 [ 0.000 sec]
10要素 3桁 :x 8= 720 [ 0.002 sec]
10要素 4桁 :x 7= 5040 [ 0.014 sec]
10要素 5桁 :x 6= 30240 [ 0.095 sec]
10要素 6桁 :x 5= 151200 [ 0.545 sec]
10要素 7桁 :x 4= 604800 [ 2.606 sec]
10要素 8桁 :x 3= 1814400 [ 9.544 sec]
10要素 9桁 :x 2= 3628800 [ 30.099 sec]
10要素10桁 :x 1= 3628800
[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]
[A, B, C, D, E, F, I, G, J, H]
[A, B, C, D, E, F, I, H, G, J]
[A, B, C, D, E, F, I, H, J, G]
[A, B, C, D, E, F, I, J, G, H]
[A, B, C, D, E, F, I, J, H, G]
[A, B, C, D, E, F, J, G, H, I]

<後略>
posted by Mire at 14:39 | Comment(0) | TrackBack(0) | Pythonプログラミング | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

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


※画像の中の文字を半角で入力してください。
この記事へのトラックバックURL
http://blog.seesaa.jp/tb/244822918
※ブログオーナーが承認したトラックバックのみ表示されます。

この記事へのトラックバック
月額見放題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年以上新しい記事の投稿がないブログに表示されております。