リストの共通要素のアルゴリズム

Question

def common_list(a,b):
    c = []
    for i in a:
        for j in b:
            if i == j:
                c.insert(0,i)
    c.reverse()
    print(c)

として、リストa,bの共通要素を返すプログラムを組んだのですが、
for二回、if一回使っているので、計算量が多くかかってしまいます。
どのように改良したら、計算量を少しでも減らせますか？

Answer 1

順序が関係ないのなら

def common_set(list1, list2) -> set:
    return set(list1) & set(list2)

順序が関係あるのなら

def common_list(list1, list2) -> list:
    return [elem for elem in list1 if elem in list2]

Comments

[eme]

listの集合型を利用して、積集合でokなんですね！
ありがとうございます。
順序が関係ある方は、どのような操作を実行しているのですか？

[LouiS0616]

リスト内包表記を利用しています。
次のように書いているのと結果は同じですが、実行速度が速いです。

ret = []
for elem in list1:
....if elem in list2:
........ret.append(elem)

註：空白をドットで代替しています。

---
内包表記を使いこなすと何かと便利なので、少しずつ慣れていくと良いでしょう。

[eme]

そんな方法もあるのですね！ありがとうございました！

[eme]

順序が関係ないとして、
もし、list1,list2のそれぞれの長さをa,bとしたら、
計算量はmin(a,b)ですか？

[LouiS0616]

https://qiita.com/Hironsan/items/68161ee16b1c9d7b25fb#set
a & b の平均計算量は O(min(len(a), len(b))), 最悪計算量は O(len(a) * len(b)) だとか。

リストからセットを作る計算量はどうなるのかちょっとわからんです。O(1)でやってほしい感がありますが。

[eme]

そうですよねw
ありがとうございます