第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の世界を体験してみよう
  Coding Edgeフォーラムフィード  2.01.00.91


Coding Edge フォーラム 新着記事
@ITメールマガジン 新着情報やスタッフのコラムがメールで届きます(無料)

注目のテーマ

>

Coding Edge 記事ランキング

本日 月間