新規ドキュメント


忘れていく脳のための備忘録
by w_l_s
プロフィールを見る
画像一覧

PythonでQueueを作ってみた

今、アルゴリズムの勉強をしている。
学生のころ、ほとんどやってこなかったせいで、今かなり苦しんでる。
やっぱり時間があるときやっとくべきだったなぁ…。

そんなわけで本を買ってきて勉強してるんだけど、中身はCで書かれている。
最近はPythonにあまり触ってこなかったし、せっかくなのでPythonでも書いてみることにした。

ちなみに本は「定本 Cプログラマのためのアルゴリズムとデータ構造」(著者: 近藤 嘉雪)です。

そのまんま書き写しただけだとつまらないので、ちょっと関数を追加してたりする。

/*************************************************************************/

# -*- coding: utf-8 -*-

class Queue:
def __init__(self, MAXQUEUESIZE = 100):
self.queue = []
self.MAXQUEUESIZE = MAXQUEUESIZE

# queueが空?
def isEmpty(self):
return (self.total() == 0)

# queueがいっぱい?
def isFull(self):
return (self.total() == self.MAXQUEUESIZE)

# 残りのqueue数
def remain(self):
return self.MAXQUEUESIZE - self.total()

# 今のqueue数
def total(self):
return len(self.queue)

# queueの初期化
def init(self, MAXQUEUESIZE = 100):
self.__init__(MAXQUEUESIZE)

# queueの中身を取得
def peekAll(self):
return self.queue[:]

# 次のpush()の値を取得
def peek(self):
stat = None
if not self.isEmpty():
stat = self.queue[0]
return stat

# queueに値を入れる
def enqueue(self, element):
state = False
if not self.isFull():
self.queue.append(element)
state = True
return state

# queueから値を取り出す
def dequeue(self):
state = None
if not self.isEmpty():
state = self.queue.pop(0)
return state


/*************************************************************************/

最初は本のとおりにリングバッファを使おうとしていた。
でも途中でpop()は削除して以降の要素を詰めることに気づく。
本のままじゃうまくいかなくなるわけだ。
Cの配列とは違うなぁ。

いまさら変数名が気に入らなくなってきた。
pointerよりcurrentIndexとかのほうがいい気がする。

2009/1/9修正
pointerなんていらなかったので消去。
peek()は今のリストのコピーを取れるように変更。
ほかいくつか関数を追加

2009/1/11修正
enqueue, dequeueだよね
[PR]
by w_l_s | 2009-01-09 01:52 | Python

人の記事にけちをつけてみる

メモ帳のところにリンクを張ってあるbokujuの日記さん。
そこで気になる日記を見つけた。

pythonでの文字の連結は、文字列よりリストを使おう!

なるほど、結果を見ると早い。
ただ、ひとつ気になることが。。。

リストにくっつけるだけじゃ連結してないんじゃないか?

気になったので調べてみたら、join関数でくっつけられるらしい。
>>> s = "こんばんわ" + "ひとふくろうです"
>>> print s
こんばんわひとふくろうです

リストだとこうなる。
>>> ls = ["こんばんわ"]
>>> ls.append("ひとふくろうです")
>>> print "".join(ls)
こんばんわひとふくろうです

おお、これで早い文字列連結が可能だ!

...ここでやめときゃよかったんだ。
なんで"じゃあ、リストの要素にリストやタプルがあったらどうなるんだろう"なんて考えるんだ。

結果は、例外が発生して終了する。
さらに、str型とunicode型が混在すると、今度はUnicodeDecodeErrorが発生。これは+を使った連結でも起きる。

どんな状況でも連結させたい。
リストの要素にリストやタプルがあっても一直線に連結させたい。
...需要があるかどうかは知らないけど。

そんなわけで、リストの中身を文字列にして返す関数を書いてみた。

##########################################################
def ListToStr(obj, encoding = 'utf-8'):
target = []
for item in obj:
if isinstance(item, unicode):
item.encode(encoding)
elif not isinstance(item, str):
if isinstance(item, int) or isinstance(item, float):
item = str(item)
else:
item = ListToStr(item)

target.append(item)

s = ''.join(target)
return s

##########################################################

要素にリストがあるとこけるなら、リストがなくなるまで要素をばらしてしまえばいい。
乱暴だけど、再帰で書けるので少し楽かも。

数値があってもstr型に変換するので連結できる。
虚数?そんなの知らんわ。
…虚数を入れると例外が起きます。
辞書を要素に入っていると、キーだけを連結します。
正直使いづらいです。

早さはどうなんだろ…。
いまさらだけど、文字列の連結にリスト使おうとする人が、要素にリスト突っ込んだりするもんなんだろうか…。
なんか午前中を無駄にした気になってきたぞ。
[PR]
by w_l_s | 2008-12-21 20:16 | Python

カテゴリ

全体
erlang
Python
c言語
作って遊ぼう
シェルスクリプト
OS
javascript
jQuery
反省
vim
未分類

お気に入りブログ

メモ帳

最新のトラックバック

ライフログ

検索

タグ

ファン

記事ランキング

ブログジャンル

画像一覧