STLでrandom_shufleに存在する問題と改善(このブログは間違っている)
申し訳ありませんが、最近やっとこの博文が间违っていることに気づいて、ここで指摘して、二度と人を误导しないことを望んで、ああ、学芸が精巧ではありませんて、sorry、sorry!!!
先にG++のライブラリ関数のSTLのコードを貼り付けます:ubuntuの下のファイル/usr/include/c+/4.7/bits/stl_に由来しますalgo.h
コアのコードは最後の2行で、他のコードは注目しなくてもいいです.アルゴリズムの核心は、反復器を順次遍歴し、ランダムにiより小さい下付きjを生成し、現在の下付きiの要素と下付きjの要素を交換させることである.このようなアルゴリズムは、下にiと表記された要素が0−iの間に位置する傾向があるため、要素をランダム化することはできないに違いない.
改善されたアルゴリズム:
なぜ改善されたアルゴリズムが良いのでしょうか.STL版ランダム化アルゴリズムでnを生成!配列(重複を含む)、改良アルゴリズムはnn種配列(重複を含む)を生成することができ、n個数の全配列はn!である.つまりSTL版ランダム化アルゴリズムはn個数の全配列を生成することは不可能である.重複があるからである.もちろんこれは改良アルゴリズムが良いことを直接説明するわけではないが、少なくともSTL版の存在問題を説明している!!!
问题があれば指摘を歓迎します!!!
先にG++のライブラリ関数のSTLのコードを貼り付けます:ubuntuの下のファイル/usr/include/c+/4.7/bits/stl_に由来しますalgo.h
/**
* @brief Randomly shuffle the elements of a sequence.
* @ingroup mutating_algorithms
* @param __first A forward iterator.
* @param __last A forward iterator.
* @return Nothing.
*
* Reorder the elements in the range @p [__first,__last) using a random
* distribution, so that every possible ordering of the sequence is
* equally likely.
*/
template<typename _RandomAccessIterator>
inline void
random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
if (__first != __last)
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
}
コアのコードは最後の2行で、他のコードは注目しなくてもいいです.アルゴリズムの核心は、反復器を順次遍歴し、ランダムにiより小さい下付きjを生成し、現在の下付きiの要素と下付きjの要素を交換させることである.このようなアルゴリズムは、下にiと表記された要素が0−iの間に位置する傾向があるため、要素をランダム化することはできないに違いない.
改善されたアルゴリズム:
/**
* @brief Randomly shuffle the elements of a sequence.
* @ingroup mutating_algorithms
* @param __first A forward iterator.
* @param __last A forward iterator.
* @return Nothing.
*
* Reorder the elements in the range @p [__first,__last) using a random
* distribution, so that every possible ordering of the sequence is
* equally likely.
*/
template<typename _RandomAccessIterator>
inline void
random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
srand((unsigned)time(NULL));//
if (__first != __last)
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
std::iter_swap(__i, __first + (std::rand() % (__last - __first)));//
}
なぜ改善されたアルゴリズムが良いのでしょうか.STL版ランダム化アルゴリズムでnを生成!配列(重複を含む)、改良アルゴリズムはnn種配列(重複を含む)を生成することができ、n個数の全配列はn!である.つまりSTL版ランダム化アルゴリズムはn個数の全配列を生成することは不可能である.重複があるからである.もちろんこれは改良アルゴリズムが良いことを直接説明するわけではないが、少なくともSTL版の存在問題を説明している!!!
问题があれば指摘を歓迎します!!!