Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #168644 > unrolled thread

Compute Unique Numbers in a Set

Back to article view | Back to comp.lang.c

Contents

  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

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

#168769

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;
}

[toc] | [prev] | [next] | [standalone]

#168770

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.

[toc] | [prev] | [next] | [standalone]

#168771

On 1/8/2023 3:13 PM, Bart wrote:
> 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

[...]

It looks like shuffle of a set of unique numbers.

[toc] | [prev] | [next] | [standalone]

#168766

08.01.2023 07:01 Bonita Montero kirjutas:
> Now it's perfect:
> 
> #include <iostream>
> #include <unordered_set>
> #include <charconv>
> #include <random>
> 
> using namespace std;
> 
> int main( int argc, char **argv )
> {
>      try
>      {
>          if( argc < 4 )
>              return
>                  cout << argv[0] << " n from to" << endl,
>                  EXIT_FAILURE;
>          auto parse = []( char const *str, char const *err )
>          {
>              size_t value;
>              if( from_chars_result fcr = from_chars( str, str + strlen( 
> str ), value ); (bool)fcr.ec || *fcr.ptr )
>                  throw invalid_argument( err );
>              return value;
>          };
>          size_t
>              n = parse( argv[1], "wrong number of values" ),
>              from = parse( argv[2], "wrong from-value" ),
>              to = parse( argv[3], "wrong to-value" );
>          if( from > to )
>              swap( from, to );
>          if( !n || n - 1 > to - from )
>              return
>                  cout << "n is too small" << endl,
>                  EXIT_FAILURE;
>          unordered_set<size_t> already;
>          already.reserve( n );
>          mt19937_64 mt;
>          uniform_int_distribution<size_t> uid( from, to );
>          while( already.size() != n )
>          {
>              size_t value;
>              do
>                  value = uid( mt );
>              while( already.contains( value ) );
>              already.emplace( value );
>              cout << value << endl;
>          }
>      }
>      catch( exception const &exc )
>      {
>          return
>              cout << exc.what() << endl,
>              EXIT_FAILURE;
>      }
> }

I see two issues with this perfect solution:

   - repeated values are excluded, so the randomness is less than 
perfect. But this seems to be by design.

   - two lookups in 'already' instead of the optimal one. What's wrong 
with insert() and checking its return value?

[toc] | [prev] | [next] | [standalone]

#168774

On 2023-01-08 6:01 AM, Bonita Montero wrote:
>          if( !n || n - 1 > to - from )
>              return
>                  cout << "n is too small" << endl,
>                  EXIT_FAILURE;

Presumably you meant "n is too large".

Tip: you can get vastly more clear code by avoiding side effects in 
expressions rather than trying to leverage such side effects.


>          unordered_set<size_t> already;
>          already.reserve( n );
>          mt19937_64 mt;
>          uniform_int_distribution<size_t> uid( from, to );
>          while( already.size() != n )
>          {
>              size_t value;
>              do
>                  value = uid( mt );
>              while( already.contains( value ) );
>              already.emplace( value );
>              cout << value << endl;
>          }

When n is large and is near or equal to the number of possible values, 
this loop becomes inefficient: for the last number you can expect on 
average n iterations to find that number, because each call of uid has a 
1/n chance of finding it.

Not sure of the exact overall complexity but for that case I guess O(n^2).

However this can be a good way to generate distinct random numbers when 
n is very small compared to the range size. But when n is close to the 
range size, if the range size is small compared to available memory then 
just store the sequence of numbers in the range and shuffle it, and use 
the first n values in the shuffled sequence. When neither of these 
conditions hold I don't know how to approach the problem; I'd probably 
then start by looking it up in Wikipedia or general googling.

- Alf

[toc] | [prev] | [next] | [standalone]

#168779

Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach:

> When n is large and is near or equal to the number of possible values, 
> this loop becomes inefficient: for the last number you can expect on 
> average n iterations to find that number, because each call of uid has a 
> 1/n chance of finding it.

I know that the loop becomes inefficient then, but tell me a better
alternative algorithm. You'd have a list of eligible numbers and
randomly chose one of them. That would also take a lot of time to
remove the number from the list.

[toc] | [prev] | [next] | [standalone]

#168781

On Monday, 9 January 2023 at 16:42:29 UTC, Bonita Montero wrote:
> Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach: 
> 
> > When n is large and is near or equal to the number of possible values, 
> > this loop becomes inefficient: for the last number you can expect on 
> > average n iterations to find that number, because each call of uid has a 
> > 1/n chance of finding it.
> I know that the loop becomes inefficient then, but tell me a better 
> alternative algorithm. You'd have a list of eligible numbers and 
> randomly chose one of them. That would also take a lot of time to 
> remove the number from the list.
>
Can't you try this?
Set M to the number of unique elements you want.
Iterate over the range from i = 0 to N -1.
For each i, generate a random number p on 0.0 to 1.0 minus epsilon.
If (p < M/(N-i)) add i to the set, and decrement M.

[toc] | [prev] | [next] | [standalone]

#168782

Bonita Montero <Bonita.Montero@gmail.com> writes:

> Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach:
>
>> When n is large and is near or equal to the number of possible
>> values, this loop becomes inefficient: for the last number you can
>> expect on average n iterations to find that number, because each call
>> of uid has a 1/n chance of finding it.
>
> I know that the loop becomes inefficient then, but tell me a better
> alternative algorithm.

An alternative that works well in those cases (and in some others) has
already been described where each candidate is chosen with the
appropriate probability.  I originally set it out as an exercises since
I thought the OP was doing homework, but the gist of it was explained.

> You'd have a list of eligible numbers and
> randomly chose one of them. That would also take a lot of time to
> remove the number from the list.

No need:

  void choose(int choose_n, int from_m, int *output)
  {
       for (int i = 0, j = 0; j < choose_n; i++)
            if (true_with_probability(choose_n - j, from_m - i))
                 output[j++] = i + 1;
  }

Obviously using one would not use this to choose 3 numbers from a set of
millions!

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#168783

On Monday, 9 January 2023 at 23:22:24 UTC, Ben Bacarisse wrote:
> Bonita Montero <Bonita....@gmail.com> writes: 
> 
> > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach: 
> > 
> >> When n is large and is near or equal to the number of possible 
> >> values, this loop becomes inefficient: for the last number you can 
> >> expect on average n iterations to find that number, because each call 
> >> of uid has a 1/n chance of finding it. 
> > 
> > I know that the loop becomes inefficient then, but tell me a better 
> > alternative algorithm.
> An alternative that works well in those cases (and in some others) has 
> already been described where each candidate is chosen with the 
> appropriate probability. I originally set it out as an exercises since 
> I thought the OP was doing homework, but the gist of it was explained.
> > You'd have a list of eligible numbers and 
> > randomly chose one of them. That would also take a lot of time to 
> > remove the number from the list.
> No need: 
> 
> void choose(int choose_n, int from_m, int *output) 
> { 
> for (int i = 0, j = 0; j < choose_n; i++) 
> if (true_with_probability(choose_n - j, from_m - i)) 
> output[j++] = i + 1; 
> } 
> 
> Obviously using one would not use this to choose 3 numbers from a set of 
> millions! 
> 
We're choosing M values from N.
If we choose a random member, i, then we have two sets, 0 to i-1, and i+1 to N-1,
and M-1 values left to choose.
So basically we would expect a binomial distribution, with each remaining value
having an  (i-1)/(N-1) chance of ending up in the first set. We then recurse.
However the whole point of the problem is that the distribution is discrete, and this
isn't quite correct, because we could end up with more values to choose than
members of the set. This would happen very rarely if N is large in relation to M,
but it could happen.
I'm not quite sure how to correct for this.

[toc] | [prev] | [next] | [standalone]

#168784

On Tuesday, 10 January 2023 at 02:28:48 UTC, Malcolm McLean wrote:
> On Monday, 9 January 2023 at 23:22:24 UTC, Ben Bacarisse wrote: 
> > Bonita Montero <Bonita....@gmail.com> writes: 
> > 
> > > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach: 
> > > 
> > >> When n is large and is near or equal to the number of possible 
> > >> values, this loop becomes inefficient: for the last number you can 
> > >> expect on average n iterations to find that number, because each call 
> > >> of uid has a 1/n chance of finding it. 
> > > 
> > > I know that the loop becomes inefficient then, but tell me a better 
> > > alternative algorithm. 
> > An alternative that works well in those cases (and in some others) has 
> > already been described where each candidate is chosen with the 
> > appropriate probability. I originally set it out as an exercises since 
> > I thought the OP was doing homework, but the gist of it was explained. 
> > > You'd have a list of eligible numbers and 
> > > randomly chose one of them. That would also take a lot of time to 
> > > remove the number from the list. 
> > No need: 
> > 
> > void choose(int choose_n, int from_m, int *output) 
> > { 
> > for (int i = 0, j = 0; j < choose_n; i++) 
> > if (true_with_probability(choose_n - j, from_m - i)) 
> > output[j++] = i + 1; 
> > } 
> > 
> > Obviously using one would not use this to choose 3 numbers from a set of 
> > millions! 
> >
> We're choosing M values from N. 
> If we choose a random member, i, then we have two sets, 0 to i-1, and i+1 to N-1, 
> and M-1 values left to choose. 
> So basically we would expect a binomial distribution, with each remaining value 
> having an (i-1)/(N-1) chance of ending up in the first set. We then recurse. 
> However the whole point of the problem is that the distribution is discrete, and this 
> isn't quite correct, because we could end up with more values to choose than 
> members of the set. This would happen very rarely if N is large in relation to M, 
> but it could happen. 
> I'm not quite sure how to correct for this.
>
Ah. It's the hypergeometric distribution. Very messy. 

[toc] | [prev] | [next] | [standalone]

#168786

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Tuesday, 10 January 2023 at 02:28:48 UTC, Malcolm McLean wrote:
>> On Monday, 9 January 2023 at 23:22:24 UTC, Ben Bacarisse wrote: 
>> > Bonita Montero <Bonita....@gmail.com> writes: 
>> > 
>> > > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach: 
>> > > 
>> > >> When n is large and is near or equal to the number of possible 
>> > >> values, this loop becomes inefficient: for the last number you can 
>> > >> expect on average n iterations to find that number, because each call 
>> > >> of uid has a 1/n chance of finding it. 
>> > > 
>> > > I know that the loop becomes inefficient then, but tell me a better 
>> > > alternative algorithm. 
>> > An alternative that works well in those cases (and in some others) has 
>> > already been described where each candidate is chosen with the 
>> > appropriate probability. I originally set it out as an exercises since 
>> > I thought the OP was doing homework, but the gist of it was explained. 
>> > > You'd have a list of eligible numbers and 
>> > > randomly chose one of them. That would also take a lot of time to 
>> > > remove the number from the list. 
>> > No need: 
>> > 
>> > void choose(int choose_n, int from_m, int *output) 
>> > { 
>> > for (int i = 0, j = 0; j < choose_n; i++) 
>> > if (true_with_probability(choose_n - j, from_m - i)) 
>> > output[j++] = i + 1; 
>> > } 
>> > 
>> > Obviously using one would not use this to choose 3 numbers from a set of 
>> > millions! 
>> >
>> We're choosing M values from N. 
>> If we choose a random member, i, then we have two sets, 0 to i-1, and i+1 to N-1, 
>> and M-1 values left to choose. 
>> So basically we would expect a binomial distribution, with each remaining value 
>> having an (i-1)/(N-1) chance of ending up in the first set. We then recurse. 
>> However the whole point of the problem is that the distribution is discrete, and this 
>> isn't quite correct, because we could end up with more values to choose than 
>> members of the set. This would happen very rarely if N is large in relation to M, 
>> but it could happen. 
>> I'm not quite sure how to correct for this.
>>
> Ah. It's the hypergeometric distribution. Very messy.

What quantity are you referring to?  There may be something that has a
messy distribution in all of this but (a) I don't know what quantity you
are talking about and (b) I don't think it matters.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#168787

On Tuesday, 10 January 2023 at 03:08:40 UTC, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> writes: 
> 
> > On Tuesday, 10 January 2023 at 02:28:48 UTC, Malcolm McLean wrote: 
> >> On Monday, 9 January 2023 at 23:22:24 UTC, Ben Bacarisse wrote: 
> >> > Bonita Montero <Bonita....@gmail.com> writes: 
> >> > 
> >> > > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach: 
> >> > > 
> >> > >> When n is large and is near or equal to the number of possible 
> >> > >> values, this loop becomes inefficient: for the last number you can 
> >> > >> expect on average n iterations to find that number, because each call 
> >> > >> of uid has a 1/n chance of finding it. 
> >> > > 
> >> > > I know that the loop becomes inefficient then, but tell me a better 
> >> > > alternative algorithm. 
> >> > An alternative that works well in those cases (and in some others) has 
> >> > already been described where each candidate is chosen with the 
> >> > appropriate probability. I originally set it out as an exercises since 
> >> > I thought the OP was doing homework, but the gist of it was explained. 
> >> > > You'd have a list of eligible numbers and 
> >> > > randomly chose one of them. That would also take a lot of time to 
> >> > > remove the number from the list. 
> >> > No need: 
> >> > 
> >> > void choose(int choose_n, int from_m, int *output) 
> >> > { 
> >> > for (int i = 0, j = 0; j < choose_n; i++) 
> >> > if (true_with_probability(choose_n - j, from_m - i)) 
> >> > output[j++] = i + 1; 
> >> > } 
> >> > 
> >> > Obviously using one would not use this to choose 3 numbers from a set of 
> >> > millions! 
> >> > 
> >> We're choosing M values from N. 
> >> If we choose a random member, i, then we have two sets, 0 to i-1, and i+1 to N-1, 
> >> and M-1 values left to choose. 
> >> So basically we would expect a binomial distribution, with each remaining value 
> >> having an (i-1)/(N-1) chance of ending up in the first set. We then recurse. 
> >> However the whole point of the problem is that the distribution is discrete, and this 
> >> isn't quite correct, because we could end up with more values to choose than 
> >> members of the set. This would happen very rarely if N is large in relation to M, 
> >> but it could happen. 
> >> I'm not quite sure how to correct for this. 
> >> 
> > Ah. It's the hypergeometric distribution. Very messy.
> What quantity are you referring to? There may be something that has a 
> messy distribution in all of this but (a) I don't know what quantity you 
> are talking about and (b) I don't think it matters. 
> 
The alorithm is we choose M values from a set of N.
So choose a single value, call it i, using a standard uniform random number.
Now we've got M-1 values to choose, from two sets, 0 to i-1, and i+1 to N-1.
So if we take another rnadom number, we can work out how many values
we need from the first set, and thus how many values from the second set, 
and we recurse.
But what is the distribution of those values? It's close to binomial. But it's
binomial without repalcement. Which is the hypergeomtric distribution.

However if we can draw one number from the hypergeomtric distribution,
in constant time, then the algorithm is O(M).

[toc] | [prev] | [next] | [standalone]

#168788

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Tuesday, 10 January 2023 at 03:08:40 UTC, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.ar...@gmail.com> writes: 
>> 
>> > On Tuesday, 10 January 2023 at 02:28:48 UTC, Malcolm McLean wrote: 
>> >> On Monday, 9 January 2023 at 23:22:24 UTC, Ben Bacarisse wrote: 
>> >> > Bonita Montero <Bonita....@gmail.com> writes: 
>> >> > 
>> >> > > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach: 
>> >> > > 
>> >> > >> When n is large and is near or equal to the number of possible 
>> >> > >> values, this loop becomes inefficient: for the last number you can 
>> >> > >> expect on average n iterations to find that number, because each call 
>> >> > >> of uid has a 1/n chance of finding it. 
>> >> > > 
>> >> > > I know that the loop becomes inefficient then, but tell me a better 
>> >> > > alternative algorithm. 
>> >> > An alternative that works well in those cases (and in some others) has 
>> >> > already been described where each candidate is chosen with the 
>> >> > appropriate probability. I originally set it out as an exercises since 
>> >> > I thought the OP was doing homework, but the gist of it was explained. 
>> >> > > You'd have a list of eligible numbers and 
>> >> > > randomly chose one of them. That would also take a lot of time to 
>> >> > > remove the number from the list. 
>> >> > No need: 
>> >> > 
>> >> > void choose(int choose_n, int from_m, int *output) 
>> >> > { 
>> >> > for (int i = 0, j = 0; j < choose_n; i++) 
>> >> > if (true_with_probability(choose_n - j, from_m - i)) 
>> >> > output[j++] = i + 1; 
>> >> > } 
>> >> > 
>> >> > Obviously using one would not use this to choose 3 numbers from a set of 
>> >> > millions! 
>> >> > 
>> >> We're choosing M values from N. 
>> >> If we choose a random member, i, then we have two sets, 0 to i-1, and i+1 to N-1, 
>> >> and M-1 values left to choose. 
>> >> So basically we would expect a binomial distribution, with each remaining value 
>> >> having an (i-1)/(N-1) chance of ending up in the first set. We then recurse. 
>> >> However the whole point of the problem is that the distribution is discrete, and this 
>> >> isn't quite correct, because we could end up with more values to choose than 
>> >> members of the set. This would happen very rarely if N is large in relation to M, 
>> >> but it could happen. 
>> >> I'm not quite sure how to correct for this. 
>> >> 
>> > Ah. It's the hypergeometric distribution. Very messy.
>> What quantity are you referring to? There may be something that has a 
>> messy distribution in all of this but (a) I don't know what quantity you 
>> are talking about and (b) I don't think it matters. 
>> 
> The alorithm is we choose M values from a set of N.

What algorithm?  You posted in direct reply to what I posted.  Are you
commenting on that code or just making some tangential remarks?  If it's
the latter, a reply to the head post would have been more logical.

> So choose a single value, call it i, using a standard uniform random
> number.

OK, so you are not talking about the algorithm I posted, right?

Ah.  I've seen a post in comp.lang.c++ with code and, yes, you are not
commenting on what I wrote.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#168789

On Tuesday, 10 January 2023 at 17:30:37 UTC, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> writes: 
> 
> > On Tuesday, 10 January 2023 at 03:08:40 UTC, Ben Bacarisse wrote: 
> >> Malcolm McLean <malcolm.ar...@gmail.com> writes: 
> >> 
> >> > On Tuesday, 10 January 2023 at 02:28:48 UTC, Malcolm McLean wrote: 
> >> >> On Monday, 9 January 2023 at 23:22:24 UTC, Ben Bacarisse wrote: 
> >> >> > Bonita Montero <Bonita....@gmail.com> writes: 
> >> >> > 
> >> >> > > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach: 
> >> >> > > 
> >> >> > >> When n is large and is near or equal to the number of possible 
> >> >> > >> values, this loop becomes inefficient: for the last number you can 
> >> >> > >> expect on average n iterations to find that number, because each call 
> >> >> > >> of uid has a 1/n chance of finding it. 
> >> >> > > 
> >> >> > > I know that the loop becomes inefficient then, but tell me a better 
> >> >> > > alternative algorithm. 
> >> >> > An alternative that works well in those cases (and in some others) has 
> >> >> > already been described where each candidate is chosen with the 
> >> >> > appropriate probability. I originally set it out as an exercises since 
> >> >> > I thought the OP was doing homework, but the gist of it was explained. 
> >> >> > > You'd have a list of eligible numbers and 
> >> >> > > randomly chose one of them. That would also take a lot of time to 
> >> >> > > remove the number from the list. 
> >> >> > No need: 
> >> >> > 
> >> >> > void choose(int choose_n, int from_m, int *output) 
> >> >> > { 
> >> >> > for (int i = 0, j = 0; j < choose_n; i++) 
> >> >> > if (true_with_probability(choose_n - j, from_m - i)) 
> >> >> > output[j++] = i + 1; 
> >> >> > } 
> >> >> > 
> >> >> > Obviously using one would not use this to choose 3 numbers from a set of 
> >> >> > millions! 
> >> >> > 
> >> >> We're choosing M values from N. 
> >> >> If we choose a random member, i, then we have two sets, 0 to i-1, and i+1 to N-1, 
> >> >> and M-1 values left to choose. 
> >> >> So basically we would expect a binomial distribution, with each remaining value 
> >> >> having an (i-1)/(N-1) chance of ending up in the first set. We then recurse. 
> >> >> However the whole point of the problem is that the distribution is discrete, and this 
> >> >> isn't quite correct, because we could end up with more values to choose than 
> >> >> members of the set. This would happen very rarely if N is large in relation to M, 
> >> >> but it could happen. 
> >> >> I'm not quite sure how to correct for this. 
> >> >> 
> >> > Ah. It's the hypergeometric distribution. Very messy. 
> >> What quantity are you referring to? There may be something that has a 
> >> messy distribution in all of this but (a) I don't know what quantity you 
> >> are talking about and (b) I don't think it matters. 
> >> 
> > The alorithm is we choose M values from a set of N.
> What algorithm? You posted in direct reply to what I posted. Are you 
> commenting on that code or just making some tangential remarks? If it's 
> the latter, a reply to the head post would have been more logical.
> > So choose a single value, call it i, using a standard uniform random 
> > number.
> OK, so you are not talking about the algorithm I posted, right? 
> 
> Ah. I've seen a post in comp.lang.c++ with code and, yes, you are not 
> commenting on what I wrote. 
> 
You said "We would not use this algorithm to choose 3 numbers froma  set of millions".
I was responding to that by providing an algorithm which does work well with such
a pair of sets. Sorry if that wasn't clear.

[toc] | [prev] | [next] | [standalone]

#168785

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Monday, 9 January 2023 at 23:22:24 UTC, Ben Bacarisse wrote:
>> Bonita Montero <Bonita....@gmail.com> writes: 
>> 
>> > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach: 
>> > 
>> >> When n is large and is near or equal to the number of possible 
>> >> values, this loop becomes inefficient: for the last number you can 
>> >> expect on average n iterations to find that number, because each call 
>> >> of uid has a 1/n chance of finding it. 
>> > 
>> > I know that the loop becomes inefficient then, but tell me a better 
>> > alternative algorithm.
>> An alternative that works well in those cases (and in some others) has 
>> already been described where each candidate is chosen with the 
>> appropriate probability. I originally set it out as an exercises since 
>> I thought the OP was doing homework, but the gist of it was explained.
>> > You'd have a list of eligible numbers and 
>> > randomly chose one of them. That would also take a lot of time to 
>> > remove the number from the list.
>> No need: 
>> 
>> void choose(int choose_n, int from_m, int *output) 
>> { 
>> for (int i = 0, j = 0; j < choose_n; i++) 
>> if (true_with_probability(choose_n - j, from_m - i)) 
>> output[j++] = i + 1; 
>> } 
>> 
>> Obviously using one would not use this to choose 3 numbers from a set of 
>> millions! 
>> 
> We're choosing M values from N.

This function chooses "choose_n" from "from_m".  Not great names I
admit...

> If we choose a random member, i, then we have two sets, 0 to i-1, and
> i+1 to N-1, and M-1 values left to choose.
> So basically we would expect a binomial distribution, with each
> remaining value having an (i-1)/(N-1) chance of ending up in the first
> set. We then recurse.
> However the whole point of the problem is that the distribution is>
> discrete, and this isn't quite correct, because we could end up with
> more values to choose than members of the set. This would happen very
> rarely if N is large in relation to M, but it could happen.  I'm not
> quite sure how to correct for this.

I can't follow this.  Do you think there is a problem with the
algorithm?

Every candidate is considered, and i is chosen with a probability that
takes account of how many numbers have already been selected (j) and how
many candidates remain (from_m - i).


-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#168793

Am 09.01.2023 um 17:42 schrieb Bonita Montero:
> Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach:
> 
>> When n is large and is near or equal to the number of possible values, 
>> this loop becomes inefficient: for the last number you can expect on 
>> average n iterations to find that number, because each call of uid has 
>> a 1/n chance of finding it.
> 
> I know that the loop becomes inefficient then, but tell me a better
> alternative algorithm. You'd have a list of eligible numbers and
> randomly chose one of them. That would also take a lot of time to
> remove the number from the list.

Now I make a list of eligible numbers, randomly chode one of them
and remove the item from the list:

#include <iostream>
#include <charconv>
#include <random>
#include <concepts>
#include <vector>

using namespace std;

int main( int argc, char **argv )
{
	try
	{
		if( argc < 4 )
			return
				cout << argv[0] << " n from to" << endl,
				EXIT_FAILURE;
		auto parse = []( char const *str, char const *err )
		{
			size_t value;
			if( from_chars_result fcr = from_chars( str, str + strlen( str ), 
value ); (bool)fcr.ec || *fcr.ptr )
				throw invalid_argument( err );
			return value;
		};
		size_t n = parse( argv[1], "wrong number of values" );
		if( !n )
			return EXIT_SUCCESS;
		size_t
			from = parse( argv[2], "wrong from-value" ),
			to = parse( argv[3], "wrong to-value" );
		if( from > to )
			swap( from, to );
		if( n - 1 > to - from )
			return
				cout << "n is too small" << endl,
				EXIT_FAILURE;
		vector<size_t> free;
		free.resize( to - from + 1 );
		for( size_t i = from; size_t &v : free )
			v = i++;
		mt19937_64 mt;
		size_t above = to;
		while( free.size() )
		{
			auto pick = free.begin() + (uniform_int_distribution<size_t>( 0, 
free.size() - 1 ))( mt );
			//cout << *pick << endl;
			free.erase( pick );
		}
	}
	catch( exception const &exc )
	{
		return
			cout << exc.what() << endl,
			EXIT_FAILURE;
	}
}

But that's _much_ slower.

[toc] | [prev] | [next] | [standalone]

#168794

On Friday, 13 January 2023 at 07:26:24 UTC, Bonita Montero wrote:
> Am 09.01.2023 um 17:42 schrieb Bonita Montero: 
> > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach: 
> > 
> >> When n is large and is near or equal to the number of possible values, 
> >> this loop becomes inefficient: for the last number you can expect on 
> >> average n iterations to find that number, because each call of uid has 
> >> a 1/n chance of finding it. 
> > 
> > I know that the loop becomes inefficient then, but tell me a better 
> > alternative algorithm. You'd have a list of eligible numbers and 
> > randomly chose one of them. That would also take a lot of time to 
> > remove the number from the list.
> Now I make a list of eligible numbers, randomly chode one of them 
> and remove the item from the list: 
> 
> #include <iostream> 
> #include <charconv> 
> #include <random> 
> #include <concepts> 
> #include <vector>
> using namespace std; 
> 
> int main( int argc, char **argv ) 
> { 
> try 
> {
> if( argc < 4 ) 
> return 
> cout << argv[0] << " n from to" << endl, 
> EXIT_FAILURE; 
> auto parse = []( char const *str, char const *err ) 
> { 
> size_t value; 
> if( from_chars_result fcr = from_chars( str, str + strlen( str ), 
> value ); (bool)fcr.ec || *fcr.ptr ) 
> throw invalid_argument( err ); 
> return value; 
> };
> size_t n = parse( argv[1], "wrong number of values" ); 
> if( !n ) 
> return EXIT_SUCCESS; 
> size_t
> from = parse( argv[2], "wrong from-value" ), 
> to = parse( argv[3], "wrong to-value" ); 
> if( from > to ) 
> swap( from, to );
> if( n - 1 > to - from )
> return 
> cout << "n is too small" << endl, 
> EXIT_FAILURE;
> vector<size_t> free; 
> free.resize( to - from + 1 ); 
> for( size_t i = from; size_t &v : free ) 
> v = i++; 
> mt19937_64 mt; 
> size_t above = to; 
> while( free.size() ) 
> { 
> auto pick = free.begin() + (uniform_int_distribution<size_t>( 0, 
> free.size() - 1 ))( mt ); 
> //cout << *pick << endl; 
> free.erase( pick );
> } 
> } 
> catch( exception const &exc ) 
> { 
> return 
> cout << exc.what() << endl, 
> EXIT_FAILURE; 
> } 
> }
> But that's _much_ slower.
>
Yes. If you construct a list of "free" choice, then the algorithm is at least O(N), where
N is the number of items to choose from. If you use a vector and delete, then it's
O(NM), where M is the number of choices. However you can change this by using
a container which allows for O(log N) deletion.

Run time is inherently at least O(M), where M is the number of choices. The question is
how far you can get down the other factors. And you need to avoid catastrophic behaviour
when M gets close to N. The other behaviour to avoid is an N term in the runtime, if N can 
be very large.

[toc] | [prev] | [next] | [standalone]

#168795

In article <tpr12i$1i7r6$1@dont-email.me>,
some lunatic  <Bonita.Montero@gmail.com> wrote:
...
>Now I make a list of eligible numbers, randomly chode one of them
>and remove the item from the list:
>
>#include <iostream>
>#include <charconv>
>#include <random>
>#include <concepts>
>#include <vector>

You still just don't seem to get this whole topicality thing, do ya?

-- 
Reading any post by Fred Hodgin, you're always faced with the choice of:
    lunatic, moron, or troll.

I always try to be generous and give benefit of the doubt, by assuming troll.

[toc] | [prev] | [next] | [standalone]

#168796

Am 13.01.2023 um 13:21 schrieb Kenny McCormack:
> In article <tpr12i$1i7r6$1@dont-email.me>,
> some lunatic  <Bonita.Montero@gmail.com> wrote:
> ...
>> Now I make a list of eligible numbers, randomly chode one of them
>> and remove the item from the list:
>>
>> #include <iostream>
>> #include <charconv>
>> #include <random>
>> #include <concepts>
>> #include <vector>
> 
> You still just don't seem to get this whole topicality thing, do ya?

My code is beyond that topic. You may elect only a small number
of values like in the original code, but you might also chose
million of numbers.

[toc] | [prev] | [next] | [standalone]

#168797

In article <tprl89$1k839$1@dont-email.me>,
some lunatic  <Bonita.Montero@gmail.com> wrote:
>Am 13.01.2023 um 13:21 schrieb Kenny McCormack:
>> In article <tpr12i$1i7r6$1@dont-email.me>,
>> some lunatic  <Bonita.Montero@gmail.com> wrote:
>> ...
>>> Now I make a list of eligible numbers, randomly chode one of them
>>> and remove the item from the list:
>>>
>>> #include <iostream>
>>> #include <charconv>
>>> #include <random>
>>> #include <concepts>
>>> #include <vector>
>> 
>> You still just don't seem to get this whole topicality thing, do ya?
>
>My code is beyond that topic. You may elect only a small number
>of values like in the original code, but you might also chose
>million of numbers.

Whoooooosh!!!

-- 
Many people in the American South think that DJT is, and will be remembered
as, one of the best presidents in US history. They are absolutely correct.

He is currently at number 46 on the list.  High praise, indeed!

[toc] | [prev] | [next] | [standalone]

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

Back to top | Article view | comp.lang.c

csiph-web