服务器之家

服务器之家 > 正文

Python 实现集合Set的示例

时间:2021-08-17 00:07     来源/作者:_慕

Python的集合set原理

集合(set)是一个无序的不重复元素序列。

可以使用大括号 { } 或者 set() 函数创建集合,注意:创建一个空集合必须用 set() 而不是 { },因为 { } 是用来创建一个空字典。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
class Array(object):
 
 def __init__(self, size=32, init=None):
  self._size = size
  self._items = [init] * self._size
 
 def __getitem__(self, index):
  return self._items[index]
 
 def __setitem__(self, index, value):
  self._items[index] = value
 
 def __len__(self):
  return self._size
 
 def clear(self, value=None):
  for i in range(len(self._items)):
   self._items[i] = value
 
 def __iter__(self):
  for item in self._items:
   yield item
 
class Slot(object):
 """定义一个 hash 表 数组的槽
 注意,一个槽有三种状态,看你能否想明白
 1.从未使用 HashMap.UNUSED。此槽没有被使用和冲突过,查找时只要找到 UNUSED 就不用再继续探查了
 2.使用过但是 remove 了,此时是 HashMap.EMPTY,该探查点后边的元素扔可能是有key
 3.槽正在使用 Slot 节点
 """
 def __init__(self, key, value):
  self.key, self.value = key, value
 
class HashTable(object):
 # 表示从未被使用过
 UNUSED = None
 # 使用过,但是被删除了
 EMPTY = Slot(None, None)
 
 def __init__(self):
  self._table = Array(8, init=HashTable.UNUSED)
  self.length = 0
 
 # 负载因子
 @property
 def _load_factor(self):
  return self.length/float(len(self._table))
 
 def __len__(self):
  return self.length
 
 # 哈希函数 用内置的哈希哈数进行哈希一下,然后对数组长度取模
 def _hash(self, key):
  return abs(hash(key)) % len(self._table)
 
 def _find_key(self, key):
  # 得到第一个值的位置
  index = self._hash(key)
  _len = len(self._table)
  # 当这个槽不是未使用过的,才接着往下找;如果是未使用过的,这个key肯定不存在
  while self._table[index] is not HashTable.UNUSED:
   # 槽使用过,但是被删除了
   if self._table[index] is HashTable.EMPTY:
    # cpython解决哈希冲突的一种方式
    index = (index*5 + 1) % _len
    continue
   elif self._table[index] == key:
    return index
   else:
    index = (index * 5 + 1) % _len
  return None
 
 # 检测槽是否能被插入
 def _slot_can_insert(self, index):
  return (self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED)
 
 # 找到能被插入的槽的index
 def _find_slot_insert(self, key):
  # 得到第一个值的位置
  index = self._hash(key)
  _len = len(self._table)
  while not self._slot_can_insert(index):
   index = (index * 5 + 1) % _len
  return index
 
 # in 操作符
 def __contains__(self, key):
  index = self._find_key(key)
  return index is not None
 
 def add(self, key, value):
  if key in self:
   index = self._find_key(key)
   # 更新值
   self._table[index].value = value
   return False
  else:
   index = self._find_slot_insert(key)
   self._table[index] = Slot(key, value)
   self.length += 1
   if self._load_factor > 0.8:
    return self._rehash()
   return True
 
 def _rehash(self):
  oldtable = self._table
  newsize = len(self._table) * 2
  # 新的table
  self._table = Array(newsize, HashTable.UNUSED)
  self.length = 0
  for slot in oldtable:
   if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY:
    index = self._find_slot_insert(slot.key)
    self._table[index] = slot
    self.length += 1
 
 def get(self, key, default=None):
  index = self._find_key(key)
  if index is None:
   return default
  else:
   return self._table[index].value
 
 def remove(self, key):
  index = self._find_key(key)
  if index is None:
   raise KeyError
  value = self._table[index].value
  self.length -= 1
  # 把槽设置为空槽
  self._table[index] = HashTable.EMPTY
  return value
 
 def __iter__(self):
  for slot in self._table:
   if slot not in (HashTable.UNUSED, HashTable.EMPTY):
    yield slot.value
 
 
class SetADT(HashTable):
 
 def add(self, key):
  return super(SetADT, self).add(key, True)
 
 def __and__(self, other_set):
  # 求交集
  new_set = SetADT()
  for element_a in self:
   if element_a in other_set:
    new_set.add(element_a)
  return new_set
 
 def __sub__(self, other_set):
  # 求差集
  new_set = SetADT()
  for element_a in self:
   if element_a not in other_set:
    new_set.add(element_a)
  return new_set
 
 def __or__(self, other_set):
  # 求交集
  new_set = SetADT()
  for element_a in self:
   new_set.add(element_a)
  for element_b in other_set:
   new_set.add(element_b)
  return new_set

以上就是Python 实现集合Set的示例的详细内容,更多关于Python 实现集合Set的资料请关注服务器之家其它相关文章!

原文链接:https://www.cnblogs.com/guotianbao/p/12731390.html

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部