ホーム » スタッフ » 斉藤徹 (ページ 32)

「斉藤徹」カテゴリーアーカイブ

2025年6月
日	月	火	水	木	金	土
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

ランダムアクセス・シーケンシャルアクセスから双方向リスト

2022年10月6日

前期期末試験のテスト返却と解説を行ってから、ランダムアクセスO(1)とシーケンシャルアクセスO(N)の説明を踏まえ、リスト構造のO(N)の改善にむけた解説を行う。

リスト構造の利点と欠点

リストを使った集合演算のように、データを連ねたリストは、単純リストとか線形リストと呼ばれる。特徴はデータ数に応じてメモリを確保する点や、途中へのデータの挿入削除が得意な点があげられる。一方で、配列は想定最大データ件数で宣言してしまうと、実際のデータ数が少ない場合、メモリの無駄も発生する。しかし、想定件数と実データ件数がそれなりに一致していれば、無駄も必要最小限となる。リスト構造では、次のデータへのポインタを必要とすることから、常にポインタ分のメモリは、データにのみ注目すれば無駄となる。

例えば、整数型のデータを最大 MAX 件保存したいけど、実際はそれ以下の、平均 N 件扱うとする。この時のメモリの使用量 M は、以下のようになるであろう。

配列の場合	リスト構造の場合
${M_{array}=\mbox{sizeof(int)} \times MAX}$	${M_{list}=(\mbox{sizeof(int)+sizeof(List*)})\times N}$ (ただしヒープ管理用メモリ使用量は無視)

シーケンシャルアクセス・ランダムアクセス

もう１つの欠点がシーケンシャルアクセスとなる。テープ上に記録された情報を読む場合、後ろのデータを読むには途中データを読み飛ばす必要があり、データ件数に比例したアクセス時間を要する。このような N番目データ参照に、O(N)の時間を要するものは、シーケンシャルアクセスと呼ばれる。

一方、配列はどの場所であれ、一定時間でデータの参照が可能であり、これは ランダムアクセスと呼ばれる。N番目のアクセス時間がO(1)を要する。

このため、プログラム・エディタの文字データの管理などに単純リストを用いた場合、１つ前の行に移動するには、先頭から編集行までの移動で O(N) の時間がかかり、大量の行数の編集では、使いものにならない。ここで、シーケンシャルアクセスでも１つ前にもどるだけでも処理時間を改善してみよう。

単純リストから双方向リストへ

ここまで説明してきた単純リストは、次のデータへのポインタを持つ。ここで、１つ後ろのデータ(N番目からN+1番目)をアクセスするのは簡単だけど、１つ前のデータ(N-1番目)を参照しようと思ったら、先頭から(N-1)番目を辿るしかない。でも、これは O(N) の処理であり時間がかかる処理。
ではどうすればよいのか？

この場合、一つ前のデータの場所を覚えているポインタがあれば良い。

// 双方向リストの宣言
struct BD_List {
    struct BD_List* prev ; // 1つ前のデータへのポインタ
    int             data ;
    struct BD_List* next ; // 次のデータへのポインタ
} ;

情報ネットワーク基礎・ガイダンス2022

2022年10月4日

情報ネットワーク基礎2022・シラバス

情報ネットワーク基礎では、インターネットがどのような仕組みなのか、どのようにして動いているのかを説明する。TCP/IPって何? IPアドレスって何? セキュリティって何?

あなたが使っているネットワーク機能は?

共有：ネットワークプリンタ、ファイル共有…
(ハードウェアや情報を共有)

分散：大量のコンピュータで負荷分散、リスク分散…
(仕事を分散し全体で高速化, 沢山のコンピュータの1台が壊れても全体は動く)

ネットワークの歴史

昔のコンピュータは、開発にお金がかかるため1台のコンピュータを全員で使うもの(TSS: Time Sharing System)だった。冷戦の時代、軍の重要な処理を行うコンピュータでは、コンピュータのある所に核攻撃を加えられ、軍の機能がすべて動かなくなることは問題だった。1970年頃にアメリカ国防総省ARPANETがインターネットの原型(TCP/IP)を作る。

1980年代には、パソコンがインターネットで繋がるようになる(LAN)。1990年代には、LANどうしを遠隔地接続をするWANが発達。欧州原子核研究機構(CERN)で、ティム・バーナーズ=リーがWorld Wide Web/httpを開発(1989)。1995年、マイクロソフトの家庭用パソコンのOS Windows95の普及と共にWWWが普及する。

※1980年代:パソコン通信、1997年:weblog,1998年:Google検索、1999年:2ch、2002年:SNSの誕生、2006年:Twitter,Facebook(一般開放)

コンピュータインタフェースとネットワーク(物理層)

ネットワークにおける情報伝達において、伝送媒体(電気信号,光)にて0/1を伝えるための取り決めは、物理層という。まずは、コンピュータと機器の接続について考えると、シリアル通信とパラレル通信に分類できる。

通信の高速化に伴い、伝送の配線はコンデンサやインダクタンスを考慮したインピーダンスマッチングが重要となる。このため、高速通信のインタフェース両端は終端抵抗(ターミネータ)が必要だった。

パラレル通信の例：パラレルポート(プリンタ用)IEEE 1284、ハードディスクATA(IDE)、計測器GP-IB

シリアル通信の例：RS-232C、USB1.1、IEEE1394(FireWire)、USB2.0、USB3.0、Ethernet

Ethernetの種別

10Mbit/sec通信
- 10BASE/5 – ケーブルに針を刺して増設
- 10BASE/2 – T型BNCケーブルで延長
- 10BASE/T – HUBで分配(終端抵抗などの問題はHUBが解決してくれる)
100BASE-T
1000BASE-T ギガビット
10000BASE , 10GBase

理解確認

ネットワークにおける共有と分散について例をあげて説明せよ。
TSSのような通信によるコンピュータと、TCP/IPによる通信網を比べ何がどう良いのか？
シリアル通信とパラレル通信、それぞれの利点欠点は？
10BASE/5,10BASE/2,10BASE/Tのそれぞれの問題点は？

情報制御基礎2022全講義録

2022年10月3日

情報メディア工学(前期)全講義録

2022年10月3日

オブジェクト指向プログラミング2022全講義録

2022年10月3日

データベースガイダンス2022

2022年10月2日

2022年度データベース・シラバス

インターネットの情報量

インターネット上の情報量の話として、2010年度に281EB(エクサバイト)=281✕10¹⁸B(参考:kMGTPEZY)で、2013年度で、1.2 ZB(ゼタバイト)=1.2✕10²¹B という情報があった。ムーアの法則の「2年で2倍」の概算にも、それなりに近い。では、今年2022年であれば、どのくらいであろうか？

ムーアの法則でいけば、281EB(2010年)×64=18ZB(2022年)だけど
大塚商会の2016年度における2020年度の予測では…
アメリカのIDCの2020/5月の発表では、59ZB!? — 118ZB??

しかし、これらの情報を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に問合せを行う。
大量のユーザからの問合せを１台のデータベースシステムで捌くには処理の負荷が高い場合、複数のデータベースで負荷分散を行う。プライマリDBは、複数のデータベースシステムの原本となるべきデータを保存される。負荷分散の為に分散されたセカンダリDBは、プライマリDBと内容の同期をとりながらフロントエンドからの問合せに応答する。

データベースシステム

データベースには、ファイル内のデータを扱うためのライブラリの BerkleyDB といった場合もあるが、複雑なデータの問い合わせを実現する場合には、リレーショナル・データベース(RDB)を用いる。 RDBでは、データをすべて表形式であらわし、SQLというデータベース問い合わせ言語でデータを扱う。また、問い合わせは、ネットワーク越しに実現可能であり、こういった RDBで有名なものとして、Oracle , MySQL , PostgreSQL などがある。単一コンピュータ内でのデータベースには、SQLite などがある。

リレーショナルデータベースの串刺し

商品名	単価	個数	価格
りんご	200	2	400
みかん	50	6	300
アイスクリーム	125	1	125
みかん	50	3	150

このような表データでは、たとえば「みかん」の単価が変更になると、2行目,4行目を変更しなければいけなくなる。巨大な表の場合、これらの変更は大変。

そこで、この表を2つに分類する。

単価表
商品ID	商品名	単価
1010	りんご	125
1011	みかん	50
2101	アイスクリーム	125

販売表
商品ID	個数
1010	2
1011	6
2101	1
1011	3

必要に応じて、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万になるかもしれない。

さらに、コンピュータといってもハードディスクの故障などは発生する。障害が発生してもデータの原子性や永続性を保つためには、バックアップや障害対応が重要となる。

福井大学リカレント教育・プログラミング応用

2022年10月1日

mariadbトラブル appamor

2022年9月24日

mariadb が止まってしまう

パッケージの更新をしていたら、mariadb が起動しなくなる。systemctl start mariadb を実行すると、コマンドラインに帰ってこない。Ctrl-Z で background にすると WordPress も動いているし問題ないのかと思えば、30分ほどするとエラーを吐いてとまる。journalctl -xe で吐いているエラーを確認すると以下のようなメッセージが残っていた。

AVC apparmor="DENIED" operation="connect" info="Failed name lookup - disconnected path" error=-13 profile="/usr/sbin/mysqld" name="run/nscd/socket" pid=67400 comm="mysqld" requested_mask="wr" denied_mask="wr" fsuid=118

メッセージを元にググると、こちらの記事が該当した。

AppArmor（Application Armor）は、各プログラムにセキュリティプロファイルを結びつけ、プログラムのできることに制限をかけるプログラム…らしい。(wikipediaより)

AppArmor の不具合を解消

パッケージを MySQL から MariaDB に移行する際に、AppArmor でトラブルが残ったみたい。こちらの記事を参考に、以下のコマンドで、ゴミを消したらうまく起動するようになった。

$ sudo aa-remove-unknown
Removing '/usr/sbin/mysqld'         mysql関連のゴミを消してくれたみたい。
$ sudo systemctl start mariadb      無事に起動

VSCodeとXAMPPのインストール

2022年9月22日

Webアプリ開発の基本を勉強するために、HTML+CSS、JavaScript のフロントエンドと、PHP+データベースのバックエンドを簡単な演習で体験するのであれば、プログラムのエディタの VS Code (Visual Studio Code) と、自分のパソコンで動かせる Webサーバ XAMPP をインストールして演習してみましょう。

Visual Studio Code のインストール

Visual Studio Code は、Microsoft 社が開発しているプログラムのエディタ(様々なテキストの編集ソフト)であり、最近のプログラマーの中で一番利用されています。

まずは、Visual Studio Code をパソコンにインストールしてみましょう。Visual Studio Code で検索すれば、簡単に見つかると思います。

https://azure.microsoft.com/ja-jp/products/visual-studio-code/

Windows 10,11 (64bit OS)であれば、Windows System Installer 64bit を選んで、ダウンロードしたファイルを実行しましょう。インストールが始まります。

Visual Studio Code の起動と設定

インストールが終わったら、メニューからを起動してください。

拡張機能のインストール機能を用いて、日本語メニューを出すための Japanese Language Pack をインストールしてください。

拡張機能のインストールが終わると Restart の表示がでるので VSCode の再起動を行ってください。

XAMPP のインストール

次に、XAMPP(正式にはシャンプと発音, ザンプは間違いらしい😢) をインストールします。XAMPP は、様々なOS の上で、ウェブアプリケーションの開発に必要な Webサーバ機能(Apache)、データベース機能(Maria DB)、動的Webページ用言語(PHP, Perl) をまとめてインストールでき、ウェブアプリケーションの学習用に広く使われています。

インターネットに自分の作ったウェブアプリケーションのシステムを公開するのであれば、OS Linux で、Apache, MySQL, PHP を動かすのが一般的です。この構成は通称 LAMP (ランプ) と呼ぶことが多い。XAMPP も X(??), Apache, MariaDB, PHP, Perl の組み合わせなので XAMPP と名付けられた。