 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Ross MacGregor
Guest
|
 Posted: Wed Aug 27, 2003 9:28 am Post subject: Re: STL Proposal: partial_random_shuffle() |
 |
|
Working in the game industry, randomization is used everywhere. It is a
fundamental operation.
I think partial_random_sort() should be included in the STL to guide
people. To show them this is the most efficient way to randomly select a
subset of elements from a container.
It took me several iterations of code before I realized
partial_random_sort() is the algoritm I should use, and was by far the
most efficient method (due to the swapping operations).
Also, I like to use Scott Meyers rule of thumb to use STL built-in
algorithms whereever possible. It implement partial_random_sort() I
needed to use a complex looping operation and create a template to make
it general purpose.
I think randomly selecting a subset of elements from a container is a
fundamental container operation and should be included. I don't think it
matters that it can be done in ten lines of code.
Francis Glassborow wrote:
| Quote: | In article <xYs2b.836859$ro6.16583126 (AT) news2 (DOT) calgary.shaw.ca>, Ross
MacGregor <rossmacgregor (AT) shaw (DOT) ca> writes
Shouldn't the STL include a partial_random_shuffle() to complement
partial_sort()?
Why? Library design is not some profound philosophical activity but
founded in need. partial_sort() is costly to develop for yourself and
has great benefits where the user only needs the top few out of a large
collection.
Making a random selection of a few elements of a large collection is
very easy to implement for oneself and so there is no great benefit in
providing it. In addition randomly shuffling the whole container is
usually perfectly suitable and has adequate performance.
|
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
llewelly
Guest
|
| Posted: Thu Aug 28, 2003 10:38 am Post subject: Re: STL Proposal: partial_random_shuffle() |
|
|
Ross MacGregor <rossmacgregor (AT) shaw (DOT) ca> writes:
| Quote: | Working in the game industry, randomization is used everywhere. It is a
fundamental operation.
I think partial_random_sort() should be included in the STL to guide
people. To show them this is the most efficient way to randomly select a
subset of elements from a container.
It took me several iterations of code before I realized
partial_random_sort() is the algoritm I should use, and was by far the
most efficient method (due to the swapping operations).
Also, I like to use Scott Meyers rule of thumb to use STL built-in
algorithms whereever possible. It implement partial_random_sort() I
needed to use a complex looping operation and create a template to make
it general purpose.
I think randomly selecting a subset of elements from a container is a
fundamental container operation and should be included. I don't think it
matters that it can be done in ten lines of code.
[snip] |
First, you've been using weird names for what you want. The subject
says ' partial_random_shuffle ' - but in your text you 3 times say
'partial_random_sort'. Then you say 'randomly select a subset of
elements from a contianer' - and niether of your names says that
to me. I'd call that function random_subset_select.
Whatever it is called, it is certainly important for games, but I
don't think it's necessary many other places. So arguably it
belongs in the 'Standard Game Programmer's C++ Library'
(unfortunately there is no such thing), but I don't think in the
'Standard C++ Library'. OTOH, look at all the numerics stuff that
got into C99 ... :-)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ross MacGregor
Guest
|
| Posted: Fri Aug 29, 2003 11:38 am Post subject: Re: STL Proposal: partial_random_shuffle() |
|
|
llewelly wrote:
| Quote: | First, you've been using weird names for what you want. The subject
says ' partial_random_shuffle ' - but in your text you 3 times say
'partial_random_sort'. Then you say 'randomly select a subset of
elements from a contianer' - and niether of your names says that
to me. I'd call that function random_subset_select.
|
Sorry, that was a bad typo in triplicate. I was comparing
partial_random_shuffle() to partial_sort() and got them terribly mixed up.
As for the the name, it is very much equivalent to partial_sort() so it
seemed an obvious choice. It maps nicely like this:
sort (beg, end, op) // sorts a container
random_shuffle(beg, end, op) // unsorts a container
partial_sort (beg, sort_end, end, op) // sorts N elements
partial_random_shuffle(beg, shuffle_end, end, op) // unsorts N elements
I think there is a great symmetry here myself, but people argue there is
only a need to partial sort not to partial unsort.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
llewelly
Guest
|
| Posted: Sat Aug 30, 2003 1:20 pm Post subject: Re: STL Proposal: partial_random_shuffle() |
|
|
Ross MacGregor <rossmacgregor (AT) shaw (DOT) ca> writes:
| Quote: | llewelly wrote:
First, you've been using weird names for what you want. The subject
says ' partial_random_shuffle ' - but in your text you 3 times say
'partial_random_sort'. Then you say 'randomly select a subset of
elements from a contianer' - and niether of your names says that
to me. I'd call that function random_subset_select.
Sorry, that was a bad typo in triplicate. I was comparing
partial_random_shuffle() to partial_sort() and got them terribly mixed up.
As for the the name, it is very much equivalent to partial_sort() so it
seemed an obvious choice. It maps nicely like this:
sort (beg, end, op) // sorts a container
random_shuffle(beg, end, op) // unsorts a container
|
I have a problem with your comment. random_shuffle will not likely
return the sorted container's contents to their original
(pre-sorted) order.
| Quote: | partial_sort (beg, sort_end, end, op) // sorts N elements
partial_random_shuffle(beg, shuffle_end, end, op) // unsorts N
elements
|
I can see a need for partial_random_shuffle - after all, I've had to
implement it a few times. But I don't think the need is broad
enough to warrant it's inclusion into the standard.
| Quote: | I think there is a great symmetry here myself, but people argue there is
only a need to partial sort not to partial unsort.
|
I don't see a connection between random_shuffle and unsort.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
