Thread: Generating 100k to 1 million unique random numbers

  1. #1
    Registered User
    Join Date
    Aug 2003
    Posts
    34

    Generating 100k to 1 million unique random numbers

    Hey guys,
    I need your help. Do you have any advice on how to generate 100k to 1 million unique random numbers, relatively fast? I have an assignment to compare the times needed to search for a record in a binary search tree (stored in in a file) and normal file. Each record has a key that is generated on random. Since the binary search tree uses that key for sorting data, it needs to be unique. I also need a large number of records, otherwise the search times will not be noticeable (they need to be expressed in miliseconds).

    I've tried various ways to generate such a large number of unique random numbers and the maximum that I managed to accomplish is around 110 000.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Generate a million unique numbers, then shuffle them randomly.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    .
    Join Date
    Nov 2003
    Posts
    307
    We have this code for creatign sequential numbers, then scrambling them:
    Code:
    #include <stdlib.h>
    #include <time.h>
    /* 
    *  this is from Linux source, 
    *  if you run on linux you don't need this function 
    */
    
    /* Reentrant random function frm POSIX.1c.
       Copyright (C) 1996, 1999 Free Software Foundation, Inc.
       This file is part of the GNU C Library.
       Contributed by Ulrich Drepper <[email protected]>, 1996.
    
       The GNU C Library is free software; you can redistribute it and/or
       modify it under the terms of the GNU Lesser General Public
       License as published by the Free Software Foundation; either
       version 2.1 of the License, or (at your option) any later version.
    
       The GNU C Library is distributed in the hope that it will be useful,
       but WITHOUT ANY WARRANTY; without even the implied warranty of
       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
       Lesser General Public License for more details.
    
       You should have received a copy of the GNU Lesser General Public
       License along with the GNU C Library; if not, write to the Free
       Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
       02111-1307 USA.  */
    
    
    int
    rand_r (unsigned int *seed)
    {
      unsigned int next = *seed;
      int result;
    
      next *= 1103515245;
      next += 12345;
      result = (unsigned int) (next / 65536) % 2048;
    
      next *= 1103515245;
      next += 12345;
      result <<= 10;
      result ^= (unsigned int) (next / 65536) % 1024;
    
      next *= 1103515245;
      next += 12345;
      result <<= 10;
      result ^= (unsigned int) (next / 65536) % 1024;
    
      *seed = next;
    
      return result;
    }
    /* change this to get size you want */
    #define ARRSIZE 100000  
    
    /* use 32 bit extended rand function rand_r */
    int main(int argc, char *argv[])
    {
        int arr[ARRSIZE];
        unsigned int seed=time(NULL);
        int i=0;
        int j=0;
        int limit=2;
        int tmp=0;
        
        for(i=0;i<ARRSIZE;i++) arr[i]=i+1; /* 1 - ARRSIZE unique values */
      
        while(limit<ARRSIZE)     /* "randomize" */
        {
            j=arr[ rand_r(&seed) % limit ];
            tmp=arr[j];
            arr[j]=arr[limit];
            arr[limit]=tmp;
            limit++;
        }
        for(i=0;i<ARRSIZE;i++) printf("%d\n",arr[i]);
        return 0;
    }

  4. #4
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    Code:
    std::vector<long> vec(1000000);
    for( long i=0; i< 1000000; ++i) vec.push_back(i);
    std::random_shuffle(vec.begin(),vec.end());
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  5. #5
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    oops c forum. disregard my c++
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. generating 10 unique random numbers in C
    By creeping death in forum C Programming
    Replies: 4
    Last Post: 01-28-2009, 11:23 AM
  2. random numbers
    By mesmer in forum C Programming
    Replies: 4
    Last Post: 10-24-2008, 01:22 PM
  3. random numbers
    By ballmonkey in forum C++ Programming
    Replies: 3
    Last Post: 01-18-2005, 02:16 PM
  4. Unique random numbers
    By aydin in forum C Programming
    Replies: 7
    Last Post: 11-23-2004, 12:21 PM
  5. generating random numbers within a range
    By tucky in forum C Programming
    Replies: 3
    Last Post: 09-14-2001, 12:59 PM