이것은 (아마도) 모든 고급 프로그래밍 언어에 적용되는 일반적인 질문입니다. 여기 상황은 다음과 같습니다.고유 단어 수
문자열 배열이 있다고 가정합니다. 말하자면, 짧은 이야기의 500,000 문자열을 배열에 넣을 수있었습니다 (입력 형식에 대한 옵션이 없다고 가정). 결과적으로 중복되는 항목이 임의의 수만큼 존재할 가능성이 큽니다.
문자열의 배열을 가져 와서 해당 배열의 고유 한 하위 집합 (?)을 포함하는 다른 배열을 만들려고합니다 (즉 중복되지 않음). 이 시나리오에서 입출력은 모두 배열이어야하므로 다양한 옵션에서 제한 될 수 있습니다.
성능면에서 가장 빠른 방법은 무엇입니까? 나는 현재 단어가 존재 하는지를 검사하기 위해 선형 검색을 사용하고 있지만, 선형 검색이므로 작업하기에 무리한 문자열이있는 경우 특히 더 빠른 방법이있을 수 있다고 생각합니다. 더 큰 소설처럼!
해시 세트를 사용하는 것이 가장 현명한 방법 일 수 있습니다. 복잡성은 O (N)이어야합니다.
참고 : 대부분의 고급 프로그래밍 언어에는 배열에서 중복을 제거하는 함수 구현이 포함되어 있습니다 (예 : PHP.
당신이 말로 표현하자면 directed acyclic word graph이 내가 아는 가장 효율적인 데이터 구조입니다.
아직 개념적으로 매우 간단한 데이터 구조입니다.
A * minimal * directed acyclic word graph는 생성 속도가 매우 느리기 때문에 실제로 옵션이 아닙니다. 어쩌면 당신은 "최소한으로 최소화 된"단어 그래프 인 [trie] (http://en.wikipedia.org/wiki/Trie)를 의미 할 수 있습니다. 이것은 생성하는 것이 훨씬 빠르지 만, 사전에 따라 메모리를 많이 차지할 수 있습니다. 나는 아직도 OP가하려고하는 것을 위해 해시 셋을 추천 할 것이다. (비록 OP가 많은 말을 들으면 DAWG와 시도에 대해 알아내는 것은 그 자체로 흥미로울 수있다.) – Timwi
@Timwi 아마도 나는 트라이를 의미 할 것이다 - 나는 항상 "DAWG"가이 가족을 언급했다고 생각했다. 특정 개념보다는 개념의 –
기술적으로 DAWG가 더 일반적인 용어이고 trie가 DAWG의 특별한 경우라고 가정합니다. 그러나 실제로, DAWG라는 용어는 보통 * minimal * DAWG를 나타냅니다 ... – Timwi
해시 기반 집합 인지도는 키와 값이 있음을 의미하지만이 값을 사용하여 개수를 저장할 수 있습니다. – vickirk
예, 미안 해요, 나는 해시 세트를 의미했습니다. 편집 됨. – CAFxX