임베디드/Algorithm2009. 1. 29. 10:14

http://sweeper.egloos.com/



Posted by 삼스

댓글을 달아 주세요

  1. 좋으면 좋고 싫으면 싫은 거지, 뭐가 이렇게 어렵고 복잡하냐구

    2013.07.11 01:43 [ ADDR : EDIT/ DEL : REPLY ]

임베디드/Algorithm2009. 1. 29. 10:09

출처 -> http://sweeper.egloos.com/921858

정렬 알고리즘 정리

1. 비교 정렬 리스트

아래 테이블에서 n은 개체수이고 k는 키들의 평균적인 길이이다. 클릭해서 보도록...

연결 리스트를 머지 소트할 경우는 메모리 차지가 O(1)로 줄어들게 된다.

2. !비교 정렬 리스트

n = 개체수
k = 각 key의 크기
s = 구현에 사용된 chunk 크기

비교 정렬이 아닌 알고리즘들은 O(n(log n))의 lower bound 제한에 걸리지 않는다. 즉, O(n(log n))보다 더 좋은 성능을 낼 수도 있다. 하지만 기수 정렬(Radix sort)을 예로 설명하면 키의 크기가 제한적일 때 성능이 좋아지는 등, 여러 가지 제약이 있다.

3. Memory usage patterns and index sorting

정렬해야 될 데이터가 물리 메모리의 한계를 넘어서면 디스크 스왑을 사용해야 하는데, 이 경우 RAM 영역에서 효과적으로 정렬되던 방식들이 사실상 비현실적일 정도로 성능을 내지 못할 수 있다. 이 상황에서는 비교 횟수 보다 swap 등 데이터의 이동 회수가 훨씬 중요하게 여겨져 복사나 값 교환 작업이 알고리즘의 성능을 좌우하게 된다.

예를 들어 가장 인기있는 퀵 소트 알고리즘은 RAM 영역에서 상당히 만족스러운 성능을 제공하지만 리스트의 일부를 복사하는 순환 방식 때문에 디스크 상에서는 상당히 비효율적인 알고리즘이 된다. 고로 더 많은 비교 회수를 요구하더라고 좀 더 적합한 알고리즘을 사용해야 한다.

위 같은 상황을 극복할 수 있는 방법을 살펴보자.

(관계형 데이터베이스에서와 같은) 복합 레코드들을 key 값으로 정렬하듯이, 리스트 자체를 정렬하지 말고 인덱스를 만들어 그 인덱스로 정렬을 하는 방법이 있다. 인덱스는 전체 리스트보다 훨씬 작으므로 전체 물리 메모리에 못 들어갈 데이터들을 RAM 영역에서 정렬할 수 있으며 효과적으로 디스크 스와핑을 없앨 수 있다. 이 과정은 종종 "tag sort"라 불리기도 한다.

메모리 한계를 극복하는 또 다른 방법은 전체적인 성능 향상을 위해 두 알고리즘의 강점을 조합하는 것이다. 예를 들어 배열은 RAM 영역에 쉽게 포함될 수 있는 크기 단위로 나뉘어 질 수 있을 것이고 나뉘어진 분할 리스트들을 각기 퀵 소트나 힙 소트로 정렬한다. 그리고 정렬된 분할 리스트들을 머지 소트로 병합하는 것이다. 이렇게 하면 머지 소트만 하는 것보다 성능이 뛰어나며 퀵 소트만 하는 것 보다 작은 물리 메모리를 필요로 하게 된다.  


  • [기수 정렬] 정렬 알고리즘 중 radix sort를 C#으로 구현한 프로그램. by 브렉스톤
  • 최적 자료구조 선택의 어려움 by object
  • 프로그래머를 위한 공부론 by ssulsamo
  • 프로그래밍 공부론 펌 by wrpark
  • 같은 이름을 가진 것이 있다면 일반 알고리즘보다 멤버 함수가 더 낫다. by 쌩쥐 
  • Posted by 삼스

    댓글을 달아 주세요

    1. 다른 남자 부르면서 울거면 나한테 이쁘지나 말던지

      2013.07.18 06:12 [ ADDR : EDIT/ DEL : REPLY ]

    임베디드/Algorithm2009. 1. 29. 10:05

    1. Hash

    데이터를 저장하고 찾는데 사용되는 자료 구조의 한 종류. 찾고자 하는 문자열을  특정한 함수(hash function)로 처리해 얻은 값으로 데이터의 위치를 찾는 방법을 말한다.

    데이터를 찾는 속도가 데이터 개수의 영향을 거의 받지 않는 특성을 지니고 있어, 효율적이고 빠르게 데이터의 위치를 찾을 수 있다. 다른의미로 데이터베이스에서 임의의 레코드를 빠르게 찾아가기 위한 직접 파일 구조를 말하기도 한다.


    2. Hash table

    레코드를 한 개 이상 보관할 수 있는 버킷들로 구성된 기억공간을 말한다. 레코드들을 보조 기억 공간에 저장할 때는 그 공간 내의 주소와 레코드 키를 한 단위로 해시 테이블에 보관하고, 이 해시 테이블을 주기억 공간에 보관하기도 한다.

    참고) 버킷(Bucket) : 어떤 종류의 레코드를 몇 개씩 묶은 것을 기억하는 장소이다. 이 경우 주소는 1버킷에 1개만 붙인다. 또 다른 의미로 여러개의 데이터를 어떤 기준에 의해 묶을 때 같은 부류에 속하는 데이터들의 모임을 말한다.

    해시 테이블의 시작 주소로부터 각 버킷들은 연속된 주소를 가지며 그 시작 주소를 기준으로 상대 주소를 산출할 수 있으므로 이 상대 주소를 이용하여 각 버킷들을 구별하면 편리하다.


    3. Hashing

    여러개의 명칭(identifier)들이 무작위로 들어있는 테이블에서 특정 명칭을 찾고자 하는 경우 원하는 키값을 가지는 테이블 항목을 검색하기 위해 특정한 변환 함수를 이용하여 키값을 항목 의 주소로 직접 바꿔서 검색하는 방법을 해슁이라 한다. 이때 변환 함수는 해쉬 함수(hash function)라 한다.

    명칭 테이블에서 키 값과 일치하는 명칭을 찾는 방법으로는 테이블에 있는 각각의 명칭을 키 값과 차례로 비교하는 방법이 있다. 이 방법을 사용하면 최악의 경우 n회의 비교가 필요하다. 해슁을 이용하면 해쉬 함수가 키값을 해당 주소로 단번에 변환해 주므로 매우 빠른 검색이 가능하다.

    정적 해싱은 고정 크기의 테이블을 이용하여 해슁하는 방법으로서 한번 저장된 명칭의 상대적 위치가 변경되지 않는다. 해싱을 이용하지 않는 경우에는 명칭들의 모든 가능한 조합을 수용할 수 있도
    록 명칭 테이블을 만들어야 한다.

    조합 가능한 명칭들 중에 실제로 존재하는 명칭들의 수는 매우 적기 때문에 대부분의 공간은 낭비된다. 명칭 테이블의 기억공간 낭비를 막기 위해 해쉬 테이블을 사용한다. 해쉬 테이블은 b개의 버켓(bucket)으로 구성되고, 하나의 버켓은 s개의 슬롯(slot)으로 구성된다. 각각의 슬롯에는 명칭 테이블 항목처럼 하나의 명칭이 저장된다.

    해쉬 테이블의 크기는 필요에 따라 달리할 수 있는데 일반적인 명칭 테이블보다는 크기가 현저히 작다. 하나의 버켓에 여러개의 슬롯을 두는 이유는 서로 다른 두개의 명칭이 해쉬 함수에 의해 동일한 주소로 변환되는 경우 두 명칭을 같은 버켓에 저장하기 위해서이다.

    해슁을 하는 경우 서로 다른 두개 이상의 명칭이 해쉬 함수에 의해 동일한 주소로 변환되는 경우가 있다. 이 현상을 "충돌(collision)"이라 한다. 충돌이 자주 발생하면 탐색 시간이 길어지는 등 성능이 저하되므로 해쉬 함수를 수정하거나 해쉬 테이블의 크기를 적절히 조절해 주어야 한다.

    충돌이 발생한 경우 같은 버켓에 있는 다른 슬롯에 명칭을 저장하면 된다. 그러나 슬롯의 갯수만큼 충돌이 생기면 빈 슬롯이 소진되어 오버플로우(overflow)가 생길 수 있다. 오버 플로우가 발생하면 해슁에 의해 원하는 명칭을 찾을 수 없게 되므로, 오버 플로우를 해결하기 위한 방법이 고안되어야 한다.

    *********************************************************************************

    덧붙이자면, Hash는 우체국에 분리된 우편물들이라고 볼 수 있다.

    각 주소는 key가 되고 우편 번호는 backet이 된다.

    Posted by 삼스

    댓글을 달아 주세요

    1. 미안하지만, 실제 가입 버튼이 있습니까? 감사

      2013.02.01 07:45 [ ADDR : EDIT/ DEL : REPLY ]
    2. 당신 매력있어, 자기가 얼마나 매력있는지 모르는게 당신매력이야

      2013.07.12 12:43 [ ADDR : EDIT/ DEL : REPLY ]