第13回　考える楽しさ、習う楽しさ「１．さて問題です」

13−１　さて問題です

唐突ですが、問題です。

「１から30までの数字を、重複なく、ランダムに並べ替えた数列を作って下さい。」

Basic BASIC 第13回は、１つの問題からスタートです。皆さんならどうやって考えますか？
「定番はあの方法かな」といわれる方は、とりあえず読み飛ばして頂いて結構ですが、興味をもたれた方は、是非、考えてください。
まだ、プログラムを組まなくても結構です。頭の中で「どうやって作ろう」という大雑把なイメージを浮かべてみてください。

・・・・・・・・・・・・・・・・・・・
・・・・・・・・考え中・・・・・・・・
・・・・・・・・・・・・・・・・・・・

いかがですか？何らかの方法が思いついたでしょうか。
思いついた人も、そうでない人も、作るべき結果を考えながら読み進めて下さい。

こちらで最初に用意したのは、こんな方法です。

１〜30の数字からランダムに取り出して、それが前に出ていない数字だったらその数字を数列に追加する。

言葉で書くとわかりにくいかもしれませんが、図にするとこんな感じです。

　　　　

１〜３０までの数字が書かれたルーレットを回して、それが今までに出ていない数字が出れば、数列に追加します。
それを、３０個の数字が並ぶまで繰り返す、という方法です。
実際、これをプログラミングしてみました。数列にはLst()という配列変数を使ってあります。

    Dim Lst(30) As Integer
    Dim i As Integer
    Dim j As Integer
    Dim cFlg As Integer

    For i = 1 To 30
        
        Do
            '乱数で1〜30の数字を出して、数列に代入します
            Lst(i) = Int(Rand() * 30) + 1
            
            'フラグをリセットします
            cFlg = 0

            '過去に出た数字と比較します
            For j = 1 To i - 1
                If Lst(i) = Lst(j) Then
                    '既に出ている数字だったらフラグをセットします
                    cFlg = 1
                End If
            Next
            
            'フラグがセットされていなければ、Lst(i)は確定です
            'これで、ループを抜けて、次のLst()に移ります。
            If cFlg = 0 Then
                Exit Do
            End If
        
        Loop
    Next
    
    List1005.Clear
    For i = 1 To 30
        List1005.Add str(Lst(i))
    Next

プログラム自体はそれほど難しくないですね。
数列の i番目の数字 Lst(i)をランダムで決めて、それと過去に出た数字 Lst(j)｛j = 1 〜 i-1｝を比較しているだけですね。
でも、このシンプルなプログラムには、大きな無駄があります。下の図を見てください。

　　　　

最初のうちは、決まった側の数字が少ないですから、同じ数字が出ている確率は低いですね。
でも、後半になるにしたがって、同じ数字が出る確率が増えるわけですから、相対的にチェックに引っかかる場合が増えてきます。
そうなると、やり直しが増えてしまい、終了までに時間がかかることになります。
また、完全に乱数に頼っているため、この処理が、一体、何回くらいで終わるのか見当がつきませんから、あまり効率的ではありません。
（確率を計算すれば、確率として求めることはできますけど）
この方法の問題は、明らかに「常に１〜30の乱数が与えられる」という点のようです。
既に決まった数字が、再登場するような可能性を持った乱数を毎回処理しているのが、このプログラムのボトルネック、という見解です。

ちょっと話が違いますが、ガラス瓶などの口って、キュッと細くなっていますね。
そういうビンから中身を流そうとすると、口の部分が細いために、詰まりはしませんが流れ出す速度が低下します。
そういう状態を比喩的に用いて、全体の処理で足を引っ張る部分を「ボトルネック」、または単に「ネック」と表現します。
システム関連ではよく登場する用語ですが、こういう場面でも使うことができます。
ちなみに「セーターなどのネックから、大きな頭が出にくい状態」ではありませんが、こちらの意味でも十分通用しそうですね。

さて、この方法のボトルネック「常に１〜30の乱数が与えられる」という点を改良すべく、次の考え方を作ってみました。

１〜30の数字からランダムに取り出して、数字を数列に追加し、１度使った数字は、再登場しないようにする

という方法です。言葉にするとちょっとわかりにくいですが、箱に入ったボールに例えてみましょう。

　　　　

１〜３０の番号が書かれたボールが入っている箱から１つ取り出して、数列に加え、ボールは箱に戻さない、と考えればわかりやすいですね。
確かに、ボールの入った箱の中には、まだ出ていない数字しか残っていませんので、無駄な乱数を生成するというボトルネックは解消できそうです。
では、プログラムにしてみましょう。ここでは、箱の中のボールにも配列変数を使ってみました。

    Dim Ball(30) As Integer
    Dim Lst(30) As Integer
    
    Dim i As Integer
    Dim j As Integer
    Dim k As Integer
    
    'ボールの初期値を作成します
    For i = 1 To 30
        Ball(i) = i
    Next
    
    For i = 1 To 30
        
        'j に 1〜 31-i の乱数を代入します
        j = Int(Rand() * (31 - i)) + 1
        
        'i番目の数列に、j番目のボールの内容を代入します
        Lst(i) = Ball(j)

        'j番目以降のボールを前につめます
        For k = j To 30 - i
            Ball(k) = Ball(k + 1)
        Next
        
    Next
    
    List1005.Clear
    For i = 1 To 30
        List1005.Add str(Lst(i))
    Next

まず、箱の中のボールの初期値を作成する部分が追加になりました。
重要なのは、引いたボールを捨てる、という部分ですが、考え方は至って簡単です。

　　　　

このようにして、既に出た数字から、後ろを１つ前につめることで「捨てる」を実現してみました。
この流れなら、このプログラムがどれくらいの回数だけ、ループしたら終了するか、おおよその見当がつきます。
ただ、仕組みは簡単なのですが、毎回大量の配列変数の値を移動させるので、実は、コンピュータ的には過酷な作業なのです。
（※ブロック転送のようなことができれば、仕組みは簡単ですが、やっぱり処理は重いでしょうね。）

今までの方法を眺めてみると、まず、簡単に仕組みが思いついた最初の方法には、大きなボトルネックが存在しました。
それは、毎回、同じ乱数から数字を取り出してくる部分でしたね。いつ処理が終わるのかは、乱数のみが知る、という状態でした。
また、それを解消すべく考え出した２番目の方法は、終わるまでの回数もおおよそわかって、画期的のようですが、多くのデータ移動が行われるため、コンピュータ的にはあまり効率的ではないようでした。
特に面白いのは、後者の場合で、この方法の「非効率性」を、人間の視点からは認識できないかもしれないことです。
なにしろ、考え方としてはそれほど間違っていませんから、無理もないでしょう。

では、まったく別の考え方のものを紹介してみましょう。

「１〜３０のカードを順に並べ、
　　　　１番目と２〜３０までのランダムな位置を入れ替える
　　　　２番目と３〜３０までのランダムな位置を入れ替える
　　　　３番目と４〜３０までのランダムな位置を入れ替える
　　　　　　　　………
　　　　２８番目と２９〜３０までのランダムな位置を入れ替える
　　　　２９番目と３０番目を入れ替える」

という考え方です。図にすると、次のようになりますが、これは比較的理解しやすいですね。

　　　　

実際のプログラムはこんな感じになります。

    Dim Lst(30) As Integer
    
    Dim i As Integer
    Dim j As Integer
    
    Dim Swp As Integer
    
    'まずは１から順に並べます
    For i = 1 To 30
        Lst(i) = i
    Next
    
    For i = 1 To 29

            '　i+1 〜 30までの乱数を jに代入します
            j = Int(Rand() * (30 - i - 1 )) + i + 1

            'i番目とj番目を入れ替えます
            Swp = Lst(i)
            Lst(i) = Lst(j)
            Lst(j) = Swp
    Next
    
    List1005.Clear
    For i = 1 To 30
        List1005.Add str(Lst(i))
    Next

どうですか？
並べ替えは１つのループだけで簡潔に終わりますので、実際の実行速度は、他の方法に比べて随分と速いです。
もちろん、繰り返し回数も明朗会計です。

まず、普通は、このような考え方は、なかなか思い浮かばないでしょう。
しかし、この考え方を使ったプログラムは、コンピュータに負担をかけず、また、簡潔な考え方で目的を果たすことができるわけです。
このように、考え方一つで、プログラムの作り方はもちろん、その結果も大きく変わってきます。
そんなところにスポットをあてる意味でお送りする今回のBasic BASICは、試行錯誤で「迷路」を作ってみることにします。

目次へ　　　　　次へ
第13回　考える楽しさ、習う楽しさ「１．さて問題です」