Re: Compute Unique Numbers in a Set

From	Bart <bc@freeuk.com>
Newsgroups	comp.lang.c, comp.lang.c++
Subject	Re: Compute Unique Numbers in a Set
Date	2023-01-08 23:13 +0000
Organization	Aioe.org NNTP Server
Message-ID	<tpfimu$5ft$1@gioia.aioe.org> (permalink)
References	(3 earlier) <tpdfp6$3osch$1@dont-email.me> <tpdim3$3p3kb$1@dont-email.me> <tpel4n$ivd$1@gioia.aioe.org> <tpeurf$15ot$1@gioia.aioe.org> <slrntrmecl.o81.ike@sverige.sdf.org>

Cross-posted to 2 groups.

Show all headers | View raw

On 08/01/2023 21:45, Ike Naar wrote:
> On 2023-01-08, Bart <bc@freeuk.com> wrote:
>> On 08/01/2023 14:48, Bart wrote:
>>> On 08/01/2023 05:01, Bonita Montero wrote:
>>>> Now it's perfect:
>>>>
>>>> <snip complicated C++ code>>
>>
>>> That's some torturous-looking code.
>>
>> I tested your [BM] code for speed, using N=1000000, and limits of 1..N+1.
>>
>> The 'cout' in the loop was replaced with a count of all the values, so
>> that at the end the total was displayed to be able to compare results.
>>
>> The C++ with gcc-O3 took 1.25 seconds.
>>
>> My script initially took much longer due to using an unordered list
>> (storing up to 1M values). But I tweaked it use a bit-set.
>>
>> Then it took 0.67 seconds.
>>
>>
>> (Revised script:)
>>>   ??? a:=new(set,lower..upper)
>>>       sum:=0
>>
>>>   ??? to n do
>>>   ??????? repeat
>>>   ??????????? x:=random(lower..upper)
>>>   ??????? until x not in a
>>>   ??????? a[x]:=1
>>>           sum+:=x
>>>   ??? od
> 
> In the program below, each random number requires only constant time and
> retries are not necessary.
> For N=1000000 it runs in 0.01 second.
> 
> 
> #include <stdlib.h>
> #include <stdio.h>
> 
> enum {N = 1000000};
> static int used;
> static int numbers[N];
> /*
>    numbers[0 .. N) contain a permutation of [0 .. N)
>    0 <= used <= N
>    numbers[0 .. used) are available
>    numbers[used .. N) are already used
> */
> 
> static void reset(void)
> {
>    /* mark all numbers[0..N) as available */
>    used = N;
> }
> 
> static void init(void)
> {
>    /* fill numbers[0..N) with a permutation of [0..N) */
>    for (int i = 0; i != N; ++i)
>    {
>      numbers[i] = i;
>    }
> }
> 
> static int getrandom(void)
> {
>    /* pick a random value from the available numbers, and update the numbers array */
>    if (used == 0)
>    {
>      puts("ran out of available numbers");
>      abort();
>    }
>    int index = rand() % used;
>    --used;
>    int value = numbers[index];
>    numbers[index] = numbers[used];
>    numbers[used] = value;
>    return value;
> }
> 
> static void run(int length)
> /*
>    generate a run of 'length' unique numbers from the range [0..N)
> */
> {
>    reset();
>    long long sum = 0;
>    for (int i = 0; i != length; ++i)
>    {
>      sum += getrandom();
>    }
>    printf("%lld\n", sum);
> }
> 
> int main(void)
> {
>    /* if necessary, seed the PRNG (not done here) */
>    init();
>    run(N);
>    return 0;
> }

So, this is more of a shuffle? Since the set of numbers is not really 
random, it's a permutation of a consecutive range of values.

I tried your code on 10M numbers (to be easier to measure), and with 
gcc-O3 it took 0.22 seconds.

However, on Windows RAND_MAX is only about 32K, and the resulting 
numbers were not properly distributed. Doubling-up the rand calls was 
better, but the timing went up to 1.2 seconds for some reason.

I then imported my own prng, now timings were 0.3 seconds. Trying a 
similar shuffle on scripting code was about 3 seconds.

Thread

Compute Unique Numbers in a Set Albert <invalid@gmail.com> - 2022-12-26 23:45 +0000
  Re: Compute Unique Numbers in a Set "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-12-26 16:52 -0800
    Re: Compute Unique Numbers in a Set tTh <tth@none.invalid> - 2022-12-27 02:44 +0100
      Re: Compute Unique Numbers in a Set "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-12-27 13:35 -0800
  Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-26 20:47 -0500
    Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-27 15:57 +0000
      Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-27 11:16 -0500
        Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-27 16:59 +0000
          Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-27 12:24 -0500
            Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-27 17:53 +0000
              Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-27 13:50 -0500
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-27 20:08 +0000
                Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-27 15:31 -0500
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-28 02:57 +0000
                Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-27 23:02 -0500
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-29 02:06 +0000
                Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-28 23:42 -0500
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-29 12:26 +0000
  Re: Compute Unique Numbers in a Set Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-27 07:34 -0800
  Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-27 16:18 +0000
    Re: Compute Unique Numbers in a Set Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-12-28 01:08 +0000
      Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-28 03:30 +0000
    Re: Compute Unique Numbers in a Set Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-27 19:42 -0800
  Re: Compute Unique Numbers in a Set Manu Raju <MR@invalid.invalid> - 2022-12-27 18:11 +0000
  Re: Compute Unique Numbers in a Set antispam@math.uni.wroc.pl - 2022-12-28 01:32 +0000
    Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-27 21:13 -0500
      Re: Compute Unique Numbers in a Set Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-27 19:48 -0800
        Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-27 23:06 -0500
      Re: Compute Unique Numbers in a Set antispam@math.uni.wroc.pl - 2022-12-29 19:47 +0000
  Re: Compute Unique Numbers in a Set jak <nospam@please.ty> - 2022-12-28 11:28 +0100
  Re: Compute Unique Numbers in a Set Rosario19 <Ros@invalid.invalid> - 2023-01-01 21:06 +0100
    Re: Compute Unique Numbers in a Set Rosario19 <Ros@invalid.invalid> - 2023-01-02 06:43 +0100
  Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-01 23:19 +0000
    Re: Compute Unique Numbers in a Set jak <nospam@please.ty> - 2023-01-02 07:28 +0100
      Re: Compute Unique Numbers in a Set jak <nospam@please.ty> - 2023-01-02 08:48 +0100
      Re: Compute Unique Numbers in a Set Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-01 23:53 -0800
        Re: Compute Unique Numbers in a Set Öö Tiib <ootiib@hot.ee> - 2023-01-02 01:18 -0800
    Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-02 13:49 +0000
  Re: Compute Unique Numbers in a Set Bart <bc@freeuk.com> - 2023-01-02 12:27 +0000
  Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2023-01-02 12:13 -0500
    Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-02 17:31 +0000
      Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2023-01-02 12:46 -0500
      Re: Compute Unique Numbers in a Set Siri Cruise <chine.bleu@yahoo.com> - 2023-01-02 18:54 -0800
      Re: Compute Unique Numbers in a Set Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-02 20:52 -0800
      Re: Compute Unique Numbers in a Set David Brown <david.brown@hesbynett.no> - 2023-01-03 09:01 +0100
      Re: Compute Unique Numbers in a Set Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-03 07:28 -0800
        Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-03 15:46 +0000
          Re: Compute Unique Numbers in a Set David Brown <david.brown@hesbynett.no> - 2023-01-03 18:19 +0100
  Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-08 03:48 +0100
    Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-08 04:18 +0100
    Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-08 03:48 +0000
      Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-08 05:12 +0100
        Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-08 06:01 +0100
          Re: Compute Unique Numbers in a Set Bart <bc@freeuk.com> - 2023-01-08 14:48 +0000
            Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-08 18:22 +0100
              Re: Compute Unique Numbers in a Set Bart <bc@freeuk.com> - 2023-01-08 17:46 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-09 04:58 +0100
                Re: Compute Unique Numbers in a Set Bart <bc@freeuk.com> - 2023-01-09 11:26 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-09 15:57 +0100
            Re: Compute Unique Numbers in a Set Bart <bc@freeuk.com> - 2023-01-08 17:34 +0000
              Re: Compute Unique Numbers in a Set Ike Naar <ike@sdf.org> - 2023-01-08 21:45 +0000
                Re: Compute Unique Numbers in a Set Bart <bc@freeuk.com> - 2023-01-08 23:13 +0000
                Re: Compute Unique Numbers in a Set "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-01-08 15:18 -0800
          Re: Compute Unique Numbers in a Set Paavo Helde <eesnimi@osa.pri.ee> - 2023-01-08 21:19 +0200
          Re: Compute Unique Numbers in a Set "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-01-09 12:03 +0100
            Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-09 17:42 +0100
              Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-09 14:48 -0800
              Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-09 23:22 +0000
                Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-09 18:28 -0800
                Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-09 18:44 -0800
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-10 03:08 +0000
                Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-09 19:19 -0800
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-10 17:30 +0000
                Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-10 09:45 -0800
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-10 02:57 +0000
              Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-13 08:26 +0100
                Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-13 03:32 -0800
                Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-13 12:21 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-13 14:11 +0100
                Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-13 13:55 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-13 15:02 +0100
                Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-13 14:17 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-15 16:06 +0100
                Re: Compute Unique Numbers in a Set Bart <bc@freeuk.com> - 2023-01-15 16:27 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-15 17:42 +0100
                Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-15 17:11 +0000
        Re: Compute Unique Numbers in a Set tTh <tth@none.invalid> - 2023-01-08 10:13 +0100
          Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-08 10:25 +0100
            Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-08 13:20 +0000
    Re: Compute Unique Numbers in a Set "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-01-08 13:09 -0800
  Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-09 02:37 +0000
  Re: Compute Unique Numbers in a Set John Forkosh <forkosh@panix.com> - 2023-01-15 02:49 +0000

csiph-web