Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #88445
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c, comp.lang.c++ |
| Subject | Re: Compute Unique Numbers in a Set |
| Date | 2023-01-08 15:18 -0800 |
| Organization | A noiseless patient Spider |
| Message-ID | <tpfj09$3v65t$1@dont-email.me> (permalink) |
| References | (4 earlier) <tpdim3$3p3kb$1@dont-email.me> <tpel4n$ivd$1@gioia.aioe.org> <tpeurf$15ot$1@gioia.aioe.org> <slrntrmecl.o81.ike@sverige.sdf.org> <tpfimu$5ft$1@gioia.aioe.org> |
Cross-posted to 2 groups.
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.
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web