Link to home
Start Free TrialLog in
Avatar of nabeen
nabeen

asked on

generating numbers faster

hhhi  all there.

this is code that generate numbers. suppose i need to generate 100 numbers from 1 to 100 but no
repeation. the programe is working fine but as it goes on generating it goes slow to generate as it has to
check whether the no is generated before or not. IF not generated store it in a link list. and i need the printing of the numbers as the same sequence as it is generated, NOT IN A ORDER (i.e asscending or desending)

so can any one can give me alternative method to make
the same objective faster. plez help. i'll be very thankful to the one who can solve my tension.


int generate_array_of_numbers(int total_no)
{      int no,i;

      for(int times=0;times!=total_no;times++)
      {
            again:
            i=0;
            time_t t;
            srand((unsigned) time(&t));
            no=rand() % (total_no+1);

            if(no==0)
                  goto again;

// CHECKING PREVIOUSLY GENERATED OR NOT IF GENERATED, GENERATE  ANOTHER AGAIN
            for(node=&start;node->next!=NULL && i<=total_no;node=node->next,i++)
            {      if(node->n==no)
                  {      goto again;
                  }
            }
//IF NOT GENERATED BEFORE ALLOCATING MEMORY FOR THE SAME NO AND SAVING IN A LINK LIST
            node->next=(struct link*)malloc(sizeof(struct link));
            node=node->next;
            node->n=no;
            start.n=no;
            node->next=NULL;
      }
      return 0;
}
ASKER CERTIFIED SOLUTION
Avatar of TheComputerWhisperer
TheComputerWhisperer

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of sunnycoder
maintain additional array

say you need to generate numbers 1-100

delare an aray of 100 shorts .. initialize all elements to 0

whenever you generate a number i, check array[i]
if it is 1, then number is duplicate, reject it else use the number and set array[i] to 1
if the random number generator is giving u lots of duplicates , sunny's algo might not get to end ..as there is always a that u wi'll have to work very hard to get the last number.

so i think best is to use what ComputerWhisperer suggested.. .. start with all the numbers and shuffle them ... with this u will have a definite termination point to ur loop... u can stop shuffling whenever u feel like .. just more the shuffle u do .. more disordered it will be


Avatar of astromanju
astromanju

The problem with 2 interchange is (when rand generates the same number) you would end up with original numbers .so shuffing would not work .

I suggest that when generating randoms divide the no. of requried into equal partitons that apply shuffling to it. then start with small equivalence partition and then go up.
the algo that computerwhisperer gave works fine for duplicate random numbers..
as even if random number is repeated.. the i variable is changing for sure..
>>if the random number generator is giving u lots of duplicates sunny's algo might not get to end
then the random number generator needs to be changed ... it is working as a constant number generator :))


from the question what I could make out was that random number generation is working fine ... just that he is searching the entire list of numbers generated to check if it is a duplicate ... this takes a lot of time as the size of the list increases and it was this process which needs to be speeded up

and I think by spending a bit more memory, reducing search time to a constant is a good idea
> The problem with 2 interchange is (when rand generates the same number) you would end up with original numbers .so shuffing would not work .

Of course it would work.  Excluding the possibility of ending up with the original numbers would make the generation less random.
sunny: as i said earlier , that algorithm does not have a well defined termination condition , and it relies on  the probability that u'll get less duplicates,  which is not fair.
and looking at the probabilistic side of it , in some cases that algorithm wont finish even in million iterations.. as i said , it will be really hard to get the last number
.

>>>and I think by spending a bit more memory, reducing search time to a constant is a good idea
here is the simplest implementation of that algo.. .. with added thing that it  repeats 1 million times..
and i am also calculating the max and minimum number of iterations needed to complete the list of non duplicate random numbers
..as i observed .. minmum iterations were something like 200-300 , and maximum went upto 3000-4000..
so i dont see the performance boost here .. i still recommend Computerwispherers solution .. that is neat and faster

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

int a[100];
int b[100];
main(){
unsigned  int i,j;
unsigned  int m;
 unsigned int cnt,max=0,min,iter;
 min=-1; // this is MAX unsigned INT

  srand(time(NULL));
  for(i=0;i<1000000;i++){
    memset(a,0,400);
    memset(b,0,400);
    iter=0;cnt=0;
    while(cnt<100){
      m=rand()%100;
      if(!b[m]){
      a[cnt]=m;b[m]=1;cnt++;
      }
      iter++;
    }
    if(iter>max)max=iter;
    if(iter<min)min=iter;
  }
  printf("mx %d mn %d\n",max,min);
}
ok here is more optimised version of computer whisperers solution ,here is idea
think of a pack of cards , and u want to randomise them
take one card out randomly. place it in another box .. OR at the end of the deck.
than chose another random card , from remaining .. and join it to the resulting deck ..
continue this , until u are finished with the original deck..


now when implementing this algorithm , if u wish to have separate array for the resulting deck ,, then in the original array u wont know which space has become empty .. so here is the idea
initialise array .. from 1 - 100.

for ( i=0;i<100;i++){
m=(get random number between 1 and and 100-i );
swap(a[i],a[100-i]);
}
in this way u'll keep taking out the 'random' numbers to the end of the orginal array.. and keep reducing the range of next random number generated..

IMO this is faster than all above
once u are finished .. u can read the aray from start to end OR end to start ( if u wish to have the numbers in the same order of their generation).
>>swap(a[i],a[100-i]);
i meant swat(a[m],a[100-i];..
here is the implementation of the logic i explained above ,, its pretty fast , and doesnt care if the same number is generated again..as most likely it would have been replaced by now.... the only problem i can see is , if by any chance u keep getting random numbers like ..99 , 98,...0 , then u'll get a reverse sorted array .. but that is something which shud be taken care of by random number generator..

#include <stdio.h>
#include <stdlib.h>
main(int argc,char * argv[]){
int i,n,tmp;
int a[100];
int k;
for(i=0;i<100;i++)a[i]=i+1;
srand(time(0));
//now randomise it

for(i=0;i<100;i++){
n=rand()%(100-i);  // to get random number in the range 0 and 100-i-1 .. this will keep shortening as the i increases
tmp=a[n]; a[n]=a[100-1-i]; a[100-1-i]=tmp; //swap it with the last on in current unrandomised list..

}
for(i=0;i<100;i++)printf("%d ",a[i]);printf("\n");


}
A little out of this question.... hi Akshay ol' buddy, how're things. Great goin'.... you're at #2 now!
hi mayank,
 long time no see, that ranking is for the current year only, overall i might be somewhere around 5/6th
anyways sunnycoder is moving pretty fast , and me and gj and kocil we have become less active, so pretty soon , as always, things and hence rankings gonna change.
and we have got a real expert in Salte(Alf) here, who somehow till  now was not touching C area, but now he is here and very popular with his 1000 words posts..
good for us that  we top-experts also have some one to look up for , when we land in trouble (applies at least for me)
Hi Akshay,
Have been halluva busy.... working on a J2EE/ Oracle/ Mainframe project - its a credit-card management system for Citibank, South East Asian countries..
Yeah! I know about Alf.... had many conversations with him in the C++ section a few months back.... at that time, he had restricted himself strictly to the C++ section, but now he's started answering everywhere.... he's also at the top for C++ programmers (2003).
Guess I won't post most comments here, otherwise people will think its a public forum for keeping in touch :-)
Best of luck!
Cheers,
Mayank.
Avatar of nabeen

ASKER

hi the computer whisperer
thanx
your program works fine but i encounter a problem when the size is stored in some
other variable. i tried malloc function too but there is error that const value required.
do u have any idea how can i rectify it.

int generate_noa(int tot_file)
{      int no,r,i;
      
      int array[tot_file];


      for(i=0;i<tot_file;i++)
      {      array[i]=i+1;
      }


      for(int times=0;times!=tot_file;times++)
      {       int temp;

            time_t t;
            srand((unsigned) time(&t));
            no=rand() % (tot_file);
            temp=file_no_array[times];
            file_no_array[times]=file_no_array[no];
            file_no_array[no]=temp;

      }
      return 0;
}
This is chock full of issues.

1. "int array[tot_file]"  You can't do that.  Declaring an array in that manner requires a constant size argument.
2. What is happening with these numbers?  The array of generated numbers will be out of scope by the end of the function, and I don't see any indication of where you're actually using them.
3. What is file_no_array?
4. Why are you declaring t and seeding in a loop?
5. Why return 0?  If this is a subroutine that returns nothing, may as well declare it void and not return anything.