爲什麼python索引函數執行時間比我自己的線性搜索函數更快？

我正在做一個實驗，比較索引函數和我自己的線性搜索函數的執行時間。據我的理解，Python爲索引函數實現了一個線性搜索算法，所以執行時間應該大致相同，不是嗎？爲什麼python索引函數執行時間比我自己的線性搜索函數更快？

我自己的搜索功能，看起來像這樣

def linearSearch (x,numList,length):  
    n = 0 
    for i in range(length): 
      n = n + 1 
      if numList[i] == x: 
        return i, n 
    return -1, n

來源

2017-02-15 eukoloko

號你的搜索使用Python，Python的使用編譯的C代碼（如果你使用CPython的）。雖然時間*複雜性*將是相同的。 –

啊謝謝你的迴應。所以這兩個函數不能直接比較，因爲它們使用不同的語言？ – eukoloko

Python可能不會爲'index'使用Python實現;它可能使用了一些C代碼（或Jython實現的本地語言等）。 –

Python的list.index功能位於C的速度運行，而我看不出你的Python變種都不可能擊敗。

當然，這是假設你的Python安裝使用CPython的。

來源

2017-02-15 23:45:49

理解這一點非常重要的事情...... O(N)告訴你什麼都不約的操作將如何快速完成。僅僅因爲你的實現和Python的實現都O(N)，這並不意味着他們都會採取相同的時間量。

什麼O(N)告訴你的是，如果一個實現需要1秒來處理100個項目，這可能會花費大約2秒來處理200個項目。換句話說，O(N)告訴您如何在算法花費將規模作爲輸入的大小變化的時間。

在這種情況下，python的搜索會一直打你的搜索，因爲Python的搜索是在C（假設CPython的）與解釋非常小的開銷工作 - 而你的實現必須做大量的查找在「 python-space「（相比之下，這是相當昂貴的）。

一些具有良好JIT的Python實現（例如pypy）將能夠減少這種差異，但我懷疑你能否擊敗優化的內置函數的性能。

來源

2017-02-15 23:48:56 mgilson

的Python被寫在C這恰好是比Python快大約5倍。這意味着，它是用Python編寫的代碼比用C編寫索引（）方法大約慢5倍

來源

2017-02-15 23:50:21

爲什麼python索引函數執行時間比我自己的線性搜索函數更快？

回答

相關問題