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

MSDN マガジン > Home > 発行物 > 2008 > August > 基本的な本能 : LINQ クエリのパフォーマンスを向上させる

基本的な本能

LINQ クエリのパフォーマンスを向上させる

Jared Parsons

コードのダウンロード : BasicInstincts2008_08.exe (2,291 KB)
オンラインでのコードの参照

問題点
デモアプリケーションを構築する
基本的なユーザーインターフェイス
パフォーマンス向上のための方法
インクリメンタル検索
並べ替えと遅延評価
インクリメンタル検索の柔軟性を高める
匿名型の並べ替え

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) もぜひご参照ください。

ご意見やご質問は instinct@microsoft.com まで英語でお送りください。

Jared Parsons は、Visual Basic のデバッガおよび IDE 担当のマイクロソフトのソフトウェアエンジニアです。彼の情熱は、コード、コーディング、プログラミングに関係するものであればほとんど何にでも注がれています。blogs.msdn.com/ jaredpar でほぼ定期的にブログを更新しています。