重複なしリスト

Pythonで、RubyのArray#uniqみたいにリストから重複している要素を削除する方法ってないかなと思ったのでメモ。原理的にはこういうことだよね。

#!/usr/bin/python
#coding: utf-8
#for Python2.5

def uniq(ol):
  ul = list()
  s = set()
  for x in ol:
    if x not in s:
      ul.append(x)
      s.add(x)
  return ul

orig_list = [3,2,4,1,2,3,1,4,4,1,3,2]
set_list = list(set(orig_list))
uniq_list = uniq(orig_list)

print orig_list
print set_list
print uniq_list

以下実行結果。

[3, 2, 4, 1, 2, 3, 1, 4, 4, 1, 3, 2]
[1, 2, 3, 4]
[3, 2, 4, 1]

いったんlistからsetにしてまた戻す方法だと重複はなくなるが、順番が保持されずにソートされたようになる。この方法だと"x not in s"の計算量がどれくらいかが気になるところ。