.그물:50,000개 항목의 List<string>에서 고유성을 효율적으로 확인하는 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/1860306

문제

일부 라이브러리 코드에는 50,000개 이상의 항목을 포함할 수 있는 목록이 있습니다.

라이브러리 호출자는 목록에 문자열을 추가하는 메서드를 호출할 수 있습니다.추가되는 문자열의 고유성을 효율적으로 확인하려면 어떻게 해야 합니까?

현재는 문자열을 추가하기 직전에 전체 목록을 스캔하여 각 문자열을 추가할 문자열과 비교합니다.항목이 10,000개가 넘으면 규모 문제가 표시되기 시작합니다.

이것을 벤치마킹하겠지만 통찰력에 관심이 있습니다.

  • List<>를 Dictionary<>로 바꾸면 목록이 10,000개 이상의 항목으로 늘어남에 따라 ContainsKey()가 훨씬 더 빨라질까요?
  • 모든 항목이 추가될 때까지 고유성 검사를 연기하면 속도가 더 빨라 집니까?그 시점에서는 모든 요소를 ​​다른 모든 요소와 비교하여 확인해야 하지만 여전히 n^^2 작업입니다.

편집하다

몇 가지 기본 벤치마크 결과.두 가지 메서드를 노출하는 추상 클래스를 만들었습니다.채우기 및 스캔.Fill은 컬렉션을 n개 항목으로 채웁니다(저는 50,000개를 사용했습니다).Scan은 주어진 값이 존재하는지 확인하기 위해 목록을 m번(나는 5000을 사용함) 스캔합니다.그런 다음 List용 클래스와 HashSet용 클래스의 구현을 구축했습니다.

사용된 문자열의 길이는 균일하게 11자였으며 추상 클래스의 메서드를 통해 무작위로 생성되었습니다.

매우 기본적인 마이크로 벤치마크입니다. 

Hello from Cheeso.Tests.ListTester
filling 50000 items...
scanning 5000 items...
Time to fill: 00:00:00.4428266
Time to scan: 00:00:13.0291180

Hello from Cheeso.Tests.HashSetTester
filling 50000 items...
scanning 5000 items...
Time to fill: 00:00:00.3797751
Time to scan: 00:00:00.4364431

따라서 해당 길이의 문자열에 대해 HashSet은 고유성을 검색할 때 List보다 약 25배 빠릅니다.또한 이 크기의 컬렉션에서는 컬렉션에 항목을 추가할 때 HashSet이 List에 비해 페널티가 없습니다.

결과는 흥미롭지만 유효하지 않습니다.유효한 결과를 얻으려면 구현을 무작위로 선택하여 워밍업 간격, 여러 번의 시도를 수행해야 합니다.그러나 나는 그것이 바를 약간만 움직일 것이라고 확신합니다.

모두 감사합니다.

편집2

무작위화와 여러 번의 시도를 추가한 후 HashSet은 이 경우 지속적으로 List보다 약 20배 더 나은 성능을 발휘합니다.

이러한 결과는 가변 길이의 문자열, 더 복잡한 객체 또는 다양한 컬렉션 크기에 반드시 적용되는 것은 아닙니다.

도움이 되었습니까?

해결책

당신은 HashSet<T> 귀하가 하고 있는 일을 위해 특별히 고안된 수업입니다.

다른 팁

사용 HashSet<string> 대신에 List<string>, 그러면 확장이 매우 잘 되어야 합니다.

내 테스트에서, HashSet<string> 비해 시간이 많이 걸리지 않습니다 List<string> :)

주제에서 벗어날 수도 있지만 매우 큰 고유 문자열 세트(수백만 개 이상)를 언어 독립적인 방식으로 확장하려면 다음을 확인해 보세요. 블룸 필터.

는 Contains(T) 기능이 작동하지 않나요?

나는 Dictionary<>가 연관 배열로 구현되어 있다는 것을 읽었습니다.일부 언어(반드시 .NET과 관련된 것은 아님)에서 문자열 인덱스는 노드의 문자를 기반으로 각 노드에서 분기되는 트리 구조로 저장됩니다.참조하세요 http://en.wikipedia.org/wiki/Associative_arrays.

비슷한 데이터 구조가 1973년에 Aho와 Corasick에 의해 고안되었습니다.이러한 구조에 50,000개의 문자열을 저장하는 경우 얼마나 많은 문자열을 저장하는지는 중요하지 않습니다.더 중요한 것은 길이 문자열의.길이가 거의 같으면 검색 알고리즘이 검색 중인 문자열 길이에 대해 런타임에서 선형이기 때문에 조회 속도가 느려지는 일이 전혀 없을 것입니다.레드-블랙 트리 또는 AVL 트리의 경우에도 검색 런타임은 인덱스의 요소 수보다는 검색하는 문자열의 길이에 따라 더 많이 달라집니다.그러나 해시 함수를 사용하여 인덱스 키를 구현하기로 선택한 경우 이제 문자열 해싱 비용(O(m), m = 문자열 길이)과 인덱스에서 문자열 조회 비용이 발생합니다. O(log(n)) 순서일 가능성이 높습니다. n = 인덱스의 요소 수입니다.

편집하다:저는 .NET 전문가가 아닙니다.경험이 많은 다른 사람들은 다른 구조를 제안합니다.나는 내 말보다 그들의 말을 받아들일 것이다.

편집2:귀하의 분석은 고유성을 비교하기에는 약간 벗어났습니다.해싱 구조나 사전을 사용하는 경우 위에 게시한 이유 때문에 O(n^2) 작업이 아닙니다.목록을 계속 사용하는 경우 매번 목록의 각 요소를 검사해야 하므로 목록이 O(n^2) * (집합에 있는 문자열의 최대 길이)인 것이 맞습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top