ランダムアクセス・シーケンシャルアクセスから双方向リスト
ランダムアクセスO(1)とシーケンシャルアクセスO(N)の説明を踏まえ、リスト構造のO(N)の改善にむけた解説を行う。
リスト構造の利点と欠点
リストを使った集合演算のように、データを連ねたリストは、単純リストとか線形リストと呼ばれる。特徴はデータ数に応じてメモリを確保する点や、途中へのデータの挿入削除が得意な点があげられる。一方で、配列は想定最大データ件数で宣言してしまうと、実際のデータ数が少ない場合、メモリの無駄も発生する。しかし、想定件数と実データ件数がそれなりに一致していれば、無駄も必要最小限となる。リスト構造では、次のデータへのポインタを必要とすることから、常にポインタ分のメモリは、データにのみ注目すれば無駄となる。
例えば、整数型のデータを最大 MAX 件保存したいけど、実際は それ以下の、平均 N 件扱うとする。この時のメモリの使用量 M は、以下のようになるであろう。(sizeof()はC言語での指定した型のメモリByte数を返す演算子)
配列の場合 | リスト構造の場合 |
(ただしヒープ管理用メモリ使用量は無視) |
シーケンシャルアクセス・ランダムアクセス
もう1つのリストの欠点はシーケンシャルアクセス。テープ上に記録された情報を読む場合、後ろのデータを読むには途中データを読み飛ばす必要があり、データ件数に比例したアクセス時間を要する。このような N番目 データ参照に、O(N)の時間を要するものは、シーケンシャルアクセスと呼ばれる。
一方、配列はどの場所であれ、一定時間でデータの参照が可能であり、これは ランダムアクセスと呼ばれる。N番目のアクセス時間がO(1)を要する。配列であれば、N/2 番目のデータをO(1)で簡単に取り出せるから2分探索法が有効だが、リスト構造であれば、N/2番目のデータを取り出すのにO(N)かかってしまう。
このため、プログラム・エディタの文字データの管理などに単純リストを用いた場合、1つ前の行に移動するには、先頭から編集行までの移動で O(N) の時間がかかり、大量の行数の編集では、使いものにならない。ここで、シーケンシャルアクセスでも1つ前にもどるだけでも処理時間を改善してみよう。
単純リストから双方向リストへ
ここまで説明してきた単純リストは、次のデータへのポインタを持つ。ここで、1つ後ろのデータ(N番目からN+1番目)をアクセスするのは簡単だけど、1つ前のデータ(N-1番目)を参照しようと思ったら、先頭から(N-1)番目を辿るしかない。でも、これは O(N) の処理であり時間がかかる処理。
ではどうすればよいのか?
この場合、一つ前のデータの場所を覚えているポインタがあれば良い。
Javaの場合
import java.util.*; class BDListNode { BDListNode prev ; int data ; BDListNode next ; BDListNode( BDListNode p , int d , BDListNode n ) { this.prev = p ; this.data = d ; this.next = n ; } } public class Main { public static void main(String[] args) throws Exception { BDListNode top = new BDListNode( null , 1 , new BDListNode( null , 2 , new BDListNode( null , 3 , null ) ) ) ; top.next.prev = top ; top.next.next.prev = top.next ; for( BDListNode p = top ; p != null ; p = p.next ) System.out.println( p.data ) ; // 1,2,3 for( BDListNode p = top.next.next ; p != null ; p = p.prev ) System.out.println( p.data ) ; // 3,2,1 } }
C言語の場合
// 双方向リストの宣言 struct BD_List { struct BD_List* prev ; // 1つ前のデータへのポインタ int data ; struct BD_List* next ; // 次のデータへのポインタ } ;
このデータ構造は、双方向リスト(bi-directional list)と呼ばれる。では、簡単なプログラムを書いてみよう。双方向リストのデータを簡単に生成するための補助関数から書いてみる。
// リスト生成補助関数 struct BD_List* bd_cons( struct BD_List* p , int d , struct BD_List* n ) { struct BD_List* ans ; ans = (struct BD_List*)malloc( sizeof( struct BD_List ) ) ; if ( ans != NULL ) { ans->prev = p ; ans->data = d ; ans->next = n ; } return ans ; } void main() { struct BD_List* top ; struct BD_List* p ; // 順方向のポインタでリストを生成 top = bd_cons( NULL , 1 , bd_cons( NULL , 2 , bd_cons( NULL , 3 , NULL ) ) ) ; // 逆方向のポインタを埋める top->next->prev = top ; top->next->next->prev = top->next ; // リストを辿る処理 for( p = top ; p->next != NULL ; p = p->next ) printf( "%d\n" , p->data ) ; for( ; p->prev != NULL ; p = p->prev ) printf( "%d\n" , p->data ) ; }
双方向リストの関数作成
以上の説明で、双方向の基礎的なプログラムの意味が分かった所で、練習問題。
先のプログラムでは、1,2,3 を要素とするリストを、ナマで記述していた。実際には、どんなデータがくるか分からないし、指定したポインタ p の後ろに、データを1件挿入する処理 bd_insert( p , 値 ) , また、p の後ろのデータを消す処理 bd_delete( p ) を書いてみよう。
Javaの場合
public class Main { // 指定したノードの後ろに1件追加 static void bd_insert( BDListNode p , int d ) { p.next = new BDListNode( null , d , p.next ) ; p.next.next.prev = p.next ; p.next.prev = p ; } // 指定したノードの後ろを1件削除 static void bd_delete( BDListNode p ) { p.next = p.next.next ; p.next.prev = p ; } public static void main(String[] args) throws Exception { // 双方向リストの追加,削除 BDListNode top2 = new BDListNode( null , 1 , new BDListNode( null , 2 , new BDListNode( null , 4 , null ) ) ) ; top2.next.prev = top2 ; top2.next.next.prev = top2.next ; // 途中に挿入の実験 bd_insert( top2.next , 3 ) ; for( BDListNode p = top2 ; p != null ; p = p.next ) System.out.println( p.data ) ; // 1,2,3,4 for( BDListNode p = top2.next.next.next ; p != null ; p = p.prev ) System.out.println( p.data ) ; // 4,3,2,1 // 途中を削除の実験 bd_delete( top2.next ) ; for( BDListNode p = top2 ; p != null ; p = p.next ) System.out.println( p.data ) ; // 1,2,4 for( BDListNode p = top2.next.next ; p != null ; p = p.prev ) System.out.println( p.data ) ; // 4,2,1 } }
C言語の場合
// 双方向リストの指定場所 p の後ろに、値 d を要素とするデータを挿入せよ。 void bd_insert( struct BD_List* p , int d ) { struct BD_List*n = bd_cons( p , d , p->next ) ; if ( n != NULL ) { p->next->prev = n ; p->next = n ; } } // 双方向リストの指定場所 p の後ろのデータを消す処理は? void bd_delete( struct BD_List* p ) { struct BD_List* d = p->next ; d->next->prev = p ; p->next = d->next ; free( d ) ; } // この手のリスト処理のプログラムでは、命令の順序が重要となる。 // コツとしては、修正したい箇所の遠くの部分を操作する処理から // 書いていくと間違いが少ない。
番兵と双方向循環リスト
前述の bd_insert() だが、データの先頭にデータを挿入したい場合は、どう呼び出せば良いだろうか?
bd_insert() で、末尾にデータを挿入する処理は、正しく動くだろうか?
同じく、bd_delete() だが、データの先頭のデータを消したい場合は、どう呼び出せば良いだろうか?
また、データを消す場合、最後の1件のデータが消えて、データが0件になる場合、bd_delete() は正しく動くだろうか?
こういった問題が発生した場合、データが先頭・末尾で思ったように動かない時、0件になる場合に動かない時、特別処理でプログラムを書くことは、プログラムを読みづらくしてしまう。そこで、一般的には 循環リストの時にも紹介したが、番兵(Sentinel) を置くことが多い。
しかし、先頭用の番兵、末尾用の番兵を2つ用意するぐらいなら、循環リストにした方が便利となる。このような双方向リストでの循環した構造は、双方向循環リスト(bi-directional ring list)と呼ばれる。
情報ネットワーク基礎・ガイダンス
情報ネットワーク基礎では、インターネットがどのような仕組みなのか、どのようにして動いているのかを説明する。TCP/IPって何? IPアドレスって何? セキュリティって何?
あなたが使っているネットワーク機能は?
まずは、Teams にて「あなたが使っているネットワーク機能は?」を返信にて書き込んでください。
ただしネットワークを使うことでコンピュータがどう動いているかの視点で答えてほしい。
共有:ネットワークプリンタ、ファイル共有… – サービスを利用する視点
(ハードウェアや情報を共有)
分散:大量のコンピュータで負荷分散、リスク分散… – サービスを提供する視点
(仕事を分散し全体で高速化, 沢山のコンピュータの1台が壊れても全体は動く)
ネットワークの歴史
昔のコンピュータは、開発にお金がかかるため1台のコンピュータを全員で使うもの(TSS: Time Sharing System/時分割システム)だった。冷戦の時代、軍の重要な処理を行うコンピュータでは、コンピュータのある所に核攻撃を加えられ、軍の機能がすべて動かなくなることは問題だった。1970年頃にアメリカ国防総省ARPANETがインターネットの原型(TCP/IP)を作る。
1980年代には、パソコンが同じ組織内でネットワークで繋がるようになるLAN(Local Area Network)が使われるようになる。1990年代には、LANどうしを遠隔地接続をするWAN(Wide Area Network)が発達し、Internet(広域コンピュータネットワーク)という言葉が広く普及していった。欧州原子核研究機構(CERN)で、ティム・バーナーズ=リーがWorld Wide Web/httpを開発(1989)。1995年、マイクロソフトの家庭用パソコンのOS Windows95の普及と共にWWWが普及する。
- 1980年代:パソコン通信※
- 1997年:weblog(blog:自分で作るwebページの拡大)
- 1998年:Google検索
- 1999年:2ch
- 2003年:SNSの誕生(2004:mixi)
- 2006年:Twitter,Facebook(一般開放)
コンピュータインタフェースとネットワーク(物理層)
ネットワークにおける情報伝達において、伝送媒体(電気信号,光)にて0/1を伝えるための取り決めは、物理層という。まずは、コンピュータと機器の接続について考えると、シリアル通信とパラレル通信に分類できる。(シリアル通信は時間を細かく区切って複数の信号を送ることから時分割多重通信と呼ぶこともある)
通信の高速化に伴い、伝送の配線はコンデンサやインダクタンスを考慮したインピーダンスマッチングが重要となる。このため、高速通信のインタフェース両端は終端抵抗(ターミネータ)が必要だった。
1本の信号線で単位時間あたりのデータ通信速度が同じであれば、パラレル通信の方が高速であるが、長い通信路ではノイズ対策が重要でありノイズ対策をきちんとした線が複数本あるとケーブルが太くなることから、長い通信路ではシリアル通信が使われる。少ない信号線に対してノイズ対策をきちんと施すことができるので、長い通信路ではシリアル通信の方が高速となる。
パラレル通信の例:パラレルポート(プリンタ用)IEEE 1284、ハードディスクATA(IDE)、計測器GP-IB
シリアル通信の例:RS-232C、IEEE1394(FireWire)、ハードディスク(SATA)、USB1.1, USB2.0, USB3.0, USB3.1 Gen2, USB3.2 Gen2x2…、有線LAN/Ethernet
有線LAN/Ethernetの種別
- 半二重通信 – 送信/受信を1本の信号線でおこなう。
- 全二重通信 – 送信用の信号線、受信用の信号線がそれぞれ別。送信受信を同時にできる。
- 複信 Simplex(一方的な放送), Half Duplex(半二重), Full Duplex(全二重)
- 10BASE/* – 10Mbit/sec
- 10BASE/5 – ケーブルに針を刺して増設 – 半二重通信/ターミネータが必要
- 10BASE/2 – T型BNCケーブルで延長 – 半二重通信/ターミネータが必要
- 10BASE/T – HUBで分配(終端抵抗などの問題はHUBが解決してくれる) – 全二重通信
- 100BASE-T – 100Mbit/sec / CAT5
- 信号線のノイズ対策は、シールドで覆う、信号線を“より線”(ツイストペア)にするなどの対策が重要
- シールドや”より線”の方式でカテゴリー CAT5,CAT6,CAT7 などで分類される
- 信号線のノイズ対策は、シールドで覆う、信号線を“より線”(ツイストペア)にするなどの対策が重要
- 1000BASE-T ギガビット – 1000Mbit/sec = 1Gbit/sec / CAT6
- 10000BASE , 10GBase – 10Gbit/sec / CAT7
![]() 同軸ケーブル |
![]() ツイストペアケーブル |
ツイストペアケーブルがノイズに強い理由
理解確認
- ネットワークにおける共有と分散について例をあげて説明せよ。
- TSSのような通信によるコンピュータと、TCP/IPによる通信網を比べ何がどう良いのか?
- シリアル通信とパラレル通信、それぞれの利点欠点は?
- 10BASE/5,10BASE/2,10BASE/Tのそれぞれの問題点は?
- CD1枚のデータを1000BASE-Tのネットワークで転送するのに何秒かかる?
- サンプリングレート44.1kHz,16bit,ステレオ2ch,74分
データベースガイダンス2024
インターネットの情報量
インターネット上の情報量の話として、2010年度に281EB(エクサバイト)=281✕1018B(参考:kMGTPEZY)で、2013年度で、1.2 ZB(ゼタバイト)=1.2✕1021B という情報があった。ムーアの法則の「2年で2倍」の概算にも、それなりに近い。 では、今年2024年であれば、どのくらいであろうか?
- ムーアの法則でいけば、281EB(2010年)×214/2=36ZB(2024年)だけど
- 大塚商会の2016年度における2020年度の予測では…
- アメリカのIDCの2020/5月の発表では、59ZB!? — 236ZB
しかし、これらの情報をGoogleなどで探す場合、すぐにそれなりに情報を みつけてくれる。これらは、どの様に実装されているのか?
Webシステムとデータベース
まず、指定したキーワードの情報を見つけてくれるものとして、 検索システムがあるが、このデータベースはどのようにできているのか?
Web創成期の頃であれば、Yahooがディレクトリ型の検索システムを構築してくれている。(ページ作者がキーワードとURLを登録する方式) しかし、ディレクトリ型では、自分が考えたキーワードではページが 見つからないことが多い。
そこで、GoogleはWebロボット(クローラー)による検索システムを構築した。 Webロボットは、定期的に登録されているURLをアクセスし、 そのページ内の単語を分割しURLと共にデータベースに追加する。 さらに、ページ内にURLが含まれていると、そのURLの先で、 同様の処理を再帰的に繰り返す。
これにより、巨大なデータベースが構築されているが、これを普通のコンピュータで実現すると、処理速度が足りず、3秒ルール or 5秒ルール (Web利用者は次のページ表示が3秒を越えると、次に閲覧してくれない)を実現するための能力が不足してしまう。だからこそ、これらを処理するには負荷分散が重要となる。
Webシステムの負荷分散
一般的に、Webシステムを構築する場合には、 1段:Webサーバ、2段:動的ページ言語、3段:データベースとなる場合も 多い。この場合、OS=Linux,Web=Apache,DB=MySQL,動的ページ生成言語=PHPの組合せによる、 LAMP構成とする場合も多い。
OS = Linux [ Webサーバ 動的Web言語 データベース ] User - - - - - Apache ----- PHP ----- MySQL
一方で、大量のデータを処理するDBでは、フロントエンド,セカンダリDB(スレーブDB),プライマリDB(マスタDB)のWebシステムの3段スキーマ構成となることも多い。
フロントエンドは、大量のWebユーザからの問合せを受ける部分であり、必要に応じてセカンダリDBに問合せを行う。
大量のユーザからの問合せを1台のデータベースシステムで捌くには処理の負荷が高い場合、複数のデータベースで負荷分散を行う。プライマリDBは、複数のデータベースシステムの原本となるべきデータを保存される。負荷分散の為に分散されたセカンダリDBは、プライマリDBと内容の同期をとりながらフロントエンドからの問合せに応答する。
データベースシステム
データベースには、ファイル内のデータを扱うためのライブラリの BerkleyDB といった場合もあるが、複雑なデータの問い合わせを実現する 場合には、リレーショナル・データベース(RDB)を用いる。 RDBでは、データをすべて表形式であらわし、SQLというデータベース 問い合わせ言語でデータを扱う。 また、問い合わせは、ネットワーク越しに実現可能であり、こういった RDBで有名なものとして、Oracle , MySQL , PostgreSQL などがある。 単一コンピュータ内でのデータベースには、SQLite などがある。
リレーショナルデータベースの串刺し
|
このような表データでは、たとえば「みかん」の単価が変更になると、2行目,4行目を変更しなければいけなくなる。巨大な表の場合、これらの変更は大変。
そこで、この表を2つに分類する。
|
|
||||||||||||||||||||||||||||
必要に応じて、2つの表から、以下のような SQL の命令で、データを抽出する。
select 単価表.商品名, 単価表.単価, 販売表.個数, 単価表.単価*販売表.個数 from 単価表, 販売表 ; |
データベースに求められるのACID特性
データベースシステムと呼ばれるには、ACID特性が重要となる。(次に述べるデータベースが無かったら…を参照)
- A: 原子性 (Atomicity) – 処理はすべて実行するか / しない のどちらか。
- C: 一貫性 (Consistency) – 整合性とも呼ばれ、与えられたデータのルールを常に満たすこと。
- I: 独立性 (Isolation) – 処理順序が違っても結果が変わらない。それぞれの処理が独立している。
- D: 永続性 (Durability) – データが失われることがない(故障でデータが無くならないとか)
しかし、RDBでは複雑なデータの問い合わせはできるが、 大量のデータ処理のシステムでは、フロントエンド,セカンダリDB,プライマリDB の同期が問題となる。この複雑さへの対応として、最近は NoSQL(RDB以外のDB) が 注目されている。(例: Google の BigTable)
データベースが無かったら
これらのデータベースが無かったら、どのようなプログラムを作る 必要があるのか?
情報構造論ではC言語でデータベースっぽいことをしていたが、 大量のデータを永続的に扱うのであれば、ファイルへのデータの読み書き 修正ができるプログラムが必要となる。
こういったデータをファイルで扱う場合には、1件のデータ長が途中で 変化すると、N番目のデータは何処?といった現象が発生する。 このため、簡単なデータベースを自力で書くには、1件あたりのデータ量を 固定し、lseek() , fwrite() , fread() などの 関数でランダムアクセスのプログラムを書く必要がある。
また、データの読み書きが複数同時発生する場合には、排他処理(独立性)も 重要となる。例えば、銀行での預け金10万の時、3万入金と、2万引落としが 同時に発生したらどうなるか? 最悪なケースでは、 (1)入金処理で、残金10万を読み出し、 (2)引落し処理で、残金10万を読み出し、 (3)入金処理で10万に+3万で、13万円を書き込み、 (4)引落し処理で、残金10万-2万で、8万円を書き込み。 で、本来なら11万になるべき結果が、8万になるかもしれない。
さらに、コンピュータといってもハードディスクの故障などは発生する。 障害が発生してもデータの原子性や永続性を保つためには、バックアップや 障害対応が重要となる。