初心者ガイド: アルゴリズムとは何ですか? 11行の擬似コードで説明します

この記事はWeChatの公開アカウント「Big Data DT（ID：hzdashuju）」から転載したもので、著者はPanos Louridasです。この記事の転載については、Big Data DTの公開アカウント（ID: hzdashuju）までご連絡ください。

アルゴリズムはプロセスであり、特別な種類のプロセスです。有限の一連のステップとして記述され、有限の時間内に完了する必要があります。各ステップは、人間がペンと紙を使って実行できる程度に明確に定義される必要があります。

アルゴリズムは、与えられた入力に基づいて何らかの処理を実行し、実行内容を反映した出力を生成します。アルゴリズム 1-1 は、上で説明したプロセスを実装します。

• アルゴリズム1-1 シンプルなストックスパンアルゴリズム

SimpleStockSpan(引用符) → スパン

• 入力: quotes、n 個の株価情報の配列
• 出力: spans、n 個のストック スパンを保持する配列

spans←CreateArray(n)
 i ← 0からnまで
    か←1
    span_end ←偽 
    ik ≥ 0かつ  span_end しない
       quotes[ik] ≤ quotes[i]ならば 
           k←k+1
それ以外 
           span_end ← TRUE  
    spans[i] ← k
リターンスパン

アルゴリズム 1-1 はアルゴリズムの記述方法を示しています。アルゴリズムのロジックとは無関係な実装の詳細を扱わなければならないコンピュータ言語を使用する代わりに、疑似コード形式を使用します。

疑似コードは、実際のプログラム コードと非公式な記述の中間に位置するコード形式です。構造化された形式を使用し、特定の意味を持つ一連の単語を採用しています。ただし、疑似コードは実際のコンピュータ コードではありません。これはコンピュータによって実行されることを目的としているのではなく、人間が簡単に理解できることを目的としています。

ちなみに、プログラムは人間にも理解できるものでなければなりませんが、すべてのプログラムがそうであるわけではありません。理解しにくい、質の悪いコンピュータ プログラムが数多く使用されています。

すべてのアルゴリズムには名前があり、何らかの入力を受け取り、何らかの出力を生成します。この本では、アルゴリズム名は CamelCase で記述され、入力は括弧で囲まれ、出力は → で示されます。次の数行は、アルゴリズムの入力と出力について説明します。アルゴリズムは、その名前の後に括弧で囲んだ入力を続けることで呼び出すことができます。

アルゴリズムが記述されると、何らかの入力を与えてアルゴリズムの出力を返すブラック ボックスとして扱うことができます。アルゴリズムがプログラミング言語で実装されると、それは名前の付いたコンピュータ コードの一部、つまり関数になります。コンピュータ プログラムでは、アルゴリズムを実装する関数を呼び出します。

一部のアルゴリズムは出力を生成しないため、明示的に結果を返しません。代わりに、彼らの行動はコンテキストの一部に影響を与えます。たとえば、アルゴリズムに結果を書き込むためのスペースを提供する場合があります。この場合、アルゴリズムは従来の意味での出力を返しませんが、いずれにしても出力があり、つまりコンテキストの変更に影響します。

一部のプログラミング言語では、関数と呼ばれる、明示的に結果を返す名前付きのプログラム コード部分と、プロシージャと呼ばれる、結果を返さないが他の副作用を持つ可能性がある名前付きのプログラム コード部分を区別します。この違いは、関数が値を返さなければならない数学から生じます。私たちにとって、アルゴリズムが実際のプログラムとしてエンコードされる場合、それは関数またはプロシージャのいずれかになります。

私たちの擬似コードでは太字のキーワードがいくつか使用されていますが、コンピューターとプログラミング言語の仕組みをある程度理解していれば、これらのキーワードの意味は一目瞭然です。

代入を示すには文字 ← を使用し、等号比較を示すには等号 (=) を使用します。一般的に使用される 5 つの記号 (+、-、​​/、×、·) を使用して、4 つの数学演算を表します。最後の 2 つの記号はどちらも乗算を表します。私たちは、美観を考慮して、両方を使用します。疑似コードをブロックに分割するためにキーワードや記号は使用しません。ブロックはインデントによって示されます。

このアルゴリズムでは配列を使用しました。配列はデータを保持し、特定の方法でそのデータを操作できるようにする構造です。データを保存し、保存したデータに対して特定の操作を実行できるようにする構造をデータ構造と呼びます。つまり、配列はデータ構造です。

配列はコンピュータにとって、オブジェクトのシーケンスが人間にとってであるようなものです。配列は、コンピュータのメモリに格納される順序付けられた要素のシーケンスです。要素を格納するために必要なスペースを取得し、n 個の要素を格納できる配列を作成するには、アルゴリズム 1-1 の 1 行目の CreateArray アルゴリズムを呼び出すことができます。

配列に精通している場合は、配列の作成にアルゴリズムが必要な理由が疑問に思うかもしれません。しかし、それは確かに事実です。データを保持するためのメモリ ブロックを取得するには、少なくともコンピューター上で使用可能なメモリを検索し、それを配列で使用するためにマークする必要があります。

CreateArray(n) 呼び出しは必要なことすべてを実行します。つまり、n 個の要素を保持できる配列を返します。最初は要素は含まれず、要素を保持するために必要なスペースのみが含まれます。アルゴリズムは、CreateArray(n) を呼び出して配列に実際のデータを埋め込む役割を担います。

配列 A の場合、i 番目の要素を表すために A[i] を使用し、このシンボルは要素にアクセスするためにも使用されます。 A[i] の i など、配列内の要素の位置はインデックスと呼ばれます。 n要素の配列Aには要素A[0]、A[1]、…、A[n-1]が含まれます。

これは驚くかもしれません。なぜなら、最初の要素は 0 番目で、最後の要素は n-1 番目であり、1 番目と n 番目を予想していたかもしれないからです。ただし、これはほとんどのコンピュータ言語の配列に当てはまるので、今からこのメカニズムに慣れておく方がよいでしょう。これは非常に一般的で、サイズ n の配列を反復処理する場合、位置 0 から位置 n-1 まで移動します。

私たちのアルゴリズムでは、オブジェクトに x から y までの値があると言う場合 (x は y より小さいと仮定)、x から y までのすべての値 (ただしそれらを含まない) を意味します (アルゴリズムの 2 行目を参照)。

i 番目の要素へのアクセスには、i の値に関係なく同じ時間がかかるものと想定します。したがって、A[0]へのアクセスにはA[n-1]へのアクセスと同じ時間がかかります。これは配列の非常に重要な特性です。要素へのアクセスは一貫しており、一定の時間がかかります。配列要素にインデックスでアクセスする場合、配列はこの要素を検索する必要はありません。

アルゴリズムの説明における表記に関しては、アルゴリズム内の変数を表すために小文字を使用します。ただし、変数がデータ構造を表す場合は、配列 A のように大文字を使用して目立たせます。しかし、これは必要ありません。変数に複数の単語を含む名前を付ける場合は、a_connector のようにアンダースコア (_) を使用します。これが必要なのは、スペースで区切られた一連の単語がどのようにして 1 つの変数名を形成するかをコンピューターが理解できないためです。

アルゴリズム 1-1 は配列を使用して値を格納します。配列は任意のタイプの項目を保持できますが、疑似コードでは各配列は単一のタイプの項目のみを保持できます。これはほとんどのプログラミング言語にも当てはまります。

たとえば、小数の配列、分数の配列、人を表す項目の配列、住所を表す項目の別の配列を作成することはできますが、小数と人を表す項目の両方を含む配列を作成することはできません。 「人を表す項目」が何になるかは、使用するプログラミング言語によって決まります。すべてのプログラミング言語は、意味のあるものを表現する方法を提供します。

特に便利な配列の種類は文字配列です。文字配列は文字列、つまり文字のシーケンス、数字のシーケンス、単語のシーケンス、文のシーケンスなどを表します。すべての配列と同様に、インデックスを使用して配列内の個々の文字を個別に参照できます。文字列 s = "Hello, World" の場合、 s[0] は文字 "H" で、 s[11] は文字 "d" です。

要約すると、配列は同じタイプの項目のシーケンスを格納するデータ構造です。配列は次の 2 つの操作をサポートします。

• CreateArray(n) は n 個の要素を保持できる配列を作成します。配列は初期化されていません。つまり、実際の要素は保持されていませんが、要素を保持するために必要なスペースが予約されており、要素を保持するために使用できます。
• これまで見てきたように、配列 A の場合、A[i] は i 番目の要素にアクセスし、配列内のどの要素にアクセスするにも同じ時間がかかります。 i < 0の場合、A[i]にアクセスしようとするとエラーが発生します。

アルゴリズム 1-1 に戻りましょう。前述したように、アルゴリズムの 2 行目から 10 行目はループ、つまり繰り返し実行されるコード ブロックです。 n 日間の引用がある場合、ループは n 回実行され、そのたびにスパンが計算されます。変数 i は、スパンを計算する現在の日を表します。最初は、最も早い時点である 0 日目です。コードの 2 行目が実行されるたびに、ループは 1 日目、2 日目、...、n-1 日目に進みます。

変数 k を使用して、現在のスパンの長さを示します。擬似コードでは、変数は何らかのデータを参照する名前であり、そのデータの内容、より正確には変数の値は、アルゴリズムの実行中に変更される可能性があるため、変数という用語が使用されます。スパンの計算を開始すると、k の値は常に 1 になります。この初期値は 3 行目に設定します。

また、インジケーター変数 span_end も使用します。インジケーター変数は TRUE または FALSE の値を取り、何かが真か偽かを示します。スパンの終わりに到達すると、変数 span_end の値は true になります。

各スパン計算の開始時には、4 行目に示すように、span_end は false になります。 5 行目から 9 行目までの内側のループは、スパンの長さを計算します。 5 行目は、スパンがまだ終了していない限り、可能な限り戻るように指示します。どのくらい遡れるかは、条件 ik ≥ 0 によって決まります。つまり、インデックス ik で示される日に戻って範囲が終了するかどうかを確認しますが、0 は 1 日目に対応するため、インデックスは 0 にはなりません。

6 行目は、スパンが終了するかどうかを確認します。スパンの終了がない場合は、7 行目でその長さが増加します。それ以外の場合、9 行目では、ループが 5 行目に戻った後に終了するように span end を設定していることがわかります。

2 行目から 10 行目の外側のループが 10 行目で 1 サイクル終了すると、k の値が配列スパンの正しい位置に保存されます。ループを終了した後の 11 行目で、アルゴリズムの結果を保持する spans を返します。

最初は i=0、k=1 に設定することに注意してください。これは、可能な限り早い時点で 5 行目の条件が false になる必要があることを意味します。これは当然のことです。0 日目の範囲は 1 のみにすることができます。

ここで、アルゴリズム、ペン、紙について私たちが言ったことを思い出してください。アルゴリズムを理解する最良の方法は、手動で実行することです。

アルゴリズムが少し複雑に思えたり、完全に理解できていないと感じた場合は、例を解決するためにアルゴリズムを実行するプロセスをペンと紙に書き留めてください。この方法は少し古風に思えるかもしれませんが、多くの時間を節約できます。アルゴリズム 1-1 についてまだ不明な点がある場合は、今すぐこの方法を試し、アルゴリズムが完全に明確になったらここに戻ってください。

著者について: Panos Louridas はマンチェスター大学でソフトウェア エンジニアリングの博士号を取得し、現在はアテネ経済大学の経営科学技術学部の准教授を務めています。大学に入学する前は、投資銀行で上級ソフトウェアエンジニアとして働いていました。

この記事は「Real-World Algorithms: A Beginner's Guide」から抜粋したもので、出版社の許可を得て掲載されています。