@ゲー単走部

ローグライク雑記。変愚蛮怒、DCSSなど。

マージソート

部分リストのうまい取り方がわからん

merge :: [Int] -> [Int] -> [Int]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
    | x <= y    = x : merge xs (y:ys)
    | otherwise = y : merge (x:xs) ys

mergesort :: [Int] -> [Int]
mergesort [] = []
mergesort [n] = [n]
mergesort list = merge list1 list2
    where size_center = (length list) `div` 2
          leftlist  = [list !! index | index <- [0..size_center - 1]]
          rightlist = [list !! index | index <- [size_center..(length list) - 1]]
          list1 = mergesort leftlist
          list2 = mergesort rightlist

素数の列を返すプログラム、素数かどうか判定するプログラム

素数の列を返すプログラムを書いてみる。

def prime(n): # nまでの素数のリストを返す
    if n == 2:
        return [2]
    elif n > 2:
        array = [2] # 素数を集める
        for i in range(3, n + 1): # 3~nが素数かどうか
            for p in array:
                if i % p == 0: # 素数で割り切れたとき
                    break
            else:
                array.append(i)
        return array

2以上の整数nが素数であることの定義は、nが1とn以外のいずれの整数でも割り切れないことなので、
3以上の整数については、2~n-1の範囲で割れるか調べればよい。
のだが、それでは効率が悪い、実際は2~n-1の中の素数で割れるか調べるだけで十分。
素数以外の整数(合成数という)は素数の積に分解できるので、素数で割れないならその素数を素因数にもつ合成数でも割れない)

なので、素数を集めておくリストを作っておき、素数判定のたびにリストに追加していき、そのリストを用いて次の数の素数判定を行っている。
素数の列を返して欲しいプログラムなのでどうせこのリストは必要になり、この方法が効率がよい。

だが、単にある数nが素数かどうか判定したいだけのときに、まずn-1までの数が素数かどうか調べるこの方法がいいのかどうかは知らん。
というか、ちょっと考えただけでもめっちゃ効率悪そう。
「9999までの素数をすべて列挙せよ」ならともかく、「9999が素数かどうか判定せよ」なんていう本来一瞬で解き終わる問題が、この方法だと途方もない時間がかかりそうだ。

アルゴリズムの発想はあまり変えず、微妙に書き方を変えてみる。

def ismyprime(n): # nが素数かどうか判定する
    if n == 2:
        return True
    elif n > 2:
        # 「nが素数である」とは、「nがn未満の素数で割り切れない」
        array = filter(ismyprime, range(2, n))
        for p in array:
            if n % p == 0:
                return False
        else:
            return True
    else:
        return False

def myprime(n): # nまでの素数のリストを返す
    return list( filter(ismyprime, range(2, n + 1)) )

先ほどのプログラムでは2重ループでarrayにどんどん追加していったが、
ここでは再帰を用いて宣言的に書き換えた。

このプログラムでも動くが、代償として実行速度がお察し状態になった。
myprime(70)を試すと一瞬で動作が終わるprime(70)と比べて遅く感じられる。
myprime(100)は待ち切れないので強制終了させた。

インタプリタだから遅いとか元のアルゴリズムが非効率とかいうより、
酷い再帰の書き方で実行速度がお察しになったのだろう。

同じアルゴリズムHaskell版。

isprime :: Int -> Bool
isprime n
    | n <= 1     = False
    | n == 2     = True
    | otherwise  = foldr (\p acc -> if n `mod` p == 0 then False else acc) True (filter isprime [2..n - 1])

prime :: Int -> [Int]
prime n = filter isprime [2..n]

畳み込み関数を使うとコンパクトにまとまるが、慣れていないと読みにくい。しかも無駄な計算してる気がする。
原始的な再帰で書くとこうなる。

not_divisible :: Int -> [Int] -> Bool
not_divisible n [] = True
not_divisible n (x:xs)
    | n `mod` x == 0    =   False
    | otherwise         =   not_divisible n xs

isprime :: Int -> Bool
isprime n
    | n <= 1     = False
    | n == 2     = True
    | otherwise  = not_divisible n (filter isprime [2..n - 1])

部分適用とelem関数を上手く使うともっとわかりやすくなる。遅延評価の言語だから途中で無駄な計算は発生しないはず?

isprime2 :: Int -> Bool
isprime2 n
    | n <= 1 = False
    | n == 2 = True
    | otherwise  = not $ 0 `elem` (map (n `mod`) (filter isprime [2..n - 1]))

prime2 :: Int -> [Int]
prime2 n = filter isprime2 [2..n]

いずれのプログラムもprime 70くらいから遅い。これならfilter isprime [2..n - 1]とか使わずに[2..n - 1]をそのまま使っとけって感じだ。

というわけで、エラトステネスの篩ってどう実装すればいいんだっけとググる

正しくはこうらしい。

prime :: [Int] -> [Int]
prime [] = []
prime (x:xs) = x : prime [y | y <- xs, mod y x /= 0]

なるほど、頭いいな。これなら先の酷い再帰アルゴリズムと違って、一瞬で動作が終わる。
Pythonならこう。こちらもさっきの酷い再帰アルゴリズムと違って、一瞬で動作が終わる。

def myprime2(n):
    array = list(range(2, n + 1))

    def primes(array):
        if not array:
            return []
        else:
            return [array[0]] + primes([x for x in array if x % array[0] != 0])

    return primes(array)

再帰を使わずに書くとこうか。

def myprime3(n):
    array = list(range(2, n + 1))
    answer = []

    while array:
        answer.append(array[0])
        array = [x for x in array if x % array[0] != 0]

    return answer


効率のよいアルゴリズムってむずかしい


<補足>
2番目の再帰でなぜこんなに遅くなったか?

多分だが、isprime(n)を定義するのに、isprime(2)~isprime(n-1)を使っていて、・・・(ア)
isprime(n-1)を求めるにはisprime(2)~isprime(n-2)を使っていて、
isprime(n-2)を求めるにはisprime(2)~isprime(n-3)を使っていて・・・となっているのだが、
求めたisprime(i)を共用できていないからではないか?

アの各isprimeの下にisprimeのツリーが広がって、その下にまたツリーが広がって、と
おぞましいことになっている気がする。
計算結果を共有できてればいいのだが、できてないからとんでもない時間がかかっている、ということだろうか。

Iteratorパターン

イテレータイテレータってよく聞くけど、要するにこんな感じなんだろう。

class MyList:
    def __init__(self, mylist): # 引数mylistは通常のリストを想定
        self.mylist = mylist

    def getsize(self):
        return len(self.mylist)

    def __getitem__(self, index): # お遊び
        index2 = self.getsize() - 1 - index
        return self.mylist[index2]

    def myiter(self):
        return MyIterList(self)

    def __iter__(self):
        return MyIterList(self)

class MyIterList:
    def __init__(self, mylist): # 引数mylistはMyList型を想定
        self.mylist = mylist # 自フィールドがMyList型インスタンスを参照するようにする
        self.count = 0

    def hasNext(self):
        return self.count < self.mylist.getsize()

    def mynext(self):
        nextvalue = self.mylist[self.count]
        self.count += 1
        return nextvalue

    def __next__(self):
        if not self.hasNext():
            raise StopIteration()
        return self.mynext()


if __name__ == '__main__':
    test = MyList([1, 2, 3, 4, 5])
    for i in range(5):
        print(test[i])
    print('')

    print('myiter_test')
    itertest = test.myiter()
    while itertest.hasNext():
        print( itertest.mynext() )

    print('my__iter__test')
    for i in test:
        print(i)

Python3で引っかかるところ~print関数~

リスト内包表記の中にprint書けたりするの気持ち悪すぎでしょ。
純粋関数型言語でない以上、戻り値なしで副作用しかない関数も通常の関数として扱えるわけで、
その意味でprintを文としておくのは一貫性がないということで関数にしたんだろうけど。

>>>p = [print(n) for n in range(5)]
0
1
2
3
4
>>>p
[None, None, None, None, None]
>>>print(p)
[None, None, None, None, None]
>>>print( [print(n) for n in range(5)] )
0
1
2
3
4
[None, None, None, None, None]

p = [print(n) for n in range(5)] なのに、

  • print(p) と
  • print( [print(n) for n in range(5)] )

で挙動違うの気持ち悪すぎ。
何で?

<追記>
記事を投稿してから冷静に考え直してみれば、挙動違うの当たり前だった。
リスト内包表記の中にprint書けるのは気持ち悪いが・・・

  • p = [print(n) for n in range(5)]
    • print関数を5回適用して、[None, None, None, None, None]を変数pに代入する
  • print(p)
    • リストpを表示するだけ
  • print( [print(n) for n in range(5)] )
    • print関数を5回適用して、[None, None, None, None, None]を表示する


だから何もおかしいところはなかった。

p = [print(n) for n in range(5)] が、実質2つの副作用を持っているのに、1行にまとまっているのがわかりにくかった。
変数pにはただリストが代入されてるだけなんだよね、printの処理は代入されない。

Python3で引っかかるところ~リストとイテレータ~

mapやzipがリストではなくイテレータを返すようになったので、挙動がややこしい。

>>>a = [10, 20, 30]
>>>b = [1, 2, 3]
>>>z = zip(a, b)
>>>list(z)
[(10, 1), (20, 2), (30, 3)]
>>>list(z)
[]
>>>list(z)
[]

zip(a, b)がリストではなくイテレータオブジェクトであり、それにlist関数を適用している。
1回listを適用した時点でイテレータが終了するので、2回目以降listを適用しても戻り値は空。

>>>a = [10, 20, 30]
>>>b = [1, 2, 3]
>>>list(zip(a, b))
[(10, 1), (20, 2), (30, 3)]
>>>list(zip(a, b))
[(10, 1), (20, 2), (30, 3)]
>>>list(zip(a, b))
[(10, 1), (20, 2), (30, 3)]

この場合、毎回新しいイテレータオブジェクトzip(a, b)を生成しているので、戻り値は期待通り。

>>>a = [10, 20, 30]
>>>b = [1, 2, 3]
>>>z = list(zip(a, b))
>>>z
[(10, 1), (20, 2), (30, 3)]
>>>z
[(10, 1), (20, 2), (30, 3)]
>>>z
[(10, 1), (20, 2), (30, 3)]

この場合、イテレータzip(a, b)をlistに変換したものを変数zに保存しているので、zの値は変わらず、出力は期待通り。

>>>a = range(5)
>>>list(a)
[0, 1, 2, 3, 4]
>>>list(a)
[0, 1, 2, 3, 4]
>>>list(a)
[0, 1, 2, 3, 4]

はぁ?
Python3だとrange関数はリストではなくイテレータを返すはずなので、2回目以降のlist(a)は空になるんじゃないの?
何で?


<追記>
公式リファレンスを見たが、rangeは組み込み関数ではなく組み込み型、クラスだった模様。
それにイテレータオブジェクトというわけではないようだ。と思うしかない。xrangeと統合されてメモリ使用効率がよくなっただけ。
と考えないと↓の挙動との違いが説明できないし。

>>>a = iter([1, 3, 5])
>>>list(a)
[1, 3, 5]
>>>list(a)
[]
>>>list(a)
[]

Python 勉強 ~5桁の数字を漢数字に変換してみる~

つくってみた。5桁なのは、6桁以上だと規則性が変わってむずそうだから。
というか桁数なんて際限がないしとりあえず5桁で。

# 1-99999 の5桁の数字を漢数字に直す

def char_number(number):
    if not 1 <= number <= 99999:
        return "Error"

    answer = ""

    dict_number = { 1:'一', 2:'二', 3:'三', 4:'四', 5:'五', 6:'六', 7:'七', 8:'八', 9:'九', 0:'' }
    base_stlist = ['万', '千', '百', '十', '一']

    number_list = [int(n) for n in str(number)] # 各桁の数字をリストに
    stlist = [dict_number[i] for i in number_list] # 各桁の数字を漢数字に

    z = zip(stlist, base_stlist)
    for index, one_tuple in enumerate(z):
        st1, st2 = one_tuple

        if st1 == '': # 0の桁は飛ばす
            continue

        if index == 0:
            answer += st1 + st2
        elif 1 <= index <= 3:
            if st1 == '一': # 一百、一十とは言わない 一千は言うこともあるが、言わなくてもよい
                answer += st2
            else:
                answer += st1 + st2
        else: # 一の位
            answer += st1

    return answer

単方向連結リストの実装

あー疲れたー。
プログラミング・アルゴリズムの勉強がてら、連結リストを試しに実装してみたが、色々引っかかって数時間があっという間に飛んでいってしまった。
だがまあ、こうやって苦労してこそ理解も深まるというもの。決して無駄ではなかったと思いたい。

  • 言語選択の理由は特にないが、やっぱりスクリプト言語は余計な記述をしなくて済むので書くのも読むのも楽
    • とはいっても、型の情報くらいは書きたい気もする。動的型付け言語だと突然宣言されていない型も不明な怪しげな変数が出てくるので、読んでたり書いてたりするときにこれなんだよってなることはある気がする
  • 色々いわれる例のself, やっぱり(書くのが)面倒くさい。インスタンス変数を弄るときにselfを書くのはともかく、メソッドの第一引数にいちいちselfを書くのは気味が悪い。
    • 書き忘れでエラーが出るとムキーとなる
    • 書くのは面倒だがその分読みやすいのは確か
  • インスタンスを生成するときにnew演算子なりnewメソッドを使わないのが気持ち悪い。明示をよしとする言語でnew演算子がないのには、何か深い理由がありそうだが?
  • range関数も正直わかりにくいし好きじゃないなぁ
  • 最初addやdelete_lastメソッドは個別に実装していたが、insertやdeleteで流用できることに気づく。if A return B で Aが満たされないならNoneが返るのでこれでよいのだ。
  • こうして苦労しながらコードを書いてみると、連結リストがシーケンシャルアクセスであるということが身にしみて理解できる。
  • Pythonイテレータへの理解がまだあやふや。for文で呼び出したら、まず__iter__()を実行して、次にraise StopIteration()されるまで__next__()が実行されて順番に値が取り出される、ってことかな?
class MyList:
    def __init__(self, value = "Dummy"):
        self.value = value
        self.pointer = None
        self.size = 0 # list[0]="Dummy", list[1]~list[self.size]

    def getindex_cellobject(self, index): # index番目のセルオブジェクトを返す
        if index <= self.size:
            tmp = self
            for i in range(index):
                tmp = tmp.pointer
            return tmp

    def __getitem__(self, index): # index番目のセルオブジェクトに含まれる値をself[index]でアクセスできるようにする
        if index <= self.size:
            return self.getindex_cellobject(index).value

    def add(self, value): # リスト最後尾に追加
        return self.insert(self.size + 1, value)

    def delete_last(self): # 最後尾を削除
        return self.delete(self.size)

    def insert(self, index, value): # index番目に挿入
        if 1 <= index <= self.size + 1:
            leftcell  = self.getindex_cellobject(index - 1)
            rightcell = leftcell.pointer

            newcell = MyList(value)
            leftcell.pointer = newcell
            newcell.pointer = rightcell

            self.size += 1
        return self

    def delete(self, index): # index番目を削除
        if 1 <= index <= self.size:
            leftcell  = self.getindex_cellobject(index - 1)
            rightcell = leftcell.pointer.pointer
            leftcell.pointer = rightcell

            self.size -= 1
        return self

    def show(self, a, b): # list[a] ~ list[b]
        if 0 <= a <= b <= self.size:
            for i in range(a, b + 1):
                print(self[i])

    def showall(self):
        self.show(0, self.size)

    def addlist(self, anotherlist): # リストの結合
        if anotherlist.size > 0:
            lastcell = self.getindex_cellobject(self.size)
            lastcell.pointer = anotherlist.pointer
            self.size += anotherlist.size

    def __iter__(self):
        self.tmp = self
        return self

    def __next__(self):
        if self.tmp == None:
            raise StopIteration()
        result = self.tmp.value
        self.tmp = self.tmp.pointer
        return result


testList = MyList().add("aaa").add("bbb").add("ccc").insert(2, "2").delete_last().delete(1).add("LAST")
another = MyList().add(1).add(10).add(100)
testList.addlist(another)

for value in testList:
    print(value)

# 出力
# Dummy
# 2
# bbb
# LAST
# 1
# 10
# 100