▲GN⁺ 2024-07-26 | parent | ★ favorite | on: 내가 좋아하는 알고리듬: Linear Time Median Finding (2018)(rcoh.me)Hacker News 의견 4년 전 다양한 중위수 알고리듬을 비교한 긴 글을 작성했음 10-15년 전, 수십억 개의 값을 가진 로그 항목에서 중위수를 찾기 위해 MapReduce를 사용했음 데이터의 정밀도와 범위를 알면 버킷 정렬을 사용할 수 있었음 타이밍을 정수 밀리초로 표현하고 히스토그램을 생성하여 중위수를 쉽게 찾을 수 있었음 2017년에 중위수-중위수 접근법을 다른 선택 알고리듬과 경쟁력 있게 만든 논문이 발표되었음 Andrei Alexandrescu가 이 알고리듬에 대해 2016년에 강연을 했음 중위수-중위수 알고리듬의 저자 목록이 매우 유명함 Manuel Blum, Robert Floyd, Ron Rivest, Bob Tarjan, Vaughan Pratt 등 Floyd-Rivest 알고리듬도 효율적이지만 이해하기 어려움 스트리밍 알고리듬을 사용하면 전체 데이터를 메모리에 저장하지 않고도 근사치를 계산할 수 있음 퀵소트를 수정하여 중위수를 선택하는 방법이 있음 인터뷰 질문으로 수조 개의 숫자가 있는 리스트에서 중위수를 찾는 문제를 받았음 상한과 하한을 설정하여 중위수를 찾는 방식을 사용했지만 최적의 방법은 아니었음 우선순위 힙을 사용하는 더 효율적인 방법이 있었음 이후 LeetCode 구독을 시작했음 Go로 구현된 간단한 예제를 공유했음 Radix 정렬은 정수 외에도 문자열 등 다양한 데이터 타입에 사용할 수 있음
Hacker News 의견