Wisdoms131 메모리 룩업 테이블 구성(cache) 가장 빠른 방식은 배열이다. 이 방식은 요소의 갯수가 적을 때 유용하다. 다만, 이 배열 방식은 키에 해당 하는 값의 상한 값 만큼의 메모리를 요구한다. uint64_t look_up[64]; 상한 값이 큰 경우에는 해시맵을 이용할 수 있다. 키와 값 쌍을 선언하면 된다.hash_map look_up; 다른 방법으로는 pair의 배열이나 벡터를 생성하고 이를 정렬한 후에 이진 검색하는 방법이 있다. #include #include #include #include #include const int N = 16000; typedef std::pair CALC; CALC calc[N]; static inline bool cmp_calcs(const CALC &c1, const CALC &c2) { return.. 2014. 9. 5. Lightweight BWT Construction for Very Large String Collection 핵심 부분 이 알고리즘은 대량의 서열 정보로 부터 BWT된 FM-index를 생성할 수 있도록 해주는 알고리즘을 제안한다. 그중 세 저자의 이름을 따서 하나는 BCR (Markus J. Bauer-Anthony J. Cox-Giovanna Rosone), 그것의 확장된 버전은 BCRext라고 부른다. 처음에는 해당 논문의 번역 내용을 올릴려고 했으나, 완전히 이해하고 쉽게 풀어서 설명하는 것이 더 나은 듯 하여 여기에 정리해 둔다. 구현은 BEETL이라는 라이브러리에서 최초 등장했다. BCR 알고리즘 먼저 입력된 서열에 대해 행을 열로 바꾸는(transpose) 연산을 수행한다. 그리고 가장 뒤에 있는 염기에서 부터 한 염기씩 진행해가면서 처리하는데, 이를 횟수라고 하자. 알고리즘은 입력 서열 중 가장 긴 길이의 .. 2014. 8. 15. In-place hybrid Binary-Radix sort 번역 본 내용은 http://www.drdobbs.com/architecture-and-design/algorithm-improvement-through-performanc/220300654의 내용을 번역한 것이다. 기수(radix) 소팅 알고리즘은 배열의 요소들을 서로 비교하지 않기 때문에 비교 기반의 O(nlogn) 성능 제약에 걸리지 않는다. 사실, 그들은 O(kn)의 선형 성능을 가진다. 기수(radix) 정렬은 배열 요소 값의 최상위 숫자(most significant digit, MSD) 혹은 최하위 숫자(least significant digit, LSD) 한 숫자 값만을 취해서 처리한다. 예를 들어, 다음의 두자리 숫자를 정렬하기 하려면 다음과 같이 한다. 각 숫자들을 최상위 숫자값(10의 자리.. 2014. 8. 12. 상수 공간 비교 기반 버로우즈 휠러 변환 원 논문의 제목은 A Constant-Space Comparison-Based Algorithm for Computing the Burrows–Wheeler Transform이다. 원문 내용의 2절의 일부는 다음과 같다. 다음 내용은 0-index 기반이다. 즉, 문자열에서 첫 문자는 index 0을 가진다. 가령, T='temp'에서 T[0] == 't'이고, T[3] == 'p'이다. Given the input text T = T [0 ..n−1] where T [n−1] = $, moving a single character inside T can change the content of many suffixes. The idea to circumvent this difficulty without .. 2014. 8. 7. 이전 1 ··· 13 14 15 16 17 18 19 ··· 33 다음
