Dev.Basic (54) 썸네일형 리스트형 Sorting Algorithm을 비판적으로 바라보자. Sorting Algorithm을 비판적으로 바라보자.#1. 첫번째 의문 quick sort가 가장 좋고 빠르다며, 그래서 이름도 quick sort라며! 그런데 heap sort, merge sort는 왜 존재하며 왜 필요하지?어디에 쓰이고 있길래 살아남은 거지? 세 sorting algorithm(Quick sort, Merge sort, Heap sort)의 expected-Time Complexity는 O(n log n)으로 모두 동일하다. 하지만 Space Complexity는 merge sort만 Sorting하고자 하는 데이터의 크기 만큼이다. 그러면 일단 heap sort는 그렇다치고, 어떻게 Merge Sort가 살아남았을까? 한정된 메모리 상황에서 ‘빅 데이터'를 Sorting 해야하는.. RDB 성능 이슈 2. Transaction RDB 성능 이슈 2. Transaction 트랜잭션이란 무엇인가?트랜잭션은 작업의 완전성을 보장해주는 것이다.즉, 논리적인 작업 셋을 모두 완벽하게 처리하거나 또는 처리하지 못할 경우에는 원 상태로 복구해서 작업의 일부만 적용되는 현상이 발생하지 않도록 만들어주는 기능이다. 사용자의 입장에서는 작업의 논리적 단위로 이해를 할 수 있고 시스템의 입장에서는 데이터들을 접근 또는 변경하는 프로그램의 단위가 된다. 트랜잭션과 Lock은 어떤 관계인가?잠금(Lock)과 트랜잭션은 서로 비슷한 개념 같지만 사실 잠금은 동시성을 제어하기 위한 기능이고 트랜잭션은 데이터의 정합성을 보장하기 위한 기능이다. 잠금은 여러 커넥션에서 동시에 동일한 자원을 요청할 경우 순서대로 한 시점에는 하나의 커넥션만 변경할 수 있게 .. RDB 성능 이슈 1. Index란 RDB 성능 이슈 #1 데이터베이스의 성능 이슈는 디스크 I/O를 어떻게 줄이느냐에서 시작된다. 디스크 I/O란 디스크 드라이브의 플래터(원판)을 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것을 의미한다. 이 때 데이터를 읽는데 걸리는 시간은 디스크 헤더를 움직여서 읽고 쓸 위치로 옮기는 단계에서 결정된다. 즉 디스크의 성능은 디스크 헤더의 위치 이동 없이 얼마나 많은 데이터를 한 번에 기록하느냐에 따라 결정된다고 볼 수 있다. 그렇기 때문에 순차 I/O가 랜덤 I/O보다 빠를 수 밖에 없다. 하지만 현실에서는 대부분의 I/O 작업이 랜덤 I/O 이다. 랜덤 I/O를 순차 I/O로 바꿔서 실행할 수는 없을까? 이러한 생각에서부터 시작되는 데이터베이스 쿼리 튜닝은 .. [DataStructure] hashcode와 HashMap에 대해서 Hash Code와 HashMapHashMap는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. 특정한 값을 Searching 하는데 데이터 고유의 인덱스로 접근하게 되므로 Time Complexity가 O(1)이 되는 것이다. 그리고 데이터의 삽입과 삭제 시 기존 데이터를 밀어내거나 다시 채우는 작업이 필요없도록 '특별한 알고리즘'을 이용하여 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 삽입 시 다른 데이터의 사이에 끼어들거나 삭제 시 다른 데이터로 채울 필요가 없으므로 추가적인 데이터의 이동이 없다. `특별한 알고리즘`이란 것을 통해 고유한 인덱스 값을 설정하는 것이 중요해보인.. #Transport Layer, TCP vs UDP #Transport Layer, TCP vs UDP인터넷은 트랜스포츠 계층에 연결형 프로토콜과 비연결형 프로토콜, 이렇게 두 개의 주된 프로토콜을 갖는다. UDP UDP(User Datagram Protocol, 사용자 데이터그램 프로토콜)는 비연결형 프로토콜이다. IP 데이터그램을 캡슐화하여 보내는 방법과 연결 설정을 하지 않고 보내는 방법을 제공한다. UDP는 흐름제어, 오류제어 또는 손상된 세그먼트의 수신에 대한 재전송을 하지 않는다. 이 모두가 사용자 프로세스의 몫이다. UDP가 행하는 것은 포트들을 사용하여 IP 프로토콜에 인터페이스를 제공하는 것이다. UDP가 특별히 유용한 분야는 클라이언트-서버 상황이다. 종종 클라이언트는 서버로 짧은 요청을 보내고, 짧은 응답을 기대한다. 만약 요청 또는 .. [Sorting] 5. Non-Comparison Sorting - Counting Sort, Radix Sort non - Comparisons Sorting AlgorithmCounting SortSpace Complexity : in-place 알고리즘이 아니다. buffer를 필요로 한다.Time Complexity : O(n + k)Radix Sort에 대해 알아보기 전에 Count Sort에 대해서 먼저 알아보자. Count Sort에서 사용된 알고리즘이 Radix Sort에서 사용된다. 즉 Radix Sort는 Count Sort의 확장판이라고 할 수 있다. Count Sort는 말 그대로 몇 개인지 개수를 세어 정렬하는 방식이다. 정렬하고자 하는 값 중 최대값에 해당하는 값을 size로 하는 임시 배열을 만든다. 만들어진 배열의 index 중 일부는 정렬하고자 하는 값들이 되므로 그 값에는 그 값들의 .. [Sorting] 4. Heap, Heapify, Heap Sort Heap SortSpace-Complexity = In-place sort : O(1)의 보조 메모리를 사용한다. Time-Complexity = O(n log n) 원리heap 자료구조를 활용할 Sorting 방법에는 두 가지 방법이 존재한다. 하나는 정렬의 대상인 데이터들을 힙에 넣었다가 꺼내는 원리로 Sorting을 하게 되는 방법이고, 나머지 하나는 기존의 배열을 heapify(heap으로 만들어주는 과정)을 거쳐 꺼내는 원리로 정렬하는 방법이다. Heap 자료구조란?자료구조의 일종으로 Tree의 형식을 하고 있으며, Tree 중에서도 배열에 기반한 Complete Binary Tree 이다. 배열에 트리의 값들을 넣어줄 때, 0번째는 건너뛰고 1부터 루트노드가 시작된다. 이는 노드의 고유번호 값.. [Sorting] 3. Quick Sort Quick SortSpace-Complexity = In-place sort : O(1)의 보조 메모리를 사용한다. Time-Complexity = O(n log n) Sorting기법 중 가장 빠르다고 해서 quick이라는 이름이 붙여졌다. 하지만 Worst Case에서는 시간복잡도가 O(n^2)가 나올 수도 있다. 하지만 constant factor가 작아서 속도가 빠르다. 원리Quick Sort 역시 Divide and Conquer 전략을 사용하여 Sorting이 이루어진다. Divide 과정에서 pivot이라는 개념이 사용된다. 입력된 배열에 대해 오름차순으로 정렬한다고 하면 이 pivot을 기준으로 좌측은 pivot으로 설정된 값보다 작은 값이 위치하고, 우측은 큰 값이 위치하도록 partit.. 이전 1 2 3 4 5 ··· 7 다음
