2012年01月08日

【数学】順列出力関数の作成(7)〜下桁の一括処理で高速化

 前稿では、全要素桁数の順列生成時のみの最適化で、大幅な高速化を実現した。今回は、それをさらに一歩進めて残り5桁でその後の全桁の追加をまとめて行なう様にして試た。結果として、メモリ限界の12要素12桁順列の出力でも36分程度で処理出来る様になり、ようやくこの関数も実用可能性が出て来た次第だ。
 発想は前稿のコードがketa==2の時の処理だったものを、さらにketa==5のときに、追加で後の4桁分の順列文字列の生成処理を一括で行なわせるだけではあるが、全順列生成で一番時間のかかる12全要素の桁数の順列で1時間を大きく切ることが出来たことで次稿以降で予定の実用化に向け大きく前進出来たと思っている。
 そんなソースコードは以下の通りだ。




#!/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.7'
__copyright__ = 'Copyright (c) 2011-12-28 Mire'
__license__ = 'GPL'
__url__ = 'http://pythonlife.seesaa.net/article/245023928.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
, log=log) #
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 要素数と同じ桁数の順列出力の最終桁を一つ前にまとめて処理
0.0.7 2012-01-09 要素数と同じ桁数の順列出力の下5桁を一括処理に
"""

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==5 # 順列桁指定が5になり
and len(items)-pos==5) # 且つ、残り要素が5の時
or ( keta==2 #または 順列桁指定が2になり
and len(items)-pos==2)): # 且つ、残り要素が2の時で
if not log=='': # logファイル指定があれば
fpo1 = open('log6b_%03d-%03d.txt' % ( #logファイルを開く
keta+pos, keta-1), 'w')
k = k5 = ''
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) # このエラーはnest指定を疑え

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

#要素数と同桁数の順列出力をまとめて処理(要:再帰終了条件変更)
if ( keta==5 # 順列桁指定が2になり ※
and len(loop)==5): # 且つ、残り要素が2の時 ※
#print '5',
lp = loop[:] # 残り要素をコピーして ※
lp.remove(i) # 追加済要素を削除した ※
#print lp, keta
js = (h+lp[0]+lp[1]+lp[2]+lp[3] #残る4要素の全並びを追加生成
, h+lp[0]+lp[1]+lp[3]+lp[2]
, h+lp[0]+lp[2]+lp[1]+lp[3]
, h+lp[0]+lp[2]+lp[3]+lp[1]
, h+lp[0]+lp[3]+lp[1]+lp[2]
, h+lp[0]+lp[3]+lp[2]+lp[1]
, h+lp[1]+lp[0]+lp[2]+lp[3]
, h+lp[1]+lp[0]+lp[3]+lp[2]
, h+lp[1]+lp[2]+lp[0]+lp[3]
, h+lp[1]+lp[2]+lp[3]+lp[0]
, h+lp[1]+lp[3]+lp[0]+lp[2]
, h+lp[1]+lp[3]+lp[2]+lp[0]
, h+lp[2]+lp[0]+lp[1]+lp[3]
, h+lp[2]+lp[0]+lp[3]+lp[1]
, h+lp[2]+lp[1]+lp[0]+lp[3]
, h+lp[2]+lp[1]+lp[3]+lp[0]
, h+lp[2]+lp[3]+lp[0]+lp[1]
, h+lp[2]+lp[3]+lp[1]+lp[0]
, h+lp[3]+lp[0]+lp[1]+lp[2]
, h+lp[3]+lp[1]+lp[2]+lp[1]
, h+lp[3]+lp[1]+lp[0]+lp[2]
, h+lp[3]+lp[1]+lp[2]+lp[0]
, h+lp[3]+lp[2]+lp[0]+lp[1]
, h+lp[3]+lp[2]+lp[1]+lp[0])
for j in js: # その順列リストから一つずつ取り出して
k5 = j # k5に代入
jun5 = ''.join(k5) # その連結文字列を生成
_news.append(jun5) # _newsリストに順列を登録
n += 1 # 収納文字列内の順列数をカウント
if n>=str_w: # その個数がstr_w以上になったら
news.append( # 新たな順列リストに
compress(''.join(
_news))) # 圧縮した固定長文字列で追加して、
_news=[] # _newsを初期化
n = 0 # 個数を0に初期化

if not log=='': # logファイル指定があるなら
fpo1.write('%s\n' % (jun5)) # 改行区切りで順列を書出し

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


if ( keta==5 # 順列桁指定が5になり ※
and len(loop)==5): # 且つ、残り要素が5の時 ※
if not log=='':
fpo1.write('%s\n' % (h)) # 最終桁logファイルに順列追記 ※
else: # そうでないなら、
_news.append(h) # _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' % (h)) # 最終桁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 not log=='':
fpo.close()

if keta==5 and len(k5)==keta+pos:
if not log=='':
fpo1.close() # 最終桁のlogファイルを閉じる ※
keta -= 4 # その分処理桁を一つ先に進め ※
pos += 4 # 処理済桁数を増やして同期する ※
if debug>0: # デバック時なら ※
et = time() #処理終了時刻をetに代入
print '%2d要素%2d桁 :x%3d= %15d [%12.3f sec]' % ( len(items)
, pos+1
, 120 # 処理桁位置と ※
, count # 全生成順列の数を表示する ※
, et - st) #処理時間をコンソール表示
else:
if debug>0: #デバック時なら
et = time() #処理終了時刻をetに代入
ft_str = u'%2d要素%2d桁 :x%3d= %15d [%12.3f sec]'
print ft_str % (len(items) #要素数
, pos+1 #処理桁数
, len(items)-pos #処理桁位置と
, count #全生成順列の数に
, et - st) #処理時間をコンソール表示

if keta==2 and len(k)==keta+pos: #最終桁を早期処理済なら ※
if not log=='':
fpo1.close() # 最終桁のlogファイルを閉じる ※
keta -= 1 # その分処理桁を一つ先に進め ※
pos += 1 # 処理済桁数を増やして同期する ※
if debug>0: # デバック時なら ※
print '%2d要素%3d桁 :x%2d= %15d ' % ( len(items)
, pos+1
, len(items)-pos # 処理桁位置と ※
, 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', 'E', 'F'] # 6 順列生成用要素をリスト指定し
# items = ['A', 'B', 'C', 'D'] # 4 順列生成用要素をリスト指定し
keta = len(items) #全要素数を順列桁数として
#keta = 4
log = 'log7'
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 # 順列をコンソール出力
 尚、今回のコードでは、まとめ処理桁数を4桁分とした為に下4〜2桁の順列文字列の記録が出来ないし、以下の様に処理進行も下5桁が一括処理される為表示されない。その代わりに処理時間が半分になったことがご覧頂けると思う。ただ、9要素9桁以下ではいわゆる秒殺クラスの処理速度が実現出来たが、それ以上では、まだまだ待ち時間を感じてしまう点は解決できていない。そこで、次稿では、この順列出力関数に実用性を付加することでそのタイムラグ感の軽減に努める。



[mire@localhost ~]$ python junretsu_pre7c.py
12要素 1桁 :x 12= 12 [ 0.000 sec]
12要素 2桁 :x 11= 132 [ 0.000 sec]
12要素 3桁 :x 10= 1320 [ 0.003 sec]
12要素 4桁 :x 9= 11880 [ 0.038 sec]
12要素 5桁 :x 8= 95040 [ 0.275 sec]
12要素 6桁 :x 7= 665280 [ 2.144 sec]
12要素 7桁 :x 6= 3991680 [ 14.332 sec]
12要素12桁 :x120= 479001600 [ 2137.186 sec]
[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]
<後略>



[mire@localhost ~]$ python junretsu_pre7c.py
11要素 1桁 :x 11= 11 [ 0.000 sec]
11要素 2桁 :x 10= 110 [ 0.001 sec]
11要素 3桁 :x 9= 990 [ 0.003 sec]
11要素 4桁 :x 8= 7920 [ 0.029 sec]
11要素 5桁 :x 7= 55440 [ 0.181 sec]
11要素 6桁 :x 6= 332640 [ 1.169 sec]
11要素11桁 :x120= 39916800 [ 190.050 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]
<後略>



[mire@localhost ~]$ python junretsu_pre7c.py
10要素 1桁 :x 10= 10 [ 0.000 sec]
10要素 2桁 :x 9= 90 [ 0.001 sec]
10要素 3桁 :x 8= 720 [ 0.002 sec]
10要素 4桁 :x 7= 5040 [ 0.016 sec]
10要素 5桁 :x 6= 30240 [ 0.098 sec]
10要素10桁 :x120= 3628800 [ 17.488 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]
<後略>



[mire@localhost ~]$ python junretsu_pre7c.py
9要素 1桁 :x 9= 9 [ 0.000 sec]
9要素 2桁 :x 8= 72 [ 0.000 sec]
9要素 3桁 :x 7= 504 [ 0.002 sec]
9要素 4桁 :x 6= 3024 [ 0.009 sec]
9要素 9桁 :x120= 362880 [ 1.707 sec]
[A, B, C, D, E, F, G, H, I]
[A, B, C, D, E, F, G, I, H]
[A, B, C, D, E, F, H, G, I]
[A, B, C, D, E, F, H, I, G]
[A, B, C, D, E, F, I, G, H]
[A, B, C, D, E, F, I, H, G]
[A, B, C, D, E, G, F, H, I]
[A, B, C, D, E, G, F, I, H]
[A, B, C, D, E, G, H, F, I]
[A, B, C, D, E, G, H, I, F]
[A, B, C, D, E, G, I, F, H]
[A, B, C, D, E, G, I, H, F]
[A, B, C, D, E, H, F, G, I]
<後略>

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

メールアドレス:

ホームページアドレス:

コメント:

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


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

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