pythonのlistとsetについて 計算量など

前回の記事からの派生です。

pythonのListでa in listと書くとO(n)かかってしまうとのこと。
これを解決するために、Listではなくsetを使うといいようです。

ただ、setってちょっと扱いが面倒だったりするイメージ
なので、setとlistでできること、変換をまとめました。

また、計算量については以下を参考：
TimeComplexity - Python Wiki

・List
特徴：要素の書き換え可能
list_a=[]
list_a.append(a) #O(1)
list_a.pop() #O(1)
list_a.pop(3) #O(n) 使用注意！
a in list_a #O(n)

・Set
特徴：要素の書き換え不可
set_a=set() # {}だけだとdict型になる
set_a.add(a) #O(1) 値重複時は無視される
set_a.remove(a) # O(n) 値を消せる
a in set_a #O(1)

・こんなこともできる
A = {1,2,3}
B = {3,4,5}

C = A | B # 和集合 {1,2,3,4,5}
C = A & B # 積集合 {3}
C = A - B # 差集合 {1,2}
C = A ^ B # 排他的論理和 {1,2,4,5}

・変換
set_b = set(list_a) # listをsetに変換
set_c = set(strings) # 文字列をsetで変換、文字要素を重複なしで抽出できる

list_b = list(set_a) # setをlistに変換
list_c = list(strings) # 文字列をlistで変換、文字要素を単独で切り出せる



・参考　tupleについて
要素の追加、削除、変更ができない
setと混同していたので念のため記載・・・