Set

Set는 array나 list 처럼 순열 자료 구조를 뜻한다. 하지만 set는 순서라는 개념이 존재하지 않는다.

• 데이터를 비순차적으로 저장할 수 있는 순열 자료 구조
• 삽입 순서대로 저장되지 않는다. 즉, 특정한 순서를 기대할 수 없는 자료 구조이다.
• 수정 가능하다.
• 동일한 값을 여러번 삽입 불가능하다. 동일한 값이 여러번 삽입 되면 하나의 값만 저장된다.
• Fast Lookup이 필요할 때 주로 쓰인다.

>>> my_set = {1,2,3,4,5,1,2}
>>> my_set
{1, 2, 3, 4, 5}
>>> for i in my_set:
	print(i)

	
1
2
3
4
5
>>> my_set.append(7)
Traceback (most recent call last):
  File "<pyshell#5>", line 1, in <module>
    my_set.append(7)
AttributeError: 'set' object has no attribute 'append'
>>> my_set.add(7)
>>> my_set
{1, 2, 3, 4, 5, 7}
>>> 5 in my_set
True

중복을 허용하지 않기 때문에 my_set은 {1, 2, 3, 4, 5}의 값으로 출력된다. 또한, set에서는 append를 사용할 수 없으며 값을 추가할 땐 add 메소드를 사용한다.

set 요소 안에 어떤 요소가 있는지 찾고자 할 때 주로 사용된다.

Set의 구조

• Array와 달리 set은 요소들을 순차적으로 저장하지 않는다.
• Set에서 요소들이 저장 될 때 순서는 다음과 같다.
  1. 저장할 요소의 값의 hash 값을 구한다.
  2. hash 값에 해당하는 공간(bucket)에 값을 저장한다.
• set은 저장하고자 하는 값의 hash값에 해당하는 bucket에 값을 저장하기 때문에 순서가 없다. 순서가 없기 때문에 indexing도 없다.
• hash값 기반의 bucket에 저장하기 때문에 중복된 값을 저장 할 수 없게 되는 것이다.
• hash값을 기반으로 저장하기 때문에 look up 이 굉장히 빠르다.
  1. Look up : 특정 값을 포함하고 있는지를 확인 하는 것 → 5 in my_set
  2. Set의 총 길이와 상관없이 단순히 hash값 계산 후 해당 bucket을 확인하면 되기 때문에 0(1)

When To Use Set

• 중복된 값을 골라내야 할 때
• 빠른 look up 을 해야 할 때
• 그러면서 순서는 상관이 없을 때

Set 예제

>>> x = set(['wecode', 'wework', 'wecode'])
>>> x
{'wework', 'wecode'}
>>> x.add('weplay')
>>> x
{'wework', 'wecode', 'weplay'}
>>> x.add('weplay')
>>> x
{'wework', 'wecode', 'weplay'}

wecode가 중복되기 때문에 x를 출력했을 때 wework, wecode만 출력됐다.

Set에 값을 추가 할 땐 append가 아닌 add를 사용하며 중복된 값을 추가하면 저장되지 않는다.

>>> def isDuplicated(arr):
	in_set = set(arr)
	return len(in_set) < len(arr)

>>> my_list = [1,2,2,3,3,4,5]
>>> my_list2 = [1,2,3]
>>> isDuplicated(my_list)
True
>>> isDuplicated(my_list2)
False
>>> new_list = list(set(my_list))
>>> new_list
[1, 2, 3, 4, 5]

함수의 인자로 주어진 arr와 set로 변환한 in_set이 있다. 둘의 길이를 비교하여 중복된 수가 있는지 없는지 확인할 수 있는 함수이다. 인자에 중복된 값이 있다면 처음에 주어진 값의 길이보다 적은 길이가 반환될 것이기 때문에 False가 반환되고 이는 곧 중복된 요소가 있다는 것을 의미한다. 이러한 함수를 거치고 list를 만들면 중복된 값이 없는 리스트를 생성할 수 있다.

다음의 사이트에서 더 많은 자료를 확인할 수 있다.

Sets in Python - GeeksforGeeks

union

두개의 set을 union()메소드나 | 연산자를 사용해서 하나의 set으로 병합할 수 있다. 병합 될 때 중복된 값은 사라지고 중복되지 않은 요소들만 합쳐진다.

>>> people = {'Jay', 'Idrish', 'Archil'}
>>> vampires = {'Karan', 'Arjun'}
>>> dracula = {'Deepanshu', 'Raju'}
>>> population = people.union(vampires)
>>> population
{'Idrish', 'Archil', 'Arjun', 'Jay', 'Karan'}
>>> population = people | dracula
>>> population
{'Idrish', 'Archil', 'Deepanshu', 'Jay', 'Raju'}

intersection

교집합 역할을 하는 intersection은 intersection()메소드나 & 연산자를 사용해서 사용하며, 공통 된 요소들을 선택하는 기능을 한다.

>>> set1 = set()
>>> set2 = set()
>>> for i in range(5):
	set1.add(i)

	
>>> for i in range(3, 9):
	set2.add(i)

	
>>> set3 = set1.intersection(set2)
>>> set3
{3, 4}
>>> set3 = set1 & set2
>>> set3
{3, 4}

set1 = {0,1,2,3,4} , set2 = {3,4,5,6,7,8} 의 요소가 들어있을 것이다. 이 때 interaction을 사용하면 두 set에서 공통된 요소인 3,4만 출력한다.

difference

두개의 set중에서 앞에 나오는 set를 기준으로 중복되는 요소를 삭제하고 남은 요소를 출력한다.

>>> set1 = set()
>>> set2 = set()
>>> for i in range(5):
	set1.add(i)

	
>>> for i in range(3, 9):
	set2.add(i)

	
>>> set3 = set1.difference(set2)
>>> set3
{0, 1, 2}
>>> set3 = set1 - set2
>>> set3
{0, 1, 2}

Dictionary

Dictionary는 키:값 쌍을 가지는 자료 구조를 의미한다. 딕셔너리를 만드는 방법에는 네가지의 방법이 있다.

# dictionary create 1
dictionary1 = {'name':['Ryan','Lee'], 'job':'sw engineer', 'address': {'city':'seoul', 'zip_code':'1234'} }

# dictionary create 2
dictionary2 = {}
dictionary2['name'] = ['Ryan', 'Lee']
dictionary2['job'] = 'sw engineer'
dictionary2['address'] = {'city':'seoul', 'zip_code':'1234'}

# dictionary create 3
dictionary3 = dict(name=['Ryan','Lee'], job='sw engineer', address={'city':'seoul','zip_code':'1234'})

# dictionary create 4
dictionary4 = dict([('name',['Ryan','Lee']), ('job','sw enginner'), ('address',{'city':'seoul','zip_code':'1234'})])

1. 데이터가 주어지거나 딕셔너리의 내용이 고정되어 있는 경우 사용
2. 빈 딕셔너리를 만들어놓고, 데이터 베이스를 조회해서 필요한 정보를 동적으로 채워야할 때 사용
3. 문자열만 키로 사용되는 경우 사용
4. 튜플로 받아온 정보로 키와 값을 만들어야 할 경우에 사용

각각의 키에 해당하는 구조화 된 정보를 리스트 또는 딕셔너리로 쉽게 표현할 수 있다. 이렇게 중첩해서 데이터를 표현하는 방법은 구현할 때 많이 사용되기 때문에 알아두면 좋다. 특히 동적으로 키, 값을 삽입하고 접근하는 방법은 꼭 알고 넘어가도록 하자.

Hash

hash는 입력을 출력으로 바꾸는 단방향 (one way) 암호화 함수이다. 단방향이란 한번 암호화 하면 복호화가 되지 않는다는 뜻이다. 실제 값의 길이와 상관없이 hash값을 일정한 길이를 가진다. 그렇기 때문에 hash는 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 mapping 할 때 사용된다.

• 데이터 관리 및 유지를 하는데 최적화 된 자료 구조
• 해시 함수 : 해시에서 데이터를 보고 규칙적으로 뿌려주는 함수
• 해시 테이블 : 데이터가 분류 된 이후 정보가 저장되는 곳

충돌 대처 방법

1. Chaining :

   연결 리스트를 이용한다. 체인이 길어지면 검색이 느려질 수 있다. 추가적이 메모리가 필요하다는 단점이 있다.

   

2. 오픈 주소 해싱 : 주소를 다른 데이터에게 개방한다는 뜻으로 보통 해시 테이블에는 빈 공간이 많다. 추가적인 공간을 만들지 않고 기존에 해시 테이블 공간만으로 충돌을 해결하는 것이다.

3. 선형 조사(Linear Probing) : 충돌이 발생하면 해시 테이블이 인덱스를 1씩 증가시켜 비어있는지 확인하고 비어있으면 저장한다. 추가적인 메모리가 필요하지 않는다는 장점이 있지만 한번 충돌이 발생하면 그 주위에 충돌이 몰리는 군집화 현상이라는 단점이 존재한다. 또한 삭제가 복잡하다. 마지막 요소에서 충돌이 발생하면 삭제하면 되지만 마지막 요소가 아닌 경우에는 빈 공간이 생기면 검색이 끊기기 때문에 그냥 삭제 할 수가 없다.

4. 제곱 조사(Quadratic probing) : 선형 탐색은 고정폭으로 다음 요소가 비어있는지 확인하는 방법인데 반해, 제곱 탐색은 폭을 제곱으로 늘리면서 다음 요소가 비어있는지 확인한다. 군집화를 막기 위해 사용하는 방법이다.

5. 이중 해싱(double hasing) : 해싱 함수를 2개 만들어 충돌 시 2번째 함수를 이용하는 방법이다. 2번째 함수가 탐색 시 이동 폭을 결정한다. 제곱 조사보다 조금 더 발전한 방법이다.

>>> import hashlib
>>> def sha1_hash(input_str):
	hash_obj = hashlib.sha1(input_str.encode())
	hash_value = hash_obj.hexdigest()
	return hash_value

>>> wecode_hash_value = sha1_hash('wecode')
>>> wecode_hash_value
'283463014a3f8ab829fcf9087ff85d50da1d1bb6'
>>> len(wecode_hash_value)
40
>>> hash_value_1234 = sha1_hash('1234')
>>> hash_value_1234
'7110eda4d09e062aa5e4a390b0a572ac0d2c0220'
>>> len(hash_value_1234)
40

이처럼 hash 값은 일정한 길이를 가지고, 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정 된 길이의 데이터로 mapping 할 때 사용된다.

해시 함수는 같은 문자열에 대해서는 같은 인덱스를 구할 수 있어야 해시함수로 구한 버킷의 인덱스를 저장 후에도 구할 수 있다.

해시테이블은 해시함수와 버킷(bucket)의 리스트로 구현할 수 있는데 위의 wecode 의 해시값인 '283463014a3f8ab829fcf9087ff85d50da1d1bb6' 와 '1234'의 해시값인 '7110eda4d09e062aa5e4a390b0a572ac0d2c0220'을 버킷의 주소인 인덱스를 구할 때 사용하기에는 무리가 있어 보인다.

버킷의 크기에 따른 인덱스로 변환하는 방법은 입력된 문자열의 각자리의 숫자를 더하는 방식인 Digit folding 과 비트연산을 활용한 방법등 다양한 방법이 있지만 우리는 이미 SHA1 알고리즘으로 해시값을 구하였으므로 간단하게 버킷의 사이즈로 나누는 방법인 나눗셈법을 적용하면 버킷의 인덱스를 초과하지 않는 인덱스를 구할 수 있다.

Assignment

class MySet:
  def __init__(self, size):
    self.size = size
    self.bucket = [ None for x in range(size) ]

  def values(self):
    set_data =""
    for i in range(self.size):
      if self.bucket[i] != None:
        set_data += self.bucket[i]
        set_data += ", "
    if set_data[-1] == " ":
      data_set = set_data[:-2]
    return data_set

  # 1. hash_value 함수
  def hash_value(self,key):
    hash_value = hashlib.sha1(key.encode())
    # 여기서 부터 구현
    hash_value = re.findall('\d+',hash_value.hexdigest())
    hash_value = "".join(hash_value)
    index = int(hash_value) % self.size
    return index

  # 2. add 함수
  def add(self, key):
    hash_value = self.hash_value(key)
    # 여기서 부터 구현
    i = hash_value

    while self.bucket[i] != None:  
      if key == self.bucket[i]:
        return "duplicate"

      i = (i + 1) % self.size

      if i == hash_value:
        return "full"

    self.bucket[i] = key

hash_value

정규식을 사용하여 하나 이상의 붙어있는 모든 숫자들을 찾아낸 후 문자열로 변환시킨다. size의 크기만큼 나눠주면 index가 된다.

add

bucket에 담겨있는 i값이 None이 아닐 때까지 반복문을 실행한다. key가 bucket[i] 값과 같을 경우 duplicate 를 리턴하면서 다음 인덱스에 저장하기 위해 i + 1을 시킨다. 만약 i가 hash_value와 같을 경우에는 full을 리턴하고 bucket[i]값을 key값으로 저장시켜준다.