【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。

  • 2013.02.21 Thursday
  • 21:51

IReadOnlyCollection<T>が登場した時も同じ疑問が芽生えたのですが、 IList<T>がIReadOnlyList<T>を継承してない、何でだろうって思ったことあります。

ということで「IList<T>がIReadOnlyList<T>を継承してない理由」を考えてみたいと思います。

public interface IList<T> : ICollection<T>, IEnumerable<T>, IEnumerable
{
    int IndexOf(T item);
    void Insert(int index, T item);
    void RemoveAt(int index);
    T this[int index] { get; set; }
}

public interface IReadOnlyList<out T> : IReadOnlyCollection<T>, IEnumerable<T>, IEnumerable
{
    T this[int index] { get; }
}

.NET Framework 4.5では上記のように定義されているので、

public interface IList<T> : IReadOnlyList<T>, ICollection<T>, IEnumerable<T>, IEnumerable
{
  int IndexOf(T item);
  void Insert(int index, T item);
  void RemoveAt(int index);
  T this[int index] { get; set; }
}

継承関係にある二つのインターフェイスに同名のプロパティが定義されていて、とても気持ち悪い状態になり、コンパイル時に警告が出るようにはなります。ただし、このインターフェイスのみを考えるとコンパイルは通ります。問題なさそうです。ただし、実際にはIList<T>がIReadOnlyList<T>から派生すると悲劇が生まれるます。

ちょいと簡単にするために一つインターフェイスを定義してみます。

    public interface IDemo
    {
        int Get();
        void Set(int value);
    }

これに対して実装クラスをあったとします。

    public class DemoImpl : IDemo
    {
        private int _value;

        int IDemo.Get()
        {
            return _value;
        }

        void IDemo.Set(int value)
        {
            _value = value;
        }
    }

この時点ではコンパイルは通っています。これに対して、IDemoにIReadOnlyDemoを追加してみます。

    public interface IDemo : IReadOnlyDemo
    {
        int Get();
        void Set(int value);
    }

    public interface IReadOnlyDemo
    {
        int Get();
    }

なんと!コンパイルが通らなくなります(あたりまえですが)

これを.NET Frameworkに置き換えて話すと、.NET Framework 4.0までのIList<T>とList<T>がありました。.NET Framework 4.5(仮)でIList<T>をIReadOnlyList<T>から派生させました。List<T>に問題が発生するのでList<T>に修正を加えます。そこでは、.NET Frameworkのクラスライブリーの責任の範囲内なので、実装できます。しかし、IList<T>から独自に実装していたクラスがあった場合、.NET Framework 4.5にターゲットを変更した場合、とたんにコンパイルエラーになってしまいます。これは、いただけないです。拡張したつもりが、実際にはアセンブリ間では変更になってしまいます。

だったら、同時期にIList<T>とIReadOnlyList<T>が提供されていたら問題はなかったのか
?という疑問がわいてきます。が!ちょっと私わかりません。もう少し考えてから続きは書きたいと思います。

【.NET Framework 4.5】ArraySegmentの変更点

  • 2013.02.14 Thursday
  • 20:46
JUGEMテーマ:コンピュータ


.NET Framework 4.5をターゲットとして開発していると、「あれ?」って思うことが多々あります。細かいところで改善が入っていることに気づかされることがあります。

【.NET Framework 4.5】IReadOnlyListとIReadOnlyDictionary

では、IReadOnlyList<T>とIReadOnlyDictionary<TKey, TValue>が追加されたことを、今更ながらに紹介してみましたが、今回はArraySegment<T>クラス。

ArraySegment<T>クラスは、前から存在していたクラスですが、使いどころがサッパリわからないクラスでした。配列の特定の位置から特定の位置までをセグメントとして配列をラップするクラスだったのですが、血迷ったことにIEnumerableを継承していないという状態でした。なので使うときは

var arrary = new[] {0, 1, 2, 3, 4, 5, 6, 7};
var arraryMid = new ArraySegment<int>(arrary, 2, 4);
for (int index = arraryMid.Offset; index <= arraryMid.Offset + arraryMid.Count - 1; index++)
{
    Console.WriteLine(arraryMid.Array[index]);
}


かえってめんどくさい事うけあいなクラスだったのですが、.NET Framework4.5から変更があり

var arrary = new[] { 0, 1, 2, 3, 4, 5, 6, 7 };
var arraryMid = new ArraySegment<int>(arrary, 2, 4);
foreach (int i in arraryMid)
{
    Console.WriteLine(i);
}

みたいな使い方ができるようになっています。

.NET Framework 4.5より前は、インターフェイスを何も継承していないクラスだったのですが、.NET Framework 4.5では

IList<T>, ICollection<T>, IReadOnlyList<T>, IReadOnlyCollection<T>, IEnumerable<T>, IEnumerable

と、色々継承していています。

おかげで

            var array = new[] {0, 1, 2, 3, 4, 5, 6, 7, 8};
            var arrayMidle = new ArraySegment<int>(array, 2, 4);
            Console.WriteLine(string.Join(" ", arrayMidle));

            IList<int> list = arrayMidle;
            list[2] = 0;
            Console.WriteLine(string.Join(" ", array));

のようなコードを書いて実行してみると

2 3 4 5
0 1 2 3 0 5 6 7 8

ラップクラスであるArraySegmentを通して、包含されているであろう元の配列の値が書き換わった事が確認できます。これって使いどころ結構あるんじゃないかって思うんですよね。っていうか、それまでがやる気なさすぎな残念なクラスだったと言うべきか・・・。

です。おわり。


-----------------
(追記)
http://msdn.microsoft.com/ja-jp/magazine/jj133817.aspx
思いっきり紹介されてました。
情弱なのです。

【.NET Framework 4.5】IReadOnlyListとIReadOnlyDictionary

  • 2013.02.07 Thursday
  • 21:28

.NET Framework 4.5からIReadOnlyList<out T>とIReadOnlyDictionary<TKey, TValue>が追加されたようですね。

IReadOnlyList<out T>がインデックスをサポートする読み取り専用のコレクション。
IReadOnlyDictionary<TKey, TValue>がキーと値のペアの読み取り専用ディクショナリ−。

    class A
    {
        private readonly List<string> _list = new List<string>();

        public void HogeAction()
        {
            // 内部では_listを可変長で要素の入れ替えが可能なListとして扱うロジックが書ける。
        }

        // 利用する側はインデックスがサポートされた読み取り専用のコレクションとして扱う事ができる。
        // Aクラスの内部状態に不用意に干渉することを避けられる。
        public IReadOnlyList<string> Source { get { return _list; } } 
    }

IList<T>は、読み取り専用も可変長もプロパティで利用側が判断する必要があり、なかなか使いにくく、隠蔽化されたオブジェクトからメソッドやプロパティでIList<T>が返された場合は、なるべく触らぬ神にたたり無しと入った感じで、暗黙的にIReadOnlyList的な使い方をしていました。もしくは、新しくコレクションを作成していました。そういった気苦労をしなくて良くなったという訳です。

またクラス提供者としては、メソッドやプロパティでIReadOnlyListを公開し、その内部ではList<T>として扱う事ができ、可変長で値の変更も自由にできる、外部ではそのインスタンスを読み取り専用としてそのまま公開できるというメリットが生まれます。インデックスをサポートしてないだけで.NET Famework 3.5(だったかな?)でIReadOnlyCollection<T>が追加されていたので、インデックスが使えるようになったというところが良くなった点ですが・・・・。

IReadOnlyCollection<T>と同様に、IReadOnlyList<T>のTのインスタンスの状態はTクラスの設計次第で可変になるのでこの当たりは注意が必要かと・・・・心配ならTクラスに対しても読み取り専用TReadOnlyを用意し、ジェネリクスの共変性を利用すれば完全に書き換え不可能なものを返す事もできそうですが・・・めんどくさいですね。

ジェネリクスの共変性を利用して、要素の状態も書き換え不可能なコードを作成してみましたが、これはとにかくめんどくさいですね。

        static void Main(string[] args)
        {
            var list1 = new List<T> {new T() {Value = 1}, new T() {Value = 2}};
            list1[1].Value = 10; // 書き換え可能

            IReadOnlyList<T> list2 = new List<T> { new T() { Value = 1 }, new T() { Value = 2 } };
            list2[1].Value = 10; // 書き換え可能

            IReadOnlyList<IReadOnlyT> list3 = new List<T> { new T() { Value = 1 }, new T() { Value = 2 } };
            // list3[1].Value = 10; // 書き換え不可能コンパイルエラー
        }

        interface IReadOnlyT
        {
            int Value { get; }
        }

        class T : IReadOnlyT
        {
            public int Value { get; set; }
        }


----------------------------------------
今日、さんざんこのインターフェイスを使って、コードを書いてみたのですが、すごくしっくりくるコードが書けました。

----------------------------------------
IReadOnlyDictionaryは、Linq to Objectsを使っているとToDicitonaryメソッドではキーがぶつかった時に例外が発生してしまうため、あまり使う機会がなくなりました。代わりにILookupをよく使うようになりました。HashSetの読み取り専用もあっても良いかもしれません。私が利用する場合はHashSetはほとんどコンストラクタ時に決定したコレクションから変動することがないので・・・。といってもローカル変数レベルの話なので、いらないのか・・・・保守の観点から同じクラスを複数人がいじるときのコミュニケーションとして必要?

【PetaPoco】PetaPoco + Oracleで使って見た。

  • 2013.02.06 Wednesday
  • 21:59
JUGEMテーマ:コンピュータ

Source and Project

PetaPocoでOracleにつないでみました。結論から言うと、PetaPoco(バージョン 4.0.3)で、Oracle.DataAccess.Clientを利用して、DBに接続しSQLを発行することは可能でした。ただし、Pocoを自動生成するのは、現状のT4ソースコードでは無理なようです。T4のソースコードを何カ所かいじるとPocoを生成することができるようになったのでメモを残す事にしました。

■NuGetからPetaPocoをインストール

■app.config(またはweb.config ない場合は作成する)を書き換える(赤字部分を追記)

<?xml version="1.0" encoding="utf-8" ?>
<configuration>
    <startup>
        <supportedRuntime version="v4.0" sku=".NETFramework,Version=v4.5" />
    </startup>
  <connectionStrings>
    <add
      name="Art55OracleDb"
      connectionString="Data Source=XE;User Id=art55;Password=art55"
      providerName="Oracle.DataAccess.Client"/>
  </connectionStrings>

</configuration>

■Database.ttを開き

前)
ConnectionStringName = "";

後)
ConnectionStringName = "Art55OracleDb";

■Database.ttを右クリックし「カスタムツール」を実行する。

上記の手順だけで、本来ならPocoはできるはずなのですが、作成されません。エラーを追っていくとおかしな部分があるので書き換えます。

■PetaPoco.Core.ttincludeのOracleSchemaReaderクラスを書き換える。(1139行

1308行
前)
const string TABLE_SQL=@"select TABLE_NAME from USER_TABLES";

後)
 const string TABLE_SQL=
 @"select a.TABLE_NAME, b.OWNER as TABLE_SCHEMA, 'Table' as TABLE_TYPE
from USER_TABLES a
inner join ALL_TABLES b on a.TABLE_NAME = b.TABLE_NAME
union
select c.VIEW_NAME as TABLE_NAME, d.OWNER as TABLE_SCHEMA, 'View' as TABLE_TYPE
from USER_VIEWS c
inner join ALL_VIEWS d on c.VIEW_NAME = d.VIEW_NAME";

※とりあえず、ここのSQLでPocoとして作成したいテーブルを取得するためのSQLを書けば良いようです。ポイントはテーブル名にTABLE_NAME、オーナーにTABLE_SCHEMA、Viewも含めたい場合はTABLE_TYPEというカラムにViewと記述すれば良いようです。

■Nullable対応が間違えているので修正
1215行
前)
col.IsNullable=rdr["IsNullable"].ToString()=="YES";

後)
col.IsNullable=rdr["IsNull
able"].ToString()=="Y";

ここまででPocoはとりあえず作れるはずです。ただし、Number型のNullableの対応がおかしいので、それも修正する必要があります。

■PetaPoco.cs内のあるGetConverterメソッドを書き換える。

2094行
前)
    else if (!dstType.IsAssignableFrom(srcType))
    {
        converter = delegate(object src) { return Convert.ChangeType(src, dstType, null); };
    }

後)
    else if (!dstType.IsAssignableFrom(srcType))
    {
        Type innerType = Nullable.GetUnderlyingType(dstType);
        if (innerType != null)
        {
            converter = src => Convert.ChangeType(src, innerType, CultureInfo.InvariantCulture);
        }
        else
        {
            converter = src => Convert.ChangeType(src, dstType, CultureInfo.InvariantCulture);
        }
    }

これで、とりあえず私が見つけた範囲のバグは修正されます。うん。全然だめっぽいという事だけわかりました・・・ただし、ソースコードとT4 Templateで配布されており一切のdllを含めていないため、自分のやりたい範囲で都合のいいように書き換えられるというのは、メリットだと思います。

最後に、とりあえず動かしてみたコード

using System;
using System.Globalization;
using System.Linq;
using Art55OracleDb;

namespace Art55.PetaPocoDemo20130206_001
{
    class Program
    {
        static void Main()
        {
            using (var db = new PetaPoco.Database("Art55OracleDb"))
            {
                db
                .Query<EMP>("select * from emp where job=@Job", new { Job = "SALESMAN" })
                .ToList()
                .ForEach(emp => Console.WriteLine(string.Join(", ", new []
                    {
                        emp.EMPNO.ToString(CultureInfo.InvariantCulture),
                        emp.ENAME,
                        emp.JOB
                    })));
            }
        }
    }
}

実行結果

7499, ALLEN, SALESMAN
7521, WARD, SALESMAN
7654, MARTIN, SALESMAN
7844, TURNER, SALESMAN

まとめ

PetaPoco + Oracleは怪しい・・・。私の力量では手に負えないと思いました(汗)


Source and Project

【雑記】Micro ormというライブラリーが・・・

  • 2013.02.05 Tuesday
  • 20:17
JUGEMテーマ:コンピュータ
 
Micro ormという名前のライブラリーがあるのだと、思っていたことを懺悔いたします。
ちょいとツールを作るのにPetaPocoを使ってヒャハーした。
T4 Templateの有効な使い方をはじめて知って感動した。

【C#】string.Joinメソッドの存在を知らなかった・・・。

  • 2013.01.29 Tuesday
  • 19:48
JUGEMテーマ:コンピュータ
 
string.Joinメソッドの存在を知らなかった・・・。

Splitはあるのに、逆バージョンは何でないんだろう・・・なんて思ってた・・・。あるじゃないですか!!

やっぱり一度はクラス内に存在するメソッドやプロパティやイベントは確認しないとね・・・・。

【C#】Dictionaryの実装・データ構造・アルゴリズムを考える。

  • 2013.01.16 Wednesday
  • 22:03
JUGEMテーマ:コンピュータ

【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。

上記の投稿で、System.Collections.Generic.Dictionary<T, TKey>の内部の状態を観察すしてみました。あるタイミングの内部状態のスナップショットのいくつかを観察し、変化を見ていくことで、法則性をみいだし、アルゴリズムを考察したかったというのが目的でした。

今回は逆に、アルゴリズムからせめて行きたいと思います。どういうアルゴリズムを組めば、ディクショナリとして成立するかという事を考えたいと思います。

ディクショナリの要件としていくつかあると思いますが、

1.キーと値を登録できる。
2.存在するキーを渡すと値を得ることができる。
3.キーによる検索は、高速であること。
4.登録されたキーの量によって検索速度が落ちないこと。

といった感じでしょうか。これを満たすロジックを考察していきたいと思います。まず、System.Object.GetHashCodeメソッドに着目してみます。GetHashCodeメソッドで得られるハッシュ コードは、等価テスト中にオブジェクトを識別するために使用される数値です。GetHashCodeメソッドの戻り値はint型の為、ハッシュ コードはint型で表せる範囲の値を返します。KeyのGetHashCodeメソッドを利用することでハッシュ コードを取得し、その値を配列のインデックスと対応させ、その要素の値にValueを設定することによってKeyとValueが配列で管理するというアルゴリズムが成立します。

絵で描くと

残念ながら、このアルゴリズムは、いくつかの問題があります。ひとつは、異なるキーでハッシュコードが重複するという問題です。文字列など無限の組み合わせが存在する場合は、GetHashCodeメソッドの戻り値のint型で表せる範囲を超えることは自明です。



では、問題を解決してみることにします。





用意した配列に直接値を入れず、Keyと値を保持したオブジェクトの参照を配列に格納してみることにします。Keyと値を保持したオブジェクトに更に参照をつなげて線形リストにします。これでキーがぶつかった場合は、リストが連結されていき、検索する際は、ハッシュコードとまず一致する事で線形リストのヘッダーにたどり着き、Keyの等価性を見ることで、重複するハッシュコードでも検索が可能になります。

しかし、まだ、問題があります。図中では「ハッシュテーブル」と名付けている配列の要素数が問題となります。仮にGetHashCodeメソッドが返す範囲をカバーする配列を作ろうとしても作れません。まずはsz配列を利用したいため、負の値は問題となります。System.Int32.MinValueが0に対応するように計算させると、今度は最大値はintの範囲を超える値にもなります。なので負の数字は扱えません。さらに、System.Int32.MaxValueの要素数を持つ配列のインスタンスは生成できません。

var arrary = new int[System.Int32.MaxValue];

上記のコードはコンパイルは通りますが、実行すると例外が発生します。メモリが確保できないからです。リソース上の問題なので回避できません。

そこで、この問題を解決するために、GetHashCodeメソッドをから得たハッシュコードを更に圧縮する必要があります。そして、圧縮した範囲をカバーできる配列を用意するというアルゴリズムにします。前回の考察で「要素数は素数で、要素数を超える場合は、リサイズされる。要素数(素数)を2倍した値から順方向に存在する素数のメンバーのうち、最初の見つかる素数を次の要素数にする」という動きをいたと思いますが、とりあえず、要素数が7の場合で考えてみたいと思います。



上記の図は、ハッシュテーブルの要素が7の場合です。本来ならキーは4つ以上登録ずみですが、ごちゃごちゃするので省略しています。まず、AddしたタイミングでKeyからGetHashCodeメソッドを呼び出し、ハッシュコードを得ます。その値を要素数で割り余りを得ることでハッシュコードを0から6の範囲で圧縮することができます。その値がハッシュテーブルのindexに対応していることがわかります。参照をたぐる事で、検索時にキーから値を連想することが可能です。今回は、Keyで比較するよりも圧縮前のハッシュコードで比較した方が高速であるため、ハッシュテーブルの参照先のオブジェクトにハッシュコードをキャッシュさせました。

これで、ディクショナリの概念的なアルゴリズムは説明できていると思います。ただ、System.Collections.Generic.Dictionary<T, TKey>の内部状態の観察から、上記の説明で「参照」と書いた部分は、実際には「参照」ではなく、配列のインデックスを利用しているという事が分かっているため、そこを少しだけ書き換えてみることにします。



絵は大幅に変わりましたが、線形リストの実装方法を配列に切り替えただけです。


キー1から値を検索する際は、キー1のハッシュコードを圧縮し、ハッシュテーブルのインデックスに対応させ、その値からエントリーの配列のインデックスを見つけ、エントリー内の配列からキー1と一致する要素を見つけ、最終的に「メロン」という値を見つけ出すことができる。という事がわかります。

と、まあこんな感じでアルゴリズムを考える上での「トンチ絵」が書けました。・・・いつの間にか絵を描くことが目的になってしまいましたが、私の頭はすっかりすっきりになったので、今回はこれで終了。

【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。

  • 2013.01.15 Tuesday
  • 20:10
JUGEMテーマ:コンピュータ

Dictionary<T, TKey>の実装が、前々から気になっていたので、調べてみました。今回は、リフレクションを利用して、公開されていないフィールドの状態を観察することで、Dictionaryの内部で扱われているデータ構造やアルゴリズムを想像してみました。非公開な部分なので、バージョンによって差異がある可能性もあり、また、そもそも想像なので、不正確なことこの上ないことは、あらかじめご了承ください。
Dictionary<T, TKey>を観察するとpublicでないフィールドに
private int[] buckets;
private Entry<TKey, TValue>[] entries;
というのがあります。他にも沢山ありますが、アルゴリズムに関連しそうなネーミングなので、この二つを観察することにしてます。ちなみにEntry<T, TValue>構造体は以下の定義となっているようです。
private struct Entry
{
    public int hashCode;
    public int next;
    public TKey key;
    public TValue value;
}
この構造体のメンバーの名前から想像するに、hashCodeはハッシュコード、nextは次を示す何かのインデックス?、keyはおそらくDictinaryのKey、valueはおそらくDictionaryのValueという具合に予測できます。
それでは、bucketsとentriesをリフレクションを使って状態の変化を見ていきたいと思います。
書いたコードは以下の通り、

using System;
using System.Collections.Generic;
using System.Reflection;
namespace Art55.HackDecitionary20120115_001
{
    class Program
    {
        static void Main()
        {
            var dictionary = new Dictionary<int, string>();
            dictionary.Add(2, "A");
            Console.WriteLine("Add Key 2");
            ShowDictionaryState(dictionary);
            dictionary.Add(0, "B");
            Console.WriteLine("Add Key 0");
            ShowDictionaryState(dictionary);
            dictionary.Add(1, "C");
            Console.WriteLine("Add Key 1");
            ShowDictionaryState(dictionary);
        }
        private static void ShowDictionaryState(Dictionary<int, string> dictionary)
        {
            var bucketsValue = GetFieldValue<int[]>(dictionary, "buckets");
            for (int i = 0; i < bucketsValue.Length; i++)
            {
                Console.WriteLine("buckets[{0}]:{1}", i, bucketsValue[i]);
            }
            Array entriesValue = GetFieldValue<Array>(dictionary, "entries");
            for (int i = 0; i < entriesValue.Length; i++)
            {
                object entry = entriesValue.GetValue(i);
                var hashCode = GetFieldValue<int>(entry, "hashCode");
                var next = GetFieldValue<int>(entry, "next");
                var key = GetFieldValue<int>(entry, "key");
                var value = GetFieldValue<string>(entry, "value");
                Console.WriteLine("Entry[{0}]:hashCode {1,5},next {2,2},key {3,2},value {4}", i, hashCode, next, key, value);
            }
        }
        private static T GetFieldValue<T>(object instance, string fieldName)
        {
            var field = instance.GetType().GetField(fieldName, BindingFlags.Instance | BindingFlags.NonPublic | BindingFlags.Public);
            return (T)field.GetValue(instance);
        }
    }
}

実行すると

Add Key 2
buckets[0]:-1
buckets[1]:-1
buckets[2]:0
Entry[0]:hashCode     2,next -1,key  2,value A
Entry[1]:hashCode     0,next  0,key  0,value
Entry[2]:hashCode     0,next  0,key  0,value
Add Key 0
buckets[0]:1
buckets[1]:-1
buckets[2]:0
Entry[0]:hashCode     2,next -1,key  2,value A
Entry[1]:hashCode     0,next -1,key  0,value B
Entry[2]:hashCode     0,next  0,key  0,value
Add Key 1
buckets[0]:1
buckets[1]:2
buckets[2]:0
Entry[0]:hashCode     2,next -1,key  2,value A
Entry[1]:hashCode     0,next -1,key  0,value B
Entry[2]:hashCode     1,next -1,key  1,value C

実行結果を観察すると、最初にDcitionaryにKeyが2、Valueが"A"を設定したタイミングでbucketsには3つの要素があり、2番目の要素に0で後は-1になっています。後の結果を見る限り-1がなし、-1以外の場合は、Entryのインデックスに対応しているように見えます。つまりKey 2は、bucketsの2番目の要素が示す値が0なので、Entryの0番目の要素の値に対応していると想像できます。
不思議な事に、Keyを一つ加えた状態で、bucketsやEntryが3つあります。おそらくはハッシュコードを配列の要素数で割った余りで配列のindexに対応付けているものだと思われますが、要素数の増減を観察すると面白い発見があるかもしれません。
ハッシュコードを要素数で割ったあまりという考えで結果を対応づけると、

2 mod 3 = 2
0 mod 3 = 0
1 mod 3 = 1

という結果になるため

2 mod 3 = 2 -> buckets[2]:0 -> Entry[0]:hashCode     2,next -1,key  2,value A
0 mod 3 = 0 -> buckets[0]:1 -> Entry[1]:hashCode     0,next -1,key  0,value B
1 mod 3 = 1 -> buckets[1]:2 -> Entry[2]:hashCode     1,next -1,key  1,value C

という具合に、ハッシュコードからbucketsのインデックスが対応付けられ、その値からどのEntryに対応付けいるかというところまでわかりました。
では、コードを変更して、ハッシュキーがぶつかった場合はどうなるのかを見てみたいと思います。

0 mod 3 = 0
3 mod 3 = 0

なので、この例で行くと

        static void Main()
        {
            var dictionary = new Dictionary<int, string>();
            dictionary.Add(2, "A");
            Console.WriteLine("Add Key 2");
            ShowDictionaryState(dictionary);
            dictionary.Add(0, "B");
            Console.WriteLine("Add Key 0");
            ShowDictionaryState(dictionary);
            dictionary.Add(3, "C");
            Console.WriteLine("Add Key 1");
            ShowDictionaryState(dictionary);
        }

実行結果は

Add Key 2
buckets[0]:-1
buckets[1]:-1
buckets[2]:0
Entry[0]:hashCode     2,next -1,key  2,value A
Entry[1]:hashCode     0,next  0,key  0,value
Entry[2]:hashCode     0,next  0,key  0,value
Add Key 0
buckets[0]:1
buckets[1]:-1
buckets[2]:0
Entry[0]:hashCode     2,next -1,key  2,value A
Entry[1]:hashCode     0,next -1,key  0,value B
Entry[2]:hashCode     0,next  0,key  0,value
Add Key 3
buckets[0]:2
buckets[1]:-1
buckets[2]:0
Entry[0]:hashCode     2,next -1,key  2,value A
Entry[1]:hashCode     0,next -1,key  0,value B
Entry[2]:hashCode     3,next  1,key  3,value C

0と3でハッシュコードの要素割りのあまりが同じ0になっています。これをたぐっていくと

0 mode 3 -> buckets[0]:2 -> Entry[2]:hashCode     3,next  1,key  3,value C
3 mode 3 -> buckets[0]:2 -> Entry[2]:hashCode     3,next  1,key  3,value C

0 mode 3の方のEntry.hashCodeは3ではないので、ここがおかしい訳ですが、nextという値をみると1となっています。ここも想像を膨らませてみると、nextとは、次に調べる要素のインデックスと解釈してみると

Entry[1]:hashCode     0,next -1,key  0,value B

というのが見つかり

0 mode 3
 -> buckets[0]:2
 -> Entry[2]:hashCode     3,next  1,key  3,value C
 -> Entry[1]:hashCode     0,next -1,key  0,value B

という連想ができていることがわかります。keyは異なって、hachCodeは同じになる例も試してみたいのですが、見つけるのが大変そうなので今回はやめておきます。
更にハッシュコードを要素数で割ったあまりの値がぶつかるようなキーを選んでみます。

        static void Main()
        {
            var dictionary = new Dictionary<int, string>();
            dictionary.Add(6, "A");
            dictionary.Add(0, "B");
            dictionary.Add(3, "C");
            ShowDictionaryState(dictionary);
        }

実行すると

Add Key 3
buckets[0]:2
buckets[1]:-1
buckets[2]:-1
Entry[0]:hashCode     6,next -1,key  6,value A
Entry[1]:hashCode     0,next  0,key  0,value B
Entry[2]:hashCode     3,next  1,key  3,value C

bucketsが対応するインデックスが全てぶつかっているので、0以外は-1になっています。Keyからの連想を手動で調べると

6 mode 3
 -> buckets[0]:2
 -> Entry[2]:hashCode     3,next  1,key  3,value C
 -> Entry[1]:hashCode     0,next  0,key  0,value B
 -> Entry[0]:hashCode     6,next -1,key  6,value A

0 mode 3
 -> buckets[0]:2
 -> Entry[2]:hashCode     3,next  1,key  3,value C
 -> Entry[1]:hashCode     0,next  0,key  0,value B

3 mode 3
 -> buckets[0]:2
 -> Entry[2]:hashCode     3,next  1,key  3,value C

Keyから連想するValueまでが、Dictinary内部にある状態から、たどりつけることがわかります。アルゴリズムの部分は完全に想像なので、不正確なのは否定できませんが、大体当ているのではないかと思います。
今度は、配列の要素数の変化をみてみることにします。

        static void Main()
        {
            var dictionary = new Dictionary<int, int>();
            int bucketsCount = 0;
            foreach (var i in Enumerable.Range(0, 1000))
            {
                dictionary.Add(i, i);
                int tmpBucketsCount = GetFieldValue<int[]>(dictionary, "buckets").Length;
                if (bucketsCount < tmpBucketsCount)
                {
                    bucketsCount = tmpBucketsCount;
                    Console.WriteLine("Add {0}, Length {1}", i, bucketsCount);
                }
            }
        }

実行してみると

Add 0, Length 3
Add 3, Length 7
Add 7, Length 17
Add 17, Length 37
Add 37, Length 89
Add 89, Length 197
Add 197, Length 431
Add 431, Length 919
Add 919, Length 1931

List<T>のようににキャパシティーを超えたら、2倍になっているのかと思いきや、そうではないようです。見るかぎり今回の範囲では、素数になっているように見えます。ただし、連続した素数ではなく、素数を2倍して、最初に見つかる素数になっているように見えます。なぜ、そのような数字が採用されいるのかは、皆目検討がつきません。Dcitionaryにとってのキャパシティの増加傾向が、この数列が一番効果的なのかもしれませんし、キャパティが素数である必要があるのかもしれませんし、いろいろ想像が膨らみます。

        static void Main()
        {
            var dictionary = new Dictionary<int, int>();
            int entriesCount = 0;
            foreach (var i in Enumerable.Range(0, 1000))
            {
                dictionary.Add(i, i);
                int tmpEntriesCount = GetFieldValue<Array>(dictionary, "entries").Length;
                if (entriesCount < tmpEntriesCount)
                {
                    entriesCount = tmpEntriesCount;
                    Console.WriteLine("Add {0}, Length {1}", i, entriesCount);
                }
            }
        }

実行すると

Add 0, Length 3
Add 3, Length 7
Add 7, Length 17
Add 17, Length 37
Add 37, Length 89
Add 89, Length 197
Add 197, Length 431
Add 431, Length 919
Add 919, Length 1931

bucketsとentriesの要素数は同じになるようです。

ということで、今回の調査をまとめてみます。

Dictionary<T, TKey>は、内部的にはハッシュコードを更に圧縮した値をインデックスとする配列(buckets)を保持する。bucketsの各要素の値は、エントリーのインデックスに対応している。エントリーは、ハッシュキー、重複かつ見つからなかった場合の次のエントリーのインデックス、Key、Valueを保持している。

と、予測してみた!

【C#】最近、繰り返し処理のコードが読めなくなってきた。

  • 2012.12.18 Tuesday
  • 22:49
JUGEMテーマ:コンピュータ

私の開発の3分の1くらいは人様が書いたコードを読むということです。最近、forやforeachで書かれた処理が読めなくなってきたことに気づきました。読めないというのは少し語弊があるかもしれませんが、そのコードが何をしようとしているのか、すぐに分からないという状態に不快感を覚えるようになったと言うべきかもしれません。昔は読めた!昔は分かっていた!昔はすぐに理解できた!なんて言う気は、え、最初はそう主張しようとおもったのですが、いやいや、そうじゃないかもしれない。と、書きながら思いとどめました。じゃー、なんで不快感を得るのだろうか、と考えると、もっとわかりやすい表現方法とかある事がひとつかなって思います。そういうことです。

まあループの中って、外と中が微妙に曖昧で、結局何がしたいのか分からない事って多々あるよね。

【イベント】第1回 業開中心会議 .NET技術の断捨離

  • 2012.12.18 Tuesday
  • 22:32
JUGEMテーマ:コンピュータ

第1回 業開中心会議
.NET技術の断捨離

https://itmedia.smartseminar.jp/public/seminar/view/465


面白そうです。極力、引きこもりたいけど、巣穴から出てみようかしら。

calendar

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930
31      
<< December 2017 >>

あわせて読みたい

あわせて読みたいブログパーツ

selected entries

categories

archives

recent comment

  • 【キーボード】6年前のRealForceを復活させることはできる!?その3
    art55 (05/22)
  • 【キーボード】6年前のRealForceを復活させることはできる!?その3
    分解大好き (05/18)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    art55 (02/04)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    Gen (02/04)
  • 【キーボード】RealForce が壊れて帰ってきた。
    art55 (04/29)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    art55 (02/23)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    かるあ (02/22)
  • 【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。
    art55 (01/16)
  • 【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。
    karuakun (01/16)
  • 【NetOffice】【Excel】死なないExcelプロセスをKillする。
    art55 (12/05)

recent trackback

recommend

recommend

recommend

C#プログラマのための.NETアプリケーション最適化技法 (Programmer's SELECTION)
C#プログラマのための.NETアプリケーション最適化技法 (Programmer's SELECTION) (JUGEMレビュー »)
Sasha Goldshtein,Dima Zurbalev,Ido Flatow,サシャ・ゴルドシュタイン,ディマ・ズルバレフ,イド・フラトー

recommend

ろんりと集合
ろんりと集合 (JUGEMレビュー »)
中内 伸光
とてもわかりやすいです。

recommend

recommend

シャノン・ノイマン・ディジタル世界
シャノン・ノイマン・ディジタル世界 (JUGEMレビュー »)
市川 忠男
4章がリレーショナルデータベースな内容になってます。ページ数があまりありませんが、ポイントがものすごく的確にまとまっていて、感動します。

recommend

recommend

東プレ Realforce91UBK-S 静音キーボード 静電容量無接点方式 変荷重 ブラック NG01BS
東プレ Realforce91UBK-S 静音キーボード 静電容量無接点方式 変荷重 ブラック NG01BS (JUGEMレビュー »)

テンキーレス、静音のRealForce91UBK-S。スコスコ感がたまらなく気持ちいいです。家と会社で2台持ってます。

recommend

recommend

プログラミング.NET Framework 第4版 (プログラミングシリーズ)
プログラミング.NET Framework 第4版 (プログラミングシリーズ) (JUGEMレビュー »)
Jeffrey Richter
発売予定美 2013年10月10日。.NET Frameworkとお付き合いする人のバイブルですね。

recommend

recommend

キャット・シッターの君に。
キャット・シッターの君に。 (JUGEMレビュー »)
喜多嶋 隆
私のイラストレータデビュー本です。

recommend

Essential .NET ― 共通言語ランタイムの本質
Essential .NET ― 共通言語ランタイムの本質 (JUGEMレビュー »)
ドン・ボックス,クリス・セルズ,Don Box,Chris Sells,吉松 史彰

links

profile

search this site.

others

mobile

qrcode

powered

無料ブログ作成サービス JUGEM