Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #88434 > unrolled thread
| Started by | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| First post | 2023-01-08 06:01 +0100 |
| Last post | 2023-01-13 05:04 -0800 |
| Articles | 20 on this page of 74 — 15 participants |
Back to article view | Back to comp.lang.c++
This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by
below is the oldest one visible, not the original post.
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 Tim Woodall <news001@woodall.me.uk> - 2023-01-13 06:35 +0000
Re: Compute Unique Numbers in a Set Tim Woodall <news001@woodall.me.uk> - 2023-01-13 06:39 +0000
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 Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-08 19:20 +0000
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 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-10 05:11 -0800
Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-10 05:19 -0800
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 Öö Tiib <ootiib@hot.ee> - 2023-01-13 03:26 -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 Ralf Goertz <me@myprovider.invalid> - 2023-01-15 16:47 +0100
Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-15 17:13 +0100
Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-15 08:57 -0800
Re: Compute Unique Numbers in a Set Ralf Goertz <me@myprovider.invalid> - 2023-01-16 09:46 +0100
Re: Compute Unique Numbers in a Set Ralf Goertz <me@myprovider.invalid> - 2023-01-16 10:21 +0100
Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-16 13:35 +0100
Re: Compute Unique Numbers in a Set Ralf Goertz <me@myprovider.invalid> - 2023-01-16 14:46 +0100
Re: Compute Unique Numbers in a Set Ralf Goertz <me@myprovider.invalid> - 2023-01-16 14:42 +0100
Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-16 16:38 +0000
Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-16 21:06 +0100
Re: Compute Unique Numbers in a Set Ralf Goertz <me@myprovider.invalid> - 2023-01-17 09:19 +0100
Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-17 09:30 +0000
Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-17 14:14 +0100
Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-17 07:48 -0800
Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-17 16:49 +0100
Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-17 17:32 +0100
Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-17 19:24 +0100
Re: Compute Unique Numbers in a Set Ralf Goertz <me@myprovider.invalid> - 2023-01-17 17:31 +0100
Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-17 17:10 +0000
Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-17 18:18 +0100
Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-18 09:23 +0000
Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-18 13:31 +0100
Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-18 16:16 +0000
Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-18 17:20 +0100
Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-18 16:24 +0000
Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-18 17:59 +0100
Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-18 17:14 +0000
Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-18 18:23 +0100
Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-19 09:31 +0000
Re: Compute Unique Numbers in a Set "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-01-17 12:48 -0800
Re: Compute Unique Numbers in a Set scott@slp53.sl.home (Scott Lurndal) - 2023-01-17 21:21 +0000
Re: Compute Unique Numbers in a Set "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-01-17 13:29 -0800
Re: Compute Unique Numbers in a Set Paul N <gw7rib@aol.com> - 2023-01-18 06:50 -0800
Re: Compute Unique Numbers in a Set "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-01-18 11:59 -0800
Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-17 16:25 +0000
Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-17 09:08 -0800
Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-17 17:16 +0000
Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-17 17:32 +0000
Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-18 09:23 +0000
Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-18 12:26 +0000
Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-18 16:09 +0000
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 Tim Woodall <news001@woodall.me.uk> - 2023-01-13 06:32 +0000
Re: Compute Unique Numbers in a Set Öö Tiib <ootiib@hot.ee> - 2023-01-13 05:04 -0800
Page 1 of 4 [1] 2 3 4 Next page →
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-01-08 06:01 +0100 |
| Subject | Re: Compute Unique Numbers in a Set |
| Message-ID | <tpdim3$3p3kb$1@dont-email.me> |
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;
}
}
[toc] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2023-01-08 14:48 +0000 |
| Message-ID | <tpel4n$ivd$1@gioia.aioe.org> |
| In reply to | #88434 |
On 08/01/2023 05:01, Bonita Montero wrote:
> 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;
> }
> }
That's some torturous-looking code. My attempt for the same spec is give
below, in scripting code. Despite that, I'd argue that it would simpler
to use that as a starting point to create a C version rather than try
and adapt your C++ code, because it is basically pseudo-code.
Half of this is just reading and checking command line inputs which can
be in any manner at all. In any case it's of little relevance; of much
more use would be a function that returned a set of N unique random
numbers, that can be embedded into another program.
Note that your error message is wrong: N would be too large, not too small.
Neither version seeds the PRNG so they're both useless on repeated runs.
----------------------------------------------------------------
if ncmdparams<>3 then
println "Usage: N From To"
stop 1
fi
read n:"i", lower:"i", upper:"i"
if lower>upper then swap(lower,upper) fi
if n > upper-lower+1 then
abort("N is too large")
fi
a::=()
to n do
repeat
x:=random(lower..upper)
until x not in a
a &:= x
println x
od
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-01-08 18:22 +0100 |
| Message-ID | <tpeu32$3t2it$1@dont-email.me> |
| In reply to | #88435 |
Am 08.01.2023 um 15:48 schrieb Bart: > That's some torturous-looking code. My attempt for the same spec is give > below, in scripting code. Despite that, I'd argue that it would simpler > to use that as a starting point to create a C version rather than try > and adapt your C++ code, because it is basically pseudo-code. C++ is used when things are usually not that simple and you have a performance requirement. If you strip the screen output and run the code with a large number of values any the given C++ code is magni- tudes faster than any scripting code.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2023-01-08 17:46 +0000 |
| Message-ID | <tpevhg$1g8i$1@gioia.aioe.org> |
| In reply to | #88436 |
On 08/01/2023 17:22, Bonita Montero wrote: > Am 08.01.2023 um 15:48 schrieb Bart: > >> That's some torturous-looking code. My attempt for the same spec is >> give below, in scripting code. Despite that, I'd argue that it would >> simpler to use that as a starting point to create a C version rather >> than try and adapt your C++ code, because it is basically pseudo-code. > > C++ is used when things are usually not that simple and you have a > performance requirement. If you strip the screen output and run the > code with a large number of values any the given C++ code is magni- > tudes faster than any scripting code. > I posted my last reply before I even saw this comment. I explained how I did exactly that! My script was faster. I've now tried N=10M and results are: C++ 79 seconds (g++ -O0) C++ 16 seconds (g++ -O3) Script (1) 13 seconds (HLL only, unoptimised) Script (2) 9.5 seconds (ASM-accelerated unoptimised) Script (3) 7.3 seconds (HLL only, optimised via C/gcc/-O3) The 'optimisation' refers to the interpreter; the program is still bytecode. The interesting thing is that my unoptimised interpeter, executing byte-code, is 6 times as fast as unoptimised C++ executing native code. (However I don't know what's going on inside your C++ libraries; this is where C has the advantage of transparency.)
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-01-09 04:58 +0100 |
| Message-ID | <tpg3bi$3bab$1@dont-email.me> |
| In reply to | #88438 |
Am 08.01.2023 um 18:46 schrieb Bart: > I've now tried N=10M and results are: > > C++ 79 seconds (g++ -O0) > C++ 16 seconds (g++ -O3) > Script (1) 13 seconds (HLL only, unoptimised) > Script (2) 9.5 seconds (ASM-accelerated unoptimised) > Script (3) 7.3 seconds (HLL only, optimised via C/gcc/-O3) Whatever you tested: you dindn't test my code.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2023-01-09 11:26 +0000 |
| Message-ID | <tpgtlv$18cp$1@gioia.aioe.org> |
| In reply to | #88447 |
On 09/01/2023 03:58, Bonita Montero wrote:
> Am 08.01.2023 um 18:46 schrieb Bart:
>
>> I've now tried N=10M and results are:
>>
>> C++ 79 seconds (g++ -O0)
>> C++ 16 seconds (g++ -O3)
>> Script (1) 13 seconds (HLL only, unoptimised)
>> Script (2) 9.5 seconds (ASM-accelerated unoptimised)
>> Script (3) 7.3 seconds (HLL only, optimised via C/gcc/-O3)
>
> Whatever you tested: you dindn't test my code.
>
>
It wasn't /my/ code because I don't know C++. It was just tweaked from
yours:
#include <iostream>
#include <unordered_set>
#include <charconv>
#include <random>
#include <string.h>
using namespace std;
int main( int argc, char **argv )
{
try
{
int n=10000000, from=1, to=n+1;
unordered_set<size_t> already;
already.reserve( n );
mt19937_64 mt;
uniform_int_distribution<size_t> uid( from, to );
long long int sum=0;
int i=0;
while( already.size() != n )
{
size_t value;
do
value = uid( mt );
while( already.contains( value ) );
already.emplace( value );
sum+=value;
// cout << value << " " << sum << " " << ++i << endl;
}
cout << sum << endl;
}
catch( exception const &exc )
{
return
cout << exc.what() << endl,
EXIT_FAILURE;
}
}
(The calculated 'sum' is not the sum of all the final set of values; I
realised I had no idea how to access those in a separate loop.)
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-01-09 15:57 +0100 |
| Message-ID | <tph9ve$7i53$1@dont-email.me> |
| In reply to | #88452 |
Am 09.01.2023 um 12:26 schrieb Bart:
> On 09/01/2023 03:58, Bonita Montero wrote:
>> Am 08.01.2023 um 18:46 schrieb Bart:
>>
>>> I've now tried N=10M and results are:
>>>
>>> C++ 79 seconds (g++ -O0)
>>> C++ 16 seconds (g++ -O3)
>>> Script (1) 13 seconds (HLL only, unoptimised)
>>> Script (2) 9.5 seconds (ASM-accelerated unoptimised)
>>> Script (3) 7.3 seconds (HLL only, optimised via C/gcc/-O3)
>>
>> Whatever you tested: you dindn't test my code.
>>
>>
> It wasn't /my/ code because I don't know C++. It was just tweaked from
> yours:
>
> #include <iostream>
> #include <unordered_set>
> #include <charconv>
> #include <random>
> #include <string.h>
>
> using namespace std;
>
> int main( int argc, char **argv )
> {
> try
> {
> int n=10000000, from=1, to=n+1;
> unordered_set<size_t> already;
> already.reserve( n );
> mt19937_64 mt;
> uniform_int_distribution<size_t> uid( from, to );
> long long int sum=0;
> int i=0;
> while( already.size() != n )
> {
> size_t value;
> do
> value = uid( mt );
> while( already.contains( value ) );
> already.emplace( value );
> sum+=value;
> // cout << value << " " << sum << " " << ++i << endl;
> }
> cout << sum << endl;
>
> }
> catch( exception const &exc )
> {
> return
> cout << exc.what() << endl,
> EXIT_FAILURE;
> }
> }
>
>
> (The calculated 'sum' is not the sum of all the final set of values; I
> realised I had no idea how to access those in a separate loop.)
You must have made sth. wrong.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2023-01-08 17:34 +0000 |
| Message-ID | <tpeurf$15ot$1@gioia.aioe.org> |
| In reply to | #88435 |
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
[toc] | [prev] | [next] | [standalone]
| From | Ike Naar <ike@sdf.org> |
|---|---|
| Date | 2023-01-08 21:45 +0000 |
| Message-ID | <slrntrmecl.o81.ike@sverige.sdf.org> |
| In reply to | #88437 |
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]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2023-01-08 23:13 +0000 |
| Message-ID | <tpfimu$5ft$1@gioia.aioe.org> |
| In reply to | #88441 |
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]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2023-01-08 15:18 -0800 |
| Message-ID | <tpfj09$3v65t$1@dont-email.me> |
| In reply to | #88444 |
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]
| From | Tim Woodall <news001@woodall.me.uk> |
|---|---|
| Date | 2023-01-13 06:35 +0000 |
| Message-ID | <tpqu4e$d70$2@einstein.home.woodall.me.uk> |
| In reply to | #88445 |
On 2023-01-08, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: > > It looks like shuffle of a set of unique numbers. > The original spec wasn't very clear but looked to me to be a choose m from n - which can be implemented as shuffle then choose first m (with further optimization that you only need to shuffle the first m slots)
[toc] | [prev] | [next] | [standalone]
| From | Tim Woodall <news001@woodall.me.uk> |
|---|---|
| Date | 2023-01-13 06:39 +0000 |
| Message-ID | <tpqua7$d70$3@einstein.home.woodall.me.uk> |
| In reply to | #88494 |
On 2023-01-13, Tim Woodall <news001@woodall.me.uk> wrote: > On 2023-01-08, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >> >> It looks like shuffle of a set of unique numbers. >> > > The original spec wasn't very clear but looked to me to be a choose m > from n - which can be implemented as shuffle then choose first m (with > further optimization that you only need to shuffle the first m slots) further optimization that you only need to shuffle *into* the first m slots) >
[toc] | [prev] | [next] | [standalone]
| From | Paavo Helde <eesnimi@osa.pri.ee> |
|---|---|
| Date | 2023-01-08 21:19 +0200 |
| Message-ID | <tpf50m$3toqh$1@dont-email.me> |
| In reply to | #88434 |
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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2023-01-08 19:20 +0000 |
| Message-ID | <87o7r8x28j.fsf@bsb.me.uk> |
| In reply to | #88434 |
Bonita Montero <Bonita.Montero@gmail.com> writes: > Now it's perfect: Does not even compile for me (g++ -std=c++20 required). -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Date | 2023-01-09 12:03 +0100 |
| Message-ID | <tpgsar$5mge$1@dont-email.me> |
| In reply to | #88434 |
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]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2023-01-09 17:42 +0100 |
| Message-ID | <tphg58$866f$1@dont-email.me> |
| In reply to | #88451 |
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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2023-01-09 23:22 +0000 |
| Message-ID | <87eds3uwdh.fsf@bsb.me.uk> |
| In reply to | #88455 |
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]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2023-01-10 05:11 -0800 |
| Message-ID | <68546107-b09f-4b3d-94d3-12e373a32974n@googlegroups.com> |
| In reply to | #88455 |
On Monday, 9 January 2023 at 16:42:32 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.
>
Here's my go.
#include <random>
#include <vector>
#include <cstdio>
/*
Draw a enadom number form the hypergeomtric distribution (sampling
from a bi-valued population without replacement)
rndengine - a random number generator engine
Ngood - number of positives in the population
Nbad - number of negatives in the population
Nsample - number of samples to take (less than or equal to Ngood + Nbad)
Returns: the number of "good" elements drawn, randomly.
*/
template<class rndengine>
int rand_hypergeometric(int Ngood, int Nbad, int Nsample, rndengine &eng)
{
int answer = 0;
std::uniform_real_distribution<double> distr(0, 1);
for (int i =0; i < Nsample; i++)
{
double p = distr(eng);
if (p < ((double)Ngood)/(Ngood + Nbad))
{
answer++;
Ngood--;
}
else
{
Nbad--;
}
}
return answer;
}
/*
Recursive randunique function
out - vector to collect results
Nsamples - number of samples to take
Npopulation - size of population
indexbase - fiddle to have populations not starting from 0, pass 0 at top level.
eng - the random number engine
*/
template<class rndengine>
void randunique_r(std::vector<int> &out, int Nsamples, int Npopulation,
int indexbase, rndengine &eng)
{
if (Nsamples == 0)
return;
std::uniform_int_distribution<int> distr(0, Npopulation -1);
int i = distr(eng);
int Nsampleslow = rand_hypergeometric(i, Npopulation - i -1, Nsamples-1, eng);
randunique_r(out, Nsampleslow, i, indexbase, eng);
out.push_back(i + indexbase);
randunique_r(out, Nsamples - Nsampleslow -1, Npopulation - i -1, indexbase + i, eng);
}
/*
Draw a set of unique random samples from a population
Nsamples - the number of elemnts to choose.
Npopulation - the population size
eng - the random number engine
Returns: vector with indices of chosen members, sorted ascending.
*/
template<class rndengine>
std::vector<int> randunique(int Nsamples, int Npopulation, rndengine &eng)
{
std::vector<int> answer;
randunique_r(answer, Nsamples, Npopulation, 0, eng);
return answer;
}
int main(void)
{
std::mt19937 engine(123);
std::vector<int> result = randunique(10, 20, engine);
for (int i =0; i <result.size(); i++)
printf("%d, ", result[i]);
printf("\n");
return 0;
}
Not very efficient. But the rand_hypergeometric functon is written naively.
It can be rewritten to run a lot faster, though this isn't easy.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2023-01-10 05:19 -0800 |
| Message-ID | <23856c7b-1a67-4bf4-a409-652769bdc64an@googlegroups.com> |
| In reply to | #88476 |
On Tuesday, 10 January 2023 at 13:11:27 UTC, Malcolm McLean wrote: > > randunique_r(out, Nsamples - Nsampleslow -1, Npopulation - i -1, indexbase + i, eng); > } Bug:: should be indexbase + i + 1.
[toc] | [prev] | [next] | [standalone]
Page 1 of 4 [1] 2 3 4 Next page →
Back to top | Article view | comp.lang.c++
csiph-web