Click here to Skip to main content
15,883,814 members
Home / Discussions / C / C++ / MFC
   

C / C++ / MFC

 
Questionwmi problem Pin
Mogaambo11-May-09 2:19
Mogaambo11-May-09 2:19 
AnswerRe: wmi problem Pin
«_Superman_»11-May-09 2:35
professional«_Superman_»11-May-09 2:35 
Questionbuild errors Pin
josip cagalj11-May-09 1:36
josip cagalj11-May-09 1:36 
AnswerRe: build errors Pin
josip cagalj11-May-09 2:26
josip cagalj11-May-09 2:26 
QuestionHow to compress an image? Pin
kapardhi11-May-09 1:30
kapardhi11-May-09 1:30 
AnswerRe: How to compress an image? Pin
CPallini11-May-09 1:41
mveCPallini11-May-09 1:41 
AnswerRe: How to compress an image? Pin
Stuart Dootson11-May-09 6:00
professionalStuart Dootson11-May-09 6:00 
QuestionSkip list takes so much time in insertion Pin
Risa Harada11-May-09 0:56
Risa Harada11-May-09 0:56 
I have to use skip list to store ~109000 words from a text file.

Here's the code (I'm using Visual C++ 2008):

Struct of the node:

struct SkipNode
{
	SkipNode ** forward;
	CString mots;
	CString longe;
	CString pos;
};



Make a new node:

SkipNode* make_node(int level, CString mots, CString pos, CString longe) 
{
        SkipNode *sn;
	sn=new SkipNode;
	sn->forward = (SkipNode**)calloc(level + 1, sizeof(SkipNode *));	
        sn->mots = mots;
	sn->pos = pos;
	sn->longe = longe;
	sn->level=level;
    return sn;
}


Insert a node:

void insert(SkipList* ss, CString value, CString pos, CString longe) 
{
    int i;
    SkipNode* x = ss->head;	
    SkipNode* update[MAX_LEVEL + 1];
    memset(update, 0, MAX_LEVEL + 1);
    for(i = ss->level; i >= 0; i--) 
	{
        while(x->forward[i] != NULL && x->forward[i]->mots < value) 
		{
            x = x->forward[i];
        }
        update[i] = x; 
    }
    x = x->forward[0];
    if((x!=NULL)&&(x->mots!=value)||(x==NULL))
	{        
        int lvl = random_level();
        if (lvl > ss->level) 
		{
			for(i = ss->level + 1; i <= lvl; i++) 
			{
				update[i] = ss->head;
			}
		    ss->level = lvl;
		}
        x = make_node(lvl, value, pos, longe);
		for(i = 0; i <= lvl; i++)
		{
			x->forward[i] = update[i]->forward[i];
			update[i]->forward[i] = x;
		}

    }
}


My MAX_LEVEL = 17 (log109000).

I read that skip list takes less time to insert a node than some other data structure (O(log n)). So I wonder why I need ~3 minutes to make the skip list above. And when I stop debugging, the program is still running!? I've just started studying programming, please help me!
AnswerRe: Skip list takes so much time in insertion Pin
Stuart Dootson11-May-09 5:58
professionalStuart Dootson11-May-09 5:58 
GeneralRe: Skip list takes so much time in insertion Pin
Risa Harada11-May-09 6:20
Risa Harada11-May-09 6:20 
Generalproblem with CryptStringToBinary. Pin
Vineet Kumar11-May-09 0:52
Vineet Kumar11-May-09 0:52 
QuestionRe: problem with CryptStringToBinary. Pin
CPallini11-May-09 1:39
mveCPallini11-May-09 1:39 
QuestionEdit Control Problem Pin
Padmanabha_M11-May-09 0:15
Padmanabha_M11-May-09 0:15 
AnswerRe: Edit Control Problem Pin
Chandrasekharan P11-May-09 0:18
Chandrasekharan P11-May-09 0:18 
GeneralRe: Edit Control Problem Pin
Padmanabha_M11-May-09 1:01
Padmanabha_M11-May-09 1:01 
GeneralRe: Edit Control Problem Pin
Chandrasekharan P11-May-09 1:26
Chandrasekharan P11-May-09 1:26 
GeneralRe: Edit Control Problem Pin
Padmanabha_M11-May-09 1:30
Padmanabha_M11-May-09 1:30 
GeneralRe: Edit Control Problem Pin
SudharsanC11-May-09 1:41
SudharsanC11-May-09 1:41 
GeneralRe: Edit Control Problem Pin
Padmanabha_M11-May-09 19:58
Padmanabha_M11-May-09 19:58 
QuestionBlind out the Effects, color, Script, underline , struck through in CFontDialog Pin
susanne110-May-09 23:54
susanne110-May-09 23:54 
AnswerRe: Blind out the Effects, color, Script, underline , struck through in CFontDialog Pin
«_Superman_»11-May-09 2:17
professional«_Superman_»11-May-09 2:17 
GeneralRe: Blind out the Effects, color, Script, underline , struck through in CFontDialog Pin
susanne111-May-09 2:51
susanne111-May-09 2:51 
GeneralRe: Blind out the Effects, color, Script, underline , struck through in CFontDialog Pin
«_Superman_»11-May-09 16:06
professional«_Superman_»11-May-09 16:06 
GeneralRe: Blind out the Effects, color, Script, underline , struck through in CFontDialog Pin
susanne111-May-09 21:57
susanne111-May-09 21:57 
QuestionC2664 error Pin
subramanyeswari10-May-09 23:47
subramanyeswari10-May-09 23:47 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.