큰 프로젝트를 수행 중이므로 여기서 요약 할 필요는 없지만 프로젝트의이 섹션에서는 매우 큰 텍스트 문서 (최소 약 50,000 단어 (고유하지 않음))를 사용하고, 가장 자주 사용되는 순서대로 각 고유 단어를 출력합니다 (아마도 상위 3 개는 "an"및 "the"가됩니다).큰 수의 집합에 대한 가장 효율적인 정렬 알고리즘
제 질문은 물론, 사용하기에 가장 적합한 정렬 알고리즘은 무엇입니까? 나는 종류를 세고 읽는 중이었습니다. 나는 그것을 좋아하지만, 나의 관심은 값의 범위가 고유 한 단어의 수에 비해 너무 클 것이라는 것입니다.
제안 사항?
먼저 단어 -> 개수의지도가 필요합니다. 50,000 단어가별로 많지 않습니다. 쉽게 기억에 맞을 것이므로 걱정할 것이 없습니다. C++에서는 표준 STL std :: map을 사용할 수 있습니다.
그런 다음지도가 있으면 모든지도 키를 벡터에 복사 할 수 있습니다.
그런 다음 맞춤 비교 연산자를 사용하여이 벡터를 정렬합니다. 단어를 비교하는 대신지도에서 개수를 비교합니다. (특정 정렬 알고리즘에 대해 걱정하지 마십시오. 배열이 너무 크지 않으므로 모든 표준 라이브러리 정렬을 사용할 수 있습니다.)
+1 - 50,000은 매우 큰 문서가 아닙니다. – Eclipse
500,000 단어까지도 쉽게 관리 할 수 있습니다. –
나는 quicksort으로 시작하여 거기에서부터 시작합니다.
차이점을 알아 보려면 wiki page on sorting algorithms을 확인하십시오.
+1 링크입니다. 모든 프로그래머는 적어도 정렬 알고리즘에 대한 기본적인 이해가 필요합니다. –
링크를 살펴보십시오. 다른 알고리즘의 작동 방식을 나타내는 그림 표현입니다. 이것은 당신에게 힌트를 줄 것이다!
굉장 링크, 고마워! –
나는 이것들을 더 좋아한다. http://vision.bc.edu/~dmartin/teaching/sorting/anim-html/all.html –
둘 다 껍데기가 가장 좋다고 제안하는 듯하다. – aterimperator
당신은 MSD radix 종류를 시도해야합니다. 항목을 lexicographical order으로 정렬합니다. 관심 있으신 분 google code project입니다.
단어 -> 빈도의 맵을 원하기 때문에 약간 까다 롭습니다. 당신은 키가 아닌 값으로 정렬하기를 원한다. 자바 비교기 here은 맞춤형 비교기를 사용하여이를 수행하는 방법을 보여줍니다.
사용하는 특정 알고리즘은 많은 영향을 미치지 않으므로 표준 라이브러리 구현에만 충실하십시오.
두 단어가 같은 횟수만큼 발생하면 출력 순서가 중요하지 않은 것으로 가정하면이 특정 문제와 관련하여 quicksort보다 더 나은 성능을 얻을 수 있습니다.
첫 번째 단계 : 단어를 키 값 및 빈도와 연관된 값으로 사용하여 해시 맵을 만듭니다. 파일을 구문 분석 할 때이 해시 맵을 채 웁니다. 당신이 이것을하는 동안, 발생하는 가장 높은 주파수를 추적해야합니다. 이 단계는 O (n) 복잡도입니다.
두 번째 단계 : 첫 번째 단계에서 가장 높은 빈도와 같은 항목 수의 목록을 만듭니다. 이 목록에있는 각 슬롯의 색인에는 빈도 수가 색인과 동일한 단어 목록이 보관됩니다. 따라서 문서에서 3 번 나오는 단어는 예를 들어 목록 [3]에 나옵니다. 해시 맵을 반복하고 단어를 목록의 적절한 지점에 삽입하십시오. 이 단계는 O (n) 복잡도입니다.
세 번째 단계 : 역순으로 목록을 반복하고 모든 단어를 출력합니다. 이 단계는 O (n) 복잡도입니다.
전반적으로이 알고리즘은 quicksort에 필요한 O (nlogn)가 아닌 O (n) 시간 에 작업을 완료합니다.
첫 번째 단계 O (n * m) 여기서 n은 입력 단어 수, m은 고유 단어 수입니다. 두 번째 단계는 O (m) 메모리를 사용하며 캐시의 경우 무작위 인 액세스 패턴을 사용합니다. 세 번째 단계가 다른 코드 조각으로 공급되면 o (n) 개의 메모리가 할당되어야합니다. -이 모든 것은 코드가 메모리 성능이 좋지 않아 명백한 코드 개선이 우세하다는 것을 의미합니다. –
정말 효율적인 해시를 사용한 경우 매우 운이 좋고 해시 충돌이없는 경우 첫 번째 단계는 O (m) 일 수 있습니다. –
나는 아래의 게시물에 설명 된대로 당신이 뭔가를하고 싶은 생각 :
http://karephul.blogspot.com/2008/12/groovy-closures.html
에릭 언급 한 바와 같이 폐쇄 LINQ와 같은 솔루션이 훨씬 쉽게 지원 언어.
내가 테스트 한 거의 모든 경우에 Quicksort가 가장 잘 작동했습니다. 그러나, 나는 Combsort가 최고 인 2 개의 경우를 가지고 있었다. 코드가 너무 작거나 데이터가 주문 된 순서가 복잡하기 때문에 그 경우에는 combsort가 더 좋았을 수 있습니다.
내 프로필에 정렬이 나타나면 언제든지 주요 정렬을 시도합니다. 나는 Quicksort와 Combsort를 모두 능가하는 것을 갖지 못했습니다.
이것은 늦은 답변 일 수 있습니다. 하지만 나는 너와 완전히 동의한다. Combort는 정말 빠릅니다. 놀라운 점은 combsort가 느린 속도의 약간의 변화라는 점입니다. 나는 combsort의 복잡성 분석에 대해 언급하는 참고 문헌을 찾을 수 없었다. Wiki에 따르면 평균 복잡도는'n^2/2^p'입니다. 그러나 그것이 어떻게 달성되는지에 대한 세부 사항은 없습니다. – arunmoezhi
,하지만 당신은 다음을 사용할 수 있습니다 50,000 단어 :
Trie라고도하는 디지털 트리를 구현해볼 수도 있습니다. 여기에 있습니다 link
어떤 언어를 사용하고 있습니까? 일부 언어에는 LINQ와 같은 일부 기능에 대한 핸들러가 내장되어 있습니다. – Eric
C++ 어쨌든,이 정보는 현재 많이 있습니다. 오늘 너무 많은 시간을 보냈습니다. 내일 저녁에해야 할 것입니다. – aterimperator