notebook.community

Edit and run

問題：去掉 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 [ ]:

Content source: Astrohackers-TW/IANCUPythonAdventure

Similar notebooks:

notebook.community | gallery | about