カテゴリー別アーカイブ: Python

GitHubデビュー(但し使ったことないとは言ってない)

前回、せっかくPythonでSnowflake作ったので、一念発起してGitHubに晒してみた。
実はGitHubに自前のコードを公開するのは初めてだ。
ま、仕事で非公開のレポジトリはガンガン使ってるけどな。

とりあえずユーザー名とレポジトリ名を決めないとだが、ユーザー名はmitakadaiと無駄に主語を大きくしてやった。
レポジトリ名は元の名前がsnowflake(雪片)なんで、ice crystals(雪の結晶)にした。
英辞郎で snowflakes grown from ice crystals (氷の結晶が成長してできた雪片) なんて例文を見付けたからなのはここだけの秘密だ。

ということで、GitHubデビューのURLは
https://github.com/mitakadai/icecrystals
にござるよ。

ユニークID生成方法snowflakeをPythonで書いてみた

ユニークID生成方法としてはUUIDが有名だよね。
基本UUID(version4)で必要十分なんだけど、問題もあって

  1. 128bitもいらない、uint64で扱いたいのに
  2. 完全にランダムなのでソートする意味がない

なんてのがよく出る欠点。
1はまだ我慢しろとか上位or下位64bit使ってなんとかするとか逃げようもある。
しかし2、特に時系列でIDが増加していって欲しいなんてリクエストがあると途端に使えなくなる。
で、RDBMSのオートインクリメント機能使ったり、きちんとロック処理入れてカラムに現在のIDを保持、ID生成するたびにインクリメント、とかやることになる。
それで何が嫌なのって、処理数が増えるとID生成の箇所が間違いなくボトルネックと化す。
処理を軽くしようとmemcachedやredis使った所で単一点なのは変わらず、クラスタ化か? なんて話となり、結構ブルーなのである。
で、なんかUUIDくらいお手軽で、現実的なところでユニーク性が保証できて、おおよそ時系列に沿って値が増加するユニークID生成方が欲しい。
そう思い、google先生に教えを請いた所、snowflakeという生成方法があるそうだ。

snowflakeはTwitterが以前使っていたユニークID生成方法で、かつてはgithubで公開されていたそうだ。
いまでもその残骸は残っている。
https://github.com/twitter/snowflake
生成方法などはこのスライドがわかりやすい。
http://www.slideshare.net/moaikids/20130901-snowflake
簡単に言うと、3つの値からユニークIDを生成する。

  • 最上位bitは0
  • 次の41bitはunix time ミリ秒
  • 次の10bitはあらかじめユニークに割り振ったmachine id
  • 下位12bitは発行する度にインクリメントされていくシリアルナンバー

ぱっと見、必要なユニークID生成が1msで4096ID以下であればユニーク性は守られるであろう。
それで足りないなら、複数マシン/プロセスでmachine idをユニークに割り振って分散すればいい。
さらに、unix timeは通常のepoch(1970-01-01 00:00:00 UTC)ではなく、任意の時刻にセットすることで割り降れるID空間を広げる工夫も入っているようだ。
上位bitがunix timeなので、うまく時系列に並ぶ作りだ。(ミリ秒まで同じタイミングの場合は並ばないケースあり)
最上位bitが必ず0なのでsignedでも安心して使える。
なかなか良い設計に思える。さすがはTwitterだな。
とはいえ、いまは使っていないとのことなので、これでも追いつかなくなったのかID生成。
恐るべしTwitter。

といろいろだらだら書いてきたけど、本題はここから。
この便利なsnowflakeを書いてみたよ、Pythonで。

import time

class Snowflake:

    def __init__(self, machine_id, epoch=0, init_serial_no=0):
        self._machine_id = machine_id
        self._epoch = epoch
        self._serial_no = init_serial_no

    def generate(self):
        unique_id = (
            ((int(time.time() * 1000) - self._epoch) & 0x1ffffffffff) << 22 |
            (self._machine_id & 0x3ff) << 12 |
            (self._serial_no & 0xfff)
            )
        self._serial_no += 1
        return unique_id

def main():
    snowflake = Snowflake(0, epoch=int(time.time() * 1000))
    for i in xrange(100):
        print snowflake.generate()

main()

Snowflakeクラスの使い方など説明するまでもない簡単な作りだ。
実行してみた限り、ちゃんとユニークで連番になってると思う。
まあ、参考程度にどうぞ。
あ、スレッドセーフじゃないので注意ね。

62進数

Pythonで62進数を作ってみた。
なぜ62進数かって?
それは英数字全部合わせて62文字だから。
Base64とか+とか/とか入って嫌じゃないですかー。

さっそく書いてみた。

def _make_use_chars_base_62():
    return [str(i) for i in xrange(0, 10)] + \
           [chr(i) for i in xrange(ord('a'), ord('z')+1)] + \
           [chr(i) for i in xrange(ord('A'), ord('Z')+1)]

def encode_base_62(decimal):
    base_62_str = ''
    use_chars = _make_use_chars_base_62()
    while True:
        base_62_str = use_chars[decimal % 62] + base_62_str
        decimal -= decimal % 62
        decimal /= 62
        if decimal == 0:
            break
    return base_62_str

def decode_base_62(base_62_str):
    decimal = 0
    use_chars = _make_use_chars_base_62()
    for c in base_62_str:
        decimal *= 62
        decimal += use_chars.index(c)
    return decimal

もうちょっとキレイで速いコード書けそうだけど、まあいいや。時には妥協も必要さ。
encodeの方のループ抜ける所はdo-whileで書きたいけど、Pythonにはdo-whileないんだよね…

動かしてみよう。

>>> encode_base_62(0)
'0'
>>> encode_base_62(10)
'a'
>>> encode_base_62(36)
'A'
>>> encode_base_62(62)
'10'
>>> encode_base_62(124)
'20'
>>> encode_base_62(100000000)
'6LAze'
>>> decode_base_62('6LAze')
100000000
>>> decode_base_62('0')
0

なんとなく大丈夫そう。
本当はきっちりテストコード書くべきだけど、まあいいや。
62進数、というより英数字62文字で数値を表現したい場合は時々出てくるので、その時にきっちり検証しておこう。

Pythonでキューを作ってみる

プログラマたるもの、暇な時はアルゴリズムとデータ構造で時間を潰すべきと言えよう。
ということで、Pythonでキューを作ってみた。
プログラマたるもの、キューくらいサクッと書けないといけないね。

class OresamaQueue(object):
  def __init__(self):
    self._buffer = []

  def dequeue(self):
    if len(self._buffer) > 0:
      return self._buffer.pop()
    else:
      return None

  def enqueue(self, obj):
    self._buffer = [obj] + self._buffer

解説するとこもないくらい単純なキューの実装だ。
Pythonのリストにはリストの末尾を削除しつつその値を返してくれるpop()というステキメソッドがあるので、dequeueは楽勝で書けた。
enqueueもPythonではリスト同士を足し合わせると1つのリストに合体してくれるので、[obj]で受け取った値を配列にして既存の配列と足し算しちまえばいい。

テストをしよう。手動で。

>>> import OresamaQueue
>>> q = OresamaQueue()
>>> q.enqueue(1)
>>> q.enqueue(2)
>>> q.enqueue(3)
>>> q.dequeue()
1
>>> q.dequeue()
2
>>> q.dequeue()
3
>>> q.dequeue()
>>> q.dequeue() is None
True

うん、見事なまでの先入れ先出し、まごうことないキュー。

ま、Pythonには最初からQueueモジュールがあるので、そっち使えばいいんだけどね。

PythonでSHA-3を使おう

新しい一方向ハッシュ関数SHA-3をPythonで使いたくなったのでGoogle様にお伺いを立てるとpysha3を使えば良いとのお返事が。
そこでさっそくインストールしてみる。

$ pip install pysha3

CのSHA-3ライブラリのラッパーになってるようだ。
速度も期待できるかな。
さっそく使ってみる。

$ python
>>> import hashlib
>>> import sha3
>>> hashlib.sha3_256('Hello, world!').hexdigest()
'b6e16d27ac5ab427a7f68900ac5559ce272dc6c37c82b3e052246c82244c50e4'
>>> hashlib.sha3_512('Hello, world!').hexdigest()
'101f353a4727cc94ef81613bb38a807ebc888e2061baa4f845c84cd3c317f3430fda3dbeb44010844b35bccc8e190061d05b4d002c709615275a44e18e494f0c'

import sha3するとhashlibにパッチ当ててくれる。
monkey patchとかいうやつだ。
こいつのお陰でhashlibでSHA-2とかと同じ書き方でSHA-3が計算できるので便利。
ちょっとお行儀悪い気もするけど…