python內置模塊collections介紹

目錄

python內置模塊collections介紹

collections是Python內建的一個集合模塊,提供了許多有用的集合類。

1、namedtuple

python提供了很多非常好用的基本類型,比如不可變類型tuple,我們可以輕鬆地用它來表示一個二元向量。

>>> v = (2,3) 

我們發現,雖然(2,3)表示出了一個向量的兩個坐標,但是,如果沒有額外說明,又很難直接看出這個元組是用來表示一個坐標的。

為此定義一個class又小題大做了,這時,namedtuple就派上用場了。

>>> from collections import namedtuple
>>> Vector = namedtuple('Vector', ['x', 'y'])
>>> v = Vector(2,3)
>>> v.x
2
>>> v.y
3

namedtuple是一個函數,它用來創建一個自定義的tuple對象,並且規定了tuple元素的個數,並可以用屬性而不是索引來引用tuple的某個元素。

這樣一來,我們用namedtuple可以很方便地定義一種數據類型,它具備tuple的不變性,又可以根據屬性來引用,使用十分方便。

我們可以驗證創建的Vector對象的類型。

>>> type(v)
<class '__main__.Vector'>

>>> isinstance(v, Vector)
True

>>> isinstance(v, tuple)
True 

類似的,如果要用坐標和半徑表示一個圓,也可以用namedtuple定義:

>>> Circle = namedtuple('Circle', ['x', 'y', 'r'])
# namedtuple('名稱', [‘屬性列表’])

2、deque

在數據結構中,我們知道隊列和堆棧是兩個非常重要的數據類型,一個先進先出,一個後進先出。在python中,使用list存儲數據時,按索引訪問元素很快,但是插入和刪除元素就很慢了,因為list是線性存儲,數據量大的時候,插入和刪除效率很低。

deque是為了高效實現插入和刪除操作的雙向鏈表結構,非常適合實現隊列和堆棧這樣的數據結構。

>>> from collections import deque
>>> deq = deque([1, 2, 3])
>>> deq.append(4)
>>> deq
deque([1, 2, 3, 4])
>>> deq.appendleft(5)
>>> deq
deque([5, 1, 2, 3, 4])
>>> deq.pop()
4
>>> deq.popleft()
5
>>> deq
deque([1, 2, 3])

deque除了實現list的append()和pop()外,還支持appendleft()和popleft(),這樣就可以非常高效地往頭部添加或刪除元素。

3、defaultdict

使用dict字典類型時,如果引用的key不存在,就會拋出KeyError。如果希望Key不存在時,返回一個默認值,就可以用defaultdict。

>>> from collections import defaultdict
>>> dd = defaultdict(lambda: 'defaultvalue')
>>> dd['key1'] = 'a'
>>> dd['key1']
'a'
>>> dd['key2'] # key2未定義,返回默認值
'defaultvalue'

注意默認值是調用函數返回的,而函數在創建defaultdict對象時傳入。

除了在Key不存在時返回默認值,defaultdict的其他行為跟dict是完全一樣的。

4、OrderedDict

使用dict時,key是無序的。在對dict做迭代時,我們無法確定key的順序。

但是如果想要保持key的順序,可以用OrderedDict。

>>> from collections import OrderedDict
>>> d = dict([('a', 1), ('b', 2), ('c', 3)])
>>> d # dict的Key是無序的
{'a': 1, 'c': 3, 'b': 2}
>>> od = OrderedDict([('a', 1), ('b', 2), ('c', 3)])
>>> od # OrderedDict的Key是有序的
OrderedDict([('a', 1), ('b', 2), ('c', 3)])

注意,OrderedDict的key會按照插入的順序排列,不是key本身排序

>>> od = OrderedDict()
>>> od['z'] = 1
>>> od['y'] = 2
>>> od['x'] = 3
>>> list(od.keys()) # 按照插入的Key的順序返回
['z', 'y', 'x']

OrderedDict可以實現一個FIFO(先進先出)的dict,當容量超出限制時,先刪除最早添加的key。

from collections import OrderedDict

class LastUpdatedOrderedDict(OrderedDict):

    def __init__(self, capacity):
        super(LastUpdatedOrderedDict, self).__init__()
        self._capacity = capacity

    def __setitem__(self, key, value):
        containsKey = 1 if key in self else 0
        if len(self) - containsKey >= self._capacity:
            last = self.popitem(last=False)
            print('remove:', last)
        if containsKey:
            del self[key]
            print('set:', (key, value))
        else:
            print('add:', (key, value))
        OrderedDict.__setitem__(self, key, value)

5、ChainMap

ChainMap可以把一組dict串起來並組成一個邏輯上的dict。ChainMap本身也是一個dict,但是查找的時候,會按照順序在內部的dict依次查找。

什麼時候使用ChainMap最合適?舉個例子:應用程序往往都需要傳入參數,參數可以通過命令行傳入,可以通過環境變量傳入,還可以有默認參數。我們可以用ChainMap實現參數的優先級查找,即先查命令行參數,如果沒有傳入,再查環境變量,如果沒有,就使用默認參數。

下面的代碼演示了如何查找user和color這兩個參數。

from collections import ChainMap
import os, argparse

# 構造缺省參數:
defaults = {
    'color': 'red',
    'user': 'guest'
}

# 構造命令行參數:
parser = argparse.ArgumentParser()
parser.add_argument('-u', '--user')
parser.add_argument('-c', '--color')
namespace = parser.parse_args()
command_line_args = { k: v for k, v in vars(namespace).items() if v }

# 組合成ChainMap:
combined = ChainMap(command_line_args, os.environ, defaults)

# 打印參數:
print('color=%s' % combined['color'])
print('user=%s' % combined['user'])

沒有任何參數時,打印出默認參數:

$ python3 use_chainmap.py 
color=red
user=guest

當傳入命令行參數時,優先使用命令行參數:

$ python3 use_chainmap.py -u bob
color=red
user=bob

同時傳入命令行參數和環境變量,命令行參數的優先級較高:

$ user=admin color=green python3 use_chainmap.py -u bob
color=green
user=bob

6、Counter

Counter是一個簡單的計數器,例如,統計字符出現的個數:

from collections import Counter
>>> s = 'abbcccdddd'
>>> Counter(s)
Counter({'d': 4, 'c': 3, 'b': 2, 'a': 1})

Counter實際上也是dict的一個子類。

7、小結

collections模塊提供了一些有用的集合類,可以根據需要選用。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※評比前十大台北網頁設計台北網站設計公司知名案例作品心得分享

※智慧手機時代的來臨,RWD網頁設計已成為網頁設計推薦首選

※評比南投搬家公司費用收費行情懶人包大公開

【從今天開始好好學數據結構01】數組

面試的時候,常常會問數組和鏈表的區別,很多人都回答說,“鏈表適合插入、刪除,時間複雜度O(1);數組適合查找,查找時間複雜度為O(1)”。實際上,這種表述是不準確的。數組是適合查找操作,但是查找的時間複雜度並不為O(1)。即便是排好序的數組,你用二分查找,時間複雜度也是O(logn)。所以,正確的表述應該是,數組支持隨機訪問,根據下標隨機訪問的時間複雜度為O(1)。

每一種編程語言中,基本都會有數組這種數據類型。不過,它不僅僅是一種編程語言中的數據類型,還是一種最基礎的數據結構。儘管數組看起來非常基礎、簡單,但是我估計很多人都並沒有理解這個基礎數據結構的精髓。在大部分編程語言中,數組都是從0開始編號的,但你是否下意識地想過,為什麼數組要從0開始編號,而不是從1開始呢? 從1開始不是更符合人類的思維習慣嗎?帶着這個問題來學習接下來的內容,帶着問題去學習往往效果會更好!!!

什麼是數組?我估計你心中已經有了答案。不過,我還是想用專業的話來給你做下解釋。數組(Array)是一種線性表數據結構。它用一組連續的內存空間,來存儲一組具有相同類型的數據。這個定義里有幾個關鍵詞,理解了這幾個關鍵詞,我想你就能徹底掌握數組的概念了。下面就從我的角度分別給你“點撥”一下。

第一是線性表(Linear List)。顧名思義,線性表就是數據排成像一條線一樣的結構。每個線性表上的數據最多只有前和后兩個方向。其實除了數組,鏈表、隊列、棧等也是線性表結構。而與它相對立的概念是非線性表,比如二叉樹、堆、圖等。之所以叫非線性,是因為,在非線性表中,數據之間並不是簡單的前後關係。

第二個是連續的內存空間和相同類型的數據。正是因為這兩個限制,它才有了一個堪稱“殺手鐧”的特性:“隨機訪問”。但有利就有弊,這兩個限制也讓數組的很多操作變得非常低效,比如要想在數組中刪除、插入一個數據,數組為了保持內存數據的連續性,會導致插入、刪除這兩個操作比較低效,相反的數組查詢則高效

數組java代碼:

package array;

/**
 * 1) 數組的插入、刪除、按照下標隨機訪問操作;
 * 2)數組中的數據是int類型的;
 *
 * Author: Zheng
 * modify: xing, Gsealy
 */
public class Array {
    //定義整型數據data保存數據
    public int data[];
    //定義數組長度
    private int n;
    //定義中實際個數
    private int count;

    //構造方法,定義數組大小
    public Array(int capacity){
        this.data = new int[capacity];
        this.n = capacity;
        this.count=0;//一開始一個數都沒有存所以為0
    }

    //根據索引,找到數據中的元素並返回
    public int find(int index){
        if (index<0 || index>=count) return -1;
        return data[index];
    }

    //插入元素:頭部插入,尾部插入
    public boolean insert(int index, int value){
        //數組中無元素 

        //if (index == count && count == 0) {
        //    data[index] = value;
        //    ++count;
        //    return true;
        //}

        // 數組空間已滿
        if (count == n) {
            System.out.println("沒有可插入的位置");
            return false;
        }
        // 如果count還沒滿,那麼就可以插入數據到數組中
        // 位置不合法
        if (index < 0||index > count ) {
            System.out.println("位置不合法");
            return false;
        }
        // 位置合法
        for( int i = count; i > index; --i){
            data[i] = data[i - 1];
        }
        data[index] = value;
        ++count;
        return true;
    }
    //根據索引,刪除數組中元素
    public boolean delete(int index){
        if (index<0 || index >=count) return false;
        //從刪除位置開始,將後面的元素向前移動一位
        for (int i=index+1; i<count; ++i){
            data[i-1] = data[i];
        }
        //刪除數組末尾元素  這段代碼不需要也可以
        /*int[] arr = new int[count-1];
        for (int i=0; i<count-1;i++){
            arr[i] = data[i];
        }
        this.data = arr;*/

        --count;
        return true;
    }
    public void printAll() {
        for (int i = 0; i < count; ++i) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Array array = new Array(5);
        array.printAll();
        array.insert(0, 3);
        array.insert(0, 4);
        array.insert(1, 5);
        array.insert(3, 9);
        array.insert(3, 10);
        //array.insert(3, 11);
        array.printAll();
    }
}

GenericArray數組代碼

public class GenericArray<T> {
    private T[] data;
    private int size;

    // 根據傳入容量,構造Array
    public GenericArray(int capacity) {
        data = (T[]) new Object[capacity];
        size = 0;
    }

    // 無參構造方法,默認數組容量為10
    public GenericArray() {
        this(10);
    }

    // 獲取數組容量
    public int getCapacity() {
        return data.length;
    }

    // 獲取當前元素個數
    public int count() {
        return size;
    }

    // 判斷數組是否為空
    public boolean isEmpty() {
        return size == 0;
    }

    // 修改 index 位置的元素
    public void set(int index, T e) {
        checkIndex(index);
        data[index] = e;
    }

    // 獲取對應 index 位置的元素
    public T get(int index) {
        checkIndex(index);
        return data[index];
    }

    // 查看數組是否包含元素e
    public boolean contains(T e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return true;
            }
        }
        return false;
    }

    // 獲取對應元素的下標, 未找到,返回 -1
    public int find(T e) {
        for ( int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }


    // 在 index 位置,插入元素e, 時間複雜度 O(m+n)
    public void add(int index, T e) {
        checkIndex(index);
        // 如果當前元素個數等於數組容量,則將數組擴容為原來的2倍
        if (size == data.length) {
            resize(2 * data.length);
        }

        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
    }

    // 向數組頭插入元素
    public void addFirst(T e) {
        add(0, e);
    }

    // 向數組尾插入元素
    public void addLast(T e) {
        add(size, e);
    }

    // 刪除 index 位置的元素,並返回
    public T remove(int index) {
        checkIndexForRemove(index);

        T ret = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size --;
        data[size] = null;

        // 縮容
        if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }

        return ret;
    }

    // 刪除第一個元素
    public T removeFirst() {
        return remove(0);
    }

    // 刪除末尾元素
    public T removeLast() {
        return remove(size - 1);
    }

    // 從數組中刪除指定元素
    public void removeElement(T e) {
        int index = find(e);
        if (index != -1) {
            remove(index);
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("Array size = %d, capacity = %d \n", size, data.length));
        builder.append('[');
        for (int i = 0; i < size; i++) {
            builder.append(data[i]);
            if (i != size - 1) {
                builder.append(", ");
            }
        }
        builder.append(']');
        return builder.toString();
    }


    // 擴容方法,時間複雜度 O(n)
    private void resize(int capacity) {
        T[] newData = (T[]) new Object[capacity];

        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    private void checkIndex(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed! Require index >=0 and index <= size.");
        }
    }

    private void checkIndexForRemove(int index) {
        if(index < 0 || index >= size) {
            throw new IllegalArgumentException("remove failed! Require index >=0 and index < size.");
        }
    }
}

到這裏,就回溯最初的問題:

從數組存儲的內存模型上來看,“下標”最確切的定義應該是“偏移(offset)”。前面也講到,如果用a來表示數組的首地址,a[0]就是偏移為0的位置,也就是首地址,a[k]就表示偏移k個type_size的位置,所以計算a[k]的內存地址只需要用這個公式:

a[k]_address = base_address + k * type_size

但是,如果數組從1開始計數,那我們計算數組元素a[k]的內存地址就會變為:

a[k]_address = base_address + (k-1)*type_size

對比兩個公式,我們不難發現,從1開始編號,每次隨機訪問數組元素都多了一次減法運算,對於CPU來說,就是多了一次減法指令。那你可以思考一下,類比一下,二維數組的內存尋址公式是怎樣的呢?有興趣的可以在評論區評論出來哦QAQ

數組作為非常基礎的數據結構,通過下標隨機訪問數組元素又是其非常基礎的編程操作,效率的優化就要盡可能做到極致。所以為了減少一次減法操作,數組選擇了從0開始編號,而不是從1開始。
不過我認為,上面解釋得再多其實都算不上壓倒性的證明,說數組起始編號非0開始不可。所以我覺得最主要的原因可能是歷史原因。

關於數組,它可以說是最基礎、最簡單的數據結構了。數組用一塊連續的內存空間,來存儲相同類型的一組數據,最大的特點就是支持隨機訪問,但插入、刪除操作也因此變得比較低效,平均情況時間複雜度為O(n)。在平時的業務開發中,我們可以直接使用編程語言提供的容器類,但是,如果是特別底層的開發,直接使用數組可能會更合適。

如果本文對你有一點點幫助,那麼請點個讚唄,謝謝~

最後,若有不足或者不正之處,歡迎指正批評,感激不盡!如果有疑問歡迎留言,絕對第一時間回復!

歡迎各位關注我的公眾號,一起探討技術,嚮往技術,追求技術,說好了來了就是盆友喔…

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!