SortedList as an example of Python's defaultdict object using custom types in detail

write sth. upfront

Recently, I've been working on a weekly contest, and one of the questions I can't escape is designing data structures, which is the third question. To do this kind of question, you need to have a good grasp of containers in the language as well as commonly used sort-and-find algorithms, and I'm only familiar with some of the most basic methods, so I always have a timeout when working on these questions....

In order to get through these questions, I decided to learn what the big boys are doing, specifically the preferred queue approach to maintaining ordered containers as well as containers such as ordered lists, which are found in thePythonIt's very convenient to use it, but using thedefaultdictThe default datatype often needs to match the specific structure given by the topic, which requires the definition of a new datatype, and I'll take a very common structure as followsSortedListFor example, set a customized data type (in this case, change the default ascending list to descending).

Other data structures can of course be changed according to the methods listed below, the main point of knowledge is the use of functions and classes

First method: Wrapped in a function

First import the required functions, wherenegThe method can be used with thelambda x: -xInstead, it's essentially the same, and the code written below works both ways.

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

Then we look at the first method, in fact, encapsulated into a function is essentially a custom object as the return value of the function, the following two implementations are given, in fact, no parameters can be passed, but in this case the following paragraph15line is not available, it can only be accessed through theadd()to add values, there are limitations.

coded2It's straightforward to use a newlambdafunction, defining the key, there is no need to consider the case of direct initialization failure.

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)
# Can also be added directly to a sorted list
d1[2] = reverseSL([1, 2])
d2[2] = reverseSL([1, 2])
print(d1)
print(d2)

The following results can be obtained.

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]

If the first15Replace the line with the following.

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

It will say.TypeError: reverseSL_no_args() takes 0 positional arguments but 1 was givenButadd()There's no problem with the method.

Second Method: Class Encapsulation

This approach is a bit more complicated and has a small pitfall, so let's look at the code of the first class.

I have implemented two classes here, of whichmySL1Adoptedcombinatorialobject-oriented design methodology, themySL2Withpredecessor. The first is more code, because it adds a component to theSortedList, which would require a rewrite of theadd().

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

included__repr__is optional, just to clearly show that it has been added to thedefaultdictThe data situation of the If you don't write it, you'll have to callget()method, which performs a dictionary value (values) data output, here for convenience it is directly converted toListtype, without conversion, there is no way to pass thelist()The data obtained in this way is not an iterable object, and by directly outputting the type of the value, it is possible to obtain the value of<class '__main__.mySL1'>.

Then there's the second class, where the inheritance syntax is straightforward, calling the initialization methods of the parent class, but whichWhat you need to pay attention to.Yes, InheritanceSortedListclass would not work here, because if you still use theSortedList, in__init__modificationskeywill be prompted with an assertion error, theassert key is None, I'm confused by this question, and even think that maybe the inheritance method doesn't work!^,(Here's the source code for the module's __new__ method) I see the problem.

    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')

Here the author of the module provides aSortedListsubclass, calledSortedKeyList, as the name suggests, provides a way to write to thekeyclass, then inheriting from this class will not be a problem.

In fact, in the function call section above, there is already a hint, the type of the output result, it is shown to beSortedKeyListThis type is a modification ofkey(so that)key is not None). You can try it, if you don't change thekeyYeah, yeah, yeah.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)

Finally, there is the creation ofdefaultdict, and the reading of data.

d3 = defaultdict(mySL1)
d4 = defaultdict(mySL2)
for i in [19, 11, 12, 123]:
    d3['x'].add(i)
    d4['y'].add(i)
# Or just go through the list initialization
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']))

The following result can be obtained.

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]

As you can see, the creation of the first category actually ends up using theSortedKeyListThis subclass.

This article on the SortedList as an example of Python defaultdict object using a custom type of method is introduced to this article, more related Python defaultdict content, please search for my previous posts or continue to browse the following related articles I hope you will support me in the future more!