python数据结构之 set

zhouu

　　在数学概念中，被意为整合元素的定义区域
　　在python中，set最大的作用是用来去重
　　set常见操作：
　　In [158]: s ={1,1,1,1,2,22,33,3,3,3}
　　In [159]: s
　　Out[159]: {1,2, 3, 22, 33}
　　在定义一个集合的时候，只能使用大括号定义最少一个值，不然会被认为字典进行定义
　　在set中不能加入不可哈希的对象类型
　　In [161]:hash('a')
　　Out[161]:4952964627402403516
　　查看列表的哈希值，可以发现这个对象不可被哈希
　　In [162]: a =[1,2,3]
　　In [163]:hash(a)
　　---------------------------------------------------------------------------
　　TypeError                               Traceback (most recent call last)
　　<ipython-input-163-fe724719d9a1>in <module>()
　　----> 1hash(a)
　　TypeError:unhashable type: 'list'
　　set元素必须是可以哈希运算，但是需要元素可以迭代的
　　只要是能被迭代的元素都可以被加入到set中
　　In [171]:list(s)
　　Out[171]:['abc', b'abc']
　　In [172]: a =list(s)
　　In [173]: a
　　Out[173]:['abc', b'abc']
　　In [174]:set(a)
　　Out[174]:{'abc', b'abc'}
　　set.add增加元素
　　增加一个元素到set中，如果存在则什么都不做，因为存在其值
　　In [176]:s.add(1)
　　In [177]: s
　　Out[177]: {1,'abc', b'abc'}
　　In [178]:s.add(2)
　　In [179]: s
　　Out[179]: {1,'abc', 2, b'abc'}
　　set可以收集多个集合，同样的可以合并多个集合
　　使用update进行更新
　　In [180]:s.update({1,2,3},{5,7},(1,9,1))
　　In [181]: s
　　Out[181]: {1,'abc', 2, b'abc', 3, 5, 7, 9}
　　In [185]:s.update({1})
　　In [186]: s
　　Out[186]: {1,'abc', 2, b'abc', 3, 5, 7, 4, 9}
　　In [187]:s.update({10})
　　In [188]: s
　　Out[188]: {1,'abc', 2, b'abc', 3, 5, 7, 4, 9, 10}
　　set.remove删除
　　remove，将要删除的值转为hash，并按当前hash值定位其位置进行删除，这个hash将作为一个key进行操作
　　In [193]: s
　　Out[193]: {1,2, b'abc', 3, 5, 7, 4, 9, 10}
　　In [194]:s.remove(b'abc')
　　In [195]: s
　　Out[195]: {1,2, 3, 4, 5, 7, 9, 10}
　　查找元素的过程是非常快，因为是直接定义hash，并非是从头到尾去遍历
　　discard 从集合移除一个元素
　　与remove功能一样，但是discard并不会弹出异常：
　　remove 删除一个异常索引会报出keyerror
　　In [196]:s.remove('hahaha')
　　---------------------------------------------------------------------------
　　KeyError                                Traceback (most recent call last)
　　<ipython-input-196-185a5cf4c543>in <module>()
　　----> 1s.remove('hahaha')
　　KeyError:'hahaha'
　　discard 删除一个索引则不会返回任何信息
　　In [197]:s.discard('hahaha')
　　In [198]:
　　pop  随机挑选一个弹出并返回
　　pop只是随机弹出，并不能跟参数
　　In [202]:s.pop()
　　Out[202]: 2
　　In [203]:s.pop()
　　Out[203]: 3
　　In [204]: s
　　Out[204]: {4,5, 7, 9, 10}
　　clear  清除集合内所有元素，但是要考虑GC内存回收问题
　　set修改及查询
　　在set中没有修改的概念，只有两种操作:
　　删除元素 和追加元素
　　查询：非线性结构，无法进行索引查询
　　遍历：可以遍历所有可迭代的元素
　　成员运算符
　　成员运算符 in , not in ,效率很高
　　非线性结构如果找哈希值，时间复杂度相当于索引遍历列表大O(1)
　　看似通过值在遍历，实际上是用哈希值进行定位
　　可哈希的类型
　　数值型：int、float、complex
　　布尔类：True、False
　　字符串： str Bytes
　　Tuple、None都是不可变类型，称为哈希类型
　　对比list和set执行效率
　　查看set执行效率
　　导入模块timeit
　　import timeit
　　In [3]:%%timeit lst1 = set(range(1000))
　　...: a = -1 in lst1
　　...:
　　38.1 ns ± 0.0493 ns per loop(mean ± std. dev. of 7 runs, 10000000 loops each)
　　查看list效率
　　In [1]:%%timeit lst1 = list(range(1000))
　　...: a = -1 in lst1
　　...:
　　14.7 μs ± 99.3ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
　　
　　总结：
　　线性结构查询的复杂度是O(n), 随着规模增大耗时间越来越高
　　set和字典都属于特殊结构，其中都存了hash作为key，时间复杂度可以做到O(1),查询时间与数据规模无关