lab08よりsetsについて簡単な紹介と問題が出たのでそこまで時間も必要なさそうなのでさらっとsetsについて復習がてら。
sets
a set is an unordered collection of distinct objects that supports membership testing, union, intersection, and adjunction. The main difference between sets and lists are 1. they are unordered, and 2. there are no duplicates. Other than that almost everything is the same.
unorderedはそのまんまだと思うけどdistinctっていう特徴はリストにはない性質なので中々面白い。ぱっと考えたのは例えばわざわざdef lst_filter(cond, s): return filter(cond, s) where cond yields something that goes along the lines of return if x in sみたいなのしなくてもset(s)だけで余計な余りを全て消してくれたり。もしくはsorted系のscreening_funcを使ってセットをリストに返してあげることも楽に。setが何よりも優れている点はいちいち関数をつくったりしないといけないようなことをsetを通すだけで他者より圧倒的な処理速度でやってしまうこと。
ラボからの例を参考に:
>>> a = [1, 1, 2, 2, 3, 3]
>>> a = set(a)
>>> a # No duplicates
{1, 2, 3}
>>> a = {3, 1, 2}
>>> a # Not necessarily in same order
{1, 2, 3}
membership testing, union, intersection and adjunction?
イマイチ実感がわかなかったので調べてみたら意外とシンプル。一般的な解説はここに書いてあるので参考までに。一言でいうとmembership testingはx in s、unionはリストで言うadd(lst1, lst2)、intersectionは無理矢理リストの考え方を使えば[filter(lambda x: x in lst, sublist) for sublist in sublst]でadjunctionはlst.add(4)になるのかな。
ちなみに個人的にintersection (also denoted as set(x) & set(y))に混乱させられたのでSOFも参考にしながら調べました。
>> set([1,2,3]) & set([2,3,4])
set([2, 3])
>> set().intersection(*[[1,2,3], [2,3,4]])
set([])
なぜ下のコードが出ないかというと単純に最初のset()が空っぽだから。上に書いてあるように二つに何か要素が入っていないとこの場合では空のセットを出してしまうのでこのケースで考えられるとしたらあらかじめセットを何かの変数に入れておいてset.intersection(*sets)として一気に片付けてしまうのが賢いなと勉強になった。以下SOFより
>>> x = [{1, 2, 3}, {2, 3, 4}, {3, 4, 5}]
>>> set.intersection(*x)
set([3])
Exercises
エクササイズがてら実際にラボにでた問題を参考にセットの性質を考えてみることにします。
Q1
# Question2
def find_duplicates(lst):
"""Returns True if lst has any duplicates and False if it does not.
>>> find_duplicates([1, 2, 3, 4, 5])
False
>>> find_duplicates([1, 2, 3, 4, 2])
True
>>> find_duplicates(list(range(100000)) + [-1]) # make sure you have linear time
False
"""
set_lst = set(lst)
if list(set_lst) != lst:
return True
else:
return False
「setに変えたlstとinputとして入ってきたlstを比べて同じだったらFalseで違かったら（=lst has been mutated）Trueと返せばいいんじゃ」と思い以上の用に書いてみました。模範解答はもっと短くてさすが！ってうなります。return len(set(lst)) != len(lst)これだけ。。。。！たしかにmutateされたってことは究極的には長さが変わるってことだしな。snap!
Q2
def pow(n,k):
"""Computes n^k.
>>> pow(2, 3)
8
>>> pow(4, 2)
16
>>> a = pow(2, 100000000) # make sure you have log time
"""
if k == 0:
return 1
elif k == 1:
return n
elif k % 2 == 1:
return n * pow(n, k - 1)
else:
pow2 = pow(n, k / 2)
return pow2**2
これはTAからもらったヒントとたくさんぐぐって調べた結果出た答え。簡単に言うと例えば2^64を分解すると2^2 * 2^2 => 2^4 * 2^4 => 2^8 * 2^8 => 2^16 * 2^16 => 2^32 * 2^32 = 2^64を考えてみると問題が分かりやすくなる。（ちなみにこれは約logの数分（appx 5)だけ処理が行われるらしい。）結果、偶数の場合は以上の処理を行い、そうじゃない場合は無理矢理偶数の形にしてから処理を行うイメージ。
追記: Q3
HW05より。
def add_up(n, lst):
"""Returns True if any two non identical elements in lst add up to n.
>>> add_up(100, [1, 2, 3, 4, 5])
False
>>> add_up(7, [1, 2, 3, 4, 2])
True
>>> add_up(10, [5, 5])
False
>>> add_up(151, range(0, 200000, 2))
False
>>> timeit(lambda: add_up(151, range(0, 200000, 2))) < 1.0
True
>>> add_up(50002, range(0, 200000, 2))
True
"""
"*** YOUR CODE HERE ***"
最初に自分で作ったコードは以下の様な感じでした。
def add_up(n, lst):
sorted_lst = list(set(lst))
n_diff = [n - x for x in sorted_lst]
if set(sorted_lst) & set(n_diff) == set():
return False
else:
if set(sorted_lst) == set(n_diff):
return False
else:
return True
ただ色々調べていたら他にも色んな方法があったのでそっちも参考にもう一つの解答を自分なりに作ってみた。
def add_up(n, lst):
divided_n = n // 2
filtered_out_nums = set([n - x for x in lst if x <= divided_n]) & set([x for x in lst if x > divided_n])
if filtered_out_nums == set():
return False
else:
for x in filtered_out_nums:
num_list = [n-x, x]
return n == sum(num_list)
考え方は若干似てるような似てないような。最初に片方の数xを持ってきてother_val = n - xとしている。こちらではdiv_n = n // 2を用意してそれより大きい数と小さい数をベースに数を集めてきて共通する数字をfiltererd_out_numsに入れている。処理の順番が若干違うのとsetの出し方が若干異なる点以外ではそこまで変わりはなさそう。
追記: Difference
例えば2つのリストがあって各リストが持っていない要素だけを引っ張って欲しいときなどに有効活用できそうなset(lst).difference(lst2)。listに変えると更に扱いやすくなる。
def missing_val(lst0, lst1):
"""Assuming that LST0 contains all the values in LST1, but LST1 is missing
one value in LST0, return the missing value. The values need not be
numbers.
>>> from random import shuffle
>>> missing_val(range(10), [1, 0, 4, 5, 7, 9, 2, 6, 3])
8
>>> big0 = [str(k) for k in range(15000)]
>>> big1 = [str(k) for k in range(15000) if k != 293 ]
>>> shuffle(big0)
>>> shuffle(big1)
>>> missing_val(big0, big1)
'293'
>>> timeit(lambda: missing_val(big0, big1)) < 1.0
True
"""
"*** YOUR CODE HERE ***"
return list(set(lst0).difference(lst1))[0]