以SortedList为例详解Python的defaultdict对象使用自定义类型的方法

作者:zorchp 时间:2022-04-07 02:32:28 

写在前面

最近写周赛题, 逃不开的一种题型是设计数据结构, 也就是第三题, 做这种题需要的就是对语言中的容器以及常用排序查找算法的掌握, 而我只熟悉了最基本的一些方法, 做起这些题来总是超时…

为了搞定这些题, 我决定学习一下大佬们的做法, 特别是优先队列的方法维护有序容器以及有序列表等容器, 这些都在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这个子类.

来源:https://blog.csdn.net/qq_41437512/article/details/125986285

标签:Python,defaultdict,对象,自定义,类型,方法
0
投稿

猜你喜欢

  • 在ASP中改善动态分页的性能

    2008-05-08 14:27:00
  • python3实现全角和半角字符转换的方法示例

    2021-06-16 13:08:36
  • 从IIS到SQL Server数据库安全

    2008-12-24 15:58:00
  • Python统计分析模块statistics用法示例

    2021-01-20 08:44:16
  • 表格可读性提升分析

    2010-05-19 13:03:00
  • vue+axios+java实现文件上传功能

    2024-04-30 10:40:32
  • Pandas中常用的七个时间戳处理函数使用总结

    2023-05-28 21:41:33
  • 怎样管理好css样式

    2008-10-12 12:12:00
  • JS实现选择TextArea内文本的方法

    2024-04-16 10:40:02
  • Go+Kafka实现延迟消息的实现示例

    2024-05-22 10:14:29
  • JavaScript面向对象的简单介绍

    2008-06-27 12:37:00
  • MySQL过滤重复数据的两种方法示例

    2024-01-16 12:54:27
  • Pytorch 多块GPU的使用详解

    2021-01-21 09:19:09
  • Oracle数据操作和控制语言详解

    2008-01-16 19:18:00
  • win10下python2和python3共存问题解决方法

    2022-11-05 09:08:38
  • Python unittest discover批量执行代码实例

    2023-08-14 14:05:37
  • Mysql出生日期转换为年龄并分组统计人数的方法示例

    2024-01-14 14:58:03
  • 功能强大的php分页函数

    2023-11-15 03:17:37
  • Django中session登录验证操作指南

    2023-12-12 03:34:43
  • python中__init__()方法详情

    2023-06-05 21:22:46
  • asp之家 网络编程 m.aspxhome.com