24.01.20 CSAPP 3.5-3.6.4, 트라이, 다익스트라, 플로이드 워셜, prim, union_find, kruskal, 신장트리, MST

24.01.20 CSAPP 3.5-

CSAPP

3.5 산술연산과 논리연산

• 각 인스트럭션 클래스는 네개의 서로 다른 크기의 데이터 연산을 갖는다. 연산들은 4개의 그룹으로 나누어진다.
  • 유효주소 적재
  • 단항(Unary)
  • 이항(Binary)
  • 쉬프트(Shift)
  • 이항연산은 두개의 오퍼랜드를 가지는 반면, 단항연산은 한개의 오퍼랜드를 갖는다.

3.5.1 유효주소 적재(Load Effective Address)

• 유효주소 적재 인스트럭션 leaq는 실제로는 movq 인스트럭션의 변형이다.
• 메모리에서 레지스터로 읽어들이는 인스트럭션의 형태를 갖지만, 메모리를 전혀 참조하지 않는다. 이 인스트럭션의 첫번째 오퍼랜드는 일종의 메모리 참조처럼 보이지만, 가리키는 위치에서 읽기를 수행하는 대신에 유효주소를 목적지에 복사한다.
• 이 인스트럭션은 나중에 메모리 참조에 사용하게 되는 포인터를 생성하기 위해 사용된다. 또, 일반적인 산술연산을 간결하게 설명하기 위해서 사용된다.
• 컴파일러는 자주 실제 유효주소 계산과 무관한 경우에 leaq를 적절히 사용하곤 한다.
• 목적 오퍼랜드는 반드시 레지스터만 올 수 있다.
• leaq는 일반적으로 간단한 산술연산을 사용한다.

3.5.2 단항 및 이항연산

• 두번째 그룹에서의 연산은 하나의 오퍼랜드가 소스와 목적지로 동시에 사용되는 단항 연산이다.
• 이 오퍼랜드는 레지스터나 메모리위치가 될 수 있다.
• ex) incq (%rsp) : 스택 탑의 8바이트 원소 값 증가
• 세번째 그룹 이항연산자로 구성되며, 두번째 오퍼랜드는 소스이면서 목적지로 사용된다.
• C언어 에서 x+=y 같은 문장과 유사하다. 소스가 먼저오고 목적지가 나중에 오는 점에 유의.
• 비교환성(noncommutative) 연산으로 특이하게 보인다.
  • 연산의 순서를 바꾸면 부호가 반대가 되는 성질
• ex) subq %rax %rdx ⇒ rdx - rax
• 첫 번째 오퍼랜드는 상수나 레지스터 , 메모리 위치가 올 수 있다.
• 두 번째 오퍼랜드는 레지스터나 메모리가 올 수 있다. MOV인스트럭션처럼 두개의 오퍼랜드가 모두 메모리 위치가 될 수는 없다.
• 두 번째 오퍼랜드가 메모리 위치일 때 프로세서가 메모리에서 값을 읽고, 연산을 하고 그 결과를 다시 메모리에 써야 한다는 점에 유의

3.5.3 쉬프트 연산(Shift)

• 마지막 그룹은 쉬프트 연산으로 구성되며, 쉬프트 하는 크기를 먼저 주고, 쉬프트할 값을 두 번째로 준다. 산술과 논리형 우측 쉬프트가 모두 가능하다. 여러가지 쉬프트 인스트럭션들은 쉬프트할 양을 즉시 값이나 단일 바이트 레지스터 %cl로 명시할 수 있다.(이 인스트럭션들은 이 특정 레지스터만을 오퍼랜드로 허용하는 점이 일반적이지 않다.)
• x86-64에서는 w비트 길이의 데이터 값에 적용하는 쉬프트 연산은 레지스터 %cl의 하위 m비트로 쉬프트 양을 결정하며 2^m = w 관계가 성립한다.
• 좌측 쉬프트 인스트럭션에는 두가지 이름이 있다 : SAL, SHL 이들은 모두 동일한 효과를 내며, 우측에서 부터 0을 채운다. 우측 쉬프트 인스트럭션은 SHR이 논리 쉬프트(0으로 채운다)을 수행하는 반면 SAR이 산술쉬프트(부호 비트를 복사해서 채운다)를 수행한다는 점에서 차이가 있다.
• 쉬프트 연산의 목적 오퍼랜드는 레지스터나 메모리 위치가 될 수 있다.

3.5.4 토의

• 대부분 인스트럭션들은 비부호형과 2의보수 산술 연산에 사용될 수 있다.
• 오직 우측 쉬프트만이 부호형과 비부호형 데이터를 구분하는 인스트럭션을 요구한다. 이것이 부호형 정수 산술연산을 구현하는 방식으로 2의 보수 산술연산을 선호하는 주요특징이다. 일반적으로 컴파일러는 각각의 레지스터를 여러가지 프로그램의 값을 저장하는데 사용하고, 레지스터들 간에 프로그램 값을 이동하는데 사용한다.

3.5.5 특수 산술 연산

• 두개의 64비트 부호형 또는 비부호형 정수들 간의 곱셈은 결과값을 표시하기 위해 12비트를 필요로 한다. x86-64 인스트럭션 집합은 128 비트 숫자와 관련된 연산에 대해서는 제한적인 지원을 제공한다. imlq
• IMUL 인스트럭션 클래스의 멤버. 이 형식은 두 개의 64비트 오퍼랜드로 부터 64비트 곱을 생성하는 2 오퍼랜드 곱셈 인스트럭션을 제공한다.
• 추가적으로 x86-64에서는 두개의 다른 ‘단일 오퍼랜드’ 곱셈 인스트럭션을 제공하며, 두 64 비트값의 완전한 128비트 곱을 계산한다. - 하나는 비부호형 (mulq) 하나는 2의 보수 (imulq) 곱셈. 이들 모두 한개의 인자는 레지스터 %rax에 보관해야 하고, 다른 한개는 인스트럭션 소스 오퍼랜드로 주어진다. 곱은 %rdx(상위 64비트) 와 %rax(하위 64비트)에 저장된다.

3.6 제어문

• 보통 C와 기계어 인스트럭션들은 모두 프로그램에 나타나는 순서대로 순차적으로 실행된다.
• 기계어 인스트럭션들의 실행순서는 JUMP인스트럭션으로 변경할 수 있다.
• 점프 인스트럭션은 때에 따라서는 어떤 시험의 결과에 따라 프로그램의 다른 일부분으로 제어를 넘겨준다.

3.6.1 조건코드

• 정수 레지스터들과 함께 CPU는 가장 최근 산술 또는 논리연산의 특성을 설명하는 단일비트조건 코드로 구성된 레지스터들을 운영한다. 이 레지스터들은 조건부 분기를 수행하기 위해 시험될 수 있다.
  • CF(Carry Flag) : 가장 최근의 연산에서 가장 중요한 비트로부터 받아 올림이 발생한 것을 표시. 비부호형 연산에서 오버플로우를 검출 할 때 사용.
  • ZF(Zero Flag) : 가장 최근 연산의 결과가 0인 것을 표시
  • SF(Sign Flag) : 가장 최근 연산이 음수를 생성한 것을 표시
  • OF(Overflow Flag) : 가장 최근 연산이 양수/음수의 2의 보수 오버플로우를 발생 시킨것을 표시
• leaq 인스트럭션은 주소 계산에 사용하기 위한 것이므로 조건 코드를 변경하지 않는다.
• 반면 그림에 나열된 모든 인스트럭션은 조건 코드 값을 변경한다.
• CMP 인스트럭션들은 두 오퍼랜드의 차에 따라 조건코드를 설정한다.
• 이들은 목적지를 갱신하지 않고 조건코드를 설정 한다는 점을 제외하고는 SUB 인스트럭션과 같은 방법으로 동작한다.
• 이 인스트럭션들은 만일 두 오퍼랜드가 같으면 영플래그를 1로 설정한다 다른 플래그들은 두 오퍼랜드의 순서관계를 결정하는데 사용될 수 있다.

3.6.2 조건코드 사용하기

• 조건코드를 이용하는 보편적인 세가지 방법
  1. 조건코드의 조합에 따라 0 또는 1을 한 바이트에 기록
  2. 조건에 따라 프로그램의 다른 부분으로 이동하는 방법
  3. 조건에 따라 데이터를 전송하는 방법
• SET인스트럭션 조건코드의 일부 조건에 따라 하나의 바이트를 0 또는 1로 기억한다. 이들 인스트럭션은 서로 다른 접미어를 가지고, 이에 따라 다른 조건코드의 조합을 사용하여 서로 다른 동작을 한다. 여기서 접미어는 오퍼랜드 크기가 아니라 조건코드의 어떤 조합을 사용 할 것인지 나타내는 점이다.
• SET 인스트럭션은 목적지로 하위 단일 바이트 레지스터 가운데 한 개나 단일 바이트 메모리 주소를 사용하며, 이 바이트를 0이나 1로 기록한다.

3.6.3 점프 인스트럭션

• 점프 인스트럭션은 프로그램이 완전히 새로운 위치로 실행을 전환하도록 한다. 이들 점프의 목적지는 일반적으로 어셈블리 코드에서는 레이블(label)로 표시한다.
• 목적 코드파일을 만들기 위해서 어셈블러는 모든 레이블이 붙은 인스트럭션들의 주소를 결정하고, 점프 인스트럭션의 일부분인 ‘점프 목적지(Jump Target) : 목적지 인스트럭션의 주소’ 를 인코딩한다.
• jmp 인스트럭션은 점프 목적지가 인스트럭션의 일부로 인코딩되는 경우에는 직접 점프를, 점프 대상을 레지스터나 메모리 위치로부터 읽어 들어야 하는 경우 간접 점프를 사용한다.
  • 직접점프는 점프대상을 레이블로 프로그램 내에 작성한다.
  • 간접점프는 메모리 오퍼랜드 중의 하나를 이용한 오퍼랜드 식별자를 합쳐서 작성한다.
  • jmp *%rax : rax에 값을 점프 목적지로 활용
  • jmp*(%rax) = %rax에 저장된 값을 읽기 주소로 사용하여 메모리에서 점프 목적지 사용

3.6.4 점프 인스트럭션 인코딩

• 점프를 인코딩하는 여러가지 방법 중 일반적인 방법 PC상대적(PC relative) 방법
  • 대상 인스트럭션과 점프인스트럭션 주소와의 차이를 인코딩 한다.
• 두 번째 방법은 ‘절대’주소를 제공하는 방법
  • PC상대 주소지정을 수행할 때 프로그램 카운터의 값은 점프 인스트럭션 자신의 주소가 아니라 점프 다음에 나오는 인스트럭션의 주소가 된다.
• PC - 상대 방식으로 점프 목적지를 인코딩하면, 인스트럭션들이 간결하게 인코딩(2바이트) 될 수 있고, 목적코드는 수정없이 메모리상 다른 위치로 이동 될 수 있다.

자료구조

트라이(Trie)

• 문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조
• 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색등 문자열을 탐색하는데 특화 되어있는 자료구조
• 래딕스 트리(radix tree) or 접두사 트리
• (prefix tree) or 탐색 트리(retrieval tree) 라고도 한다. 트라이는 retrieval 에서 나온 단어다.

트라이 장단점

• 장점
  • 트라이는 문자열 검색을 빠르게 한다.
  • 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간복잡도 측면에서 더 효율적이다.
• 단점
  • 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장공간의 크기가 크다는 단점도 있다.
• 트라이의 생성 시간복잡도는 O(MxL): 탐색 시간복잡도 O(L)
  • 가장 긴 문자열 길이 L
  • 총 문자열의 수 M

class Node(Object):
	def __init__(self,key,data = None):
		self.key = key
		self.data = data
		self.children = {}

class Trie(Object):
	def __init__(self):	
		self.head = node(None)
	# 문자열 삽입
	def insert(self,string):
		curr_node = self.head
		for char in string:
			if char not in curr_node.children:
				curr_node.children[char]
			curr_node = curr_node.children[char]
		curr_node.data = string

	def search(self, string):
		curr_node = self.head
		for char in string:
			if char in curr_node.children:
				curr_node = curr_node.children[char]
			else:
				return False
		if curr_node.data is not None:
			return True

신장트리(Spanning Tree)

• 그래프 내의 모든 정점을 포함하는 트리
• 그래프의 최소 연결 부분 그래프다.
  • 최소연결 : 간선의 수가 가장 적다
  • n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 spanning tree가 된다.
• 그래프에서 일부 간선을 선택해서 만든 트리

특징

• BFS,DFS 를 이용해서 그래프에서 신장트리를 찾을 수 있다.
  • 탐색 도중에 사용된 간선만 모으면 만들 수 있다.
• 하나의 그래프에서 많은 신장 트리가 존재할 수 있다.
• Spanning tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.
• Spanning tree는 그래프에 있는 n개의 정점을 정확히 (n-1.)개의 간선으로 연결해야 한다.

최소 신장트리 MST(Minimum Spanning Tree)

• Spanning Tree 중 사용된 간선들의 가중치 합이 최소인 트리
• 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는건 아니다.
• MST는 간선에 가중치를 고려해서 최소 비용의 Spanning tree를 선택하는것을 말한다.
• 즉, 네트워크(가중치 그래프)에 있는 모든 정점들은 가장 적은 수의 간선과 비용으로 연결하는것

특징

• 간선의 가중치 합이 최소여야 한다.
• n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
• 사이클이 포함되어서는 안된다.

Algorithm

다익스트라

• 그래프의 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점뿐만 아니라 모든 다른 정점까지 최단경로로 방문하여 각 정점까지의 최단 경로를 모두 찾게된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.

동작과정

1. 출발노드와 도착노드를 설정한다
2. ‘최단 거리 테이블’을 초기화 한다.
3. 현재 위치한 노드의 인접노드 중 방문하지않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 짧은 노드를 선택한다. 그 노드를 방문처리한다.
4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)를 계산해 ‘최단 거리 테이블’ 을 업데이트 한다.
5. 3-4 과정을 반복한다.

• ‘최단거리 테이블’ 은 1차원 배열로, N개의 노드까지 오는데 필요한 최단거리를 기록한다. N개 크기의 배열을 선언하고 큰 값을 넘어 초기화 시킨다.

특징

• 가중치가 양수일 때만 사용가능하다.
  • 그래야 한번 방문한 정점에 대해서는 값을 업데이트 하지 않아도 된다.
• 방문하지 않은 노드 중 거리값이 가장 작은 노드’ 를 선택해 다음 탐색 노드로 삼는다.
• 순차탐색 O(N²)
  • 순차탐색을 사용할 경우 노드 개수에 따라 탐색시간이 매우 오래 걸릴 수 있다. 이를 개선하기 위해서 우선 순위 큐를 도입한다.

우선순위 큐 구현

• 거리값을 담을 우선순위 큐는 힙으로 구현하고, 만약 최소힙으로 구현한다면 매번 루트 노드가 최소 거리를 가지는 노드가 될 것이다.
• 파이썬의 경우 Priority queue, heapq 라이브러리 사용
• 우선순위 큐에서 사용할 ‘우선순위’의 기준은 ‘기작노드로 부터 가장 가까운 노드’가 된다. 따라서 큐의 정렬은 최단거리인 노드를 기준으로 최단거리를 가지는 노드를 앞에 배치한다.
• 위의 순차탐색을 쓰는 구현과는 다르게 우선순위 큐를 사용하면 방문여부를 기록할 배열은 없애도 된다. 우선순위 큐가 알아서 최단거리의 노드를 앞으로 정렬하므로 기존 최단거리보다 크다면 무시하면 그만이다. 만약 기존 최단거리보다 더 작은 값을 가지는 노드가 있다면 그 노드와 거리를 우선순위 큐에 넣는다. 우선순위 큐에 삽입되는 형태는 <거리,노드>

def dijkstra(start):
	q = []
	heapq.heappush(q,(0,start))
	distance[start] = 0
	while q:
		dist, node = heapq.heappop(q)
		if distance[node]<dist:
			continue
		for next in graph[node]:
			cost = distance[node] + next[1]
			if cost < distance[next[0]]
				distance[next[0]] = cost
				heapq.heappush(q,(cost,next[0]))

플로이드 워셜

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘
• 단계마다 ‘거쳐가는 노드’를 기준으로 알고리즘을 수행한다. 하지만 매 단계마다 방문하지 않은 노드 중에서 최단거리를 갖는 노드를 찾을 필요가 없다.
• 2차원 테이블에 최단 거리 정보를 저장한다.
• DP알고리즘에 속한다
• 노드 개수가 N이라고 할 때, N번만큼의 단계를 반복하며 ‘점화식에 맞게’ 2차원 리스트를 갱신하기 때문에 DP라고 볼 수 있다.
• 시간복잡도 O(N^3)

크루스칼(Kruskal)

• 탐욕적인 방법(greedy method)을 이용하여 네트워크(가중치 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것
  • 탐욕적인 방법
    • 결정을 할 때마다 그 순간 가장 좋다고 생각 되는것을 선택함으로서 최종적인 해답에 도달하는 것
    • 탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야한다.
    • Kruscal 알고리즘은 최적의 해답을 주는 것으로 증명되었다.

동작

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
   1. 즉 가장 낮은 가중치를 먼저 선택한다.
   2. 사이클을 형성하는 간선을 제외한다.
3. 해당 간선을 현재의 MST의 집합에 추가한다.

특징

• 간선선택을 기반으로 하는 알고리즘
• 다음 간선을 이미 선택된 간선들의 집합에 추가할 때 사이클을 생성하는지 체크
  • 새로운 간선이 이미 다른 경로에 의해 연결되어있는 정점들을 연결할 때 사이클이 형성된다.
  • 즉, 추가 할 새로운 간선의 양 끝 정점이 같은 집합에 속해 있으면 사이클이 형성된다.
• 사이클 생성 여부를 확인하는 법
  • union-find 알고리즘 이용
• 시간복잡도
  • 간선 e개를 퀵정렬과 같은 효율적인 알고리즘으로 정렬한다면 O(eloge)
  • prim 의 알고리즘 시간복잡도는 O(n²)
    • 그래프 내 적은 숫자의 간선만을 가지는 ‘희소 그래프(Spares Graph)는 Kruskal
    • 그래프 내 간선이 많이 존재하는 ‘밀집 그래프(Dense Graph)’ 는 prim

Union-Find

• Disjoint Set을 표현할 때 사용하는 알고리즘
  • 서로 중복되지 않는 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
• 집합을 구현하는데 비트벡터, 배열, 연결리스트를 이용할 수 있으나 그 중 효율적인 트리구조를 이용하여 구현

연산

• make-set(x)
  • 초기화
  • x를 유일한 원소로 하는 새로운 집합을 만든다.
• union(x,y)
  • 합하기
  • x가 속한 집합과 y가 속한 집합을 합친다.
• find(x)
  • 찾기
  • x가 속한 집합의 대표값(루트노드값)을 반환한다. x가 어떤 집합에 속해있는지 찾는 연산
• 전체 집합이 있을 때 구성 원소들이 겹치지 않도록 분할 하는데 자주 사용

최악의 상황

• 트리 구조가 완전 비대칭인 경우
• 연결리스트 형태
• 트리의 높이가 최대가 된다.
• 원소의 개수가 N일 때, 트리의 높이가 N-1이므로 union과 find(x)의 시간복잡도가 모두 O(N)
• 배열로 구현하는것보다 비효율적이다.

Prim 알고리즘

• 시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법

동작

1. 시작 단계에서는 시작 정점만이 MST에 포함
2. 앞 단계에서 만들어진 MST집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
   1. 즉, 낮은 가중치를 먼저 선택한다.
3. 위의 과정을 트리가 (N-1) 개의 간선을 가질 때까지 반복한다.

• 정점선택을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 신장트리를 확장하는식