学校如何建设网站,最新新闻国内大事件,长沙室内设计学校,银川网站建设实习生实现背景
在许多场景中#xff0c;有时需要通过多种信息来获取某个特定的值#xff0c;而各种编程语言#xff08;包括Python#xff09;使用的字典#xff08;Dict#xff09;数据结构通常只支持单个键值寻值key-val对#xff0c;即“一对一”#xff08;一个键对应一…实现背景
在许多场景中有时需要通过多种信息来获取某个特定的值而各种编程语言包括Python使用的字典Dict数据结构通常只支持单个键值寻值key-val对即“一对一”一个键对应一个值。而“多对一”的字典在复杂信息映射下有很高实用价值。例如
在实现非确定性下推自动机的时候转移函数出现下面的形式 δ(q,X){(p,Z)}。\delta(q,X) \{(p,Z)\}。 δ(q,X){(p,Z)}。 如果采用“一对一”字典的形式那么只能以qqq作为键key(X,p,Z)(X,p,Z)(X,p,Z)的集合作为其对应的值val。即dict[q] {(X,p,Z)}。这样在访问和设置值的时候遍历的复杂度显然增加了。
显然我们更希望采用形如d[q][X]{(p,Z)}的形式以q,X作为一对键值去访问和获取(p,Z)对。这就希望有一种数据结构能够实现“多对一”的访问。
为此可以设计“多键字典”来满足该要求。即对于一个键的个数为nnn的多键字典DDD它可以通过 D[key1][key2]...[keyn]D[key_1][key_2]...[key_n] D[key1][key2]...[keyn] 的方式来获取键值对(key1,key2,...,keyn)(key_1,key_2,...,key_n)(key1,key2,...,keyn)所对应的值。
设计思路
有两种方式可以实现上面提到的“多键字典”。
第一种方式是将给定的多键对multi-keys-pair转化为一个字符串进行映射 对于给定键值对(key1,key2,...,keyn)(key_1,key_2,...,key_n)(key1,key2,...,keyn)可以将其转化为一个字符串key_1,key_2,...key_n即所有键之间用逗号分隔然后用已有的字典dict映射即可。注意键之间一定要有分隔符如果直接连接起来的话有可能会造成哈希冲突导致两个不同的多键对被映射到同一处。例如(aa,b)和(a,ab)中的键如果直接连接都会形成aab的字符串导致哈希冲突。这种方式实现起来比较简单。第二种方式也是本文所介绍和实现的方式 采取”嵌套字典”的作法这种方法也很容易想到具体做法如下 设置“根字典”。对于给定的多键对(key1,key2,...,keyn)(key_1,key_2,...,key_n)(key1,key2,...,keyn)和其对应的值valvalval进行映射时按照下面的规则 令droot_dictd root\_dictdroot_dict遍历多键对key1,key2,key3,...,keyn−1key_1,key_2,key_3,...,key_{n-1}key1,key2,key3,...,keyn−1: 如果keyi(i≤n−1)key_i(i\leq n-1)keyi(i≤n−1)不在ddd中那么令d[keyi]new_dictd[key_i]new\_dictd[keyi]new_dict否则不需要进行这一步。然后令dd[keyi]dd[key_i]dd[keyi]进行字典的嵌套 令d[keyn]vald[key_n]vald[keyn]val。进行完上一步的的时候ddd已经指向了“最后一层”字典这时才真正地对multi_keys~val进行映射。
字典的嵌套如下图所示 此外为了方便需要设置一个集合对多键对进行存储以便之后获取对应dict.keys()。
代码实现
除了上面介绍的基本原理还实现了字典的诸如keys(),values(),items()的常用操作以及对in进行重载等
import copy
from typing import List,Set,Tuple,Any
class multi_key_dict:def __init__(self,key_num 1) - None:Initialize a multi-key dictionary.Args:key_num (int, optional):the number of keys. Defaults to 1.assert key_num 1self.__key_num key_numself.__dict dict()self.__keys set()passdef set_value(self,keys:tuple,val)-None:Set the value of multi_keys_dict[key_1][key_2]...[key_n].Args:keys (tuple): A tuple that contains keys in order. Its length must be equal to the number of keys.val (_type_): Value.assert len(keys) self.__key_numd self.__dictfor i in range(0,self.__key_num-1):key keys[i]if key not in d:d[key] dict()d d[key]d[keys[self.__key_num -1]] valself.__keys.add(keys) def get_value(self,keys:tuple)-Any:Get the value of multi_keys_dict[key_1][key_2]...[key_n].Args:keys (tuple): A tuple that contains keys in order. Its length must be equal to the number of keys.assert len(keys) self.__key_numd self.__dictfor i in range(0,self.__key_num):d d[keys[i]]return ddef keys(self)-Set[tuple]:Get all keys of the multi_key_dict.return self.__keys.copy()def values(self)-List[Any]:Get all values of the multi_key_dict.values []for key in self.__keys:values.append(self.get_value(key))return valuesdef items(self)-Set[Tuple[Tuple,Any]]:Get set of all (keys,val) in multi_keys_dict.mutli_keys_dict_items set()for keys in self.__keys:val self.get_value(keys)mutli_keys_dict_items.add((keys,val))return mutli_keys_dict_itemsdef __contains__(self,keys:tuple)-bool:Check whether the given multi_keys is in the dict.Args:keys (tuple): A tuple that contains keys in order. Its length must be equal to the number of keys.Returns:bool: The result.assert len(keys) self.__key_numif keys in self.__keys:return Truereturn Falsedef clear(self)-None:Clear all the keys-val pairs in the dict.Note that the number of keys is not reset.self.__dict.clear()self.__keys.clear()def keys_num(self)-int:Get the number of keys. return self.__key_numdef __str__(self) - str:items self.items()s str()for key,val in items:s f{key} : {val}\nreturn sdef copy(self):Return a deep copy of this dict.copy.deepcopy(self)进行测试
def test_multi_keys_dict():d multi_key_dict(3)l [(a,b,c),(d,e,f),(g,h,i),(g,h,j)]# test set_value and get_valuefor i in range(0,len(l)):d.set_value(l[i],i)assert d.get_value(l[i]) i# test keyskeys d.keys()for elem in l:assert elem in keys# test values:values d.values()for i in range(0,len(l)):assert i in values# test items:items d.items()for i in range(0,len(l)):assert (l[i],i) in items# test in:for elem in l:assert elem in d# test clear:d.clear()assert len(d.keys()) 0print(Test passed!)if __name__ __main__:test_multi_keys_dict()
