Ad
1: 2019-03-31 (Sun) 17:09:32 njf source Edit Backup No.1 as current. 2: 2019-03-31 (Sun) 18:01:40 njf source Edit Backup No.2 as current.
Line 35: Line 35:
など。 など。
-*よくあるサンプルにはだまされないように [#x1b6384d]+*よくあるサンプルは使わないのが無難 [#x1b6384d]
「配列 ランダム 並び替え」などでインターネット検索すると次のようなコードを記載したページが上位に現れます。 「配列 ランダム 並び替え」などでインターネット検索すると次のようなコードを記載したページが上位に現れます。
Line 48: Line 48:
         randomList[j] = a          randomList[j] = a
-つまり、配列から順に要素を選び、次にランダムに配列を一つ選び、この二つを入れ替えていく物です。+つまり、配列から順に要素を選び、次にランダムに要素を一つ選び、この二つを入れ替えていく物です。
これは結果がかなりかたよります。 これは結果がかなりかたよります。
Line 63: Line 63:
となり、明らかに14800ぐらいのものと、18500ぐらいのものに二分されました。 となり、明らかに14800ぐらいのものと、18500ぐらいのものに二分されました。
-これは[[こちら:http://nmi.jp/archives/541]]の記事で指摘されているように、アルゴリズムの構造的な欠陥です。+これは[[こちらの記事:http://nmi.jp/archives/541]]で指摘されているように、アルゴリズムの構造的な欠陥です。
-たとえば3つのものの並べ替えの結果は3!=6通りですが、上のアルゴリズムでは3回3つの要素をランダムに入れ替えるので、3*3*3=27通りです。+たとえば3つのものの並べ替えの結果は3!=6通りですが、上のアルゴリズムでは3回3つの要素をランダムに入れ替えるので、並び替えの方法の数は3*3*3=27通りです。
-27は6で割り切れませんから、かならず上のアルゴリズムはそれぞれの結果に対して、どれかが多く、どれかが少ない並べ替えを行っています。(詳しくは[[上記記事:http://nmi.jp/archives/541]]にあります。)+27は6で割り切れませんから、かならず上のアルゴリズムはそれぞれの結果に対して、どれかが多く、どれかが少なく並び替え方を割り振りを行って並べ替えています。(詳しくは[[上記記事:http://nmi.jp/archives/541]]にあります。)
今は長さ3の配列ですが、配列の長さが大きくなるにつれて不均等になりやすくなることも分かっています。 今は長さ3の配列ですが、配列の長さが大きくなるにつれて不均等になりやすくなることも分かっています。


Front page   Edit Diff Backup Upload Copy Rename ReloadPrint View   New Page Page list Search Recent changes   Help   RSS of recent changes (RSS 1.0) RSS of recent changes (RSS 2.0) RSS of recent changes (RSS Atom) Powered by xpWiki
Counter: 793, today: 2, yesterday: 1
広告

ログイン

ユーザー名:


パスワード:





パスワード紛失


NJF