6內置數(shù)據(jù)結構_set

set

?

set（集合|集）：

可變的，無序的，不重復的元素的集合；

set最大用處：去重；

約定：set翻譯為集合；collection翻譯為集合類型，是一個大概念；

list，鏈表，棧，queue（兩頭操作用queue）；

?

set定義、初始化：

set()-->new empty set object

set(iterable)-->new set object

?

set的元素：

要求必須可以hash；

目前學過的不可hash的類型有list,bytearray,set；

元素不可以索引（無序）；

set可以迭代（所有集合類型都可迭代）；

?

例：

In [1]: s1=set()?? #創(chuàng)建空集合只能用這種方式，{}是留給dict用的

In [2]: s2=set(range(5))

In [3]: s2

Out[3]: {0, 1, 2, 3, 4}

In [4]: s3=set(list(range(10)))

In [5]: s3

Out[5]: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

In [6]: s4={}?? #{}優(yōu)先給dict使用

In [7]: type(s4)

Out[7]: dict

In [8]: s5={9,10,11}

In [9]: type(s5)

Out[9]: set

In [10]: s6={(1,2),3,'a'}

In [11]: s7={[1],(1,),1}

---------------------------------------------------------------------------

TypeError???????????????????????????????? Traceback (most recent call last)

<ipython-input-11-25e234815aba> in <module>()

----> 1 s7={[1],(1,),1}

TypeError: unhashable type: 'list'

In [12]: s8={bytearray(b'abc')}

---------------------------------------------------------------------------

TypeError????????????????????? ???????????Traceback (most recent call last)

<ipython-input-12-d066a36dc55b> in <module>()

----> 1 s8={bytearray(b'abc')}

TypeError: unhashable type: 'bytearray'

In [13]: s9={'abc',b'abc'}

In [16]: s10=set(['abc',b'abc'])?? #雖hash值一樣，但可放在set中，不是沖突元素

In [17]: hash(1)

Out[17]: 1

In [18]: hash([1])

---------------------------------------------------------------------------

TypeError???????????????????????????????? Traceback (most recent call last)

<ipython-input-18-0579e98ca3ee> in <module>()

----> 1 hash([1])

TypeError: unhashable type: 'list'

In [19]: hash('abc')

Out[19]: 7077160064984426464

In [20]: hash(b'abc')

Out[20]: 7077160064984426464

In [21]: hash('abc') == hash(b'abc')

Out[21]: True

In [22]: hash('abc') is hash(b'abc')

Out[22]: False

In [23]: s11=set(s10)

In [24]: s11

Out[24]: {'abc', b'abc'}

?

set增加元素：

add(elem)，增加一個元素到set中；如果元素存在，什么都不做do nothing；

update(*others)，合并其它元素到set集合中來；參數(shù)others必須是可迭代對象；就地修改；

?

例：

In [25]: s=set()

In [26]: s.add(1)

In [27]: s

Out[27]: {1}

In [28]: s.add(2)

In [29]: s.add(1)

In [30]: s

Out[30]: {1, 2}

In [31]: s.update({1,2,3},{2,3,4})?? #update(*other)，把多個集合的元素合并到當前集合，不是解構的概念，others是iterable

In [32]: s

Out[32]: {1, 2, 3, 4}

?

set刪除：

remove(elem)，從set中移除一個元素；元素不存在，拋出KeyError異常，為什么是KeyError，key是hash值，根據(jù)hash值來定位刪除；

discard(elem)，從set中移除一個元素，元素不存在，do nothing；

pop()-->item，移除并返回任意的元素，為什么是任意元素？無序，不可以索引；空集返回KeyError異常；

clear()，移除所有元素，注意GC；

?

例：

In [33]: s.remove(2)

In [34]: s

Out[34]: {1, 3, 4}

In [35]: s.discard(5)

In [36]: s.pop()

Out[36]: 1

In [37]: s.pop()

Out[37]: 3

In [38]: s.pop()

Out[38]: 4

In [39]: s.pop()

---------------------------------------------------------------------------

KeyError????????????????????????????????? Traceback (most recent call last)

<ipython-input-39-c88c8c48122b> in <module>()

----> 1 s.pop()

KeyError: 'pop from an empty set'

?

set修改、查詢：

修改，要么刪除，要么加入新的元素，為什么沒有修改？可變類型list,bytearray均不可hash；

查詢，非線性結構無法索引；

遍歷，可迭代所有元素；

成員運算符，in,not in，效率？很高，相當于用index遍歷list，O(1)；

?

set成員運算符的比較：

list和set比較：

list隨著值的增加耗時是數(shù)量級的增加；

set，隨著值的增加，基本不變，適用于在集合中查找某個值，set中查時先轉為key（hash值）再查；

?

set和線性結構：

線性結構的查詢時間復雜度是O(n)，即隨著數(shù)據(jù)規(guī)模的增大而增加耗時；

set,dict等結構，內部使用hash值作為key，時間復雜度可以做到O(1)，查詢時間和數(shù)據(jù)規(guī)模無關；

可hashable類型：數(shù)值型（int,float,complex）；布爾型（True,False）；字符串（string,bytes）；tuple；None；以上都是不可變類型；

注：set的元素必須是可hashable的；

?

set基本概念：

全集，所有元素的集合，如實數(shù)集，所有實數(shù)組成的集合就是全集；

子集subset，超集superset，一個集合A所有元素都在另一個集合B內，A是B的子集，B是A的超集；

真子集和真超集，A是B的子集，且A不等于B，A就是B的真子集，B是A的真超集；

并集，多個集合合并的結果；

交集，多個集合的公共部分；

差集，集合中除去和其它集合公共部分；

?

集合運算：

并集：

將兩個集合A和B的所有元素合并到一起，組成的集合稱作集合A和集合B的并集；

union(*others)，返回多個集合合并后的新集合；

|，運算符重載，等同union(*others)；

update(*others)，和多個集合合并，就地修改；

|=，等同update(*others)；

?

例：

In [40]: s1={1,2,3}

In [41]: s2={2,3,4}

In [43]: s1.union(s2)

Out[43]: {1, 2, 3, 4}

In [44]: s1

Out[44]: {1, 2, 3}

In [45]: s2

Out[45]: {2, 3, 4}

In [47]: s3=s2.union(s1)

In [48]: s3

Out[48]: {1, 2, 3, 4}

In [49]: s1 | s2

Out[49]: {1, 2, 3, 4}

In [50]: s2 | s1

Out[50]: {1, 2, 3, 4}

In [51]: s3 |= {5,6} | {7,8}?? #類似a += 1+2

In [52]: s3

Out[52]: {1, 2, 3, 4, 5, 6, 7, 8}

?

交集：

集合A和B，屬于A且屬于B的元素組成的集合；

intersection(*others)，返回多個集合的交集；

&，等同intersection(*others)；

intersection_update(*others)，獲取和多個集合的交集，并就地修改；

&=，等同intersection_update(*others)；

?

例：

In [53]: s1 & s2

Out[53]: {2, 3}

In [54]: s3=s1 & s2

In [55]: s3

Out[55]: {2, 3}

In [56]: s1.intersection(s2)

Out[56]: {2, 3}

In [57]: s2.intersection(s1)

Out[57]: {2, 3}

In [58]: s3.intersection_update(s2)

In [59]: s3

Out[59]: {2, 3}

In [60]: s3.intersection_update(s1)

In [61]: s3

Out[61]: {2, 3}

?

差集（常用）：

集合A和B，屬于A但不屬于B的元素組成的集合；

difference(*others)，返回多個集合的差集；

-，等同difference(*others)；

difference_update(*others)，獲取和多個集合的差集，并就地修改；

-=，等同difference_update(*others)；

A-B=A-A∩B

A-B=A

A-B=環(huán)形

A-B=None

?

例：

In [62]: s1

Out[62]: {1, 2, 3}

In [63]: s2

Out[63]: {2, 3, 4}

In [64]: s3

Out[64]: {2, 3}

In [65]: s1-s2

Out[65]: {1}

In [66]: s2-s1

Out[66]: {4}

In [67]: s1-=s2

In [68]: s1

Out[68]: {1}

?

對稱差集：

集合A和B，不屬于A和B的交集元素組成的集合，記作(A-B)∪(B-A)；

symmetric_difference(other)，返回一個集合的差集；

^，等同symmetric_difference(other)；

symmetric_difference_update(other)，獲取和另一個集合的差集，并就地修改；

^=，等同symmetric_difference_update(other)；

?

例：

In [70]: s1={1,2,3}

In [71]: s2

Out[71]: {2, 3, 4}

In [72]: s1^s2

Out[72]: {1, 4}

In [73]: s2^=s1

In [74]: s2

Out[74]: {1, 4}

In [75]: s1

Out[75]: {1, 2, 3}

?

issubset(other)，<=，判斷當前集合是否是另一個集合的子集；

set1 < set2，判斷set1是否是set2的真子集；

issuperset(other)，>=，判斷當前集合是否是other的超集；

set1>set2，判斷set1是否是set2的真超集；

isdisjoint(other)，當前集合和另一個集合有沒有交集，沒有交集返回True，用于判斷交集；

?

例：

In [76]: s1={1,4,5,6}

In [77]: s2={1,3,4,5,6}

In [78]: s1>s2

Out[78]: False

In [79]: s1>=s2

Out[79]: False

In [80]: s1<s2

Out[80]: True

In [81]: s1<=s2

Out[81]: True

In [82]: s1.issubset(s2)

Out[82]: True

In [83]: s2.issuperset(s1)

Out[83]: True

In [84]: s1.issuperset(s1&s2)

Out[84]: True

In [85]: s3=set()

In [86]: {}>s3?? #{}是dict，

---------------------------------------------------------------------------

TypeError???????????????????????????????? Traceback (most recent call last)

<ipython-input-86-f3e15203fad2> in <module>()

----> 1 {}>s3

TypeError: unorderable types: dict() > set()

In [88]: set() == s3

Out[88]: True

In [89]: s3={10}

In [90]: s1

Out[90]: {1, 4, 5, 6}

In [91]: s1.isdisjoint(s3)?? #沒有交集返回True

Out[91]: True

?

集合set應用：

共同好友：你好好友A,B,C，他的好友B,C,D，求共同好友？

{'A','B','C'}.intersection({'B','C','D'})

微信群提醒：xxx與群里其它人都不是微信朋友關系？

userid not in (A | B | C | D) 返回False，A,B,C,D為集合

權限判斷：

有一個API，要求權限同時具備A,B,C才能訪問，用戶權限是B,C,D，判斷用戶是否能訪問API？

A={'A','B','C'}

B={'B','C','D'}

A >= B返回False

A - B == set()?? #方一，A-B為空集，B包含A

A.issubset(B)?? #方二，A是B的子集

A & B == A?? #方三

有一個API，要求權限具備A,B,C任意一項就可訪問，用戶權限是B,C,D，判斷用戶是否能訪問該API？

A={'A','B','C'}

B={'B','C','D'}

A & B != set()?? #方1，返回True

A.isdisjoint(B)?? #方2，返回False表示有交集

一個總任務列表，存儲所有任務，一個完成的任務列表，找出未完成的任務？

任務ID不可以重復；

所有任務ID放到一個set中，如A集合；

所有已完成的任務ID放到另一個set中，如B集合；

A - B = UNCOMPLETED，未完成任務ID；

?

?