큰 파일에서 문자열 고유성 결정

C에서 1 16 자리 영숫자 문자열이 포함 된 파일을 처리하고 각각이 파일에서 고유한지 확인합니다. 어떻게해야합니까?큰 파일에서 문자열 고유성 결정

2010-08-13 venkat

지금까지 해보신 것은 무엇입니까? 문제가있는 곳은 어디입니까? 우리는 코드 원숭이가 아닙니다. –

각각 고유한지 확인하거나 고유 한 것을 추출해야합니까? –

얼마나 많은 RAM이 있습니까? 식별자를 저장하는 데는 약 800MB가 필요합니다. 약 두 배를 사용할 여력이 있다면 합리적인 데이터 구조 (해시 테이블, 균형 트리, 트라이)를 사용할 수 있습니다. 그렇지 않으면, 당신은 더 영리해야합니다. – Gilles

~ 16 메가 바이트의 데이터를 말하면 데이터를 해시 테이블 (또는 그 순서대로 무언가)에로드하고 각 문자열의 개수를 계산하는 것이 가장 확실한 방법입니다.

대부분의 다른 언어는 합리적인 데이터 구조 (일종의 맵)를 제공하므로 작업이 훨씬 쉬워집니다.

출처

2010-08-13 21:29:55

흠, 내 수학에 따르면 16 메가 비트가됩니다. –

16 * 10^8은 ~ 16 GB –

입니다. 튜링을 위해 사람들을 헤아릴 수 있습니까? –

파일을 정렬해야합니다.

단일 메모리 블록에로드하기 만하면 메모리 블록의 C 런타임 라이브러리에서 qsort을 실행하고 마지막으로 모든 문자열에 대해 순차적으로 실행하여 동일한 두 개의 연속 문자열을 확인합니다.

출처

2010-08-13 21:33:23 Codo

나는 동의해야한다. n 요소 배열을 정렬하는 것은 O (n log n)이며 해시 테이블이나 해시 세트를 채우는 것은 O (n)을 상각합니다. 이 크기의 데이터에서는 실용적인 차이가 있습니다. –

@Matthew : 그러나 우리는 여기 대략 1.6GB를 말하고 있으며 공간이 제한 될 수 있습니다.데이터를 정렬하는 작업은 약간의 메모리만으로 수행 할 수 있지만 해시는 훨씬 많은 데이터를 처리합니다. 사용 가능한 메모리가 충분하면 (예 : 대량의 메모리가 부족한 64 비트 시스템처럼) 해싱을 수행하십시오. 그렇지 않으면 디스크 캐싱을 포함하는 솔루션보다 더 빠르게 정렬 될 수 있습니다 (또는 1.6G 로그가 상당히 클 수 있습니다). –

@David, 그게 유효한 지적입니다. 일정 요소 (디스크로의 스왑 포함)는 항상 실행 시간에 영향을 줄 수 있습니다. 하지만 또 다시,'log2 (10^8)'은 26입니다. 어쨌든, 그것을 정렬 할 필요가 있다는 것은 사실이 아닙니다. 적어도 해싱에는 고려가 필요합니다. –

설정 /지도 기능이있는 라이브러리를 가져옵니다. link text

출처

2010-08-13 21:37:49 user411313

@all 모든 데이터 구조를 모르겠다. 기본을 알고있다. ........ 나는 고유 한 것이 든 1,000 만개의 문자열이든 각각의 ID를 검색하려고한다. ..... – venkat

다른 사람들이 말했듯이 가장 간단한 방법은 전체 파일을로드하고 qsort과 같은 것을 사용하여 정렬하는 것입니다.

메모리에 한꺼번에로드 할 수없는 경우 몇 가지 단계로 데이터를로드 할 수 있습니다. 첫 번째 단계에서 파일을 읽고 A으로 시작하는 줄에만로드하십시오. 그들을 정렬하고 고유 한 라인을 찾으십시오. 다음 단계에서는 B으로 시작하고 정렬하고 고유 한 행을 찾는 모든 행을로드하십시오. 한 줄로 시작할 수있는 모든 영숫자 문자에 대해이 과정을 반복하십시오. 이 기술을 사용하면 한 번에 파일의 일부만을 메모리에로드하면되므로 모든 행을 잘못 분류해서는 안됩니다.

출처

2010-08-13 21:39:54 bta

버킷 정렬 (해시 기능)을 여러 파일로, 각 버킷마다 하나의 파일로 수행합니다. 그런 다음 각 버킷의 파일을 처리하여 모든 문자열이 버킷 내에서 고유한지 판별하십시오.

출처

2010-08-13 21:48:32 Mike

큰 파일에서 문자열 고유성 결정

답변

관련 문제