Javaのデータ構造とアルゴリズム、パート1:概要

Javaプログラマーは、データ構造を使用してデータを格納および編成し、アルゴリズムを使用してそれらの構造内のデータを操作します。データ構造とアルゴリズム、およびそれらがどのように連携するかを理解すればするほど、Javaプログラムはより効率的になります。

このチュートリアルでは、データ構造とアルゴリズムを紹介する短いシリーズを開始します。パート1では、データ構造とは何か、およびデータ構造がどのように分類されるかを学習します。また、アルゴリズムとは何か、アルゴリズムがどのように表現されるか、時間と空間の複雑さの関数を使用して同様のアルゴリズムを比較する方法についても学習します。これらの基本を理解したら、パート2で、1次元配列を使用した検索と並べ替えについて学習する準備が整います。

データ構造とは何ですか?

データ構造は、ウィキペディアが次のように定義している抽象データ型(ADT)に基づいています。

[A]データ型の数学モデル。データ型は、データのユーザーの観点から、特に可能な値、この型のデータに対する可能な操作、および動作の観点から、その動作(セマンティクス)によって定義されます。これらの操作の。

ADTは、その値のメモリ表現やその操作の実装方法を気にしません。これはJavaインターフェースのようなもので、どの実装からも切り離されたデータ型です。対照的に、データ構造は、Javaクラスがインターフェースを実装する方法と同様に、1つ以上のADTの具体的な実装です。

ADTの例には、Employee、Vehicle、Array、およびListが含まれます。共通の型を共有する要素の順序付けられたコレクションを記述するリストADT(シーケンスADTとも呼ばれます)について考えてみます。このコレクションの各要素には独自の位置があり、重複する要素が許可されます。ListADTでサポートされている基本的な操作は次のとおりです。

  • 新しい空のリストを作成する
  • リストの最後に値を追加する
  • リスト内に値を挿入する
  • リストから値を削除する
  • リストを反復処理する
  • リストを破棄する

リストADTを実装できるデータ構造には、固定サイズおよび動的サイズの1次元配列と単一リンクリストが含まれます。(パート2で配列を紹介し、パート3でリンクリストを紹介します。)

データ構造の分類

単一の変数から、複数のフィールドを含むオブジェクトの配列またはリンクリストまで、さまざまな種類のデータ構造があります。すべてのデータ構造はプリミティブまたは集約として分類でき、一部はコンテナーとして分類されます。

プリミティブと集合体

最も単純な種類のデータ構造は、単一のデータ項目を格納します。たとえば、ブール値を格納する変数や整数を格納する変数などです。私はそのようなデータ構造をプリミティブと呼びます。

多くのデータ構造は、複数のデータ項目を格納できます。たとえば、配列はさまざまなスロットに複数のデータアイテムを格納でき、オブジェクトはそのフィールドを介して複数のデータアイテムを格納できます。これらのデータ構造を集計と呼びます。

このシリーズで取り上げるデータ構造はすべて集計です。

コンテナ

データ項目が格納および取得されるものはすべて、データ構造と見なすことができます。例には、前述のEmployee、Vehicle、Array、およびListADTから派生したデータ構造が含まれます。

多くのデータ構造は、さまざまなエンティティを記述するように設計されています。Employeeクラスのインスタンスは、たとえば、さまざまな従業員を記述するために存在するデータ構造です。対照的に、一部のデータ構造は、他のデータ構造の汎用ストレージ容器として存在します。たとえば、配列にはプリミティブ値やオブジェクト参照を格納できます。私はこの後者のカテゴリーのデータ構造をコンテナーと呼びます。

このシリーズで取り上げるデータ構造はすべて、集合体であるだけでなく、コンテナーでもあります。

Javaコレクションのデータ構造とアルゴリズム

Javaコレクションフレームワークは、さまざまな種類のコンテナ指向のデータ構造と関連するアルゴリズムをサポートしています。このシリーズは、このフレームワークをよりよく理解するのに役立ちます。

デザインパターンとデータ構造

大学生にデータ構造を紹介するためにデザインパターンを使用することはかなり一般的になっています。ブラウン大学の論文は、高品質のデータ構造を設計するのに役立ついくつかの設計パターンを調査しています。とりわけ、このペーパーは、アダプタパターンがスタックとキューの設計に役立つことを示しています。デモコードをリスト1に示します。

リスト1.スタックとキューにアダプター・パターンを使用する(DequeStack.java)

public class DequeStack implements Stack { Deque D; // holds the elements of the stack public DequeStack() { D = new MyDeque(); } @Override public int size() { return D.size(); } @Override public boolean isEmpty() { return D.isEmpty(); } @Override public void push(Object obj) { D.insertLast(obj); } @Override public Object top() throws StackEmptyException { try { return D.lastElement(); } catch(DequeEmptyException err) { throw new StackEmptyException(); } } @Override public Object pop() throws StackEmptyException { try { return D.removeLast(); } catch(DequeEmptyException err) { throw new StackEmptyException(); } } }

リスト1DequeStackは、Adapterパターンを示すブラウン大学の論文のクラスを抜粋したものです。StackおよびDequeは、StackおよびDequeADTを記述するインターフェイスであることに注意してください。MyDequeを実装するクラスですDeque

インターフェイスメソッドのオーバーライド

リスト1に基づいていることを元のコードは、ソースコードを提示しなかったStackDequeMyDeque。わかりやすく@Overrideするために、のすべてDequeStackの非コンストラクターメソッドがStackメソッドをオーバーライドすることを示すアノテーションを導入しました。

DequeStackMyDequeを実装できるように適応しますStack。のすべてDequeStackのメソッドは、Dequeインターフェイスのメソッドへの1行の呼び出しです。ただし、Deque例外が例外に変換される小さなしわがありStackます。

アルゴリズムとは何ですか?

歴史的に数学計算のツールとして使用されてきたアルゴリズムは、コンピューターサイエンス、特にデータ構造と深く関係しています。このアルゴリズムは、有限の時間でタスクを達成する一連の命令です。アルゴリズムの品質は次のとおりです。

  • 0個以上の入力を受け取ります
  • 少なくとも1つの出力を生成します
  • 明確で明確な指示で構成されています
  • 有限のステップ数の後に終了します
  • 人が鉛筆と紙を使ってそれを実行できるほど基本的です

プログラムは本質的にアルゴリズム的である可能性がありますが、多くのプログラムは外部の介入なしに終了しないことに注意してください。

多くのコードシーケンスはアルゴリズムとして適格です。1つの例は、レポートを出力するコードシーケンスです。さらに有名なのは、ユークリッドのアルゴリズムを使用して、数学的な最大公約数を計算することです。データ構造の基本的な操作(配列スロットに値格納するなど)がアルゴリズムである場合もあります。このシリーズでは、ほとんどの場合、二分探索アルゴリズムや行列乗算アルゴリズムなど、データ構造の処理に使用される高レベルのアルゴリズムに焦点を当てます。

フローチャートと擬似コード

アルゴリズムをどのように表現しますか?基礎となるアルゴリズムを完全に理解する前にコードを書くとバグが発生する可能性があるので、より良い代替手段は何ですか?2つのオプションは、フローチャートと擬似コードです。

フローチャートを使用してアルゴリズムを表す

A flowchart is a visual representation of an algorithm's control flow. This representation illustrates statements that need to be executed, decisions that need to be made, logic flow (for iteration and other purposes), and terminals that indicate start and end points. Figure 1 reveals the various symbols that flowcharts use to visualize algorithms.

Consider an algorithm that initializes a counter to 0, reads characters until a newline (\n) character is seen, increments the counter for each digit character that's been read, and prints the counter's value after the newline character has been read. The flowchart in Figure 2 illustrates this algorithm's control flow.

A flowchart's simplicity and its ability to present an algorithm's control flow visually (so that it's is easy to follow) are its major advantages. Flowcharts also have several disadvantages, however:

  • It's easy to introduce errors or inaccuracies into highly-detailed flowcharts because of the tedium associated with drawing them.
  • It takes time to position, label, and connect a flowchart's symbols, even using tools to speed up this process. This delay might slow your understanding of an algorithm.
  • Flowcharts belong to the structured programming era and aren't as useful in an object-oriented context. In contrast, the Unified Modeling Language (UML) is more appropriate for creating object-oriented visual representations.

Using pseudocode to represent algorithms

An alternative to flowcharts is pseudocode, which is a textual representation of an algorithm that approximates the final source code. Pseudocode is useful for quickly writing down an algorithm's representation. Because syntax is not a concern, there are no hard-and-fast rules for writing pseudocode.

You should strive for consistency when writing pseudocode. Being consistent will make it much easier to translate the pseudocode into actual source code. For example, consider the following pseudocode representation of the previous counter-oriented flowchart:

 DECLARE CHARACTER ch = '' DECLARE INTEGER count = 0 DO READ ch IF ch GE '0' AND ch LE '9' THEN count = count + 1 END IF UNTIL ch EQ '\n' PRINT count END

The pseudocode first presents a couple of DECLARE statements that introduce variables ch and count, initialized to default values. It then presents a DO loop that executes UNTILch contains \n (the newline character), at which point the loop ends and a PRINT statement outputs count's value.

For each loop iteration, READ causes a character to be read from the keyboard (or perhaps a file--in this case it doesn't matter what constitutes the underlying input source) and assigned to ch. If this character is a digit (one of 0 through 9), count is incremented by 1.

Choosing the right algorithm

The data structures and algorithms you use critically affect two factors in your applications:

  1. Memory usage (for data structures).
  2. CPU time (for algorithms that interact with those data structures).

It follows that you should be especially mindful of the algorithms and data structures you use for applications that will process lots of data. These include applications used for big data and the Internet of Things.

Balancing memory and CPU

When choosing a data structure or algorithm, you will sometimes discover an inverse relationship between memory usage and CPU time: the less memory a data structure uses, the more CPU time associated algorithms need to process the data structure's data items. Also, the more memory a data structure uses, the less CPU time associated algorithms will need to process the data items–leading to faster algorithm results.

As much as possible, you should strive to balance memory use with CPU time. You can simplify this task by analyzing algorithms to determine their efficiency. How well does one algorithm perform against another of similar nature? Answering this question will help you make good choices given a choice between multiple algorithms.

Measuring algorithm efficiency

Some algorithms perform better than others. For example, the Binary Search algorithm is almost always more efficient than the Linear Search algorithm–something you'll see for yourself in Part 2. You want to choose the most efficient algorithm for your application's needs, but that choice might not be as obvious as you would think.

For instance, what does it mean if the Selection Sort algorithm (introduced in Part 2) takes 0.4 seconds to sort 10,000 integers on a given machine? That benchmark is only valid for that particular machine, that particular implementation of the algorithm, and for the size of the input data.

As computer scientist, we use time complexity and space complexity to measure an algorithm's efficiency, distilling these into complexity functions to abstract implementation and runtime environment details. Complexity functions reveal the variance in an algorithm's time and space requirements based on the amount of input data:

  • A time-complexity function measures an algorithm's time complexity--meaning how long an algorithm takes to complete.
  • 宇宙複雑機能は、アルゴリズムの測定領域の複雑さをオーバーヘッドそのタスクを実行するためのアルゴリズムが必要とするメモリの量を--meaning。

両方の複雑さの関数は、入力のサイズ(n)に基づいており、入力データの量を何らかの形で反映しています。配列印刷用の次の擬似コードを検討してください。

 DECLARE INTEGER i, x[] = [ 10, 15, -1, 32 ] FOR i = 0 TO LENGTH(x) - 1 PRINT x[i] NEXT i END

時間計算量と時間計算量関数

このアルゴリズムの時間計算量は、時間計算量関数を指定することで表すことができます。ここで、(定数乗数)は、1回のループ反復を完了するまでの時間を表し、アルゴリズムのセットアップ時間を表します。この例では、時間計算量は線形です。t(n) = an+bab