[알고리즘] 알고리즘 실용화

웹 개발자를 위한 대규모 서비스를 지탱하는 기술, 7장

대규모 서비스를 지탱하는 기술 - YES24

7장, 알고리즘 실용화

 

대규모 데이터를 현실적인 시간 내에 처리할 때, 적합한 알고리즘과 데이터 구조를 사용함으로써 시간을 크게 단축할 수 있다.

 

데이터가 클수록 알고리즘이나 데이터 구조 선택이 속도에 영향을 미친다. (ex. 이분탐색)

알고리즘?
어떤 값 또는 값의 집합을 입력으로 하고 어떤 값 또는 값의 집합을 출력으로 하는, 명확하게 정의된 계산절차

알고리즘은 디자인 패턴과 마찬가지로 엔지니어에게 공통언어이므로, 커뮤니케이션을 위해서도 올바르게 이해할 필요가 있다.

 

알고리즘의 평가에는 주로 Order 표기법을 사용한다.

Order 표기란, 대상이 되는 알고리즘이 입력 크기가 n일 때 대략적으로 이 정도의 계산량이 소요된다라는 것을 표기하는 기법이다.

• 주로 나타나는 표기: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³)  ... O(n**k) < O(2ⁿ) 
• 상수항을 무시한다.

실행시간이나 단계 횟수뿐만 아니라, 메모리 사용량을 논할 경우에도 Order 표기가 사용된다.

 

지수의 역인 대수적으로만 증가하는 O(log n)인 알고리즘은 데이터량이 꽤 커져도 적은 계산량으로 문제를 해결할 수 있다.

 

알고리즘은 데이터 구조와 세트로 많이 언급되는데, 알고리즘에서 자주 사용하는 조작에 맞춰 데이터 구조를 선택할 필요가 있기 때문이다. (ex. B+트리구조로 저장해두면 데이터의 탐색이 빠르다.)

 

Order 표기에는 상수항이 무시되는데, 그에 따라서도 시간의 차이가 존재하므로 그 부분도 잘 고려해야한다.

하지만 마냥 알고리즘의 최적화만을 고민하기보다는 그 이전에 프로그램의 문제를 제대로 측정하여 좋은 알고리즘을 선택하는 것이 중요하다.

 

하테나 북마크 Firefox 확장기능에서의 시행착오

검색 기능에서 많은 검색 빈도를 고려하여 suffix array구조를 사용했는데, 고속 검색을 위한 전처리 과정에 상당한 시간이 필요했다. 이 전처리 과정 때문에 머신에 부하도 많이 걸릴뿐더러 만족스러운 속도가 나오지 않았다. 이에 데이터량이 많은 사람이 오래 기다려야할지라도, 선형탐색을 하도록 변경했더니 오히려 문제 없이 사용할 수 있었다.

-> 예측/측정의 중요성. 데이터의 양에 대해 직감으로 판단하지 않기.

 

잘 만들어진 오픈 소스를 활용하면 공수를 줄일 수 있지만, 아예 내부 구조를 모르는 채로 사용하는 것은 좋지않다. 때론 적절한 스펙의 API가 존재하지 않아서 직접 구현하는 게 나을 때도 있다.

---

실제 사례

하테나 다이어리의 키워드 링크

블로그에 글을 작성하면, 일부 키워드에 자동으로 링크가 걸리는 기능.

 

기존 방법:

정규표현식을 사용하여 치환 옵션과 eval을 활용하여 구현. NFA(Nondeterministic Finite Automata) - 키워드에 비례하는 계산량.

문제:

키워드 수가 늘어나면서 정규표현식 처리에 많은 시간이 소요됨. 

해결 방법:

Trie(트라이)를 사용한 매칭 구현.

 

Trie?

• 트리구조의 일종인 데이터 구조.
• 탐색대상 데이터의 공통 접두사를 모아서 트리구조를 이룬다.
• 공통 접두사는 단 한 번 탐색으로 마칠 수 있게 된다.

나중에는 개선된 AC법을 사용함.

AC(Aho-Corasick)법?

• Trie에서의 패턴 매칭으로 매칭이 진행되다가 도중에 실패했을 경우, 되돌아오는 길의 엣지를 다시Trie에 추가한 데이터 구조를 사용하는 방식

최종적으로는 Regexp::List 사용

Regexp::List?

• Trie기반의 정규표현 라이브러리
• 공통 접두사나 접미사가 정리되어 있어 시행 횟수를 큰 폭으로 줄일 수 있다.
• 계산량을 줄일 뿐만 아니라, 정규표현으로 사용할수 있다는 장점 -> 유연성

 

하테나 북마크의 기사 분류

베이지안 필터에 의한 카테고리 판정

베이지안 필터?

나이브 베이즈(Naive Bayes)알고리즘을 사용하여 해당 문서가 어느 카테고리에 속하는지 판정하는 프로그램.

정답이 되는 정해 데이터를 주고 학습시켜 수동으로 개입하지 않고 정해를 알 수 있게 되는 프로그램. -> 기계학습, 패턴인식

 

GPT에게 물어보자!

 

 

유사 기능

• 하테나의 관련 엔트리 기능 - 특정 기사와 매우 비슷한 다른 관련정보를 사용자에게 제시하는 기능
• Google의 검색어 수정 기능

나이브 베이즈

조건부 확률

P(C|D) = P(D|C) P(C) / P(D)

특정 문서 D가 주어졌을 때, 어떤 카테고리 C에 속하는 조건부 확률을 구하는 것.

P(D)는 무시할 수 있고, P(D|C) P(C)만 고려하면 되어 간단해진다.

 

실제로 실무에 적용할 때에는 고려할 점이 많다.

 

수비 /  공격 ?

수비적인 자세 - 데이터 정렬, 검색, 압축

공격적인 자세 - 기계학습, 패턴인식 등두 가지 자세를 모두 알고 있어야한다.

 

스펠링 오류 수정기능

1. 단어 정해 사전 만들기

2. 편집거리를 구해 오류 정도를 정량화 하기

3. 일정한 오류 정도를 기준으로 사전 내에 있는 단어군을 정해 후보로 얻어내기

4. 정해 후보를 단어 이용빈도를 기준으로 정렬하기

5. 가장 이용빈도가 높은 단어를 정해로 간주하고 이용자에게 제시하기