データ構造|シナリオ

1.スタック領域とヒップ領域

プログラムがオペレーティングシステムから割り当てる代表的なメモリ領域は、コード領域、データ領域、スタック領域、スタック領域から構成されます.
スタック領域とヒップ領域を比較します.

출처: https://velog.io/@tonic523/%ED%9E%99-%EC%98%81%EC%97%AD-vs-%EC%8A%A4%ED%83%9D-%EC%98%81%EC%97%AD

スタック領域(静的メモリ)

スタックフレームのメモリ容量

スタックフレームを割り当てるには、事前に割り当てられるスタックフレームのサイズを知っている必要があります.

関数、領域変数、パラメータの保存

関数呼び出しとともに割り当てられ、関数呼び出しが完了すると消えます.

ヒップ領域(ダイナミックメモリ)

メモリの領域を動的に割り当て、プログラマは変数の作成時間と破棄時間を決定します.

より多くのメモリが必要な場合は、コピー前のすべての要素をコピーした後に新しいデータを挿入するために、より大きなスペースが必要です.

グローバル変数を処理し、ユーザーが管理するメモリ領域

メモリ領域はユーザーによって動的に割り当てられ、解放されます.

2.動的配置

大きさが固定されていない配列は、お尻領域に格納された配列です.
データは線形です
C++のVector,JavaのArrayList,Pythonのリストは動的配列に対応する

2-1. Operation

Array.is_empty()

リストが空の場合は、真または偽です.

Pythonでは、空のリストはFalse→リストそのものから見ることができます

Array.add_last(element)

リストの最後に要素を追加

list명.append(element)

Array.insert(index, element)

リストのindex位置に要素を挿入

list명.insert(index, element)

Array[index]

インデックス内の要素(インデックス)を返します.

list명[index]

Array.remove_last()

リストの最後の要素を削除して返します

list명.pop()

Array.remove(index)

インデックス内の要素を削除して返します

list명.pop(index)

2-2. データの挿入と削除

capacity:アレイのメモリ容量size:パディングデータサイズ

配列の末尾を追加、削除→O(1)

Capcity>Size:O(1)

Capcity

分割払い解析の概念を適用すると,対応する演算はO(1)となる.

注意:アレイが満たされている場合、動的アレイの容量は、アレイサイズの2倍で再びノイズによって干渉されます.

アレイの中間に追加または削除→O(n)

2-3. 索引

配列はインデックスを使用してデータにアクセスします.
データがいくらであっても1回の演算しか必要ないのでBIOはO(1)
データアドレス値=アレイの最初のアドレス値+(データサイズインデックス)データアドレス値=アレイの最初のアドレス値+(データサイズ*インデックス)データアドレス値=アレイの最初のアドレス値+(データサイズインデックス)

3.地域原理とキャッシュ

地域原理→CPUとホストメモリの間にキャッシュを配置する
プライマリ・メモリの変数は、演算の前後にレジスタを通過する必要があります.
キャッシュされていない場合、CPUがデータを要求すると、メモリからレジスタにデータをインポートしてALU(算術論理デバイス)に転送し、結果値をレジスタに保存し、メモリにデータを繰り返し格納すると、効率が低下する可能性があります.
CPUとメインメモリの間にパフォーマンスの速いメモリを配置して、効率が悪い場合を減らすことを望んでいます.このとき入ったメモリはキャッシュメモリです.
キャッシュはメインメモリからCPU要求の変数を一度に取得し,周辺変数を加えることで,メモリに線形に配列する特徴を考慮すれば,より高い性能が期待できる.
すなわち,空間の地域性を考慮すると,キャッシュ熱が発生すると性能の向上が期待でき,線形配列がキャッシュ熱を発生させるのに最適な条件である.

クリーンアップ用語

レジスタ:CPU上のメモリ空間で、自主メモリに来るデータを一時的に記憶する

算術ロジックユニット:CPU演算ユニット

キャッシュミス:CPUから要求されたデータはキャッシュにありません

キャッシュヒット:CPU要求データがキャッシュにある場合

3-1. 地域性の原理

時間領域性(temporal locality):1回のアクセスの変数がアクセスを継続する可能性が高い

空間位置性(spatial locality):アクセスされた変数が以前にアクセスされた変数の近くにある可能性が高い

3-2. キャッシュ(cache memory)

メインメモリでよく使用されるプログラムとデータを高速化するメモリ
サイクルメモリとCPUの間にあります.

4.参考資料

臀部領域vsスタック領域
メモリの構造(コード、データ、hip、スタック領域)
ダイナミック配列
[OS]キャッシュメモリとは?キャッシュの地域性とは?
キャッシュの領域
楊太煥