以SortedList為例詳解Python的defaultdict物件使用自定義型別的方法

寫在前面

最近寫周賽題, 逃不開的一種題型是設計資料結構, 也就是第三題, 做這種題需要的就是對語言中的容器以及常用排序查詢演演算法的掌握, 而我只熟悉了最基本的一些方法, 做起這些題來總是超時…

為了搞定這些題, 我決定學習一下大佬們的做法, 特別是優先佇列的方法維護有序容器以及有序列表等容器, 這些都在Python中封裝好了, 用起來很是方便, 但是採用defaultdict的時候, 其預設資料型別常常需要與題目給出的特定結構匹配, 這就需要定義一個新的資料型別, 下面我就以一種十分常用的結構SortedList為例, 設定自定義的資料型別(本例為將預設的升序列表變成降序列表).

其他的資料結構當然也可以根據下面列出的方法來改, 主要知識點就是函數與類的運用了

第一種方法: 封裝成函數

首先匯入需要的函數, 其中neg方法可以用lambda x: -x代替, 本質上是一樣的, 下面寫的程式碼這兩種均可.

from collections import defaultdict
from sortedcontainers import (SortedList as SL, SortedKeyList as SKL)
from operator import neg  # or `lambda x: -x`

然後我們來看第一種方法, 其實封裝成函數本質上就是將自定義物件作為函數返回值, 下面給出兩種實現, 其實不傳入引數也可以, 但是這樣的話下面的第15行就不能使用了, 只能通過add()來新增值, 還是有侷限的.

程式碼中的d2直接用一個新的lambda函數, 定義鍵, 就不需要考慮直接初始化失效的情況.

def reverseSL(x=None):
    return SL(iterable=x, key=lambda x: -x)

def reverseSL1_no_args():
    return SL(key=lambda x: -x)

d1 = defaultdict(reverseSL)
d2 = defaultdict(lambda: SL(key=neg))

data = [3, 2, 4, 1]
for i in data:
    d1[1].add(i)
    d2[1].add(i)
# 也可以直接加入排序列表
d1[2] = reverseSL([1, 2])
d2[2] = reverseSL([1, 2])
print(d1)
print(d2)

可以得到如下的結果:

defaultdict(<function reverseSL at 0x100a680d0>, {1: SortedKeyList([4, 3, 2, 1], key=<function reverseSL.<locals>.<lambda> at 0x100c659d0>), 2: SortedKeyList([2, 1], key=<function reverseSL.<locals>.<lambda> at 0x100caa550>)})
defaultdict(<function <lambda> at 0x100c65820>, {1: SortedKeyList([4, 3, 2, 1], key=<built-in function neg>), 2: SortedKeyList([2, 1], key=<function reverseSL.<locals>.<lambda> at 0x100cb9940>)})
[Finished in 214ms]

如果第15行改為:

d1[2] = reverseSL_no_args([1, 2])

就會提示:TypeError: reverseSL_no_args() takes 0 positional arguments but 1 was given, 但是add()方法不會有問題.

第二種方法: 類封裝

這種方法比較複雜, 並且有一個小坑, 這裡先看第一個類的程式碼.

我這裡實現了兩個類, 其中mySL1採用的是組合的物件導向設計方法, mySL2用的是繼承. 第一種程式碼比較多, 因為裡面新增了一個元件SortedList, 就需要重寫add().

class mySL1:
    def __init__(self, iterable=None):
        self.sl = SL(iterable=iterable, key=lambda x: -x)
    def add(self, item):
        self.sl.add(item)
    def get(self):
        return list(self.sl)
    def __repr__(self):
        return repr(self.sl)

其中的__repr__是可選的, 只是為了清楚地顯示已加入到defaultdict的資料情況. 不寫的話還得呼叫get()方法, 進行字典值(values)資料的輸出, 這裡為方便就直接轉換為List型別了, 如果不轉換, 沒辦法在類外通過list()進行轉換, 因為這樣得到的資料不是可迭代物件, 通過直接輸出值的型別, 可以得到<class '__main__.mySL1'>.

然後是第二個類, 繼承語法簡潔明瞭, 直接呼叫父類別的初始化方法, 但是這裡需要注意的是, 繼承SortedList類的程式碼這裡就不能用了, 因為如果還是使用SortedList, 在__init__中修改key就會提示斷言錯誤, assert key is None, 這個問題讓我比較困惑, 甚至覺得可能繼承的方法行不通^,(下面是模組的__new__方法的原始碼) 我知道了問題的所在.

    def __new__(cls, iterable=None, key=None):
        """Create new sorted list or sorted-key list instance.
        Optional `key`-function argument will return an instance of subtype
        :class:`SortedKeyList`.
        >>> sl = SortedList()
        >>> isinstance(sl, SortedList)
        True
        >>> sl = SortedList(key=lambda x: -x)
        >>> isinstance(sl, SortedList)
        True
        >>> isinstance(sl, SortedKeyList)
        True
        :param iterable: initial values (optional)
        :param key: function used to extract comparison key (optional)
        :return: sorted list or sorted-key list instance
        """
        # pylint: disable=unused-argument
        if key is None:
            return object.__new__(cls)
        else:
            if cls is SortedList:
                return object.__new__(SortedKeyList)
            else:
                raise TypeError('inherit SortedKeyList for key argument')

這裡模組的作者提供了一個SortedList的子類, 叫做SortedKeyList, 顧名思義, 就是提供了一種可以寫入key的類, 這時候繼承這個類就不會有問題了.

其實在上面的函數呼叫那塊, 就已經有所提示, 輸出結果中的型別, 就顯示是SortedKeyList, 這個型別就是修改了key(使得key is not None)之後得到的物件. 大家可以嘗試一下, 如果不修改key, 就還是SortedList.

class mySL2(SKL):
    """use SortedKeyList instead SortedList,
    because SortedList cannot init argument `key`,
    `assert key is None` in its `__init__`"""

    def __init__(self, iterable=None):
        super().__init__(iterable=iterable, key=neg)

最後是建立defaultdict, 以及資料的讀取:

d3 = defaultdict(mySL1)
d4 = defaultdict(mySL2)
for i in [19, 11, 12, 123]:
    d3['x'].add(i)
    d4['y'].add(i)
# 或者直接通過列表初始化
d3['z'] = mySL1([1, 2])
d4['w'] = mySL2([1, 2])
print(d3)
print(d4)
print(d3['x'].get(), d3['z'].get())
print(list(d4['y']), list(d4['w']))

可以得到下面的結果:

defaultdict(<class '__main__.mySL1'>, {'x': SortedKeyList([123, 19, 12, 11], key=<function mySL1.__init__.<locals>.<lambda> at 0x1008e40d0>), 'z': SortedKeyList([2, 1], key=<function mySL1.__init__.<locals>.<lambda> at 0x100bebd30>)})
defaultdict(<class '__main__.mySL2'>, {'y': mySL2([123, 19, 12, 11], key=<built-in function neg>), 'w': mySL2([2, 1], key=<built-in function neg>)})
[123, 19, 12, 11] [2, 1]
[123, 19, 12, 11] [2, 1]

可以看出, 第一種類的建立, 其實最後還是用到了SortedKeyList這個子類.

到此這篇關於以SortedList為例詳解Python的defaultdict物件使用自定義型別的方法的文章就介紹到這了,更多相關Python defaultdict內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！