정수 세트 집합에 대한 간단한 C 라이브러리는 무엇입니까?

Question

C 프로그램을 수정해야하고 부호없는 정수 세트를 포함해야합니다. 즉, 나는 수백만 개의 정수 집합을 가지고 있습니다. (이 정수 집합은 각각 3과 100 사이의 정수를 포함합니다.) 그리고이를 구조체에 저장해야합니다.이 배열을 대수라고 할 수 있습니다. 정수 세트가 디렉토리에 이미 있습니다. 디렉토리에서 정의해야 할 유일한 작업은 조회 및 삽입입니다.

유용한 데이터 구조에 대한 지원이 내장 된 언어에서는 쉬울 것이지만 저는 C의 외국인이며 Google에서 (놀랍게도) 만족스럽게 내 질문에 대답하지 않았습니다.

http://uthash.sourceforge.net/

하지만 난 내 자신의 해시 키 생성을 마련 할 필요가 :이 프로젝트에 대한 권리 보인다.

이것은 표준적이고 간단한 문제이므로 표준적이고 간단한 해결책이 있기를 바랍니다.

Answer 1

데이터를 사용하여 수행 할 작업에 따라 다릅니다. 하지만 어쩌면 tsearch이 원하는대로 할 수 있습니다. 삽입하는 동안 성능이 저하 될 수 있지만 각 집합에 대해 정렬 된 배열을 작성하고 bsearch를 사용하여 값을 조회 할 수도 있습니다.

EDIT : (외부) 라이브러리를 찾고 있다면 일부 C 및 C++ 해시 테이블 구현 here을 비교할 수 있습니다. 이 기사의 저자는 khash이라는 일반 헤더 구현을 작성했습니다. 따라서 컴파일 된 바이너리에는 추가 종속성이 없습니다.

Answer 2

직접 간단한 해시 테이블을 구현하십시오. 스스로 구현하는 방법을 알면 더 나은 프로그래머가 될 것입니다.

http://en.wikipedia.org/wiki/Hash_table

Answer 3

편집 : 그것은 C의 ++와 이미 집합의 평균 크기를 알고 있기 때문에 C. 예 다음 ... 자신하여 해시 함수와 코드를 찾을 수 있어야하지 미안, 나는 대답 시작 그렇게 어려운 것은 아니며 단지 좋은 해시 함수를 선택하십시오! 그러나 디렉토리가 이미 있는지 확인하려면 전체 세트를 단일 번호로 성문화해야합니다.

당신은 반복적으로 세트의 단일 번호를 해싱에 의해 시도 할 수 있습니다 :

int hashcode = initvalue 
for (int i = 0; i < 0; ++i) 
    hashcode = calc_code(hashcode, number_set[i], i); 

을하는 방식으로 hashfunction가 이전 값, 현재 수와 현재 인덱스에 따라 달라집니다.

STL 세트는 무엇입니까?

#include <set> 

int nums[6] = {1,6,34,2,67,41}; 
set<int> numbers; 

for(int i = 0; i < 6; ++i) numbers.insert(nums[i]); 

for(set<int>::const_iterator iter = numbers.begin(); iter != numbers.end(); ++iter) 
    cout << *iter << ' '; 

이 데이터 구조는 쉽게 모든 세트를 저장할 수 있습니다 사용,하지만 당신은 세트가 이미 디렉토리에 포함되어 있는지 확인하는 것도 방법이 필요합니다. 명확하지 않습니다. 모든 요소가 동일한 세트가 이미 디렉토리에 있는지 알고 싶습니까?

당신은 모든 요소를 ​​확인하여 수동으로 할 수

하지만 당신은 당신이 고유 번호의 집합의 요소를 해시 및 세트의 맵을 사용하는 방법을 찾아야한다 그들의 수백만 ..

Answer 4

만약이 있기 때문에 당신을 정확하게 이해합니다. 특히 사소한 생각이 아닌 정수 집합을 표현하고자합니다.

첫 번째 요점은 정수 집합을 나타내는 것입니다. 당신은 (요소의 고정 된 수의) 새로운 세트를 만들 수있는 것보다

intset *newset(int size) 
{ 
    intset *set; 
    set = malloc(sizeof(intset) + sizeof(int)*(size-1)); 
    if (set) set->size = size; 
    return set; 
} 

와

typedef struct { 
    int size; 
    int elems[1]; 
} intset; 

및 set->elems[0]=i1; ...와 요소를 저장 : 가장 간단한 방법은이 같은 가변 크기 배열을 사용하는 것입니다.

또 다른 옵션은 비트 배열을 사용하는 것이지만 구현은 정수의 특성에 따라 달라집니다 (예 : 고정 된 범위 내에 있습니까? 일반적으로 집합에 그룹으로 표시됩니까?).

일단 정수가 있으면 두 세트의 요소가 같은지 비교하기 위해 비교 함수가 필요합니다. 배열을 나타내도록 배열을 선택하고 배열을 정렬 된 상태로 유지한다면 두 세트가 동일한 지 확인하는 것이 매우 간단합니다. 비트 맵인 경우 구현 방법에 따라 다릅니다.

이제 세트 집합에 대해 요소를 삽입하는 동안 수시로 크기를 조정해야하는 (정렬 된) 벡터 또는 해시 테이블을 선택할 수 있습니다. 후자의 경우 정수 집합에 대한 해시 함수를 작성해야합니다 (기존 함수를 사용하는 경우도 가능).

내가 말했듯이, 나에게는 사소한 것처럼 보이지 않는다. 나는 구글이 도움이되지 않는다는 사실에 놀라지 않는다.

그래도 진행하기 전에 결정을 내려야합니다.