Ad
1: 2019-03-31 (日) 17:09:32 njf ソース バックアップ No.1 を復元して編集 2: 2019-03-31 (日) 18:01:40 njf ソース バックアップ No.2 を復元して編集
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の配列ですが、配列の長さが大きくなるにつれて不均等になりやすくなることも分かっています。


トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード印刷に適した表示   ページ新規作成 全ページ一覧 単語検索 最新ページの一覧   ヘルプ   最新ページのRSS 1.0 最新ページのRSS 2.0 最新ページのRSS Atom Powered by xpWiki
Counter: 1805, today: 1, yesterday: 0
MenuBar
広告

ログイン

ユーザー名:


パスワード:





パスワード紛失

Portuguese | English | German | Greek | Japanese | Korean | Russian | T-Chinese top
NJF