第1回 TListの実装と性能
はやしつとむ
アナハイムテクノロジー株式会社
2009/2/12
オブジェクト指向によって、アルゴリズムは隠ぺいされていることが多くなった。しかし、「用意されていない処理」が求められたときに対応できるだろうか(編集部)
君は用意されていない処理に対応できるか
エンバカデロ・テクノロジーズの製品であるDelphiは、BorlandのTurboPascalを元祖とする製品です。1995年の発売当初から、コンパイル速度の速さとデータベースとの接続性の高さ、またPascalに追加されたオブジェクト指向による生産性の高さからユーザーを獲得してきました。
2008年9月にはDelphi 2009が発売され、内部文字コードがすべてユニコード化されるなどの新フィーチャーによって注目を集めています。
ご多分に漏れずDelphiもオブジェクト指向な言語なわけですが、オブジェクト指向の三要素として、継承・隠ぺい・多態があります。昨今のプログラミング事情ではありとあらゆるクラスが提供されているため、例えば、ソートのアルゴリズムを知らなくても xxobj.sort のようにすればソートが実行されるという環境が整っています。
つまり、「アルゴリズムが隠ぺいされている」わけです。しかし、いったん「用意されていない処理」を書こうとした瞬間にプリミティブな問題に突き当たることになります。
本連載ではこうした事情に鑑みて、クラスの中に隠ぺいされているアルゴリズムに再度焦点を当てることを目標とします。本フォーラムでは山下寛人氏が「コーディングに役立つ!アルゴリズムの基本」を連載していらっしゃるので、本連載ではDelphiで実際に使えるクラスとして、アルゴリズムを実装するということをテーマにしたいと思います。
また、本連載ではDelphiのクラスライブラリであるVCL(Visual Component Library)の内部構造にも言及しますが、これはオープンソースではないので勝手に引用するわけにもいきません。そこで、Delphiをお持ちでない方がいらっしゃいましたら、下記のURLから無償版のTurbo Delphiをダウンロードしてインストールしてみてください。
関連リンク: | |
Delphiトライアル版/無償バージョン http://www.codegear.com/jp/downloads/free/delphi |
Turbo Delphi にもVCLのソースコードが付属していますので、これをご覧になれば多少のバージョン間の相違はあるかもしれませんが、基本的な部分は理解いただけるのではないかと思います。
Delphiでのリスト
さて、第1回のお題はリスト構造です。Delphiでのプログラミングで多用するTListやTStringListもリストなわけですが、こういう便利なものがあると通常はあまり困りません。
以前、取引先の部長さんから聞いた話ではVisual Basicしか経験のないプログラマにDelphiでプログラムを書いてもらったら、TStringListなどを使わずにTMemoをフォーム上に非表示状態にして置いて、その中でソートをしていたということがあったそうです。なんだか、へんてこりんな話ですがAccessなんかでは確かによく使う手です。
また、よく考えるとTMemo.Lines はTStrings を継承しているので、やっぱりリストを使っているわけですから、「中(あた)らずと雖(いえど)も遠からず」といったところでしょうか。
VCLには以下の4つのクラスが主にリスト構造を実現するために用意されています。
- TList
- TStrings
- TStringList
- THashedStringList
この中で、TListはTObjectから直接派生したクラスですが、TStrings以下はTObject→TPersistent→TStrings→TStringList→SHashedStringListと継承関係になっています。
TPersistentは公開できるプロパティを持った基底クラスで設計時に表示可能なものですが、設計時に単独で存在することができないため、コンポーネントの一部として利用するためのクラスです。先ほど例として挙げたTMemo.Linesなどがこれに当たります。
Listとは何か
ところで、そもそもListとは何であるのかを定義しないと、議論が始まらないと思います。
手元にある『アルゴリズムとデータ構造―改訂C言語版』(平田富夫著 森北出版刊)では「各要素aiごとに次の要素ai+1を指すポインタを持たせることが考えられる、これがリスト(list、 linked list)と呼ばれるデータ構造である」と書いてあります。
また、『Delphiアルゴリズム』(Rod Stephens著 ソフトバンククリエイティブ刊)では「複数のオブジェクトをグループにまとめたデータ構造を『リスト』と呼びます」と書いてあります。Linked Listといってしまうとデータ構造の話になってしまうし、外形的にこれがListだという定義っていうのがどうも見当たりません。
そこで、僕的にこれがクラスとしてのListとして最低限必要だという定義を勝手にしてみました。ほかにもたくさん要素はありますが、以下の要素があればほかのこともできると思います。1番目と2番目は別として、データ操作に関する基本要素であるCRUD(Create/Reference/Update/Delete)ができることが必要ですね。
Listクラスの定義:
- Listは複数のデータを保持することができる
- Listは保持しているデータの個数を返すことができる
- Listは指定したn番目にデータを挿入することができる
- Listは指定したn番目のデータを返すことができる
- Listは指定したn番目のデータを削除することができる
- Listは指定したn番目のデータを変更することができる
1/2 |
Index | |
TListの実装と性能 | |
Page1 君は用意されていない処理に対応できるか Delphiでのリスト Listとは何か |
|
Page2 TList TLinkList |
Delphiアルゴリズムトレーニング |
Coding Edgeお勧め記事 |
いまさらアルゴリズムを学ぶ意味 コーディングに役立つ! アルゴリズムの基本(1) コンピュータに「3の倍数と3の付く数字」を判断させるにはどうしたらいいか。発想力を鍛えよう |
|
Zope 3の魅力に迫る Zope 3とは何ぞや?(1) Pythonで書かれたWebアプリケーションフレームワーク「Zope 3」。ほかのソフトウェアとは一体何が違っているのか? |
|
貧弱環境プログラミングのススメ 柴田 淳のコーディング天国 高性能なIT機器に囲まれた環境でコンピュータの動作原理に触れることは可能だろうか。貧弱なPC上にビットマップの直線をどうやって引く? |
|
Haskellプログラミングの楽しみ方 のんびりHaskell(1) 関数型言語に分類されるHaskell。C言語などの手続き型言語とまったく異なるプログラミングの世界に踏み出してみよう |
|
ちょっと変わったLisp入門 Gaucheでメタプログラミング(1) Lispの一種であるScheme。いくつかある処理系の中でも気軽にスクリプトを書けるGaucheでLispの世界を体験してみよう |
|
- プログラムの実行はどのようにして行われるのか、Linuxカーネルのコードから探る (2017/7/20)
C言語の「Hello World!」プログラムで使われる、「printf()」「main()」関数の中身を、デバッガによる解析と逆アセンブル、ソースコード読解などのさまざまな側面から探る連載。最終回は、Linuxカーネルの中では、プログラムの起動時にはどのような処理が行われているのかを探る - エンジニアならC言語プログラムの終わりに呼び出されるexit()の中身分かってますよね? (2017/7/13)
C言語の「Hello World!」プログラムで使われる、「printf()」「main()」関数の中身を、デバッガによる解析と逆アセンブル、ソースコード読解などのさまざまな側面から探る連載。今回は、プログラムの終わりに呼び出されるexit()の中身を探る - VBAにおけるFileDialog操作の基本&ドライブの空き容量、ファイルのサイズやタイムスタンプの取得方法 (2017/7/10)
指定したドライブの空き容量、ファイルのタイムスタンプや属性を取得する方法、FileDialog/エクスプローラー操作の基本を紹介します - さらば残業! 面倒くさいエクセル業務を楽にする「Excel VBA」とは (2017/7/6)
日頃発生する“面倒くさい業務”。簡単なプログラミングで効率化できる可能性がある。本稿では、業務で使うことが多い「Microsoft Excel」で使えるVBAを紹介する。※ショートカットキー、アクセスキーの解説あり
|
|