나는 정렬되지 않은 항목을 100 개 말합니다. 각 항목은 그룹에 속합니다. 항목이 속한 그룹은 단순히 항목 클래스의 구성원입니다.C/C++에서 항목을 나열하는 가장 효율적인 방법
C/C++을 사용하여 항목 목록을 검색하고 해당 그룹을 확인하고 항목을 화면에 인쇄하는 가장 효율적인 방법을 찾고 있습니다. 그래도 캐치가 있습니다. 그룹의 항목이 화면에 인쇄되면 해당 그룹에 속한 항목을 더 이상 인쇄하지 않습니다.
전 STL 컴파일러를 사용하고 있으며 실행 파일의 크기가 중요하므로 내 자신의 해시 클래스를 정의하기 시작하고 싶지 않습니다.
그룹의 사전/해시 맵을 만들 수 있으며 각 그룹 저장소에 대해 해당 그룹의 항목이 인쇄되었는지 아닌지를 나타내는 bool을 작성할 수 있습니다.
샘플 코드 :
#include <unordered_map>
#include <string>
#include <iostream>
std::string getGroupForNumber(int num)
{
//
}
int main()
{
typedef std::tr1::unordered_map< std::string, bool > hashmap;
hashmap groupsPrinted;
for(int i = 0 ; i < 100 ; ++i) {
if (groupsPrinted[ getGroupForNumber(i) ] == false) {
groupsPrinted[ getGroupForNumber(i) ] = true;
std::cout << i << std::endl;
}
}
return 0;
}
고마워, 그 생각하지만 문제는 내가 내 자신의 해시 클래스를 만들어야 할 것입니다 뜻 pre STL 컴파일러를 사용하고 있습니다. 이것은 공간 제한의 이유 때문에 피하고 싶습니다. – KJF
정렬 그룹 값에 따라 항목 (그것이 포인터 있다면, 당신은 그 주소를 사용할 수 있습니다 그렇지 않으면 사전 편찬 정렬 문자열). 그런 다음 정렬 된 목록을 반복하면서 각 그룹의 첫 번째 항목을 항상 가져옵니다.
는이 약
n + n * log(n)
나는이 실행 파일과 속도의 크기 사이에 합리적인 대안이라고 생각합니다.
n은 약 100이므로이 절충은 완전히 합리적입니다. 그러한 작은 문제 크기에 대해 복잡한 데이터 구조를 사용할 이유가 없습니다. –
그룹 수를 0.99로 지정할 수 있으면 최적화하려는 경우 부울 배열 또는 비트 집합이 필요합니다. 모든 배열을 '거짓'으로 초기화합니다. 인쇄 후 arr [groupId] = 'true'로 설정하고 다음에 인쇄하기 전에 값을 확인하십시오. STL은 필요하지 않습니다.
항목이 더 이상 인쇄되지 않아야하는 그룹 이름 집합을 유지하십시오.
질문에 c/C++를 작성 했으므로 다음은 일부 C 코드입니다. 몇 가지 질문이 있습니다. 미래에 그룹이 인쇄 가능한 상태가됩니까? 항목 목록이 정적입니까? 인쇄 할 특정 그룹의 항목이 중요합니까? 목록
배열 :
나는 (문제의 내 제한된 이해) 다음과 같은 구조를 제안했다.
typedef struct node{
void *item; /* this is your item */
node *next;
} node_t;
typedef struct {
node_t *my_group;
int used;
} group_t;
static group_t my_items[NUM_OF_GROUPS]; /* this is your ordered by groups list.*/
더 나은 목록 목록을 사용하십시오. group_t는 다음과 같습니다 :
더 많은 질문에 답변 해주십시오.
항목 목록이 정적입니까?
아니요, 언제든지 축소되거나 커질 수 있습니다.
특정 그룹에서 인쇄하는 항목이 중요합니까?
당분간은 아니요. 어쩌면 미래에는,하지만 지금은 고유 한 그룹에 속하는 첫 번째 항목을 인쇄하는 것으로 충분할 것입니다.
그룹은 어떻습니까? 새로운 그룹을 얻을 수 있습니까? 그리고 회원 중 한 명을 인쇄 한 후 그룹이 관련성있게 될 수 있습니까?
화면에 인쇄하는 데 드는 비용은 개체로 수행 할 수있는 것보다 몇 배 더 중요합니다. 단지 몇 개의 그룹에 1 천만 개의 개체 배열이 있다면 정렬은 합리적인 선택이 아닙니다. 그룹을 정적 색인 (즉 지정된 범위의 정수)으로 식별 할 수있는 경우 마스크 배열을 사용하여 그룹이 표시되었는지 여부를 나타낼 수 있습니다. 그룹이 더 복잡하면 설정된 데이터 구조 (해시, 트리 등)에 표시된 그룹을 저장할 수 있습니다.
자세한 정보를 제공해야합니다. 항목 목록이 정렬되어 있습니까? 어떤 항목과 그룹 간의 연결을 구성합니까? 그게 단순히 std :: string 멤버인가요? –
의견을 보내 주셔서 감사합니다. 나는 약간의 편집을했다. – KJF