.NET TIPS

ハッシュテーブル(Dictionaryクラス)を値でソートするには?[2.0のみ、C#、VB]

デジタルアドバンテージ 遠藤 孝信
2006/04/28

 「TIPS:ハッシュテーブル(連想配列)を使うには?(Dictionaryクラス編)」では、Dictionaryクラス(System.Collections.Generic名前空間)の利用方法について解説した。そこでも触れているように、ハッシュテーブルに格納した要素の順序は保持されない。

 しかし、ハッシュテーブルの要素のソート(並べ替え)を行ってから、要素を順に処理したい場合はよくある。例えば、テキスト内の単語とその出現頻度をハッシュテーブルによりカウントしてから、出現頻度の多い順に処理したいような場合だ。

 前掲のTIPSの最後にあるように、SortedDictionaryクラス(System.Collections.Generic名前空間)を使えば、コレクションの要素をキー(Key)の値でソートすることはできる。しかし、各キーに対する値(Value)でのソート方法は標準では用意されておらず、独自に実装する必要がある。

 本稿では、Dictionary<string, int>クラス(VBの場合にはDictionary(Of String, Integer)クラス)を、要素の値(整数値)によりソートする場合の実装について紹介する。

Listクラスを利用したソート

 ここで紹介する方法は、すべての要素の追加が完了したハッシュテーブルの全要素を最初にListクラス(System.Collections.Generic名前空間)にコピーしてから、各要素をその値でソートする方法だ。なおハッシュテーブルでは、各要素はキーと値のペアからなるKeyValuePair構造体(System.Collections.Generic名前空間)のオブジェクトで表される。

 まずハッシュテーブルをListクラスのオブジェクトにコピーするには、次のようにListクラスのコンストラクタにハッシュテーブル(Dictionaryオブジェクト)を指定するだけでよい。これによりKeyValuePairオブジェクトを要素に持つリストが作成される。

List<KeyValuePair<string, int>> list = new List<KeyValuePair<string, int>>(dict);
Dim list As New List(Of KeyValuePair(Of String, Integer))(dict)
DictionaryオブジェクトからListオブジェクトを作成(上:C#、下:VB)
変数dictはDictionary(string, int)クラス(VBの場合にはDictionary(Of String, Integer)クラス)のオブジェクト。

 次に、ListクラスのSortメソッドを使用してリストのソートを行う。本稿では、要素の比較を行うメソッドを示すデリゲート(System名前空間のComparisonデリゲート)をパラメータに持つSortメソッドを利用している。

// Valueの大きい順にソート
list.Sort(hikaku);

……省略……

int hikaku(
  KeyValuePair<string, int> kvp1,
  KeyValuePair<string, int> kvp2)
{
  return kvp2.Value - kvp1.Value;
}
' Valueの大きい順にソート
list.Sort(AddressOf hikaku)

……省略……

Function hikaku( _
  ByVal kvp1 As KeyValuePair(Of String, Integer), _
  ByVal kvp2 As KeyValuePair(Of String, Integer)) As Integer

  Return kvp2.Value - kvp1.Value
End Function
ListクラスのSortメソッドを使用してリストをソート(上:C#、下:VB)

 比較を行うメソッド(上記コードではhikakuメソッド)では、メソッドのパラメータで与えられる2つのKeyValuePairオブジェクトについて、要素の値を示すValueプロパティにより値の比較を行い、その結果を0より大きい値、0、0より小さい値のいずれかで返せばよい。

 以下に、これらを実装したサンプル・プログラムを示す。

ハッシュテーブルを値でソートするサンプル・プログラム

 このサンプル・プログラムでは、@ITのトップページのHTMLを取得し、その内容を単語に分割してから、単語ごとの出現頻度をハッシュテーブルによりカウントする。そして、値によるソートを実装したsortByValueメソッドによりListオブジェクトを得て、その各要素を順に画面に出力する。

// sortbyvalue.cs

using System;
using System.Net;
using System.Text.RegularExpressions;
using System.Collections.Generic;

class DictionarySortByValue {
  static void makeDict(Dictionary<string, int> dict) {
    string html;

    // HTMLの取得
    using (WebClient wc = new WebClient()) {
      html = wc.DownloadString("http://www.atmarkit.co.jp/");
    }

    // 単語に分割して、各単語の出現頻度をカウント
    foreach (string s in Regex.Split(html, "\\W")) {
      string word = s.Trim();
      if (word != "") {
        if (dict.ContainsKey(word)) {
          dict[word]++;
        } else {
          dict[word] = 1;
        }
      }
    }
  }

  static void Main() {
    Dictionary<string, int> dict = new Dictionary<string, int>();
    makeDict(dict);

    List<KeyValuePair<string, int>> sorted = sortByValue(dict);
    // sorted.Reverse(); // 逆順にする場合

    foreach (KeyValuePair<string, int> kvp in sorted) {
      Console.WriteLine(kvp.Key + ":" + kvp.Value);
    }
    // 出力例:
    // a:542
    // td:394
    // 0:328
    // width:289
    // tr:284
    // ……
  }

  static List<KeyValuePair<string, int>>
    sortByValue(Dictionary<string, int> dict)
  {
    List<KeyValuePair<string, int>> list
      = new List<KeyValuePair<string, int>>(dict);

    // Valueの大きい順にソート
    list.Sort(
      delegate(KeyValuePair<string, int> kvp1, KeyValuePair<string, int> kvp2) {
        return kvp2.Value - kvp1.Value;
      });
    return list;
  }
}

// コンパイル方法:csc sortbyvalue.cs
ハッシュテーブルを値でソートするC#のサンプル・プログラム(sortbyvalue.cs)

' sortbyvalue.vb

Imports System
Imports System.Net
Imports System.Text.RegularExpressions
Imports System.Collections.Generic

Class DictionarySortByValue
  Shared Sub makeDict(ByVal dict As Dictionary(Of String, Integer))
    Dim html As String

    ' HTMLの取得
    Using wc As New WebClient()
      html = wc.DownloadString("http://www.atmarkit.co.jp/")
    End Using

    ' 単語に分割して、各単語の出現頻度をカウント
    For Each s As String In Regex.Split(html, "\W")
      Dim word As String = s.Trim()
      If Not word = "" Then
        If dict.ContainsKey(word) Then
          dict(word) += 1
        Else
          dict(word) = 1
        End If
      End If
    Next
  End Sub

  Shared Sub Main()
    Dim dict As New Dictionary(Of String, Integer)
    makeDict(dict)

    Dim sorted As List(Of KeyValuePair(Of String, Integer)) = sortByValue(dict)
    ' sorted.Reverse() ' 逆順にする場合

    For Each kvp As KeyValuePair(Of String, Integer) In sorted
      Console.WriteLine(kvp.Key & ":" & kvp.Value)
    Next
    ' 出力例:
    ' a:542
    ' td:394
    ' 0:328
    ' width:289
    ' tr:284
    ' ……
  End Sub

  Shared Function hikaku( _
    ByVal kvp1 As KeyValuePair(Of String, Integer), _
    ByVal kvp2 As KeyValuePair(Of String, Integer)) As Integer

    ' Valueの大きい順にソート
    Return kvp2.Value - kvp1.Value
  End Function

  Shared Function sortByValue( _
    ByVal dict As Dictionary(Of String, Integer)) _
      As List(Of KeyValuePair(Of String, Integer))

    Dim list As New List(Of KeyValuePair(Of String, Integer))(dict)

    list.Sort(AddressOf hikaku)
    Return list
  End Function
End Class

' コンパイル方法:vbc sortbyvalue.vb
ハッシュテーブルを値でソートするVBのサンプル・プログラム(sortbyvalue.vb)

 なお、C#版ではSortメソッドのパラメータ部分に匿名メソッドを使用している。

汎用的なsortByValueメソッド

 上記サンプル・プログラムのsortByValueメソッドでは、キーが文字列、値が整数値の要素のみしか扱えないが、ジェネリック・メソッドの仕組みを用いれば、これをもう少し汎用的に記述できる。以下にその記述例を示しておく。

static List<KeyValuePair<TKey, TValue>>
  sortByValue<TKey, TValue>(IDictionary<TKey, TValue> dict)
    where TValue: IComparable<TValue>
{
  List<KeyValuePair<TKey, TValue>> list
    = new List<KeyValuePair<TKey, TValue>>(dict);

  // Valueの大きい順にソート
  list.Sort(
    delegate(KeyValuePair<TKey, TValue> kvp1, KeyValuePair<TKey, TValue> kvp2) {
      return kvp2.Value.CompareTo(kvp1.Value);
    });
  return list;
}
Shared Function hikaku(Of TKey, TValue As IComparable(Of TValue))( _
  ByVal kvp1 As KeyValuePair(Of TKey, TValue), _
  ByVal kvp2 As KeyValuePair(Of TKey, TValue)) As Integer

  Return kvp2.Value.CompareTo(kvp1.Value)
End Function

Shared Function sortByValue(Of TKey, TValue As IComparable(Of TValue))( _
  ByVal dict As Dictionary(Of TKey, TValue)) _
  As List(Of KeyValuePair(Of TKey, TValue))

  Dim list As New List(Of KeyValuePair(Of TKey, TValue))(dict)

  ' Valueの大きい順にソート
  list.Sort(AddressOf hikaku)
  Return list
End Function
ジェネリック・メソッドにより記述したsortByValueメソッド(上:C#、下:VB)
C#版ではSortメソッドのパラメータ部分に匿名メソッドを使用している。

 このsortByValueメソッドは、要素の値(Value)の型がIComparableインターフェイス(System名前空間)を実装している場合に利用できる。文字列や基本的な数値型はこのインターフェイスを実装している。End of Article

利用可能バージョン:.NET Framework 2.0のみ
カテゴリ:クラス・ライブラリ 処理対象:コレクション
使用ライブラリ:Dictionaryクラス(System.Collections.Generic名前空間)
使用ライブラリ:KeyValuePair構造体(System.Collections.Generic名前空間)
使用ライブラリ:Listクラス(System.Collections.Generic名前空間)
使用ライブラリ:IComparableインターフェイス(System名前空間)
関連TIPS:ハッシュテーブル(連想配列)を使うには?(Dictionaryクラス編)

この記事と関連性の高い別の.NET TIPS
ハッシュテーブル(連想配列)を使うには?(Dictionaryクラス編)
ハッシュテーブル(連想配列)を使うには?
配列を独自の順序でソート(並べ替え)するには?
自作クラスによる配列をソート(並べ替え)するには?
要素を重複なく管理するには?(HashSetクラス編)
このリストは、(株)デジタルアドバンテージが開発した
自動関連記事探索システム Jigsaw(ジグソー) により自動抽出したものです。
generated by

「.NET TIPS」


Insider.NET フォーラム 新着記事
  • 第2回 簡潔なコーディングのために (2017/7/26)
     ラムダ式で記述できるメンバの増加、throw式、out変数、タプルなど、C# 7には以前よりもコードを簡潔に記述できるような機能が導入されている
  • 第1回 Visual Studio Codeデバッグの基礎知識 (2017/7/21)
     Node.jsプログラムをデバッグしながら、Visual Studio Codeに統合されているデバッグ機能の基本の「キ」をマスターしよう
  • 第1回 明瞭なコーディングのために (2017/7/19)
     C# 7で追加された新機能の中から、「数値リテラル構文の改善」と「ローカル関数」を紹介する。これらは分かりやすいコードを記述するのに使える
  • Presentation Translator (2017/7/18)
     Presentation TranslatorはPowerPoint用のアドイン。プレゼンテーション時の字幕の付加や、多言語での質疑応答、スライドの翻訳を行える
@ITメールマガジン 新着情報やスタッフのコラムがメールで届きます(無料)

注目のテーマ

Insider.NET 記事ランキング

本日 月間