yundream의 구현

#include <stdio.h>
#include <vector>
#include <iostream>
#include <set>
#include <time.h>
#include <map>
#include <unistd.h>
#include <sys/time.h>

using namespace std;

// <did, score> 구조체
struct KeyValue
{
	int did;
	int score;
};

struct ltstr
{
	bool operator() (const KeyValue s1, const KeyValue s2) const
	{
		return s1.score > s2.score; 
	}
};

vector<KeyValue> MakeTermScore(int, int);

int main(int argc, char **argv)
{
	vector<KeyValue> Term1;
	vector<KeyValue> Term2;
	srandom(time((time_t *)NULL));
	vector<KeyValue> tempTerm;
	vector<KeyValue> tempTerm2; 
	multiset<KeyValue, ltstr> InvertDoc;
	KeyValue *tempTerm3;

	struct timeval mytime1, mytime2;

	// 테스트를 위한 2개의 배열 set 생성    ------------------------
	vector< vector<KeyValue>::iterator > ScoreQueue;
	vector< vector<KeyValue>::iterator > ScoreEnd;

	Term1 = MakeTermScore(100, 200);
	Term2 = MakeTermScore(100, 400);
	// 테스트를 위한 2개의 배열 set 생성 end ------------------------ 

	// 2개의 배열 set에 대한 iterator 저장
	ScoreQueue.push_back(Term1.begin());
	ScoreQueue.push_back(Term2.begin());
	ScoreEnd.push_back(Term1.end());
	ScoreEnd.push_back(Term2.end());

	gettimeofday(&mytime1, NULL);
	tempTerm3 = (KeyValue *)malloc(sizeof(KeyValue)*1200); 

	unsigned int i=0;
	unsigned int inputidx = 0;

	int sum = 0;

	/* Vector And */
	unsigned int size2 = Term2.size();
	unsigned int size1 = Term1.size();
	unsigned int index = 0;
	int turn = 0;
	int topdoc = -1;

	// 교집한 연산 -----------------------------------------------
	for ( i = 0; i < size2; i++)
	{
		if (Term2[i].did > topdoc)	
		{
			topdoc = Term2[i].did;
			turn++;
			for (index; index < size1; index++)
			{
				if (Term1[index].did > topdoc)
				{
					topdoc = Term1[index].did;
					break;
				}
				if (Term1[index].did == topdoc)
				{
					index++;
					tempTerm3[inputidx] = Term2[i];
					inputidx++;
					topdoc = Term1[index].did;
					break;
				}
			}
		}
		if (Term2[i].did == topdoc)
		{
			index++;
			turn++;
			topdoc = Term1[index].did;
			tempTerm3[inputidx] = Term2[i];
			inputidx++;
		}
	}
	// 교집한 연산 end -------------------------------------------
	gettimeofday(&mytime2, NULL);

	// 연산 테스트 -----------------------------------------------
	for (i =0; i < Term1.size(); i++)
	{
		printf("%d ", Term1[i].did);
	}
	printf("\n\n");
	for (i =0; i < Term2.size(); i++)
	{
		printf("%d ", Term2[i].did);
	}
	printf("\n\n");
	for (i = 0; i < inputidx; i++)
	{
		printf("%d ", tempTerm3[i].did);
	}
	printf("\n\n");

	// 연산시간 측정
	printf("TIME SEC  :  %lu\n", mytime2.tv_sec  - mytime1.tv_sec);
	printf("TIME USEC :  %lu\n", mytime2.tv_usec - mytime1.tv_usec);
	printf("Term1 : %d\n", Term1.size());
	printf("Term2 : %d\n", Term2.size());
	printf("SUM   : %d\n", inputidx); 
	printf("SUM   : %d\n", sum); 
	printf("TURN  : %d\n", turn); 

	return 0;
}

vector<KeyValue> MakeTermScore(int num, int maxdoc)
{
	KeyValue lvalue;
	vector<KeyValue> term;
	set<int> did;
	set<int>::iterator si;


	for (int i = 0; i < num; i++)
	{
		did.insert(random()%maxdoc);
	}
	si = did.begin();
	while(si != did.end())
	{
		lvalue.did   = *si;
		lvalue.score = random()%100;	
		term.push_back(lvalue);
		*si++;
	}
	return term;
}