2011-06-07 59 views
2

我對Python相當陌生,希望在繼續前進之前能夠得到一些建議。我有一組整數,我想檢查一個給定的元素是否包含在該組中,儘可能快(速度在這裏很重要)。使用Python,我應該看看爲這些操作(BST等)定製的自定義數據結構,像使用any()包裝一樣的python欺騙,還是有任何這類標準的着名Python/C庫的東西。我不想在這裏重新發明輪子,所以我很有興趣聽到在Python中使用這種方法的常用方法。改進Python比較和存在操作

稍微有些背景,元素都是先插入組中,之後沒有任何元素出現,因此插入時間無關緊要。這似乎意味着維護一個已排序的組並進行類似二進制搜索的操作將是最好的方法,但我相信這已經實現得比我能夠實現的效率高得多,並且可以在Python/C庫中使用。有興趣聽到你們的想法。

謝謝!

+5

您是否需要存在?你的團隊有多大?如果設置/插入時間無關緊要,「x in a」其中x是一個整數,a是一個集合已經很快了。 – DSM 2011-06-07 14:26:26

回答

6

最Pythonic的方式是不將它們存儲在已排序的容器中,而是使用set(或不可變的變體frozenset)。這些是基於散列的容器,因此查找是O(1)。更重要的是,哈希算法是Python中的核心操作之一(用於字典和屬性查找),所以它用C編寫,並且寫成快速

這通常與Python的情況。使用標準容器比在Python級別上自己的滾動要快,所以儘可能使用它們。

如果您確實想將它們存儲在有序列表中,請查看標準庫中的bisect模塊。它具有二進制搜索的標準功能。 (呃,實際上並不是,我實際上會返回搜索到的項目的索引,你必須自己做最後的比較。)它可以在C中實現它們(取決於你的配置),所以它會比你自己寫的要快。

6

由於DMS在評論中說,有一個內置set(和不可變的變體,frozenset,這是非常有用的,你不需要進行變異,並可以將值的生成放入單個生成器表達式中) 。它是基於散列的,因此犧牲了分期O(1)成員資格測試的順序。它是用C語言編寫的,花費更多的時間比它可以合理花費的時間更快。如果內存是正確的,它是基於字典實現的,這個實現可以存在於固定散列表(通常用法)中。

請注意,「散列」部分也將爲O(1),因爲整數散列爲自己。這些算法適合於非常好地處理「非隨機」(例如有些連續的)哈希。