2012年01月03日

【数学】順列出力関数の作成(5)〜固定長複数順列のZIP化でメモリー対策

 前稿では複数の順列をtab区切り文字列でまとめてメモリー上に置くことで11要素11桁の全順列を生成する様に出来た。しかし、12要素12桁では正味の順列文字列だけで5,748,019,200バイト(12バイト×12!)も必要な為、当方のPCの様に実メモリー2G、SWAP 4Gというメモリー空間ではまともなやり方では物理的に処理出来る筈もない。本稿では、それを可能にするコードを提示させて頂く。
 対策方法は首記の通り、等幅の順列を区切り文字なしで固定長文字列で扱う仕様にした上でZIP圧縮をかけメモリー上の記録量を削減させることにある。結果として個別の記録文字列の生成には多少時間がかかるが、メモリーへの書込み負荷が減る分早く処理出来るし、12要素12桁の順列処理迄ならメモリー不足も解消した。次回は高速化を課題として取り組む予定である。



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

"""

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

def junretsu(items=[1, 2, 3], keta=3):
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) #要素を渡し、その全順列文字列のリストを取得
for _jun in junretsus: #その全順列文字列のリストから
# _juns = _jun.split('\t') # tab区切り順列文字列を取出しtab分割し
try:
_jn = decompress(_jun) # 圧縮済の筈の文字列の復元を試みる
except: # 失敗なら
_jn = _jun # そのままで
s = 0 # 順列文字列の先頭アドレスを0に初期化し
while len(_jn[s:])>=keta: # 文字列の残りが生成済順列長以上なら
jun = _jn[s:s+keta] # 先頭アドレスsで長さposの順列文字列を取得
s += keta # 次の処理の為、先頭アドレスを次に進めて置く
# 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
, 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区切りの文字列で保持する様に変更
0.0.5 2012-01-02 その文字列を固定長化&zip圧縮し保持する様に変更
"""

from time import time
from zlib import compress, decompress
fpo = open('log_09_%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: # 生成済の上位桁数の全順列について
#print '#_kumis=', _kumis
## _kumi = _kumis.split('\t') # tab区切り文字列をtab分割したリストを生成
n = 0 # 個数カウンタを0に初期化
# for kumi in _kumi: # その中身の順列を一つずつ取り出して
s = 0 # 順列文字列の先頭アドレスを0に初期化し
try:
_ks = decompress(_kumis) # 圧縮文字列の復元を試みる
except: # 処理に失敗したら
_ks = _kumis # そのままの文字列を宛てる
while len(_ks[s:])>=pos: # 文字列の残りが生成済順列長以上なら
kumi = list(_ks[s:s+pos]) # 先頭アドレスsで長さposの文字列をリスト化
#print 'kumi=', kumi
loop=items[:] # 全itemsをloopにコピーし
for item in kumi: # 配置済の全要素について
try:
loop.remove(item) # loopから取り除いた上で
except:
print item, loop, kumi
loop.remove(item) # loopから取り除いた上で

#print 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)) # 文字列で追加して、
compress(''.join(_news))) # 文字列で追加して、
_news=[] # _newsを初期化
n = 0 # 個数を0に初期化
fpo.write('%s\n' % (''.join(k)))
s += pos
count = len(news) * str_w + len(_news)
if not len(_news)==0: # _newsにnewsへの未追加分があるなら
# news.append('\t'.join(_news)) # newsにそれをtab区切り文字列にして追加
_str = ''.join(_news)
try:
str = compress(_str)
except:
str = _str
news.append(str) # 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', 'L'] #順列生成用要素をリスト指定し
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 # 順列をコンソール出力

今回のコードは総メモリー量を超える12要素12桁の全順列を生成することが目標だったので、それのみの結果を掲載させて頂いた。ご覧の通り最後迄メモリー制約に阻まれることなく処理が出来た。しかし、その所用時間は約4時間近くと最早実用レベルを完全に超えている。今後は処理速度対策に軸足を変えていくと共により大きな桁数の順列出力の方法を模索して行くことになる。



[mire@localhost ~]$ python junretsu_pre5d.py
12: 12 [ 0.000 sec]
11: 132 [ 0.001 sec]
10: 1320 [ 0.005 sec]
9: 11880 [ 0.061 sec]
8: 95040 [ 0.376 sec]
7: 665280 [ 2.838 sec]
6: 3991680 [ 18.728 sec]
5: 19958400 [ 105.531 sec]
4: 79833600 [ 460.835 sec]
3: 239500800 [ 1682.132 sec]
2: 479001600 [ 4382.655 sec]
1: 479001600 [ 7475.624 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]

<中略>

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

メールアドレス:

ホームページアドレス:

コメント:

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


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

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