Ruby開発者向けのデータ構造の概要

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

データ構造は、データを整理してアクセスするための特定の方法です。 。

例：

• 配列
• 二分木
• ハッシュ

さまざまなデータ構造がさまざまなタスクに優れています。

たとえば、辞書（単語と定義）や電話帳（人の名前と番号）のようなデータを保存する場合は、ハッシュが最適です。

利用可能なデータ構造を知る 、およびそれぞれの特徴 、より優れたRuby開発者になります。

それがこの記事で学ぶことです！

配列について

配列は、プログラミングについて読み始めたときに最初に学習するデータ構造です。

配列は、オブジェクトがギャップなしで次々に格納される連続したメモリのチャンクを使用します。

Cのような低レベルのプログラミング言語とは異なり、Rubyはメモリの管理、最大配列サイズの拡張、要素の削除時の圧縮など、すべてのハードワークを実行します。

用途 ：

• より高度なデータ構造のベースとして
• ループの実行から結果を収集するには
• アイテムの収集

splitのように、どこにでも配列があります ＆chars 文字列を文字の配列に分解するメソッド。

例 ：

out = []

10.times { |i| out << i }

out
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

次の表は、配列のサイズが大きくなるにつれて、さまざまな配列操作がどのように動作するかを示しています。

時間計算量の表記に慣れていない場合は、この記事をお読みください。

配列の時間計算量 ：

操作 複雑さ プッシュ アクセス 削除

O（1）
ポップ	O（1）
O（1）
検索	O（n）
O（n）

なぜこれが役立つのですか？

アレイのパフォーマンス特性がわかるからです。

多くのfindを実行している場合 遅くなる巨大なアレイでの操作...

ただし、使用するインデックスがわかっている場合は、O(1)があるため、配列は高速になります。 時間計算量。

この基準でデータ構造を選択してください ：

1. パフォーマンス特性 =>データをどのように処理していますか？データセットの大きさはどれくらいですか？
2. データの形状と形式 =>どのような種類のデータを使用していますか？より良いデータ構造に合うようにデータを再編成できますか？

ハッシュデータ構造

国コードと国名のマッピングはありますか？

または、単にものを数えたいだけかもしれません。

それこそがハッシュが役立つのです！

ハッシュは、すべての値にキーがあり、このキーは何でもかまいませんデータ構造です。 、文字列、整数、記号などのように。

どのように機能しますか？

ハッシュはキーを数値に変換します（hashを使用） Rubyのメソッド）＆次にその番号をインデックスとして使用します。ただし、Rubyプログラムでハッシュを使用できるようにするためにそれを理解する必要はありません。

用途 ：

• 文字列内の文字を数える
• 単語を定義に、名前を電話番号にマッピングするなど。
• 配列内の重複を見つける

例 ：

"aaabcd"
  .each_char
  .with_object(Hash.new(0)) { |ch, hash| hash[ch] += 1 }

# {"a"=>3, "b"=>1, "c"=>1, "d"=>1}

時間計算量 ：

操作 複雑さ ストア アクセス 削除

O（1）
O（1）
O（1）
検索（値）	O（n）

ハッシュは、定数O(1)があるため、パフォーマンスに関して最も役立つデータ構造の1つです。 時間の保存、削除、アクセス。

ハッシュのコンテキストで検索するということは、特定の値を探していることを意味します。

スタック

スタックはプレートのスタックのようなもので、1つのプレートを別のプレートの上に置き、その上にあるプレートのみを取り外すことができます。

これは、最初に聞こえるよりも便利です！

用途 ：

• 再帰メソッドを通常のループに置き換えます
• 残された作業を追跡し、最新のものを上に残します
• 配列を逆にする

例 ：

stack = [1,2,3,4,5]

(1..stack.size).map { stack.pop }

# [5, 4, 3, 2, 1]

はい、reverseを使用できます 代わりに。

これは、スタックのこの特定の特性を示すための単なる例です。

時間計算量 ：

操作 複雑さ プッシュ アクセス

O（1）
ポップ	O（1）
検索	---
---

スタック（およびキュー）には、insertという2つの操作しかないことに注意してください。 ＆delete 、またはpush ＆pop 。

スタック内を検索することは可能ですが、それは非常にまれです。

二分木の使い方

ほとんどのRuby開発者は、おそらくバイナリツリーについて聞いたことはありますが、使用したことはありません。

それはなぜですか？

まず、組み込みのバイナリツリー実装がありません。

第二に、バイナリツリーは、常に使用する配列やハッシュとは異なり、日常のプログラミングの課題にはそれほど役立ちません。

しかし、二分木は非常に興味深いデータ構造です 。

実際、Trie（次のセクションで説明）、B-Tree（データベースで使用）、ヒープなどの多方向ツリーなど、さまざまなバリエーションがあります。

用途 ：

• データ圧縮
• ルーティングテーブル
• 抽象構文木（AST）

例 ：

# https://github.com/jamesconant/bstree

require 'bstree'

root = Bstree::Node.new(5)

root.insert(2)
root.insert(7)

root.search(3)
# nil

時間計算量 ：

操作 複雑さ 挿入 削除 アクセス

O（log n）
O（log n）
検索	O（log n）
---

平衡二分木は、すべてのノードに2つの子があり、すべての葉が同じレベルである場合です

ツリーのバランスが崩れると、パフォーマンスがO(n)に低下します。 。

自己平衡二分木 （赤黒木、AVL木など）、すべての操作には、木の高さ（またはレベル）に比例した時間がかかります。

ノードにアクセスするには、最初にノードを見つける必要があるため、アクセス時間がないことに注意してください...

その場合、O(log n)があります。 アクセス用。

ただし、特定のノードへの参照を（変数として）保持する場合、それはO(1)になります。 アクセス時間。

トライデータ構造

トライは、特殊なツリーのようなデータ構造です。

単語を操作してから、接頭辞で始まる単語をすばやく検索したり、単語全体を検索したりする場合に便利です。

用途 ：

• ワードゲーム
• スペルチェッカー
• オートコンプリートの提案

例 ：

# https://github.com/gonzedge/rambling-trie

require 'rambling-trie'

trie = Rambling::Trie.create('words.txt')

trie.include?('chocolate')
# true
trie.include?('salmon')
# true

時間計算量 ：

操作 複雑さ 単語

追加	O（k）
含める？	O（k）
O（k）

この表では、kを使用しています 入力文字列のサイズを示し、n データ構造自体のサイズを示すために使用されます。

つまり、appleという単語の場合 、k 5になります。

概要

一般的なデータ構造、それらの主な用途と特性、およびRubyでのそれらの使用方法について学習しました。

この新しい知識を適用すると、問題をより早く解決できるようになります！

この投稿が役に立ったら教えていただけますか？

ありがとう🙂