Groups > comp.lang.c++ > #88434 > unrolled thread

Re: Compute Unique Numbers in a Set

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 2 of 4 — ← Prev page 1 [2] 3 4 Next page →

#88496

From	Bonita Montero <Bonita.Montero@gmail.com>
Date	2023-01-13 08:26 +0100
Message-ID	<tpr12i$1i7r6$1@dont-email.me>
In reply to	#88455

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]

#88500

From	Öö Tiib <ootiib@hot.ee>
Date	2023-01-13 03:26 -0800
Message-ID	<1fdf11e6-a22d-4db3-b5ad-2276f5478af4n@googlegroups.com>
In reply to	#88496

On Friday, 13 January 2023 at 09:26:26 UTC+2, 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: 
> 
Some kind of weird algorithm ... what it supposedly does?
Why you require n from user if the algorithm does nothing with it? 
Variable above is also ignored, perhaps the algorithm is meant as
half-made complete-yourself pseudocode?

> But that's _much_ slower. 
> 
Very likely as it does do something odd.

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

#88501

From	gazelle@shell.xmission.com (Kenny McCormack)
Date	2023-01-13 12:21 +0000
Message-ID	<tprics$2h9b5$1@news.xmission.com>
In reply to	#88496

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]

#88504

From	Bonita Montero <Bonita.Montero@gmail.com>
Date	2023-01-13 14:11 +0100
Message-ID	<tprl89$1k839$1@dont-email.me>
In reply to	#88501

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]

#88505

From	gazelle@shell.xmission.com (Kenny McCormack)
Date	2023-01-13 13:55 +0000
Message-ID	<tprntf$2hb2h$1@news.xmission.com>
In reply to	#88504

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]

#88506

From	Bonita Montero <Bonita.Montero@gmail.com>
Date	2023-01-13 15:02 +0100
Message-ID	<tpro7o$1ki63$1@dont-email.me>
In reply to	#88505

Am 13.01.2023 um 14:55 schrieb Kenny McCormack:
> 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!!!

It's not the absolute number of values which can be chosen
but the flexibility or finding the most efficient way to
have this flexibility.

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

#88508

From	gazelle@shell.xmission.com (Kenny McCormack)
Date	2023-01-13 14:17 +0000
Message-ID	<tprp68$2hb2h$2@news.xmission.com>
In reply to	#88506

In article <tpro7o$1ki63$1@dont-email.me>,
some lunatic  <Bonita.Montero@gmail.com> wrote:
>Am 13.01.2023 um 14:55 schrieb Kenny McCormack:
>> 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!!!
>
>It's not the absolute number of values which can be chosen
>but the flexibility or finding the most efficient way to
>have this flexibility.

Due anziani che convivono da una vita:
Lei: "Caro, ormai ci potremmo anche sposare...".
Lui: "Ma cara, alla nostra eta', chi ci prenderebbe?".

-- 
"Women should not be enlightened or educated in any way. They should be
segregated because they are the cause of unholy erections in holy men.

    -- Saint Augustine (354-430) --

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

#88525

From	Bonita Montero <Bonita.Montero@gmail.com>
Date	2023-01-15 16:06 +0100
Message-ID	<tq14n7$2cgbf$1@dont-email.me>
In reply to	#88496

Now it's perfect:

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

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;
		unordered_set<size_t> values;
		mt19937_64 mt;
		uniform_int_distribution<size_t> uid( from, to );
		if( to - from != (size_t)-1 && to - from + 1 < n / 2 )
		{
			values.reserve( n );
			while( values.size() < n )
			{
				size_t value;
				do
					value = uid( mt );
				while( values.contains( value ) );
				values.emplace( value );
			}
		}
		else
		{
			if( to - from == (size_t)-1 )
				throw bad_alloc();
			values.reserve( to - from + 1 );
			size_t i = from - 1;
			do
				values.emplace( ++i );
			while( i != to );
			while( values.size() > n )
				for( ; ; )
				{
					auto itRemove = values.find( uid( mt ) );
					if( itRemove == values.end() )
						continue;
					values.erase( itRemove );
					break;
				}
		}
		for( size_t value : values )
			cout << value << endl;
	}
	catch( exception const &exc )
	{
		return
			cout << exc.what() << endl,
			EXIT_FAILURE;
	}
}

If less than half of the range of numbers is selected (n < (to - from
+ 1) / 2) the unordered map is filled up to n elements and if an element
is found that's already there another value is chosen. If more than half
of the range is selected (n >= (to - from + 1) / 2) the set is filled up
to contain the whole range and the elements are incrementally removed at
a random value.

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

#88526

From	Ralf Goertz <me@myprovider.invalid>
Date	2023-01-15 16:47 +0100
Message-ID	<tq1770$2ch5a$2@dont-email.me>
In reply to	#88525

Am Sun, 15 Jan 2023 16:06:00 +0100
schrieb Bonita Montero <Bonita.Montero@gmail.com>:

> Now it's perfect:
 
[snip]

> If less than half of the range of numbers is selected (n < (to - from
> + 1) / 2) the unordered map is filled up to n elements and if an
> element is found that's already there another value is chosen. If
> more than half of the range is selected (n >= (to - from + 1) / 2)
> the set is filled up to contain the whole range and the elements are
> incrementally removed at a random value.

What's wrong with a clean two line solution:


#include <algorithm>
#include <iostream>
#include <random>
#include <charconv>
#include <vector>
#include <cstring>

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;
		mt19937_64 mt;
        vector<int> values( to - from );
        // ------
        //only two lines to find random subset of fixed size:
        fill(values.begin(), values.begin() + n, 1);
        shuffle(values.begin(), values.end(), mt);
        // ------
        for( size_t i=0; i < values.size(); ++i )
			if( values[i]) cout << i+from << endl;
	}
	catch( exception const &exc )
	{
		return
			cout << exc.what() << endl,
			EXIT_FAILURE;
	}
}

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

#88527

From	Bonita Montero <Bonita.Montero@gmail.com>
Date	2023-01-15 17:13 +0100
Message-ID	<tq18lu$2csp4$1@dont-email.me>
In reply to	#88526

Am 15.01.2023 um 16:47 schrieb Ralf Goertz:
> Am Sun, 15 Jan 2023 16:06:00 +0100
> schrieb Bonita Montero <Bonita.Montero@gmail.com>:
> 
>> Now it's perfect:
>   
> [snip]
> 
>> If less than half of the range of numbers is selected (n < (to - from
>> + 1) / 2) the unordered map is filled up to n elements and if an
>> element is found that's already there another value is chosen. If
>> more than half of the range is selected (n >= (to - from + 1) / 2)
>> the set is filled up to contain the whole range and the elements are
>> incrementally removed at a random value.
> 
> What's wrong with a clean two line solution:

You might have less numbers than to - from + 1 (you omitted the 1 on
allocation of the vector).

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

#88530

From	Malcolm McLean <malcolm.arthur.mclean@gmail.com>
Date	2023-01-15 08:57 -0800
Message-ID	<ee5874c7-be6d-4bc5-902b-1a04bfa7003en@googlegroups.com>
In reply to	#88526

On Sunday, 15 January 2023 at 15:48:01 UTC, Ralf Goertz wrote:
> Am Sun, 15 Jan 2023 16:06:00 +0100 
> schrieb Bonita Montero <Bonita....@gmail.com>: 
> 
> > Now it's perfect: 
> 
> [snip]
> > If less than half of the range of numbers is selected (n < (to - from 
> > + 1) / 2) the unordered map is filled up to n elements and if an 
> > element is found that's already there another value is chosen. If 
> > more than half of the range is selected (n >= (to - from + 1) / 2) 
> > the set is filled up to contain the whole range and the elements are 
> > incrementally removed at a random value.
> What's wrong with a clean two line solution: 
> 
> 
> #include <algorithm> 
> #include <iostream> 
> #include <random> 
> #include <charconv> 
> #include <vector> 
> #include <cstring>
> 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;
> mt19937_64 mt; 
> vector<int> values( to - from ); 
> // ------ 
> //only two lines to find random subset of fixed size: 
> fill(values.begin(), values.begin() + n, 1); 
> shuffle(values.begin(), values.end(), mt); 
> // ------ 
> for( size_t i=0; i < values.size(); ++i ) 
> if( values[i]) cout << i+from << endl;
> } 
> catch( exception const &exc ) 
> { 
> return 
> cout << exc.what() << endl, 
> EXIT_FAILURE; 
> } 
> }
>
Where N is the range and M the number of elements to choose, it's O(N)
in space and time. So unsuitable if N is very much larger than M.

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

#88534

From	Ralf Goertz <me@myprovider.invalid>
Date	2023-01-16 09:46 +0100
Message-ID	<tq32sn$2lmca$1@dont-email.me>
In reply to	#88530

Am Sun, 15 Jan 2023 08:57:24 -0800 (PST)
schrieb Malcolm McLean <malcolm.arthur.mclean@gmail.com>:

> On Sunday, 15 January 2023 at 15:48:01 UTC, Ralf Goertz wrote:
> > Am Sun, 15 Jan 2023 16:06:00 +0100 
> > schrieb Bonita Montero <Bonita....@gmail.com>: 
> >   
> > > Now it's perfect:   
> > 
> > [snip]  
> > > If less than half of the range of numbers is selected (n < (to -
> > > from 
> > > + 1) / 2) the unordered map is filled up to n elements and if an 
> > > element is found that's already there another value is chosen. If 
> > > more than half of the range is selected (n >= (to - from + 1) /
> > > 2) the set is filled up to contain the whole range and the
> > > elements are incrementally removed at a random value.  
> > What's wrong with a clean two line solution: 
> > …
> > // ------ 
> > //only two lines to find random subset of fixed size: 
> > fill(values.begin(), values.begin() + n, 1); 
> > shuffle(values.begin(), values.end(), mt); 
> > // ------ 
> > …
> >  
> Where N is the range and M the number of elements to choose, it's O(N)
> in space and time. So unsuitable if N is very much larger than M.

I just tried it out. Both methods (mine with the corrected off by 1
error) applied 100000 times outputting the last result:

./rg 10 1 1000
193 198 257 384 474 581 606 620 682 954 
0.718732s

./rg 990 1 1000
…
0.715686s

./bonita 10 1 1000
919 888 875 567 563 499 323 306 61 34 
14.0962s

./bonita 990 1 1000
…
4.7713s


The problem seems to be the unordered_set. I created it outside the loop
(just like my vector), but I had to empty it at the beginning of the
loop. (Is there another way to reuse it?) So in theory you're right but
I guess the set approach is a heavy burden.

My loop:

for (int k=0; k < 100000 ; ++k) {
    fill( values.begin(), values.begin() + n, 1);
    fill( values.begin() + n, values.end(), 0);
    shuffle(values.begin(), values.end(), mt);
}

bonita's:

for (int k=0; k < 100000 ; ++k) {
    values.erase( values.begin(), values.end()); 
    //her stuff
}

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

#88535

From	Ralf Goertz <me@myprovider.invalid>
Date	2023-01-16 10:21 +0100
Message-ID	<tq34ui$2lmca$2@dont-email.me>
In reply to	#88534

Am Mon, 16 Jan 2023 09:46:15 +0100
schrieb Ralf Goertz <me@myprovider.invalid>:

> Am Sun, 15 Jan 2023 08:57:24 -0800 (PST)
> schrieb Malcolm McLean <malcolm.arthur.mclean@gmail.com>:
> 
> > On Sunday, 15 January 2023 at 15:48:01 UTC, Ralf Goertz wrote:  
> > > Am Sun, 15 Jan 2023 16:06:00 +0100 
> > > schrieb Bonita Montero <Bonita....@gmail.com>: 
> > >     
> > > > Now it's perfect:     
> > > 
> > > [snip]    
> > > > If less than half of the range of numbers is selected (n < (to -
> > > > from 
> > > > + 1) / 2) the unordered map is filled up to n elements and if
> > > > an element is found that's already there another value is
> > > > chosen. If more than half of the range is selected (n >= (to -
> > > > from + 1) / 2) the set is filled up to contain the whole range
> > > > and the elements are incrementally removed at a random value.
> > > >  
> > > What's wrong with a clean two line solution: 
> > > …
> > > // ------ 
> > > //only two lines to find random subset of fixed size: 
> > > fill(values.begin(), values.begin() + n, 1); 
> > > shuffle(values.begin(), values.end(), mt); 
> > > // ------ 
> > > …
> > >    
> > Where N is the range and M the number of elements to choose, it's
> > O(N) in space and time. So unsuitable if N is very much larger than
> > M.  
> 
> I just tried it out. Both methods (mine with the corrected off by 1
> error) applied 100000 times outputting the last result:
> 
> ./rg 10 1 1000
> 193 198 257 384 474 581 606 620 682 954 
> 0.718732s
> 
> ./rg 990 1 1000
> …
> 0.715686s
> 
> ./bonita 10 1 1000
> 919 888 875 567 563 499 323 306 61 34 
> 14.0962s
> 
> ./bonita 990 1 1000
> …
> 4.7713s
> 
> 
> The problem seems to be the unordered_set. I created it outside the
> loop (just like my vector), but I had to empty it at the beginning of
> the loop. (Is there another way to reuse it?) So in theory you're
> right but I guess the set approach is a heavy burden.

Surprisingly, Bonita's method also seems to be very dependent on the
range:

./rg 10 1 10000
214 2035 2188 3525 4142 5765 6021 6571 7000 8902 
7.09215s

(No surprise here.)


./bonita 10 1 10000
7400 7185 5343 4357 2990 2011 1478 1078 859 719 
184.93s

(Wow!)

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

#88540

From	Bonita Montero <Bonita.Montero@gmail.com>
Date	2023-01-16 13:35 +0100
Message-ID	<tq3g9r$2nhg2$1@dont-email.me>
In reply to	#88535

Am 16.01.2023 um 10:21 schrieb Ralf Goertz:

> Surprisingly, Bonita's method also seems to be very dependent on the
> range:
> 
> ./rg 10 1 10000
> 214 2035 2188 3525 4142 5765 6021 6571 7000 8902
> 7.09215s
> 
> (No surprise here.)
> 
> 
> ./bonita 10 1 10000
> 7400 7185 5343 4357 2990 2011 1478 1078 859 719
> 184.93s

Test the algorithm without screen output !

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

#88541

From	Ralf Goertz <me@myprovider.invalid>
Date	2023-01-16 14:46 +0100
Message-ID	<tq3kge$2ngf9$2@dont-email.me>
In reply to	#88540

Resent the reply, since I can't see it on my server.

Am Mon, 16 Jan 2023 13:35:57 +0100 schrieb Bonita Montero
<Bonita.Montero@gmail.com>:

> Am 16.01.2023 um 10:21 schrieb Ralf Goertz:
>   
> > Surprisingly, Bonita's method also seems to be very dependent on the
> > range:
> > 
> > ./rg 10 1 10000
> > 214 2035 2188 3525 4142 5765 6021 6571 7000 8902
> > 7.09215s
> > 
> > (No surprise here.)
> > 
> > 
> > ./bonita 10 1 10000
> > 7400 7185 5343 4357 2990 2011 1478 1078 859 719
> > 184.93s    
> 
> Test the algorithm without screen output !  

I did of course! The timer starts immediately before the loop and stops
after it, before only the last result is output. Your version:


#include <iostream>
#include <unordered_set>
#include <charconv>
#include <random>
#include <concepts>
#include <chrono>
#include <cstring>

using namespace std;
using namespace std::chrono;

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;
        unordered_set<size_t> values;
        mt19937_64 mt;
        uniform_int_distribution<size_t> uid( from, to );
        steady_clock::time_point t1 = steady_clock::now();
        for (int k=0; k < 100000 ; ++k) {
            values.erase( values.begin(), values.end());
            if( to - from != (size_t)-1 && to - from + 1 < n / 2 )
            {
                values.reserve( n );
                while( values.size() < n )
                {
                    size_t value;
                    do
                        value = uid( mt );
                    while( values.contains( value ) );
                    values.emplace( value );
                }
            }
            else
            {
                if( to - from == (size_t)-1 )
                    throw bad_alloc();
                values.reserve( to - from + 1 );
                size_t i = from - 1;
                do
                    values.emplace( ++i );
                while( i != to );
                while( values.size() > n )
                    for( ; ; )
                    {
                        auto itRemove = values.find( uid( mt ) );
                        if( itRemove == values.end() )
                            continue;
                        values.erase( itRemove );
                        break;
                    }
            }
        }
        steady_clock::time_point t2 = steady_clock::now();
        for( size_t value : values )
            cout << value << " ";
        cout << endl << duration_cast<duration<double>>(t2 - t1)<<endl;
    }
    catch( exception const &exc )
    {
        return
            cout << exc.what() << endl,
            EXIT_FAILURE;
    }
}


and mine:


#include <algorithm>
#include <iostream>
#include <random>
#include <charconv>
#include <vector>
#include <cstring>
#include <chrono>

using namespace std;
using namespace std::chrono;

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;
        mt19937_64 mt;
        vector<int> values( to - from + 1);
        steady_clock::time_point t1 = steady_clock::now();
        for (int k=0; k < 100000 ; ++k) {
            fill(values.begin(), values.begin() + n, 1);
            fill(values.begin() + n, values.end(), 0);
            shuffle(values.begin(), values.end(), mt);
        }
        steady_clock::time_point t2 = steady_clock::now();
        for( size_t i=0; i < values.size(); ++i )
            if( values[i]) cout << i+from << " ";
        cout << endl << duration_cast<duration<double>>(t2 - t1)<<endl;

    }
    catch( exception const &exc )
    {
        return
            cout << exc.what() << endl,
                 EXIT_FAILURE;
    }
}

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

#88542

From	Ralf Goertz <me@myprovider.invalid>
Date	2023-01-16 14:42 +0100
Message-ID	<tq3k8q$2ngf9$1@dont-email.me>
In reply to	#88540

Am Mon, 16 Jan 2023 13:35:57 +0100
schrieb Bonita Montero <Bonita.Montero@gmail.com>:

> Am 16.01.2023 um 10:21 schrieb Ralf Goertz:
> 
> > Surprisingly, Bonita's method also seems to be very dependent on the
> > range:
> > 
> > ./rg 10 1 10000
> > 214 2035 2188 3525 4142 5765 6021 6571 7000 8902
> > 7.09215s
> > 
> > (No surprise here.)
> > 
> > 
> > ./bonita 10 1 10000
> > 7400 7185 5343 4357 2990 2011 1478 1078 859 719
> > 184.93s  
> 
> Test the algorithm without screen output !

I did of course! The timer starts immediately before the loop and stops
after it, before only the last result is output. Your version:


#include <iostream>
#include <unordered_set>
#include <charconv>
#include <random>
#include <concepts>
#include <chrono>
#include <cstring>

using namespace std;
using namespace std::chrono;

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;
        unordered_set<size_t> values;
        mt19937_64 mt;
        uniform_int_distribution<size_t> uid( from, to );
        steady_clock::time_point t1 = steady_clock::now();
        for (int k=0; k < 100000 ; ++k) {
            values.erase( values.begin(), values.end());
            if( to - from != (size_t)-1 && to - from + 1 < n / 2 )
            {
                values.reserve( n );
                while( values.size() < n )
                {
                    size_t value;
                    do
                        value = uid( mt );
                    while( values.contains( value ) );
                    values.emplace( value );
                }
            }
            else
            {
                if( to - from == (size_t)-1 )
                    throw bad_alloc();
                values.reserve( to - from + 1 );
                size_t i = from - 1;
                do
                    values.emplace( ++i );
                while( i != to );
                while( values.size() > n )
                    for( ; ; )
                    {
                        auto itRemove = values.find( uid( mt ) );
                        if( itRemove == values.end() )
                            continue;
                        values.erase( itRemove );
                        break;
                    }
            }
        }
        steady_clock::time_point t2 = steady_clock::now();
        for( size_t value : values )
            cout << value << " ";
        cout << endl << duration_cast<duration<double>>(t2 - t1)<<endl;
    }
    catch( exception const &exc )
    {
        return
            cout << exc.what() << endl,
            EXIT_FAILURE;
    }
}


and mine:


#include <algorithm>
#include <iostream>
#include <random>
#include <charconv>
#include <vector>
#include <cstring>
#include <chrono>

using namespace std;
using namespace std::chrono;

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;
        mt19937_64 mt;
        vector<int> values( to - from + 1);
        steady_clock::time_point t1 = steady_clock::now();
        for (int k=0; k < 100000 ; ++k) {
            fill(values.begin(), values.begin() + n, 1);
            fill(values.begin() + n, values.end(), 0);
            shuffle(values.begin(), values.end(), mt);
        }
        steady_clock::time_point t2 = steady_clock::now();
        for( size_t i=0; i < values.size(); ++i )
            if( values[i]) cout << i+from << " ";
        cout << endl << duration_cast<duration<double>>(t2 - t1)<<endl;

    }
    catch( exception const &exc )
    {
        return
            cout << exc.what() << endl,
                 EXIT_FAILURE;
    }
}

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

#88543

From	Muttley@dastardlyhq.com
Date	2023-01-16 16:38 +0000
Message-ID	<tq3uhs$16if$1@gioia.aioe.org>
In reply to	#88542

On Mon, 16 Jan 2023 14:42:50 +0100
Ralf Goertz <me@myprovider.invalid> wrote:
>Am Mon, 16 Jan 2023 13:35:57 +0100
>schrieb Bonita Montero <Bonita.Montero@gmail.com>:
>
>> Am 16.01.2023 um 10:21 schrieb Ralf Goertz:
>> 
>> > Surprisingly, Bonita's method also seems to be very dependent on the
>> > range:
>> > 
>> > ./rg 10 1 10000
>> > 214 2035 2188 3525 4142 5765 6021 6571 7000 8902
>> > 7.09215s
>> > 
>> > (No surprise here.)
>> > 
>> > 
>> > ./bonita 10 1 10000
>> > 7400 7185 5343 4357 2990 2011 1478 1078 859 719
>> > 184.93s  
>> 
>> Test the algorithm without screen output !
>
>I did of course! The timer starts immediately before the loop and stops
>after it, before only the last result is output. Your version:

But wait, didn't she state that her algorithm was "perfect"? I simply won't
believe Bonita has more hubris and self delusion than an angry mouse.

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

#88549

From	Bonita Montero <Bonita.Montero@gmail.com>
Date	2023-01-16 21:06 +0100
Message-ID	<tq4an1$2s02t$1@dont-email.me>
In reply to	#88543

Am 16.01.2023 um 17:38 schrieb Muttley@dastardlyhq.com:

> But wait, didn't she state that her algorithm was "perfect"? I simply won't
> believe Bonita has more hubris and self delusion than an angry mouse.

And you don't check that Ralf's code does sth. completely different.

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

#88551

From	Ralf Goertz <me@myprovider.invalid>
Date	2023-01-17 09:19 +0100
Message-ID	<tq5ln0$35a9d$1@dont-email.me>
In reply to	#88549

Am Mon, 16 Jan 2023 21:06:41 +0100
schrieb Bonita Montero <Bonita.Montero@gmail.com>:

> Am 16.01.2023 um 17:38 schrieb Muttley@dastardlyhq.com:
> 
> > But wait, didn't she state that her algorithm was "perfect"? I
> > simply won't believe Bonita has more hubris and self delusion than
> > an angry mouse.  
> 
> And you don't check that Ralf's code does sth. completely different.

I assume you don't mean to say, that I implemented your algorithm
incorrectly (if I'm wrong about that will you please care to elaborate?)
but that my algorithm is completely different from yours. Then, yes that
was my point. I don't understand why you use such a complicated
algorithm (compared to the very few lines I needed) if it doesn't
outperform a much simpler approach. Of course one could say that I hid
the complexity behind the call to std::shuffle() but you do the same
with std::unordered_set.emplace() an co.

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

#88552

From	Muttley@dastardlyhq.com
Date	2023-01-17 09:30 +0000
Message-ID	<tq5prq$1u45$1@gioia.aioe.org>
In reply to	#88551

On Tue, 17 Jan 2023 09:19:44 +0100
Ralf Goertz <me@myprovider.invalid> wrote:
>Am Mon, 16 Jan 2023 21:06:41 +0100
>schrieb Bonita Montero <Bonita.Montero@gmail.com>:
>
>> Am 16.01.2023 um 17:38 schrieb Muttley@dastardlyhq.com:
>> 
>> > But wait, didn't she state that her algorithm was "perfect"? I
>> > simply won't believe Bonita has more hubris and self delusion than
>> > an angry mouse.  
>> 
>> And you don't check that Ralf's code does sth. completely different.
>
>I assume you don't mean to say, that I implemented your algorithm
>incorrectly (if I'm wrong about that will you please care to elaborate?)
>but that my algorithm is completely different from yours. Then, yes that
>was my point. I don't understand why you use such a complicated
>algorithm (compared to the very few lines I needed) if it doesn't

You must be new here :) Complexity is Bonitas calling card.

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

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

csiph-web

Re: Compute Unique Numbers in a Set

Contents

#88496

#88500

#88501

#88504

#88505

#88506

#88508

#88525

#88526

#88527

#88530

#88534

#88535

#88540

#88541

#88542

#88543

#88549

#88551

#88552