alternatives to php in_array for large arrays for avoiding duplicates entries

Question

I need to generate a large list of random numbers from 600k to 2000k, but the list can not have duplicates.

My current 'implementation' looks like this:

<?php
    header('Content-type: text/plain');
    $startTime = microtime(true);
    $used = array();
    for ($i=0; $i < 600000; ) { 
        $random = mt_rand();
        //if (!in_array($random, $used)) {
        $used[] = $random;
        $i++;
        //}
    }
    $endTime = microtime(true);
    $runningTime = $endTime - $startTime;
    echo 'Running Time: ' . $runningTime;
    //print_r($used);
?>

If I keep the in_array test commented the processing time is around 1 second, so the mt_rand calls and the used array filling are relatively 'cheap' but when I uncomment the in_array test bad things happens! (I'm just waiting -it's been more then 10 minutes- for the script to terminate...)

So I'm looking for alternatives either on the duplicate detection side or in the generation part (How could i generate random numbers without the risk of getting duplicates)

I'm open to any suggestion.

Matt Huggins · Accepted Answer · 2009-09-22 05:28:34Z

16

For a quick/dirty solution, does using/checking array keys improve your speed at all?

$used = array();
for ($i = 0; $i < 600000; ) { 
    $random = mt_rand();
    if (!isset($used[$random])) {
        $used[$random] = $random;
        $i++;
    }
}
$used = array_values($used);

answered Sep 22, 2009 at 5:28

Matt Huggins

83.7k37 gold badges153 silver badges220 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Cesar Over a year ago

Thanks! The difference in running time is very big! Even when running the loop 2000k times. It's lightning fast!

Valentin Rusk Over a year ago

+1. This way is good, as in_array not only runs slow, but also eats memory. after reducing if of ~20 cases and removing from all of them in_array i saved 1.2mb of memory on critical resource that serves to 25 millions of users.

Gumbo · Accepted Answer · 2009-09-22 06:12:44Z

5

in_array requires to search the whole array in the worst case, that means linear costs (O(n)). But using the array key as – well – the key, the costs are constant (O(1)) since the costs for array access is always constant.

answered Sep 22, 2009 at 6:12

Gumbo

657k112 gold badges792 silver badges852 bronze badges

Comments

Artheus · Accepted Answer · 2010-06-16 15:34:36Z

2

You could for example do something like this instead

$random = mt_rand();

$array = range($random, $random + 600000);

$array = shuffle($array);

That would create a array that first is in order, but then it shuffles the array, so the values will be random. No collisions! :D

answered Jun 16, 2010 at 15:34

Artheus

211 bronze badge

Comments

markus · Accepted Answer · 2009-09-22 06:00:32Z

1

If you do the looping anyways and if you don't need more than 600000 why would you check them at all, why not just append $i to $random. done. not random enough?

for ($i = 0; $i < 600000; $i++)
{
    $yourArray[] = mt_rand() . $i; 
}

Furthermore there is the array function array_unique, which removes duplicate values from an array.

edited Sep 22, 2009 at 6:00

answered Sep 22, 2009 at 5:40

markus

40.8k23 gold badges100 silver badges143 bronze badges

Collectives™ on Stack Overflow

alternatives to php in_array for large arrays for avoiding duplicates entries

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related