2014/06/23

ライブラリ:collections.deque

collections の deque というクラスについてご紹介します。

from collections import deque

deque は、キュー・スタック的処理を効率的に行うためのクラスです。

通常のリストでも append pop insert などのキュー・スタック的処理は行えますが、キュー・スタック処理のためだけに設計されたものではないため効率的ではありません。一方この deque はキュー・スタック的処理を行うことを念頭に作られているため、先頭での処理、末尾での処理ともに O(1) のオーダーで高速に実行できるとのことです。

使い方は、そのままキュー・スタック的処理を行う形になります。

以下、基本的な使い方を見ていきます。


オブジェクトの生成 基本編

オブジェクトの生成は、リストの生成時に list を使うのと同じように deque 関数を使います。
from collections import deque

# インスタンス生成
# 何も渡されなければ空のキューを生成する
d1 = deque()


要素の追加

末尾や先頭への要素の追加は append や appendleft を使います。
# 末尾への要素の追加
d1.append(5)
d1.append(10)
print(d1)  # => deque([5, 10])

# 先頭への要素の追加
d1.appendleft("first")
print(d1)  # => deque(['first', 5, 10])


要素の取り出し

末尾や先頭からの要素の取り出しは pop や popleft を使います。
# 末尾の要素の取り出し
d1.pop()
print(d1)  # => deque(['first', 5])

# 先頭の要素の取り出し
d1.popleft()
print(d1)  # => deque([5])


複数要素の一括追加

複数の要素をまとめて追加する場合は extend や extendleft を使います。
# 末尾への複数要素の追加
d1.extend([11, 12, 13])  
print(d1)  # => deque([5, 11, 12, 13])

# 先頭への複数要素の追加 前から順番に追加されるので逆になる
d1.extendleft([-11, -12, -13])
print(d1)  # => deque([-13, -12, -11, 5, 11, 12, 13])


カウント

含まれる要素の数を数えたい場合には count を使います。
# 指定した要素がいくつ含まれているかのカウント
d1.extend([100] * 3)
print(d1.count(100))  # => 3


要素を値で指定しての削除

要素を指定して削除する場合には remove を使います。該当する値がない場合には ValueError があげられます。
# 指定した要素がいくつ含まれているかのカウント
d1.remove(100)  # => 成功した場合は戻り値 None


オブジェクトの生成 応用編

オブジェクト生成に使う deque にイテラブルな要素を渡すと、各要素を持ったキューができあがります。
# list と同じようにイテラブルなオブジェクトを渡すことが可能
d2 = deque("abcd")
print(d2)  #  => deque(['a', 'b', 'c', 'd'])

maxlen というオプション引数を渡すと、キューの最大長さを決めておくことが可能です。
# 最大長をあらかじめ決めておくことも可能
d3 = deque([], maxlen=5)
d3.extend([3] * 10)
d3.append(100)
print(d3)  # => deque([3, 3, 3, 3, 100], maxlen=5)

新たな要素が追加されたとき、長さが maxlen を越えるような場合は追加したのとは逆側の要素がところてん方式的に削除されます。


回転

中身を回転させたい(先頭から要素を取り出して末尾に回したい)場合には rotate を使います。
# 回転
d2 = deque("abcd")
d2.rotate(1)
print(d2)  # => deque(['d', 'a', 'b', 'c'])


通常のリストへの変換

通常のリストに戻したい場合には、そのまま list 関数に渡せばOKです。
# 通常のリストに戻す
d2_list = list(d2)
print(d2_list)  # => ['d', 'a', 'b', 'c']

ちなみに、文字列に戻したい場合も次のやり方で大丈夫かと思います。
# 通常の文字列に戻す
d2_string = "".join(list(d2))
print(d2_string)  # => dabc

deque オブジェクトも list と同じくイテラブルなオブジェクトなので、 for ループに渡して処理することなんかも可能です。


インストール

デフォルトで標準ライブラリに入っているため、インストールは不要です。


以上です。

ちなみに deque の呼び方は「デック」だそうです。名前の由来も「 deque = Double Ended QUEue 」の略だと公式ドキュメントには書かれています。


参考
collections.deque — Python公式ドキュメント

2014/06/16

Python Tips:あるオブジェクトが特定のクラスのインスタンスかチェックしたい

Pythonで、あるオブジェクトが特定のクラスのインスタンスかどうかをチェックする方法をご紹介します。

大きく分けて2つの方法があります。
type
isinstance


type

type 関数は、引数に渡されたオブジェクトのクラスを返す関数です。ですので、 type の戻り値とクラスの is 比較を行うことによってクラス・インスタンスの関係をチェックすることができます。
s = "hello"
print type(s) == str  # => True
# s は str のインスタンスなので True

i = 10
print type(i) == int  # => True
# i は int のインスタンスなので True

f = 7.77
print type(f) == float  # => True
# f は float のインスタンスなので True

もちろん、自作クラスの場合も組み込みの型と同じ形でチェックが可能です。
class MyClass(object):
    pass

m1 = MyClass()

print type(m1) == MyClass  # => True


isinstance

isinstance 関数は、引数をふたつ受け取り、ひとつめにオブジェクト、ふたつめにクラスを受け取ります。ひとつめに渡したオブジェクトがふたつめのクラスのインスタンスである場合は True を返します。
print isinstance("hello", str)  # => True

print isinstance([], list)  # => True

print isinstance({}, dict)  # => True

isinstance が type と異なるのは、クラスが継承元の場合にも True を返す点です。
class Parent(object):
    pass

class Child(Parent):
    pass

c1 = Child()
print isinstance(c1, Parent)  # => True
# 継承元のクラスでも True となる

print isinstance(c1, object)  # => True
# object も同様

また、 isinstance のふたつめの引数をタプルにすることによって、複数のクラスに対して一度にクラス・インスタンス関係を調べることなんかも可能です。
class A(object):
    pass

class B(object):
    pass

b1 = B()
print isinstance(b1, (A, B))  # => True
# b1 は A には属さないがBには属するので True


参考
type() — Python公式ドキュメント
isinstance() — Python公式ドキュメント
Differences between isinstance() and type() in python - Stack Overflow

2014/06/10

Python Tips:自作クラスの演算子のふるまいを定義したい

Pythonで、自分で作ったクラスの演算子のふるまいを定義する方法をご紹介します。

Pythonでは、「特殊メソッド」(special methods/magic methods)と呼ばれるものを使って +-*/ << += などの各種演算子の挙動を定義することができます。

特殊メソッドというのは、「ふるまいは自分で定義できるけれど、その呼び出しタイミングなど使われ方はあらかじめ決められているメソッド」のこと。ことばでの説明を聞くとなんやらよくわかりませんが、具体例を見るとわかりやすいと思います。たとえば、インスタンスを生成したときに呼び出される __init__ メソッドなんかも特殊メソッドです。 __init__ の場合なんかは顕著に、「ふるまいは自分で決められるけれど、呼び出されるタイミングはあらかじめ決まっているメソッド」ですね。

以下、この特殊メソッドを使って演算子のふるまいを定義する方法を具体的に見ていきます。ここでは典型的なものとして次の4つを見ていきたいと思います。
  • __add__
  • __mul__
  • __lshift__
  • __iadd__


__add__

__add__ は + 演算子に対応した特殊メソッドです。 __add__ の中で定義した処理が + 演算子の処理となります。
class Array(object):
    def __init__(self, values):
        """インスタンス生成時に呼び出されるメソッド
           values には数字を格納したリストを渡す
        """
        self.values = values

    def __add__(self, other):
        """+ 演算子を定義するメソッド
           values 内の要素同士を足し合わせた新しい Array インスタンスを返す """
        return Array(list(map(lambda x, y: x + y,
                          self.values,
                          other.values)))

m1 = Array([3, 5])
m2 = Array([10, 11])

m3 = m1 + m2
print(m3.values)
# => [13, 16]
# __add__ メソッドで定義したとおりの結果となっている

このコードでは、 __add__ メソッドの中に values の要素同士を足し合わせて新たなインスタンスを生成する処理を書いています。 m3 の中身を見ると、 + の挙動が __add__ で定めたとおりになっていることが確認できます。


__mul__

__add__ を詳しく見たので、ここからは手短に行ければと思います。 __mul__ は * 演算子に対応したメソッドです。 multiply multiplication の略ですね。
class Array(object):
    # ここに __init__ などの定義
    # ...

    def __mul__(self, other):
        """* 演算子を定義するメソッド
           values 内の要素同士をかけ合わせた新しい Array インスタンスを返す """
        return Array(list(map(lambda x, y: x * y,
                          self.values,
                          other.values)))

m1 = Array([3, 5])
m2 = Array([10, 11])

m4 = m1 * m2
print(m4.values)
# => [30, 55]
# __mul__ メソッドで定義したとおりの結果となっている

こちらも __add__ と同様の結果が得られていることがわかります。


__lshift__

つづいて、 __lshift__ は << 演算子に対応したメソッドです。
class Array(object):
    # ここに __init__ などの定義
    # ...

    def __lshift__(self, new_element):
        """<< 演算子を定義するメソッド
           新しいオブジェクトは生成せず values の末尾に要素を append する(破壊的メソッド) """
        self.values.append(new_element)
        return self

m1 = Array([3, 5])

m1 << 10
print(m1.values)
# => [3, 5, 10]
# こちらも __lshift__ で定義したとおりの結果となっている
<< 演算子なんかも自分で定義することができます。<< を定義すると Ruby の配列みたいですね。


__iadd__

__iadd__ は += 演算子に対応したメソッドです。
class Array(object):
    # ここに __init__ などの定義
    # ...

    def __iadd__(self, element):
        """+= 演算子を定義するメソッド
           values の各要素に渡された値を加算する """
        self.values = list(map(lambda x: x + element, self.values))
        return self

m1 = Array([3, 5])

m1 += 1
print(m1.values)
# => [4, 6]
# こちらも __iadd__ で定義したとおりの結果
# オブジェクト id も不変
こちらも定義したとおりに動いてくれています。ちなみに、戻り値はレシーバ自身にしないと( return self としておかないと)うまく動いてくれません。

以上です。

ここであげたのはごくごく一部です。演算子の挙動を定義できる特殊メソッドは豊富に用意されているので、どういうメソッドがあるのかは一度公式ドキュメントリファレンスをご覧になってみてください。


参考
Python 2.6 Quick Reference
3.4. Special method names - Python公式ドキュメント
Special Method Names - Dive Into Python 3
演算子のオーバーロード - とりあえず