🔖

データ構造：Wikipediaを読んでみようの会

2023/12/06に公開

これはなに？

CS の基礎を少しずつでも固めていきたいなと思い立ち、すごい基礎的な内容のことを Wikipedia で勉強しようと思いました。日本語の Wikipedia だと翻訳の際に英語のニュアンスが抜け落ち、深い理解の妨げになると考えて英語の Wikipedia を読んでみようと思いました。

今回は 1 回目で、すぐにコーディングに活かせそうな「データ構造」のお話から手を付けることにしました。

やること

Wikipedia を読む（引用する）
内容をざっくりまとめる

得られること

各分野のデータに対する表現への理解度があがり、習熟速度が上がるかもしれません。

DB ではレコードという言葉があります。
ネットワークでは 5tuple という言葉があります。
AWS SQS などのキューイングサービスではキュー（Queue）という言葉があります。
みんな大好き OOP（オブジェクト指向）ではオブジェクトという言葉があります。
モバイルアプリには push や pop といった画面操作があります、そして Stack という言葉があります。

これらの言葉の定義や背景、周辺知識を知ることでその分野の思想に対する考え方が深まるかと思います。（少なくとも私は学びがありました）

DataStructure

コンピュータ・サイエンスにおいてデータ構造とは、データへの効率的なアクセスのために通常選択される、データの構成、管理、保存形式のことである[1][2][3]。より正確には、データ構造とは、データ値の集まり、それらの間の関係、データに適用できる関数や操作[4]、すなわちデータに関する代数的な構造である。

データ構造とはデータの構成、管理、保存形式のこと
値の集まり、値どうしの関係性、値に適用できる関数や操作のこと
データへの効率的なアクセスが目的

Usage

抽象データ型（ADT）はデータ型の数学的モデルであり、データの利用者の視点から見た振る舞い（セマンティクス）によって定義される。この数学的モデルは、データの具体的な表現であり、ユーザーではなく実装者の視点であるデータ構造とは対照的である。

抽象データ型はユーザー視点で、振る舞いによって定義されたモデルのこと
対象的に、データ構造（Data Structure）は、その構造の実装者の視点にたっている
Integer（整数）も抽象データ型にあたるみたい
→ そのデータを扱いたい人の目線で定義した型だから

データ構造の種類によって適したアプリケーションは異なり、特定のタスクに高度に特化したものもある。例えば、リレーショナル・データベースでは、データ検索に B-tree インデックスを使用するのが一般的であり[6]、コンパイラの実装では、識別子検索にハッシュテーブルを使用するのが一般的である[7]。

目的によって適したデータ構造は異なる
Ex, RDB ではデータ検索に B-tree インデックスを使用するのが一般的

データ構造は、大規模データベースやインターネット・インデックス・サービスなどの用途において、大量のデータを効率的に管理する手段を提供する。通常、効率的なデータ構造は効率的なアルゴリズムを設計するための鍵となる。形式的な設計手法やプログラミング言語の中には、ソフトウェア設計における重要な組織化要素として、アルゴリズムではなくデータ構造を重視するものもある。データ構造は、主記憶と二次記憶の両方に格納された情報の記憶と検索を整理するために使用できる[8]。

ChatGTP サンの補足

主記憶（Main Memory）:
これは、コンピュータがプログラムやデータを実行するために使用する一時的なメモリです。
主記憶は高速なアクセスが可能で、通常は RAM（ランダムアクセスメモリ）として知られています。
例：あなたがコンピュータ上で実行しているアプリケーションやオペレーティングシステムが主記憶に読み込まれています。
補助記憶（Secondary Memory）:

これは、永続的なデータ保存のために使用されるメモリで、通常はハードディスクドライブや SSD などの形で実装されます。
主記憶よりも大容量で、データは電源が切れても保存されます。
例：ハードディスクに保存されているファイルや、データベースの永続的なストレージが補助記憶になります。

データ構造は効率的なアルゴリズムを設計する鍵となる
設計手法やプログラミング言語のなかには、アルゴリズムではなくデータ構造を重視するものがある
RAM と永続化層の記録、検索を整理するために利用できるよ

Implementation

データ構造は様々なプログラミング言語や技法を用いて実装することができるが、データを効率的に整理して格納するという共通の目標がある[9]。データ構造は一般に、ポインタ（メモリアドレスを表すビット列）によって指定されたメモリ上の任意の場所にデータをフェッチして格納するコンピュータの能力に基づいており、それ自体がメモリに格納され、プログラムによって操作される。このように、配列とレコードのデータ構造は、算術演算によってデータ項目のアドレスを計算することを基本としているが、リンクされたデータ構造は、データ項目のアドレスを構造自体に格納することを基本としている。このようなデータ構造化のアプローチは、アルゴリズムの効率性とスケーラビリティに大きな影響を与える。例えば、配列における連続したメモリ割り当てにより、迅速なアクセスと変更操作が容易になり、シーケンシャルなデータ処理シナリオにおけるパフォーマンスの最適化につながる[10]。

データ構造の実装には通常、その構造のインスタンスを作成し操作する一連の手続きを記述する必要がある。データ構造の効率は、これらの操作と切り離して分析することはできない。この観察により、抽象データ型という理論的概念が動機付けられ、そのデータ型に対して実行される可能性のある操作と、それらの操作の数学的特性（空間コストと時間コストを含む）によって間接的に定義されるのがデータ構造である[11]。

データ構造は様々なプログラミング言語や技法を用いて実装することができる
データを効率的に整理して格納するという共通の目標がある
ポインタ（メモリアドレスを表すビット列）によって指定されたメモリ上の任意の場所にデータをフェッチして格納するコンピュータの能力に基づいている
実装するときにはインスタンスを作成し、操作する一連の処理を記述する必要がある
データ構造の効率と操作は切り離して分析することはできない、この背景から ADB という概念が動機づけられている
データ構造とは、抽象化した ADB という概念（≒ データ型）と、それに対して実行される可能性のある操作によって間接的に定義される

Examples

データ構造には多くの種類があり、一般に、より単純なプリミティブ・データ型の上に構築されている。よく知られている例は以下の通りである[12]。

array

An array とは、特定の順序で並んだ要素のことで、通常はすべて同じ型である（言語によっては、個々の要素がすべて同じ型であることを強制される場合もあれば、ほとんどすべての型である場合もある）。要素へのアクセスには、どの要素が必要かを指定する整数インデックスを使用する。一般的な実装では、配列の要素に連続したメモリ・ワードを割り当てる（ただし、これは必ずしも必要ではない）。配列は固定長でもサイズ変更可能でも構わない。

Sample Code

var riversArray = arrayOf("Nile", "Amazon", "Yangtze")

https://kotlinlang.org/docs/arrays.html

linked list (also just called list)

A linked list (also just called list)　とは、ノードと呼ばれる任意の型のデータ要素の線形コレクションであり、各ノードはそれ自体が値を持ち、リンクリスト内の次のノードを指す。配列に対するリンクリストの主な利点は、リストの残りの部分を再配置することなく、常に効率的に値を挿入したり削除したりできることである。しかし、特定の要素へのランダムアクセスなど、他の特定の操作は、リストでは配列よりも遅い。

ArrayList とは違う
下記のサイトがとても分かりやすい
https://www.ios-net.co.jp/blog/20230705-1204/

Kotlin では linked list は実装されてない、が Java の LinkedList を使える

import java.util.LinkedList

fun main(args: Array<String>)
{
    var planets =  LinkedList<String>();
    planets.addAll(listOf("Earth", "Venus", "Mars"))

    println("Planets = " + planets)
}

record (also called tuple or struct)

A record (also called tuple or struct) は、集約データ構造である。レコードは、他の値を含む値であり、通常は固定番号とシーケンスで、通常は名前によってインデックス付けされます。レコードの要素は通常、フィールドまたはメンバと呼ばれる。オブジェクト指向プログラミングの文脈では、レコードはオブジェクトと区別するために古いデータ構造として知られている[1]。

ChatGTP サンの補足

「Fixed number and sequence」を直訳すると、「固定された数値と順序」となりますが、これを理解するためには文脈が重要です。この場合、おそらく「typically in fixed number and sequence」は、データ構造内の要素が通常固定の数と順序で格納されることを指しています。ただし、これが「固定値」を意味するのか、それとも別の意味なのかは文脈からはっきりしません。しかし、通常は「固定値」と解釈されることが多いです。

レコードについての説明では、以下のポイントが挙げられています：
レコード（Record）:
レコードは、他の値を含む値の集まりであり、通常は固定された数と順序で格納されます。
レコード内の各要素は通常「フィールド」または「メンバー」と呼ばれます。
要素は通常名前でインデックス化されます。
レコードは、タプルや構造体とも呼ばれます。

オブジェクトとの違い:
レコードは「プレーン・オールド・データ構造（plain old data structures）」として知られており、これはオブジェクト指向プログラミングの文脈での言葉です。
オブジェクトとの主な違いは、オブジェクトがメソッド（関数）を持ち、それにより振る舞いを表現できるのに対して、レコードは通常データのコンテナとしてのみの機能があります。
オブジェクトはクラスを基にしており、継承やポリモーフィズムなどの概念が適用されますが、レコードは単なるデータの塊です。
簡単に言うと、レコードは主にデータをまとめて保持するための構造であり、オブジェクトとは異なり振る舞いを表現するメソッドを持ちません。レコードはデータの集まりとしての機能が強調され、オブジェクト指向の文脈では「プレーン・オールド・データ構造」として位置づけられています。

レコードと言った場合、データの塊という意味合いが強い
期待される振る舞いが異なるのでオブジェクトとは異なる
DB や Excel のテーブルで、行の１つ１つをレコードと表現するのはこのため

補足

タプル、ストラクトの表現について

タプル：
複数の構成要素からなる組を総称する一般概念（Wikipedia）
0 個以上の要素の有限列を一つの対象と見たもの。プログラミング用語としては、各要素が同じ型とは限らない点において、配列やベクターと区別される。（英辞郎）
https://ja.wikipedia.org/wiki/タプル
https://eowf.alc.co.jp/search?q=tuple

ストラクト：
構造体
・構造体とは異なる型のデータの並びをひとまとめにしたもの
・名前を付けた新しいデータ型で、レコードとも呼ぶこともある
・各々の要素は、名前が付けられ、メンバと呼ばれる

Hash tables, also known as hash maps

Hash tables, also known as hash maps はキーに基づいた値の高速検索を提供するデータ構造である。ハッシュ関数を用いてキーを配列のインデックスにマッピングするため、平均的なケースでは一定時間のアクセスが可能である。ハッシュ・テーブルは辞書、キャッシュ、データベースのインデックス作成によく使われる。しかし、ハッシュの衝突が発生し、性能に影響を与えることがある。衝突を処理するために、チェーニングやオープンアドレッシングなどの技術が採用されている。

キーに基づいて値を素早く取得するためのデータ構造で、ハッシュテーブルとも呼ばれる
ハッシュ関数を用いて、キーと配列のインデックスを対応させる f(key) = index
平均ケース（Average-case complexity、アルゴリズムの平均計算量のケース）では、定数時間のアクセスが可能
辞書型のデータ構造（Map とか）、キャッシュ、DB のインデックス作成によく使用される
ハッシュ関数の実装方法次第では異なる Key で同じ Index にアクセスできてしまう、これを衝突（collison、コリジョン）という
衝突を解決するための手法として、連鎖法やオープンアドレッシングがあり、衝突が発生した場合はこれらの手法で整合性を保ちながら処理される

補足（Dictionary, Map, HashMap の違い）

Dictionary, Map, HashMap の意味の違いを調べていたのですが、言語ごとに具体的に何を指しているのかが異なるようです。今自分が触っているものではどのような定義となっているかを調べたほうが良いと考えています。
なお、KVS（Key Value Store）という単語はデータベースを指すことが多いようです（※筆者調べ）

Graphs

グラフは、エンティティ間の関係を表すエッジで接続されたノードのコレクションです。グラフは、社会的ネットワーク、コンピュータ・ネットワーク、交通網などをモデル化するのに使われる。グラフは頂点（ノード）と辺（ノード間の接続）で構成される。グラフは有向または無向であり、サイクルを持つことも無循環であることもある。グラフ探索アルゴリズムには、幅優先探索と深さ優先探索がある。

グラフはノード（頂点）とエッジ（辺）から成るデータ構造で、エンティティ（物事や概念など）の関係を表現する
関係を表現する中で、エッジ（辺）は方向を持っている場合（Ex, →）と持っていない場合（Ex, ー）がある。
そのグラフの特性として循環しているものもあれば、循環していないものもある
グラフ内のノードを効率的に探索するアルゴリズムとして、幅優先探索（Breadth-first search）と深さ優先探索（Depth-first search）がある

ノード、エッジについて

nodes_and_edges

Stacks and queues

スタックとキューは、配列やリンクリストを使って実装できる抽象データ型である。スタックには、プッシュ（スタックの先頭に要素を追加する）とポップ（スタックから先頭の要素を削除する）の 2 つの主要な操作があり、これらは LIFO（Last In, First Out）の原則に従っている。キューには、先入れ先出し（FIFO）の原則に従った、enqueue（要素をキューの最後尾に追加）と dequeue（要素をキューの先頭から削除）の 2 つの主要操作がある。

スタックは後入先出（LIFO：Last In, First Out）で、後入れに該当するのがプッシュ、先出しに該当するのがポップ
キューは先入先出（FIFO：First In, First Out）で、先入れに該当するのが enquere（エンキュー）、先出しに該当するのが dequeue（デキュー）

Trees

木は要素の階層構造を表す。木は辺で接続されたノードで構成され、1 つのノードがルートで、他のすべてのノードがサブツリーを形成する。木は様々なアルゴリズムやデータ保存の場面で広く使われている。バイナリーツリー（特にヒープ）、AVL ツリー、B ツリーなどがよく使われるツリーの一種である。これらは、効率的で最適な検索、ソート、データの階層的表現を可能にする。

1 つのノードをルートとして、階層構造を表現したデータ構造
ツリー構造でよく使われるものにバイナリツリー、AVL ツリー、B ツリーがある

A trie, also known as a prefix tree

トライは接頭辞ツリーとも呼ばれ、文字列の効率的な検索に使われる特殊なツリーデータ構造である。トライは文字列の文字をノードとして格納し、各エッジが文字を表します。オートコンプリート、スペルチェック、辞書実装などのテキスト処理シナリオで特に有用です。トライは、文字列の高速検索や接頭辞ベースの操作を可能にします。

階層構造を取っている点ではツリーと共通している
トライはノードが文字列であること、各ノードは親のノードのキーを接頭辞として持っていることが特徴

補足

trie という名称は "retrieval"（探索、検索）が語源であるため、本来は"tree" と同じ発音を用いる（リトゥリーヴァル）
ツリー構造との呼び分けのためにトライ、またはトライ木と呼ばれる
文字列の検索や辞書的なデータの表現に使用される

Language support

ほとんどのアセンブリ言語や BCPL（Basic Combined Programming Language）のようないくつかの低レベル言語には、データ構造に対する組み込みサポートがありません。一方、多くの高水準プログラミング言語や MASM のようないくつかの高水準アセンブリ言語では、レコードや配列のような特定のデータ構造に対する特別な構文やその他の組み込みサポートがあります。例えば、C 言語（BCPL の直系の子孫）や Pascal 言語は、ベクトル（1 次元配列）や多次元配列に加えて、それぞれ構造体やレコードをサポートしている[14][15]。

ほとんどのプログラミング言語は、データ構造の実装を異なるプログラムで再利用できるようにする、ある種のライブラリ機構を備えている。最近の言語には通常、最も一般的なデータ構造を実装した標準ライブラリが付属している。例えば、C++標準テンプレート・ライブラリ、Java コレクション・フレームワーク、Microsoft .NET フレームワークなどである。

最近の言語では、一般的にモジュール・プログラミング、つまりライブラリ・モジュールのインターフェースとその実装の分離もサポートしている。クライアントが実装の詳細を隠せるように、不透明なデータ型を提供するものもある。C++、Java、Smalltalk などのオブジェクト指向プログラミング言語では、一般的にこの目的のためにクラスを使用する。

多くの既知のデータ構造には、複数の計算スレッドがデータ構造の 1 つの具体的なインスタンスに同時にアクセスできるようにする同時実行バージョンがある[16]。

高水準な言語ではデータ構造をサポートしているが、低水準な言語ではサポートしていないものもある
ほとんどの言語ではデータ構造の実装を、他の言語でも再利用できるようにするライブラリ機構を備えている
最近の言語では OOP のようにインターフェースと実装の分離をサポートしているものもある
多くのデータ構造には、１つのデータに対して同時アクセスできるようなものが用意されている