Thread: time vs memory

i am creating a double linked list of prime numbers ( 2 to 1,000,000 ). one way to do it is add nodes as each prime is found by dividing each new number by all the nodes on the list (slow). The other way is start with a list with just the odd numbers and 2 (2- 999999) and remove the nodes that are not prime. which turns out to be nearly 5 times quicker however takes a big chunk of memory at the beginning.

which way is best

i just use block comments to comment out the different bits of main

Code:

#include <stdio.h>
#include <stdlib.h>

#define Limit 1000000

typedef struct Numbers
{

    int Num;
    struct Numbers *Next;
    struct Numbers *Previous;

} Number;

Number * GetMemory();
void CreateHead( Number *, int );
Number * CreateNode( Number *, Number *, int );
Number * AppendtoList( Number *, Number *, int );
void ReadList( Number * );
Number * SearchList( Number *, Number *, int, int );
void DeleteNode( Number *, int * );
void DestroyList( Number * );

int CheckPrime( Number *, int );

int main()
{
    Number *Head = NULL, *Tail = NULL;
/*
    Head = AppendtoList( Head, Tail, 2 );
    Tail = Head;

    for ( int i = 3; i < Limit; i += 2 )
    {
        if ( CheckPrime( Head, i ) == 1 )
        {
            Tail = AppendtoList( Head, Tail, i );
        }
    }
//*/
//*
    Head = AppendtoList( Head, Tail, 2 );
    Tail = Head;

    int RecNum = 1;

    for ( int i = 3; i < Limit; i += 2 )
    {
        Tail = AppendtoList( Head, Tail, i ); // add all the odd numbers to the list
        RecNum++;
    }

    for ( int i = 3; i < 1000; i += 2)
    {
        for ( Number *Node = Head->Next; Node->Num < Limit - 1; Node = Node->Next )
        {
            if ( Node->Num != i && Node->Num % i == 0 )
            {
                Number *tmpNode = Node;
                Node = Node->Next;
                DeleteNode( tmpNode, &RecNum );
            }

            if (Node->Next == NULL)
                break;
        }
    }

    Number *tmpTail = Tail;
    Tail = Tail->Previous;
    Tail->Next = NULL;
    free (tmpTail);
//*/
    ReadList( Head );
    DestroyList( Tail );

    return 0;
}

Number * GetMemory()
{
    return ( Number * ) malloc ( sizeof( Number ) );
}

void CreateHead( Number *Tmpptr, int x )
{
    Tmpptr->Num = x;
    Tmpptr->Next = NULL;
    Tmpptr->Previous = NULL;
}

Number * CreateNode( Number *TmpPtr, Number *TPtr, int x )
{
    TmpPtr->Previous = TPtr;
    TPtr->Next = TmpPtr;
    TmpPtr->Next = NULL;
    TmpPtr->Num = x;

    return TmpPtr;
}

Number * AppendtoList( Number *HPtr, Number *TPtr, int x )
{
    if ( HPtr == NULL )
    {
        HPtr = GetMemory();
        if ( HPtr != NULL )
        {
            CreateHead( HPtr, x );
            TPtr = HPtr;
            return HPtr;
        }
        else
        {
            printf("error getting memory!\n");
            exit(0);//will improve this
        }
    }
    else
    {
        Number *tmpNode = NULL;

        tmpNode = GetMemory();
        if ( tmpNode != NULL )
        {
            TPtr = CreateNode(tmpNode, TPtr, x);
            return TPtr;
        }
        else
        {
            printf("error getting memory!  Record not created \n");
            return NULL;
        }
    }
}

void ReadList( Number * CurrentRecord) //passed head pointer
{
    int countrec = 0;

    while ( CurrentRecord != NULL )
    {
        printf("%d\n", CurrentRecord->Num);
        CurrentRecord = CurrentRecord->Next;
        countrec++;
    }

    printf("%d records displayed\n", countrec);
}

Number * SearchList( Number *FirstRec, Number *LastRec, int Goal, int NumRec )
{
    if ( NumRec == 0 )
        return NULL;

    int MidRecNum = 1;
    Number *MidRec = FirstRec;
    for ( ; MidRecNum < NumRec / 2; ++MidRecNum )
        MidRec = MidRec->Next;

    if ( MidRec == NULL )
        return NULL;

    if ( MidRec->Num == Goal )
        return MidRec;

    return Goal < MidRec->Num
         ? SearchList( FirstRec,     MidRec->Previous, Goal, MidRecNum-1 )
         : SearchList( MidRec->Next, LastRec,          Goal, NumRec-MidRecNum );
}

void DeleteNode( Number *CurrentRecord, int *x )
{
    if ( CurrentRecord != NULL )
    {
        if (CurrentRecord->Next == NULL) //tail
        {
            //printf("Tail Record DONT delete\n");
        }
        else
        {
            Number *NextNode = NULL, *PrevNode = NULL;

            NextNode = CurrentRecord->Next;
            PrevNode = CurrentRecord->Previous;

            CurrentRecord->Next->Previous = PrevNode;
            CurrentRecord->Previous->Next = NextNode;

            free ( CurrentRecord );
            *x -= 1;
            //printf("Record deleated\n");
        }
    }
    else
    {
        //printf("Deleation failed! Record not found\n");
    }
}


void DestroyList( Number *CurrentTail ) //passed tail pointer
{
    int countrec = 0;
    while ( CurrentTail != NULL )
    {
        Number *tmpTail =NULL;
        tmpTail = CurrentTail;
        CurrentTail = CurrentTail->Previous;
        free (tmpTail);
        countrec++;
    }

    printf("%d records distroyed\n", countrec);
}

int CheckPrime( Number *CurrentRecord, int x )
{
    while ( CurrentRecord != NULL )
    {
        if ( x % CurrentRecord->Num == 0 )
        {
            return -1;
        }

        CurrentRecord = CurrentRecord->Next;
    }

    return 1;
}

the one un-commented is the faster one but obviously uses a lot more memory.

the other version of main

Code:

int main()
{
    Number *Head = NULL, *Tail = NULL;
//*
    Head = AppendtoList( Head, Tail, 2 );
    Tail = Head;

    for ( int i = 3; i < Limit; i += 2 )
    {
        if ( CheckPrime( Head, i ) == 1 )
        {
            Tail = AppendtoList( Head, Tail, i );
        }
    }
//*/
/*
    Head = AppendtoList( Head, Tail, 2 );
    Tail = Head;

    int RecNum = 1;

    for ( int i = 3; i < Limit; i += 2 )
    {
        Tail = AppendtoList( Head, Tail, i ); // add all the odd numbers to the list
        RecNum++;
    }

    for ( int i = 3; i < 1000; i += 2)
    {
        for ( Number *Node = Head->Next; Node->Num < Limit - 1; Node = Node->Next )
        {
            if ( Node->Num != i && Node->Num % i == 0 )
            {
                Number *tmpNode = Node;
                Node = Node->Next;
                DeleteNode( tmpNode, &RecNum );
            }

            if (Node->Next == NULL)
                break;
        }
    }

    Number *tmpTail = Tail;
    Tail = Tail->Previous;
    Tail->Next = NULL;
    free (tmpTail);
//*/
    ReadList( Head );
    DestroyList( Tail );

    return 0;
}

thanks.....

Do i approach things logically or do you get the impression that i am thrashing around fighting it. i Feel that its like when i first started driving wagons i would strap everything up to an inch of its life so that the sides of the trailer looked like a Victorian in a corset and the dang product would still move /fall over.