알고리즘/기타 (4) 썸네일형 리스트형 Strong Connected Component - Gabow 알고리즘 Strong Connected Components(이하 SCC)를 구하기 위한 몇가지 알고리즘이 있는데, 그중에서 Gabow의 알고리즘은 간단하게 살펴보겠습니다. SCC를 구하는 알고리즘은 Gabow이외에도 여러가지가 있는데, 대표적으로 Kosaraju 알고리즘과 Tarjan 알고리즘이 있습니다. Kosaraju 알고리즘과 Tarjan 알고리즘이 궁금하다면 각각 다음 블로그를 참조하는 것을 추천드립니다. https://wondy1128.tistory.com/130 SCC-코사라주 알고리즘(Kosaraju's Algorithm) 방향 그래프(Directed Graph) 에서 SCC (Strongly Connected Component) 를 코사라주 알고리즘을 이용해 구하는 방법이다. ① 주어지는 방향 그래.. Level Compressed Trie lc-trie는 학부시절 네트워크 시간에 배운 longest prefix matching(이하 lpm) 을 효율적으로 하기 위해 만들어진 알고리즘입니다. 네트워크에서 lpm은 서브넷팅된 IP 대역대를 prefix에 따라 다음 hop을 탐색하기 위해 사용됩니다. 이런 lpm을 효율적으로 수행하기 위해서 고안된 lc-trie는 커널에서도 lpm을 위해 사용되는 자료구조입니다. 위 그림은 일반적인 이진트리로 특히 0,1 비트로 이루어진 IP주소를 탐색하기 용이한 자료구조입니다. 루트에서 시작하여 하나의 비트씩 비교하며 노드를 탐색하여 prefix 더 이상 진행하지 못하면 해당 노드의 next 값을 반환합니다. 오른쪽 트리는 path를 compress를 수행한 구조입니다. patricia trie라고 합니다. .. Rate Limiting Algorithm (Leaky Bucket) 실제 많은 서비스에서 인프라의 availability를 위해 단위 시간안에 수많은 요청이 들어오는 걸 방지하는 로직은 필수적이다. 예를 들면, 카카오톡으로 메시지를 보낼 때, 순간적으로 많은 메시지를 보내면 나오는 경고문이나, 하루에 1000건 이상 request를 받지 않는 서비스 등 다양한 방법에서 사용한다. 이는 인프라의 availability에 직접적인 관여를 하는 클라우드 환경에서도 필수적인 요소인데, 대게는 네트워크 트래픽을 컨트롤 하는 데 있어서 많은 연관을 가지고 있다. 이러한 Rate Limiting Algorithm에는 여러가지 기법들이 존재하지만 이번에는 leaky bucket 알고리즘을 다룰 것이다. Leaky Bucket Algorithm leaky bucket 알고리즘은 물 새는.. Sorting Algorithm for Hardware Acceleration Sorting이란? 순서가 없는 value들을 특정 order(Numerical order, Lexicographical order 등)들을 기준으로 자료를 재배열 하는 것을 의미한다. clustering / searching / scheduling / network / calculation / simulation 등등 탐색에 기반을 둔 모든 task를 수행하는 데 많은 리소스를 절약할 수 있다. 소팅 알고리즘은 exchange, selection, insertion, merge, distribution, concurrent, hybrid 등으로 분류할 수 있다. 이번 발표에서는 정리해 볼 소팅 알고리즘 heap: 온라인 환경에서 sram/dram에서 stream data 연산에 효율적인 internal.. 이전 1 다음
