基本的な本能
LINQ クエリのパフォーマンスを向上させる
Jared Parsons

目次
LINQ は、標準的なクエリ言語に基づいて、データをすばやくフィルタ処理できる強力なツールです。LINQ は、単純で直感的な構文を使用して、構造化されたデータ セットを検索できます。これは、データ バインド シナリオに組み込んで使用するデータのフィルタ処理にとって最適です。
ただし、落とし穴が 1 つあります。LINQ が強力で非常に効率的であることは間違いありませんが、それでも、大量のデータによって予測不可能なパフォーマンス上の問題が発生する可能性があります。このコラムでは、応答性の高い UI を作成するために、大量のデータに対する LINQ クエリで最高のパフォーマンスを得る技法に重点をおいて説明します。
問題点
筆者は最近のプロジェクトで、LINQ to XML クエリを使用してデータをフィルタ処理する XML データ セット用のワード ホイール検索 UI を考案しました。ワード ホイール検索を使用すると、データ セットを単語に基づいて検索できます。ワード ホイール検索は、ユーザーが入力したテキストを部分文字列として持つデータを表示します。ユーザーが文字を入力するごとに結果が更新されるので、瞬時にフィードバックが得られます。
筆者は、生成された XML ファイルを使用するワード ホイール UI を設計し、実装しました。ユーザーは、テキストボックスに入力できるようになっており、検索結果は、その入力されたテキストの部分文字列を含んでいる名前を持つ要素に絞り込まれます。UI については設計仕様を満たしており、筆者のテスト環境で効率の良い応答が得られました。プロジェクトの残りの作業が完了した時点で、このコードは実稼動用の XML ファイルを生成できるようになったので、新しいコードをチェックインして帰宅しました。ところが、翌朝 QA から山のような UI のバグを受け取りました。UI は、役に立たないと言っても過言ではないくらい応答速度が低下していました。
検索条件の 1 つがボトルネックになっていると想像し、簡単に直ると考えました。ところが、UI のプロファイリングを実行しクエリを最適化した後でも、パフォーマンスは許容できるレベルまでには向上しませんでした。問題はクエリの効率ではなく、大量のデータに行く手をふさがれていたのです。テスト用の XML ファイルは、わずか 5,000 ~ 10,000 個の要素から構成されていましたが、実稼動用の XML ファイルにはその約 40 倍ものデータが含まれていました。たとえどんなに高速なクエリを使用したとしても、インデックスを持たない数十万行のデータの検索が遅くなることは当然です。
検索処理を高速化するための方法を見つける必要があったため、パフォーマンスを向上させるために LINQ の持つ特殊な機能である遅延実行と遅延評価を利用することにしました。これらの機能を使用すると、LINQ クエリは、定義された時点では実行されません。代わりに、結果の列挙時に実行されます。これにより、効率的にデータをスクロールするためにクエリの結果を使用する場合に、大きな柔軟性が得られます。
デモ アプリケーションを構築する
筆者が遅延実行と遅延評価をどのように使用しているかを説明するために、XML ファイル セットと LINQ to XML クエリを使用するワード ホイール検索の簡略化バージョンを構築する手順を見ていきましょう。Visual Basic® の XML 統合機能をフルに活用するには、処理の対象となるドキュメントの XML スキーマをプロジェクトに追加する必要があります。XML スキーマは、XML の参照方法のアウトラインを提供するという点において、Microsoft® .NET Framework のメタデータに類似しています。スキーマを追加すると、Visual Studio® の IDE で LINQ to XML クエリに IntelliSense® を使用できます。
Visual Studio で、新しいスキーマに IntelliSense を使用できるようにする方法は簡単です。Visual Basic は、現在のプロジェクトに含まれているすべての XML スキーマを認識します。単にプロジェクトにスキーマを追加し、次にその XML 名前空間のインポート ステートメントを、LINQ to XML クエリを定義しているすべてのファイルに追加するだけです。
Imports <xmlns="http://tempuri.org/MsdnWheelSearch.xsd">
スキーマなしで Xlinq を使用すること自体には何の問題もありません。ただし、それは IntelliSense をオフにして Visual Studio を使用するようなものです。つまり、使用できるだけで、楽しくはないのです。
ワード ホイール検索アプリケーションで使用する XML ファイルには、基本クラス ライブラリ (BCL) のアセンブリ、型、およびメンバに関する情報が含まれています。各 XML 要素 (つまり行) は、対応する親の中でその行を一意に識別できる ID が付けられた属性を 1 つ持っています。アセンブリ行の場合、この ID は生成された番号になります。それ以外のすべての行では、ID は基になるメタデータ トークンになります。さらに、各行にはその親を一意に識別する ID も含まれています。このデータの XML スキーマを図 1 に示します。

図 1 XML スキーマ
<?xml version="1.0" encoding="utf-8"?>
<xs:schema id="MsdnWheelSearch"
targetNamespace="http://contoso.com/MsdnWheelSearch.xsd"
elementFormDefault="qualified"
xmlns="http://contoso.com/MsdnWheelSearch.xsd"
xmlns:mstns="http://contoso.com/MsdnWheelSearch.xsd"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
>
<xs:element name="Info">
<xs:complexType>
<xs:sequence>
<xs:element name="Assemblies" minOccurs="0" maxOccurs="unbounded">
<xs:complexType>
<xs:sequence>
<xs:element name="Assembly" minOccurs="0" maxOccurs="unbounded">
<xs:complexType>
<xs:attribute name="Name" type="xs:string" />
<xs:attribute name="CodeBase" type="xs:string" />
<xs:attribute name="Id" type="xs:int" />
<xs:attribute name="FullName" type="xs:string" />
</xs:complexType>
</xs:element>
</xs:sequence>
</xs:complexType>
</xs:element>
<xs:element name="Types" minOccurs="0" maxOccurs="unbounded">
<xs:complexType>
<xs:sequence>
<xs:element name="Type" minOccurs="0" maxOccurs="unbounded">
<xs:complexType>
<xs:attribute name="Name" type="xs:string" />
<xs:attribute name="Namespcae" type="xs:string" />
<xs:attribute name="Id" type="xs:int" />
<xs:attribute name="AssemblyId" type="xs:int" />
</xs:complexType>
</xs:element>
</xs:sequence>
</xs:complexType>
</xs:element>
<xs:element name="Members" minOccurs="0" maxOccurs="unbounded">
<xs:complexType>
<xs:sequence>
<xs:element name="Member" minOccurs="0" maxOccurs="unbounded">
<xs:complexType>
<xs:attribute name="Name" type="xs:string" />
<xs:attribute name="Kind" type="xs:string" />
<xs:attribute name="Id" type="xs:int" />
<xs:attribute name="TypeId" type="xs:int" />
<xs:attribute name="AssemblyId" type="xs:int" />
</xs:complexType>
</xs:element>
</xs:sequence>
</xs:complexType>
</xs:element>
</xs:sequence>
</xs:complexType>
</xs:element>
</xs:schema>
このコラムに付属のサンプル プロジェクトをダウンロードすると、このスキーマに対応する XML ファイルがいくつか利用できます。サンプル プロジェクトには、小規模なデータ セットと非常に大規模なデータ セットの両方が含まれています。UI を使用すると同じクエリを両方のデータ セットに対して簡単に実行できるので、サイズの異なるデータ セットによってパフォーマンスにどのような影響があるか比較して理解できます。
このコラムで本題として扱っているクエリは、ユーザーが現在入力している特定の文字列を部分文字列として名前に含むすべてのメンバを返します。また、このメンバを所有している型の情報も表示します。この処理は、一致する名前でメソッド行をフィルタ処理し、次にその結果を同一の Id 属性および AssemblyId 属性を持つすべての型と結合することで実現されています。
Private Function GetQueryMethodsOfName( _
ByVal doc As XDocument, ByVal name As String) As IEnumerable
Return From method In doc...<Member> _
Where method.@Name.Contains(name) _
Where 0 = String.Compare(method.@Kind, "Method") _
Join type In doc...<Type> _
On type.@Id Equals method.@TypeId _
And type.@AssemblyId Equals method.@AssemblyId _
Select Type = type.@Name, Method = method.@Name
End Function
サンプル コードには、BCL のデータを調べるために行を結合するクエリも含まれています。そちらのコードもぜひお試しください。
基本的なユーザー インターフェイス
図 2 に、サンプル アプリケーションを示します。基本となるユーザー インターフェイスは、テキストボックスです。ユーザーが文字を入力すると、アプリケーションは、クエリ結果をフィルタ処理し、入力に一致するデータが存在する行だけを含む結果を返します。ユーザーが文字を入力するごとに、アプリケーションは常にこの値を更新し、より絞り込まれた結果をユーザーに提供します。図 3 に、筆者のホイール検索クラスのコードを示します。
図 2 ワード ホイール サンプル アプリケーション (クリックすると拡大画像が表示されます)

図 3 ホイール検索クラス
Public Class WheelSearch
Private m_doc As XDocument = New XDocument()
Private m_query As Query = Query.MethodsOfName
Public Property Query() As Query
Get
Return m_query
End Get
Set(ByVal value As Query)
m_query = value
OnSearchTextChanged(Nothing, EventArgs.Empty)
End Set
End Property
Public Property Xml() As XDocument
Get
Return m_doc
End Get
Set(ByVal value As XDocument)
If value Is Nothing Then
value = New XDocument
End If
m_doc = value
OnSearchTextChanged(Nothing, EventArgs.Empty)
End Set
End Property
Public Sub New()
' This call is required by the Windows Form Designer.
InitializeComponent()
' Add any initialization after the InitializeComponent() call.
m_dataGridView.AutoGenerateColumns = True
End Sub
Protected Overrides Sub OnLoad(ByVal e As System.EventArgs)
MyBase.OnLoad(e)
OnSearchTextChanged(Nothing, EventArgs.Empty)
End Sub
#Region "Event Handlers"
Private Sub OnSearchTextChanged(ByVal sender As Object, _
ByVal e As EventArgs) Handles m_searchTb.TextChanged
If m_doc Is Nothing Then
Return
End If
m_dataGridView.IncrementalSearch = _
QueryContainer.Search(m_query, m_doc, m_searchTb.Text)
End Sub
#End Region
End Class
クエリの結果は、DataGridView に表示されます。LINQ クエリの結果は、通常データ バインドとうまく併用できますが、DataGridView との併用時には結果を List(Of Object) などの型に変換する必要があります。データ バインド インフラストラクチャへの組み込みが容易になるような型の列挙を返すのは、個々のクエリの責任です。
では、UI を読み込んでワード ホイール検索のパフォーマンスをテストしてみましょう。小さい方のデータ セットでは処理速度が速いことに気が付きます。大きい方のデータ セットでは処理速度が大幅に低下し、ほとんど実用に耐えません。
パフォーマンスの低さの原因は、LINQ クエリを List(Of Object) に変換していることにほかなりません。これは、プロファイラを使用すると検証できます。内部の処理を見ると、List(Of Object) は、クエリから返される個々の検索結果を即座に追加しなければならないため、クエリは、含んでいるデータのすべての部分を完全に処理しておく必要があります。この処理は、小さい方のデータ セットでは、気付かないくらい高速ですが、大きい方のデータ セットでは、キーストローク間に行うには時間がかかりすぎます。
パフォーマンス向上のための方法
データの構造は変更できないと仮定した場合、UI の応答性を向上させるにはどうすればよいのでしょうか。選択肢の 1 つは、ユーザーが 1 文字入力するごとに検索するのではなく、Enter キーを押す操作、ボタンをクリックする操作などによって明示的に検索処理が起動されるまで待機することです。ただし、この解決策ではユーザーが即座に応答を得られないため、ユーザー エクスペリエンスが大幅に低下します。また、どのような検索条件においても長い時間がかかるという問題点を解決するものでもありません。
クエリが返す行数を制限することで、パフォーマンスを向上させることは可能でしょうか。もちろん可能ですが、その場合一部のデータしか表示されないため、ユーザー エクスペリエンスが損なわれることに変わりはありません。また、ユーザーに検索が完了していないことを知らせるための新しい UI をデザインしたり、フル検索を実行するためのメカニズムを用意したりする必要があります。ただし、フル検索により、UI の応答が遅いという最初の問題に戻ることになります。
つまり、すべてのデータを表示する必要もあり、データ構造も変更できないということです。ただし、すべてのデータを一度に表示する必要があるでしょうか。一度にデータのごく一部のみをユーザーに提示し、さらにキー押し下げの検出時に、現在の検索を破棄して新しい検索を開始する方法はどうでしょうか。これは、Microsoft Outlook® で使用されているインスタント検索技法に近いものになります。
インクリメンタル検索
LINQ の優れた特徴の 1 つは、遅延実行をサポートしていることです。クエリは、コードに現れた時点では実行されません。その時点では、単に定義が与えられるだけです。返された列挙子に対して MoveNext が呼び出されるまで、定義されたクエリが実行されることはありません。データのインクリメンタル検索にこの遅延実行を利用すると、UI がブロックされる時間は最小限で済みます。
筆者は、IEnumerable を実装している任意のオブジェクトで使用可能な IncrementalSearch というクラスを定義しました。すべての LINQ クエリは IEnumerable インターフェイスを実装しています。IncrementalSearch は、一定の時間が経過したら検索を停止するというアイデアに基づいています。このアルゴリズムでは、一定の時間が経過するまで MoveNext を呼び出すことで次の値を取得しています。その時点で、見つかったデータは新しい Result オブジェクトに格納されて返されます (図 4 を参照)。

図 4 IncrementalSearch クラス
Public Enum SearchStatus
InProgress
Completed
End Enum
Public Class Result
Private m_allValues As IList
Private m_incrementalValues As IList
Private m_status As SearchStatus
Public ReadOnly Property AllValues() As IList
Get
Return m_allValues
End Get
End Property
Public ReadOnly Property IncrementalValues() As IList
Get
Return m_incrementalValues
End Get
End Property
Public ReadOnly Property SearchStatus() As SearchStatus
Get
Return m_status
End Get
End Property
Sub New(ByVal allValues As IList, _
ByVal incrementalValues As IList, _
ByVal status As SearchStatus)
m_allValues = allValues
m_incrementalValues = incrementalValues
m_status = status
End Sub
End Class
Public Class IncrementalSearch
Private m_enumerable As IEnumerator
Private m_allFound As New List(Of Object)
Private m_status As SearchStatus = SearchStatus.InProgress
Private m_delay As TimeSpan
Public ReadOnly Property SearchStatus() As SearchStatus
Get
Return m_status
End Get
End Property
Public Property Delay() As TimeSpan
Get
Return m_delay
End Get
Set(ByVal value As TimeSpan)
m_delay = value
End Set
End Property
Public Sub New(ByVal e As IEnumerable)
m_delay = TimeSpan.FromSeconds(0.1)
m_enumerable = e.GetEnumerator()
End Sub
Public Function Search() As Result
If m_status = SearchStatus.Completed Then
Return New Result(m_allFound, New List(Of Object), m_status)
End If
Dim found As New List(Of Object)
Dim start = DateTime.Now
Do
If Not m_enumerable.MoveNext() Then
m_enumerable = Nothing
m_status = SearchStatus.Completed
Exit Do
End If
found.Add(m_enumerable.Current)
Loop Until DateTime.Now - start > m_delay
m_allFound.AddRange(found)
Return New Result(m_allFound, found, m_status)
End Function
End Class
Search メソッドは、見つかったデータに基づいて Result オブジェクトを返します。Result オブジェクトには、現在の Search メソッドの呼び出しで見つかった値、以前の Search メソッドの呼び出しで見つかったすべての値のリスト、および検索の現在の状態が含まれます。つまり、UI がデータをいくつかの単位に分割して返せるようになりました。発生する遅延時間の最大値は、すべての行を取得する時間ではなく次の要素の取得に必要な時間になります。
Dim found As New List(Of Object)
Dim start = DateTime.Now
D
If Not m_enumerable.MoveNext() Then
m_enumerable = Nothing
m_status = SearchStatus.Completed
Exit Do
End If
found.Add(m_enumerable.Current)
Loop Until DateTime.Now - start > m_delay
目標は、UI にデータ バインドを使用してデータを表示できるようにすること、および効率的に検索できるようにすることです。データを表示しても UI がハングしないようにする必要があります。戻り値は、インクリメンタル検索パターンを使用してカスタム DataGridView に表示されます。実装例は、DataGridViewIncrementalSearch という名前で、DataGridView から派生しています (図 5 を参照)。この実装はデータ バインドと問題なく併用でき、また、大規模なデータ セットでも効率的に実行できるように設計されています。

図 5 DataGridViewIncrementalSearch
Public Class DataGridViewIncrementalSearch
Inherits DataGridView
Private m_search As IncrementalSearch
Private WithEvents m_timer As New Timer
Public Property IncrementalSearch() As IncrementalSearch
Get
Return m_search
End Get
Set(ByVal value As IncrementalSearch)
m_search = value
m_timer.Start()
End Set
End Property
Public Sub New()
m_timer.Interval = CInt(TimeSpan.FromSeconds(0.2).TotalMilliseconds)
End Sub
Protected Overrides Sub Dispose(ByVal disposing As Boolean)
If disposing Then
m_timer.Dispose()
End If
MyBase.Dispose(disposing)
End Sub
Private Sub OnTick(ByVal sender As Object, ByVal e As EventArgs) _
Handles m_timer.Tick
m_timer.Stop()
If m_search Is Nothing OrElse m_search.SearchStatus = _
SearchStatus.Completed Then
Return
End If
Dim result = m_search.Search()
DataSource = Nothing
DataSource = result.AllValues
m_timer.Start()
End Sub
End Class
型が同じで、名前が IncrementalSearch のプロパティが 1 つ追加されています。この値がセットされている場合は常に、コントロールは Search メソッドを呼び出し、表示されている一連の値を継続的に更新します。これを実現するには、コントロールは、データ ソースにデータがなくなるまで一定の間隔で Search メソッドを呼び出す必要があります。
Windows® フォームのタイマは、このシナリオに最適です。Windows フォームのタイマは、UI スレッド上で特定の間隔でメソッドを呼び出すように設定でき、また、有効と無効を切り替えることができます。IncrementalSearch プロパティが更新されると、タイマが有効化されます。ハンドラ関数は Search を呼び出します。検索が完了するとタイマは無効化されます。
Windows フォームのタイマには、1 つ問題があります。ハンドラが Tick イベントを処理するために必要な時間とは無関係に、間隔が計算されるということです。つまり、ハンドラの実行時間がこの間隔よりも長い場合、別の Tick イベントがすぐに発生するように待機状態に置かれます。最悪のシナリオでは、Tick イベントが次々に増えていき、UI が応答しなくなります。この問題は、Search を呼び出している間タイマを無効化し、まだ処理するデータが残っている場合は再度有効化すると、回避できます (図 6 を参照)。この DataGridView には、明示的に列を選択する機能はありません。この例では、筆者はデータ バインドに列を選択させています。

図 6 検索タイマを有効または無効にする
Private Sub OnTick(ByVal sender As Object, ByVal e As EventArgs) _
Handles m_timer.Tick
m_timer.Stop()
If m_search Is Nothing _
OrElse m_search.SearchStatus = SearchStatus.Completed Then
' Search is completed don't restart the timer
Return
End If
' Get the next update from the incremental search
Dim result = m_search.Search()
DataSource = Nothing
DataSource = result.AllValues
' Restart the timer to perform another search
m_timer.Start()
End Sub
このコードには、1 か所巧妙な部分があります。データ ソースの更新部分です。基になっている IncrementalSearch オブジェクトは、クエリからの戻り値を格納するために List(Of Object) を生成します。すべての Result オブジェクトには、コピーではなく、このリストへの参照が含まれています。DataSource プロパティの更新時に、DataGridview は、それが同一の Object であると見なして表示結果を更新しません。そこで、間の行で参照に Nothing を代入することでデータを強制的に再読み込みさせています。
よくできた使いやすい解決策ですが、すべてのシナリオで使用できるわけではありません。ここでの根本的な問題は、ユーザーの待ち時間です。これはシングル スレッドの解決策であるため、一度 MoveNext を呼び出したら実行を中断する方法はありません。このため、ユーザーの文字入力時の待ち時間の最大値は、現在、IncrementalSearch クラスの DelayTime 値と、検索時に要素が 1 つ見つかるまでの時間の最大値を合わせた長さです。
並べ替えと遅延評価
ほとんどの LINQ クエリは、遅延評価で処理されます。これは、列挙子で、MoveNext が呼ばれるごとに、1 個の要素だけが処理されるということです。検索時に 1 つの要素を見つけるために必要な時間は、次の要素を見つけるために必要な時間と同じです。これにより、結果を使いやすいように複数のデータ ブロックに効率的に分割できます。
Dim e = From method In doc...<Member> _
Where method.@Name.Contains(name) _
Where String.Compare(method.@Kind, "Method") = 0 _
Select MethodName = method.@Name
' Returns when the first matching <Member> is found
Dim first = e.First()
このモデルは、基になる LINQ クエリが、単一の MoveNext 呼び出しの間に相当な部分または全体を処理する場合、破綻します。この形式のクエリは、先行評価と呼ばれています。先行評価の例の 1 つは、並べ替えられた状態で結果を返す Order By 演算子です。並べ替えを行うため、クエリはすべての部分の実行が完了するまで、最初の値を返すことができません。そうしなければ、最後に返された要素が並べ替えたときに最初の要素になる可能性があるため、クエリはどの要素を最初に返すかを判断できません。先行評価を使用するクエリと共にインクリメンタル検索のパターンを実行すると、最初の問題に逆戻りします。
Dim e = From method In doc...<Member> _
Where method.@Name.Contains(name) _
Where String.Compare(method.@Kind, "Method") = 0 _
Order By method.@Name _
Select MethodName = method.@Name
' The following line won't finish until the entire query is finished
' processing
Dim first = e.First()
繰り返しますが、この方法の利点は返された行の一部だけを扱えるという点だけにあります。このコードは、データの一部だけをユーザーに表示するため、常に並べ替えておく必要があるデータはその部分だけです。基になる LINQ クエリは並べ替えられていないデータを返すことができ、コードはデータを受け取るごとに並べ替えることができます。
Search 呼び出しの終わりごとにデータを並ベ替えるように IncrementalSearch クラスを変更することは容易です。データの検索に利用可能なアプローチとしては、次の 2 つがあります。1 番目のアプローチは、組み込みの List(Of T).Sort メソッドを利用する方法です。これは、平均で O(N LogN) の複雑さを持ち、一般的にはほとんどのアプリケーションにおいて十分に高速であると言えます。
Dim search As New List(Of String)(SearchForMethodNames)
search.Sort(StringComparer.OrdinalIgnoreCase)
2 番目の方法は、呼び出しの開始時に並べ替えられているデータを利用します。既存のデータ リストの最後にデータを追加するのではなく、適切な挿入位置を検索し、新しく見つかったデータをそこに挿入することができます。リストを完全に並べ替えるのと比べた場合、適切なインデックスを検索する処理は相対的に高速な操作であるため、一見、これはより論理的な選択であるように思われます。ところが、このようにリスト内の要素の順序を維持できない理由が 2 つあります。
第一に、IncrementalSearch クラス自体は、並べ替えられたリストを維持しているにもかかわらず、呼び出し側が値の順序を変更するのを禁止する方法がありません。したがって、リストが並べ替えられていることを仮定できません。第二に、List(Of T) の途中に挿入を行うには余分なコストがかかります。実際には、List(Of T) は Array により実現されており、挿入される要素の右側にあるすべての要素は、1 つ右にシフトされます。大規模なデータ構造の場合このシフトに必要な時間は無視できなくなるため、最終的にこの並べ替え方法の効率は大幅に低下することになります。
コレクションの Sort メソッドを使用するには、値を比較するためのメソッドが必要です。フレームワークが、一般的なデータ型を並べ替えるために備えている既存の比較メソッドを使用できれば最適です。ただし、IncrementalSearch クラスは柔軟に型指定されているのに対し、ほとんどの比較メソッドはそのオブジェクトに対して厳密に型指定されています。柔軟に型指定されたオブジェクトのコレクションに保存される可能性があるため、たとえば String を返すクエリで String.Compare を使用できません。検索処理と既存のクラスの再利用を可能にするためには、柔軟に型指定された実装と、厳密に型指定された実装の両方を用意することで IncrementalSearch クラスの柔軟性を高める必要があります。
インクリメンタル検索の柔軟性を高める
現時点では、IncrementalSearch クラスは型指定のないコレクションを対象としているため、非常に柔軟性があります。ただし、型指定のないコレクションではすべてのデータがオブジェクト型であるため、検索結果の使いやすさは制約を受けます。LINQ クエリは、通常、匿名型のコレクションを返します。IntelliSense では、型を利用する方が処理がはるかに容易になります。つまり、結果に対してさらに処理ができるようにするには、IncrementalSearch を厳密に型指定されたクラスにする必要があります。
IncrementalSearch 自体をジェネリックにすることには、問題が 1 つあります。IncrementalSearch がジェネリックだとすると、IncremantalSearch をラップするコントロールもジェネリックにする必要があります。そうでなければ、特定の型に結び付けられた IncremantalSearch のインスタンスを作成する必要があるためです。Windows フォーム デザイナは、バインドされていないジェネリックなコントロールをサポートしていません。つまり、デザイナ サポートが利用できないということであり、この案は採用できません。コントロールは IncrementalSearch を特定の型とバインドすることもできますが、その場合、そのコントロールの再利用性はその特定の型の検索に制限されます。
解決策は、ハイブリッド アプローチになります。IncrementalSearch クラスは、非ジェネリックのままにしておいて、検索結果を IList などの非ジェネリック コレクション インターフェイスを通じて公開します。次に、Search メソッドが抽象メソッドになる抽象クラスに組み込みます。Result クラスも、同様に非ジェネリック コレクションだけを公開します。IncrementalSearch を非ジェネリックのままにしておき、また、抽象メソッドを用意することで IncrementalSearch クラスが Windows フォームのコントロール内で再利用できるようにすると同時に、厳密に型指定されたコレクションも使用し続けることができます。
IncrementalSearch(Of T) は、検索結果について厳密に型指定されており、また、IncrementalSearch から派生しています。IncrementalSearch(Of T) は、Search メソッドをオーバーライドして厳密に型指定されているコレクション クラスを提供します。リファクタリング後の IncrementalSearch の完全な定義は、図 7 を参照してください。

図 7 リファクタリング後の IncrementalSearch のコード
Public MustInherit Class IncrementalSearch
Protected m_status As SearchStatus = SearchStatus.InProgress
Protected m_delay As TimeSpan
Public MustOverride ReadOnly Property AllValues() As IList
Public ReadOnly Property SearchStatus() As SearchStatus
Get
Return m_status
End Get
End Property
Public Property Delay() As TimeSpan
Get
Return m_delay
End Get
Set(ByVal value As TimeSpan)
m_delay = value
End Set
End Property
Public MustOverride Function Search() As Result
Public Shared Function Create(Of T)(ByVal e As IEnumerable(Of T)) _
As IncrementalSearch(Of T)
Return New IncrementalSearch(Of T)(e)
End Function
End Class
Public NotInheritable Class IncrementalSearch(Of T)
Inherits IncrementalSearch
Private m_enumerator As IEnumerator(Of T)
Private m_allFound As New List(Of T)
Private m_comparer As IComparer(Of T)
Public Overrides ReadOnly Property AllValues() _
As System.Collections.IList
Get
Return m_allFound
End Get
End Property
Public Property Comparer() As IComparer(Of T)
Get
Return m_comparer
End Get
Set(ByVal value As IComparer(Of T))
m_comparer = value
End Set
End Property
Public Sub New(ByVal e As IEnumerable(Of T))
m_delay = TimeSpan.FromSeconds(0.1)
m_enumerator = e.GetEnumerator()
End Sub
Public Overrides Function Search() As Result
If m_status = SearchStatus.Completed Then
Return New Result(m_allFound, New List(Of T), m_status)
End If
Dim found As New List(Of T)
Dim start = DateTime.Now
Do
If Not m_enumerator.MoveNext() Then
' IEnumerable(Of T) must be disposed
m_enumerator.Dispose()
m_enumerator = Nothing
m_status = SearchStatus.Completed
Exit Do
End If
found.Add(m_enumerator.Current)
Loop Until DateTime.Now - start > m_delay
m_allFound.AddRange(found)
If m_comparer IsNot Nothing Then
m_allFound.Sort(m_comparer)
End If
Return New Result(m_allFound, found, m_status)
End Function
End Class
Public NotInheritable Class IncrementalObjectSearch
Inherits IncrementalSearch
Private m_enumerator As IEnumerator
Private m_allFound As New ArrayList
Private m_comparer As IComparer
Public Overrides ReadOnly Property AllValues() As _
System.Collections.IList
Get
Return m_allFound
End Get
End Property
Public Property Comparer() As IComparer
Get
Return m_comparer
End Get
Set(ByVal value As IComparer)
m_comparer = value
End Set
End Property
Public Sub New(ByVal e As IEnumerable)
m_enumerator = e.GetEnumerator()
End Sub
Public Overrides Function Search() As Result
If m_status <> SearchStatus.InProgress Then
Return New Result(m_allFound, New List(Of Object), m_status)
End If
Dim found As New List(Of Object)
Dim start = DateTime.Now
Do
If Not m_enumerator.MoveNext() Then
m_enumerator = Nothing
m_status = SearchStatus.Completed
Exit Do
End If
found.Add(m_enumerator.Current)
Loop Until DateTime.Now - start > m_delay
m_allFound.AddRange(found)
If m_comparer IsNot Nothing Then
m_allFound.Sort(m_comparer)
End If
Return New Result(m_allFound, found, m_status)
End Function
End Class
IncrementalSearch(Of T) クラスには、IComparer(Of T) 型の Comparer という新しいプロパティが追加されています。このプロパティが存在する場合、Search が呼び出されるたびに結果が並べ替えられます。
Public NotInheritable Class IncrementalSearch(Of T)
Inherits IncrementalSearch
Private m_enumerator As IEnumerator(Of T)
Private m_allFound As New List(Of T)
Private m_comparer As IComparer(Of T)
これで、先行評価を導入せずにクエリを並べ替えるために、既存のメカニズムを再利用できるようになりました。
Private Function GetFullMethodNameSorted( _
ByVal doc As XDocument, ByVal name As String) _
As IncrementalSearch
Dim e = From method In doc...<Member> _
Where method.@Name.Contains(name) _
Where 0 = String.Compare(method.@Kind, "Method") _
Join type In doc...<Type> _
On type.@Id Equals method.@TypeId _
And type.@AssemblyId Equals method.@AssemblyId _
Select type.@Namespace & "." & type.@Name & "." & method.@Name
Dim search = IncrementalSearch.Create(e)
search.Comparer = StringComparer.Ordinal
Return search
End Function
クエリを直接記述するのであれば、多くの場合この方法で十分です。ところが、今回の処理は、匿名型を含んでいることが多い LINQ クエリの結果を格納するために設計されています。
コード内では、匿名型の型を参照できません。そのため、厳密に型指定されたジェネリック クラスを作成するには型の推定機能に依存する必要があります。これは、IncrementalSearch 基本クラスに、Create というファクトリ メソッドを追加することにより実現できます。ジェネリック パラメータが 1 つしかなく、また、引数がこのパラメータを満たしているため、コンパイラは引数を推定でき、明示的に記述する必要はありません。
Dim e = From method In doc...<Member> _
Where String.Compare(method.@Kind, "Method") = 0 _
Select MethodName = method.@Name
' What is the type name of the element?
Dim s1 As New IncrementalSearch(Of ???)(e)
' No need to write the type name
Dim s2 = IncrementalSearch.Create(e)
柔軟に型指定されたコレクションをサポートし続けるために、IncrementalObjectSearch という IncrementalSearch の新しい子を実装できます。これは、List(Of Object) の代わりに ArrayList に基づいているという点を除いて、現在の実装に類似しています。
Public NotInheritable Class IncrementalObjectSearch
Inherits IncrementalSearch
Private m_enumerator As IEnumerator
Private m_allFound As New ArrayList
Private m_comparer As IComparer
匿名型の並べ替え
クエリは、多くの場合に匿名型のコレクションを返します。コード内では、匿名型の型を記述できないため、IComparer(Of T) の実装を記述することは不可能です。
さいわい、ここでは Visual Basic で作業しています。クエリから返されたプログラム内部の値にどのようなメンバがあるかを調べることができます。遅延バインドを使用すると、これらの値に直接アクセスできます。図 8 に、オリジナルのクエリの並べ替えバージョンを作成する手順の例を示します。Order By ステートメントの代わりに Comparer を使用しているため、この処理は遅延評価となり UI のパフォーマンスが向上します。

図 8 カスタムの並べ替え
Private Function GetQueryMethodsOfNameSorted( _
ByVal doc As XDocument, ByVal name As String) As IncrementalSearch
Dim e = From method In doc...<Member> _
Where method.@Name.Contains(name) _
Where 0 = String.Compare(method.@Kind, "Method") _
Join type In doc...<Type> On type.@Id Equals method.@TypeId _
And type.@AssemblyId Equals method.@AssemblyId _
Select Type = type.@Name, Method = method.@Name
Dim x = New IncrementalObjectSearch(e)
x.Comparer = New MethodsOfNameComparer()
Return x
End Function
Private Class MethodsOfNameComparer
Implements IComparer
Public Function Compare(ByVal x As Object, _
ByVal y As Object) As Integer Implements _
System.Collections.IComparer.Compare
Dim comp = StrComp(x.Type, y.Type)
If comp <> 0 Then
Return comp
End If
Return StrComp(x.Method, y.Method)
End Function
End Class
この例は、実装や説明が楽しいパターンですが、本コラムではあまりスペースがありません。UI の効率をさらに高める方法は、まだ他にもたくさんあります。読者がご自身で試してみたいと思うようなアイデアをいくつか挙げておきます。
- クエリの効率を高めるために、ソース データを再構成する。
- LINQ を使用して効率がよくなるように再構成されたデータ セットをメモリ上に作成し、以降のクエリをこの再構成されたデータに対して実行する。
- クエリの負荷を別のスレッドにオフロードする。
- ユーザーに、検索処理の進捗状況を示す UI を提供する。
- DataGridView を仮想モードに設定する。
- ユーザーが新しくテキストを入力するたびにドキュメント全体を検索するのではなく、前回の結果に対してのみ検索する。
- 並列 LINQ クエリを導入する。
筆者のブログでこれらについて詳しく説明できればと考えています。また、Visual Basic チーム ブログ (
blogs.msdn.com/vbteam) および MSDN
® Visual Basic デベロッパー センター (
msdn.com/vbasic) もぜひご参照ください。