'전체 글'에 해당되는 글 20건

버블 정렬

  버블 정렬은 선택 정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복한다.

단 선택 정렬이 가장 큰 수를 찾은 다음 맨 오른쪽 수와 바꾸는 반면, 버블 정렬은 왼쪽부터 이웃한 수를 비교하면서 순서가 제대로 되어있지 않으면 하나하나 바꾸어나간다. 

버블 정렬 구현

public class BubbleSort {
    public static void main(String[] args) {
        int[] arrays = new int[]{8, 31, 48, 73, 3, 65, 20, 29, 11, 15};
        int temp;
        int size = arrays.length;

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size - 1 - i; j++) {
                if (arrays[j] > arrays[j + 1]) {
                    temp = arrays[j];
                    arrays[j] = arrays[j + 1];
                    arrays[j + 1] = temp;
                }
            }
        }
    }
}

선택 정렬

  선택 정렬은 원리가 간단한 정렬 알고리즘 중 하나이다. 배열에서 가장 큰 원소를 찾아 이 원소와 배열의 끝자리에 있는 원소와 자리를 바꾼다. 그러면 방금 맨 뒷자리로 옮긴 원소, 즉 가장 큰 원소는 자기 자리를 찾았으므로 더 이상 신경 쓰지 않는다. 가장 큰 원소는 정렬이 끝났다고 볼 수 있으므로 이 원소를 제외한 나머지 원소들도 같은 작업을 반복하여 정렬한다.

선택 정렬 구현

public class SelectionSort {

    public static void main(String[] args) {
        int[] arrays = new int[]{2, 3, 4, 5, 1, 8, 7, 6, 9};

        int max;
        int idx;
        int temp;

        for (int i = arrays.length - 1; i >= 0; i--) {
            max = arrays[i];
            idx = i;
            for (int j = i - 1; j >= 0; j--) {
                if (arrays[j] > max) {
                    max = arrays[j];
                    idx = j;
                }
            }
            temp = arrays[i];
            arrays[i] = arrays[idx];
            arrays[idx] = temp;
        }
    }
}

그래프란? 

 현상이나 사물을 정점과 간선으로 표현하는 것으로, 정점(Vertex)은 대상이나 개체를 나타내고 간선(Edge)은 이들 간의 관계를 나타낸다. 

사람 간에 친밀도 표현, 두 도시를 연결하는 도로의 존재 여부, 두 집안 간의 혼인 여부 등을 나타낼 수 있다. 

간선의 방향이 없는 그래프를 무향 그래프(Undirected Graph) 또는 무방향 그래프라고 하며, 

간선의 방향이 있는 그래프를 유향 그래프(Directed Graph) 또는 방향을 가진 그래프라고 한다. 

n 개의 정점 집합 V와 이들 간에 존재하는 간선의 집합 E로 구성된 그래프 G를 보통 G=(V, E)로 표시한다. 

그래프의 표현방법

인접 행렬, 인접 리스트,인접 배열과 인접 해시 테이블을 이용한 방법 등이 있다.

1.  인접 행렬을 이용한 방법

 그래프 G=(V,E)에서 정점의 총수가 n이라고 하고, n x n 행렬을 준비한다. 정점 i와 정점 j 간에 간선이 있으면 행렬의 (i, j) 원소와 (j, i) 원소의 값을 1로 할당한다. 

• 장점: 이해하기 쉽고 간선의 존재 여부를 즉각 알 수 있다.
• 단점: n x n 행렬이 필요하므로 n제곱에 비례하는 공간이 필요하고, 행렬의 준비 과정에서 행렬의 모든 원소를 채우는 데만 n제곱에 
  비례하는 시간이 든다. 

2. 인접 리스트를 이용한 방법

 각 정점에 인접한 정점들을 리스트로 표현하는 방법이다. 각 정점마다 리스트를 하나씩 만든다. 여기에 각 정점에 인접한 정점들을 연결 리스트로 추가한다. 

• 장점: 공간이 간선의 총수에 비례하는 양만큼 필요하므로 대체로 행렬 표현에 비해 공간의 낭비가 없다. 모든 가능한 정점 쌍에 비해 간선의 수가 적을 때 특히 유용하다. 
• 단점: 정점 i 와 정점 j 간에 간선이 존재하는지 알아볼 때 리스트에서 차례대로 훑어야 하므로 인접 행렬 표현보다는 시간이 많이 걸린 z다. 특히 간선이 많은 경우에는 최악의 경우 n에 비례하는 시간이 들 수도 있다. 

3. 인접 배열과 인접 해시 테이블

인접배열

각 정점에 연결된 정점들을 연결 리스트로 저장하는 대신 배열로 저장한다. 각 정점의 인접 배열 해더에 인접 정점이 몇 개인지 표시하여 탐색을 쉽게 할 수 있다.

• 장점: 연결 리스트의 포인터를 관리하는 번거로움에서 해방될 뿐만 아니라 두 정점의 인접 여부를 체크하는 시간도 대폭 줄일 수 있다. 
• 단점: 다루어야 할 그래프가 엄청난 크기이면 크게 차이 없다.

해시 테이블

인접 배열을 해시 테이블로 대체할 수 있다. 각 인접 배열 크리를 더해 필요한 전체 배열 크기를 다 계산한 다음 하나의 배열을 할당받는다.

각 헤더에는 자신의 인접 배열이 끝나는 자리를 표시해둔다. 

• 장점: 각 인접 배열 크기의 두 배 정도의 공간을 할당하여 적재율을 0.5로 만들어 평균 2번 이내의 비교로 가능하다.
• 단점: 어떤 정점에서 인접한 정점들을 차례로 보면서 작업을 해야 할 경우는 적합하지 않다.

출처: [쉽게 배우는 알고리즘]

아래 내용은 쿠버네티스 공식 홈페이지의 Kubernetes Scheduler의 내용을 일부 정리한 글입니다. 

쿠버네티스에서 스케줄링이란? 

• Kubelet이 실행할 수 있도록 nodes와 pods를 매치시켜주는 것을 말합니다. 

스케줄링

• 스케줄러가 node에 할당되지 않는 신규 생성된 pods가 있는지 주시합니다.

• 스케줄러가 node할당이 필요한 pod을 발견했다면, pod을 실행할 수 있는 최적의 node를 찾는 작업을 진행합니다.

• 스케줄러는 스케줄링 원칙을 고려하여 node를 결정합니다. 

kube-scheduler

• 쿠버네티스의 기본 스케줄러이며, 컨트롤 플레인(control plane)에 속해 있습니다.

• 커스텀 스케줄러를 추가하여 대체할 수 있도록 설계되어 있습니다.

• pods에 있는 모든 컨테이너들 및 모든 pod들이 리소스에 대해 각기 다른 요구사항을가지고 있기 때문에,
  상세 스케줄링 요구사항들에 따른 nodes 필터링이 필요합니다.

• 클러스터에서는 상세 스케줄링 요구사항에 맞는 노드를 적합한 노드들(feasible nodes)이라고 칭합니다.

• 적합한 node가 없는 pod은 스케줄러가 적합한 위치를 찾아주기 전까지 unscheduled 상태로 남아있습니다.

• 스케줄러가 적합한 nodes을 찾은 후에는 Scoring을 위해 사전에 정의된 함수들을 이용하여 nodes의 점수를
  계산하고 가장 높은 점수를 받은 node를 선정하여 API 서버에 알립니다. 이러한 과정을 binding 한다고 합니다.

• 스케줄링 시 고려하는 내용들

  • individual and collective resource requirements

  • hardware

  • software

  • policy constraints

  • affinity and anti-affinity specifications

  • data locality

  • inter-workload interference

  • etc

kube-scheduler의 스케줄링

kube-scheduler는 pod을 위한 node 선정 시 2 단계 과정을 거칩니다.

1. Filtering: pod에 적합한 nodes를 찾는 작업

2. Scoring: Filtering 에 의해서 찾아진 노드들 중 가장 적합한 nodes를 선별하는 작업

https://kubernetes.io/docs/concepts/scheduling/kube-scheduler/