2011年12月31日

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

 前稿では、個別の順列をlistで生成したものをtuple化することで、メモリー不足から9要素9桁迄だったものを9要素9桁迄実用可能にすることでtuple型の利用の有用性を示すことが出来たのではないかと思う。list型はtuple()関数でtupleに、tuple型はlist()関数でlistにいつでも簡単に変換出来るので、編集不要なシーケンスについては初めからtuple型を利用し、編集が必要に成った段階でlist()関数で変換する様な癖付けが大切だということだ。
 さて、一般のシーケンスの扱いの結論としてはこういうことになる次第だが、順列出力という課題に対しては、出題の要素オブジェクト自体のシーケンスで毎回処理する必然性がないので、本稿では要素数と同じ数の文字に置換して個別の順列をその連続文字列で表現することで、tuple化よりメモリー効率の良いものに順列出力関数を改善して試ようと思う。
 技術的には、処理関数本体での前項でtuple()関数でtuple化していた箇所を文字列の標準メソッドjoin()を使い連続文字列化することと、処理関数に渡す前に各要素に対し1対1で対応する文字に置替えることの発想が出来るならは簡単にコーディング出来る筈である。
 例えば、['Alice', 'Ben', 'Charry']という要素に対する順列を処理する場合には、それ自体の文字列をつないで処理するのではなく、['0', '1', '2']といった1文字を要素とする順列のリストを作成し、「''.join(['2', '1', '0'])」とすることで文字列'210'を順列データとして生成して行くけば良いということである。
 具体的には次の様なコードとなった。



#!/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.3'
__copyright__ = 'Copyright (c) 2011-12-28 Mire'
__license__ = 'GPL'
__url__ = 'http://pythonlife.seesaa.net/article/243509569.html '

def junretsu(items=[1, 2, 3], keta=3):
u"""
permutation list creating function
順列リスト生成関数
 メモリー効率を高める為、順列生成時に各要素を文字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: #その全順列文字列のリストから順列文字列を取出し
data = []
for j in jun: #その文字列の1文字に対応する文字に対応する
data.append(items_dic[j]) #要素オブジェクトのリストを生成し
yield tuple(data) #メモリー不足を回避する為イテレータでタプル化して値を返す

def _junretsu(items=[1, 2, 3], keta=3, kumis=[]): #※順列リスト出力関数本体を内部関数に改名
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 順列を文字列として保持する様に変更
"""

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(''.join(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 = ''
for jun in junretsus: #全順列を一つずつコンソール出力
if fmt_str=='': # fmt_strが未生成なら、
fmt_str = format_str(len(jun)) # 要素数分format文字列の生成
print fmt_str % jun # 順列をコンソール出力

 残念ながら結果として、これでも11要素11桁の全順列の生成は出来なかった。しかし、メモリー消費が抑えられた影響だろうが処理速度が大幅にUPしたし、11要素11桁の全順列の生成でもtuple化では下4桁目で先に進まなかったものが、3桁目を108秒程度でクリアする迄改善出来た。念の為、生成順列をファイル書出しして確かめると上10桁目の8割程度でLinuxのSWAP領域が枯渇した為、OS側から強制終了させられたものと想定される。11要素11桁の全順列は10要素10桁の全順列の11倍以上のメモリー負荷が必要となるので取り敢えず、今回の手法によるメモリー消費改善による実現は諦めることにする。
 今後は現コードの処理方法の改善という非Pythonic的手法で処理可能桁数の改善に取組み、暫くはPython言語の限界を探って試ることにする。まぁ、Pythonでのこの手の課題にはイテレータ型を使うのが正攻法だけど。
posted by Mire at 03:15 | 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年以上新しい記事の投稿がないブログに表示されております。