# 컴퓨터 과학자들이 효율적인 새로운 계산 방법 발명

> Clean Markdown view of GeekNews topic #14865. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=14865](https://news.hada.io/topic?id=14865)
- GeekNews Markdown: [https://news.hada.io/topic/14865.md](https://news.hada.io/topic/14865.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2024-05-17T22:34:23+09:00
- Updated: 2024-05-17T22:34:23+09:00
- Original source: [quantamagazine.org](https://www.quantamagazine.org/computer-scientists-invent-an-efficient-new-way-to-count-20240516/)
- Points: 2
- Comments: 1

## Topic Body

### 새로운 효율적인 카운팅 알고리즘 개발

#### 소개
- 상상해보세요, 여러분이 원시림에서 야생 동물 센서를 수행하고 있음.
- 디지털 카메라로 동물 사진을 찍고, 중복되지 않은 동물의 수를 알고 싶음.
- 기존 방법은 모든 동물을 기억하고 비교해야 하지만, 이는 비효율적임.

#### 문제 상황
- 페이스북 같은 대규모 플랫폼에서는 매일 로그인하는 고유 사용자의 수를 세는 것이 어려움.
- 최근 컴퓨터 과학자들이 긴 목록에서 고유 항목 수를 추정하는 새로운 방법을 제안함.
- 이 알고리즘은 적은 수의 항목만 기억하면 됨.

#### CVM 알고리즘
- CVM 알고리즘은 40년 넘게 연구된 고유 요소 문제를 해결하는 중요한 단계임.
- 이 알고리즘은 데이터 스트림에서 고유 요소의 수를 효율적으로 추정할 수 있음.
- "새로운 알고리즘은 놀랍도록 간단하고 구현하기 쉬움" - 앤드류 맥그리거

#### 예시: 햄릿 오디오북
- 햄릿에는 30,557개의 단어가 있음. 이 중 몇 개가 고유한지 알아보려면 모든 단어를 기억해야 함.
- CVM 알고리즘은 랜덤화를 사용하여 메모리 사용을 줄임.

#### CVM 알고리즘의 작동 방식
- 첫 번째 라운드: 100개의 단어를 기록하고, 중복 단어는 코인 토스로 삭제.
- 두 번째 라운드: 중복 단어를 더 어렵게 유지하기 위해 두 번의 코인 토스 필요.
- 세 번째 라운드: 세 번의 코인 토스 필요.
- k번째 라운드까지 반복하여 고유 단어 수를 추정함.

#### 정확도 검증
- 메모리 크기에 따라 정확도가 달라짐.
- 햄릿의 고유 단어 수는 3,967개로, 메모리 100개로 평균 추정치는 3,955개, 메모리 1,000개로 평균 추정치는 3,964개임.

#### 결론
- "기본적이고 잘 연구된 문제에도 간단하지만 비직관적인 해결책이 존재함" - 윌리엄 쿠즈마울

### GN⁺의 의견
- **데이터 스트리밍 상황에서 유용함**: CVM 알고리즘은 대규모 데이터 스트림에서 고유 항목을 효율적으로 추정할 수 있어 실시간 분석에 유용함.
- **메모리 효율성**: 메모리 사용을 최소화하면서도 높은 정확도를 유지할 수 있어, 메모리 제약이 있는 환경에서 특히 유리함.
- **랜덤화의 중요성**: 랜덤화를 통해 복잡한 문제를 간단하게 해결할 수 있다는 점에서, 다른 분야에서도 응용 가능성이 큼.
- **기술 도입 고려사항**: 이 알고리즘을 도입할 때는 메모리 크기와 정확도 간의 균형을 고려해야 함. 메모리가 충분하지 않으면 정확도가 떨어질 수 있음.
- **관련 기술**: HyperLogLog와 같은 다른 고유 요소 추정 알고리즘과 비교해볼 가치가 있음. 각 알고리즘의 장단점을 파악하여 상황에 맞는 최적의 솔루션을 선택하는 것이 중요함.

## Comments



### Comment 25339

- Author: neo
- Created: 2024-05-17T22:34:24+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=40379175) 
##### 해커뉴스 댓글 모음 요약

* **HyperLogLog와 유사한 알고리즘**  
  HyperLogLog와 유사한 알고리즘으로, 동전 던지기의 연속성을 이용해 간단한 알고리즘을 설명함. 특히 스트리밍 데이터에서 효율적으로 작동하며, 메모리를 적게 사용함.

* **알고리즘 설명 오류 지적**  
  알고리즘 설명이 잘못되었다고 지적하며, 코드 예제를 통해 올바른 방법을 제시함. 단어를 먼저 저장하고 삭제하는 방식이 더 정확한 결과를 도출함.

* **논문 추천**  
  논문이 블로그 포스트만큼 읽기 쉬우며, 더 많은 정보를 제공한다고 언급함. 스트리밍 데이터에서 집합의 카디널리티를 추정하는 간단한 알고리즘을 설명함.

* **Python 구현 예제**  
  스트리밍 알고리즘의 Python 구현 예제를 제공함. 간단한 코드로 알고리즘을 이해하고 실습할 수 있음.

* **시스템 리팩토링에 유용**  
  방문 횟수를 테이블에 삽입하여 카운트하는 시스템을 리팩토링 중인데, HyperLogLog 접근 방식을 대체할 수 있는 흥미로운 방법이라고 언급함.

* **메모리 효율적인 방법**  
  컴퓨터 과학자들이 메모리 효율적인 방법으로 부분 집합의 크기를 추정하는 방법을 발명했다고 언급함.

* **Chernoff Bound에 대한 논의**  
  논문에서 사용된 Chernoff Bound의 변형에 대해 논의함. 이 변형이 증명의 정확성을 깨뜨리는지 확실하지 않다고 언급함.

* **고유 요소 추정과 카운팅의 차이**  
  고유 요소의 수를 추정하는 것과 실제로 카운팅하는 것은 매우 다르다고 언급하며, 제목이 부적절하다고 지적함.

* **효율적인 스트림 알고리즘 소개**  
  스트림에서 상위 k개의 항목을 찾는 효율적이고 쉽게 구현 가능한 알고리즘을 소개함. Karp, Shenker & Papadimitriou의 논문을 추천함.

* **창의적 사고의 중요성**  
  "상자 밖에서 생각하기"의 예시를 즐긴다고 언급하며, 문제 해결을 위한 올바른 질문을 찾는 것이 중요하다고 강조함. 다양한 예시를 통해 창의적 사고를 내재화하고 적용할 수 있기를 희망함.