Non-unique


問題:去掉 list中不重複的數字

例如輸入 [ 1, 1, 2, 3, 3],2沒有重複出現,所以要去掉 2,回傳 [ 1, 1, 3, 3]

限制:只能用原生 python,numpy之類的東西不能用

解題想法:

  1. 找出 list中,會重複出現的元素。可以用 count()方法來解
  2. 開個空 list,把 1的結果存起來。可以用 append()方法
  3. 寫個 for迴圈,把所有元素都跑過一次

In [ ]:
def Non_unique(numlist):
    result=[]
    for n in numlist:
        n_replicate=numlist.count(n)
        if n_replicate >= 2:
            result.append(n)
    return result

上面的程式碼邏輯清楚,不過有點落落長... python有個典型的句型可以套用這樣的邏輯,句型如下:

  • [元素 for 元素 in list 條件]

條件通常是 if 敘述 所以剛剛那串落落長可以簡化為下面的 python code


In [ ]:
def comlist(numlist):
    return [num for num in numlist if numlist.count(num) > 1]

簡潔多了,而且邏輯輪廓也是相當清楚。這類句型稱為 comprehensive list

這樣的 pattern在 python和其他語言中還蠻常見,所以請多多利用。

接下來介紹一個叫 $\lambda$ 的東西。一般我們寫函式都是寫在主程式的外面,比方說

def 函式名():
    ....韓式內容....
    烤肉
    人蔘雞
    年糕
    return 帳單

主程式
    主程式內容
    call函式

不過人懶起來,規矩都不管了,有人就想說那可以把函式內嵌在主程式中嗎?

然後 $\lambda$就生出來了,這樣的函式又稱為 anonymous function有沒有很神秘,很駭客呢...

廢話不多說,先介紹用法:

變數 = lambda 參數: 運算內容

在這個例子裡,參數是輸入的 list,運算內容就 copy剛剛前面的 comprehensive list用法,寫好後如下:


In [ ]:
lambda_unique=lambda numlist:[num for num in numlist if numlist.count(num)>1]

有沒有看不懂呢?沒錯!看不懂就對了...

lambda 的優點就是讓程式碼簡潔,不過也增加維護的門檻,使用時機存乎一心。

不過熟悉 $\lambda$語法對日後想要入門 functional programming 也許有幫助,各位參酌使用

換個想法

好,以上從落落長變一行。但這只是招式的變化,心法 (邏輯) 是沒有變化的。 這個解題思路的優點就是簡單直白你懂的... 蠢,缺點是它必須要掃過 list中所有的元素最後才能吐出結果,這導致許多不必要的運算。所以,po文前真的要多想三秒鐘啊~~ 也許會有更好的解...

所以呢,我想了另一個解題思路,盡量減少重複運算的問題,思路如下:

  1. 抓出輸入 list中,所有的組成元素,比方說 [1,1,2,3]的組成元素是 [1,2,3],而 [5,4,5,5,2]的組成元素是 [2,4,5]。可以用 set()方法得到
  2. 寫個 for迴圈,迴圈次數 = 組成元素個數
  3. 每次迴圈中,使用 count()方法去找符合該次組成元素的數量
  4. 如果數量 = 1,用 remove()方法移除這個組成元素

因為迴圈數降低了,不再需要跑整個 list,整體的效能將會提升,特別是當 list很長的時候


In [ ]:
def better_unique(numlist):
    for n in list(set(numlist)):
        n_replicate=numlist.count(n)
        if n_replicate ==1:
            numlist.remove(n)
    return numlist

想是這麼想,但是不是真的有用呢?讓我們來試試看...

現在我們有三種 (笨) 方法:

  • Non_unique -- 簡單直白
  • comlist -- comprehensive list法
  • lambda_unique -- anonymous function法,使用 lambda

以及一個稍微聰明一點的方法:

  • better_unique

接下來我們可以用 %timeit 這個東西來檢查這四個函式的效能如何...


In [ ]:
#先隨便給個小 list
alist=[1, 1, 6, 7, 9, 2, 5, 4, 5, 2, 3]

In [ ]:
%timeit Non_unique(alist)

上面的訊息是說:

  1. 執行了 100000次, 記錄執行時間
  2. 執行了 100000次, 記錄執行時間
  3. 執行了 100000次, 記錄執行時間
  4. 把 1. 2. 3.最短的時間拿出來,除以 100000,就得到一次計算所花的時間為 3.64 $\mu$s timeit 依照執行時間的多寡自動分配,花時間的程式會執行少一點...

接著把其他的都做一做


In [ ]:
%timeit comlist(alist)

In [ ]:
%timeit lambda_unique(alist)

In [ ]:
%timeit better_unique(alist)

不論招式如何,笨方法的執行時間大約是 3.6~3.7 $\mu$s,而聰明法的執行時間則是 1.3~1.4 $\mu$s。

這告訴我們雖然招式不同,不過進到機器底層的計算是差不多的。用好的演算法對效能的提升很有幫助。

讓我們來看看當 list變很長的時候會怎樣


In [1]:
# 亂數產生一個值域在 1~100,一次產生 10個亂數,重複兩千次的 list,所以 list 長度是兩萬。
# 長度可以自己改... 迴圈別改太多 (> 2000) 不然測試跑會很久
import random
x=[]
n=2000
for i in range(n):
    y=random.sample(range(9*n),10+4)
    x.extend(y)

print(len(set(x))/len(x)) #單一值和重複值的比例大約一半一半


0.5046785714285714

In [ ]:
y=x
%timeit Non_unique(y)

In [ ]:
y=x
%timeit comlist(y)

In [ ]:
y=x
%timeit lambda_unique(y)

In [ ]:
y=x
%timeit better_unique(y)

果然,list一長,笨方法就 hold不住了,換個想法再試試看

不過要快,還要知道使用正確的工具,不然再怎麼神妙的劍法心法,威力還是比不上 新阿姆斯特朗旋風噴射阿姆斯特朗砲 的... 請看以下範例


In [2]:
# from Checkio "O(n) :-P" by "Veky"
# https://checkio.org/mission/non-unique-elements/publications/veky/python-3/on-p/?ordering=most_voted
from collections import Counter
def counter_unique(data):
    nonunique = Counter(data) - Counter(set(data))
    return [x for x in data if x in nonunique]

In [3]:
y=x
%timeit counter_unique(y)


100 loops, best of 3: 17 ms per loop

下面是 veky提供的另一解,基本上是做一個 tuple來放兩個 set,一個存看過的(seen),一個存不是唯一的 (nonunique)

但為什麼也可以這麼快我就不太懂,因為是 tuple?... Orz


In [4]:
# from Checkio "Two bins" by "Veky"
#https://checkio.org/mission/non-unique-elements/publications/veky/python-3/two-bins/?ordering=most_voted
def two_bins(sequence):
    bins = seen, nonunique = set(), set()  #指定 bins = (set(), set()), 第一個叫 seen, 第二個叫 nonunique
    for number in sequence:bins[number in seen].add(number) 
    return [number for number in sequence if number in nonunique]

In [5]:
y=x
%timeit two_bins(y)


100 loops, best of 3: 7 ms per loop

不像 veky那麼神,又想要加速的話,anaconda提供一個叫 numba的作弊器,在不改 code的情況下加速。用法也很簡單... 如下


In [ ]:
from numba import jit
@jit
def fast_Non_unique(numlist):
    result=[]
    for n in numlist:
        n_replicate=numlist.count(n)
        if n_replicate >= 2:
            result.append(n)
    return result

In [ ]:
y=x
%timeit fast_Non_unique(y)

In [ ]:
from numba import jit
@jit
def fast_better_unique(numlist):
    for n in list(set(numlist)):
        n_replicate=numlist.count(n)
        if n_replicate ==1:
            numlist.remove(n)
    return numlist

In [ ]:
y=x
%timeit fast_better_unique(y)

In [ ]: