c# - 文字列のインターンと代替について

Question

本質的に次のようなデータを含む大きなファイルがあります。

Netherlands,Noord-holland,Amsterdam,FooStreet,1,...,...
Netherlands,Noord-holland,Amsterdam,FooStreet,2,...,...
Netherlands,Noord-holland,Amsterdam,FooStreet,3,...,...
Netherlands,Noord-holland,Amsterdam,FooStreet,4,...,...
Netherlands,Noord-holland,Amsterdam,FooStreet,5,...,...
Netherlands,Noord-holland,Amsterdam,BarRoad,1,...,...
Netherlands,Noord-holland,Amsterdam,BarRoad,2,...,...
Netherlands,Noord-holland,Amsterdam,BarRoad,3,...,...
Netherlands,Noord-holland,Amsterdam,BarRoad,4,...,...
Netherlands,Noord-holland,Amstelveen,BazDrive,1,...,...
Netherlands,Noord-holland,Amstelveen,BazDrive,2,...,...
Netherlands,Noord-holland,Amstelveen,BazDrive,3,...,...
Netherlands,Zuid-holland,Rotterdam,LoremAve,1,...,...
Netherlands,Zuid-holland,Rotterdam,LoremAve,2,...,...
Netherlands,Zuid-holland,Rotterdam,LoremAve,3,...,...
...

これは数ギガバイトのファイルです。このファイルを読み取り、これらの行 (レコード) をIEnumerable<MyObject>. これMyObjectには、いくつかのプロパティ ( Country、Province、City、...) などがあります。

ご覧のとおり、データの重複がたくさんあります。基になるデータをとして公開し続けたいと思いIEnumerable<MyObject>ます。ただし、他のクラスでは、次のようなこのデータの階層ビュー/構造を作成する可能性があります (おそらくそうするでしょう)。

Netherlands
    Noord-holland
        Amsterdam
            FooStreet [1, 2, 3, 4, 5]
            BarRoad [1, 2, 3, 4]
            ...
        Amstelveen
            BazDrive [1, 2, 3]
            ...
         ...
    Zuid-holland
        Rotterdam
            LoremAve [1, 2, 3]
            ...
        ...
    ...
...

このファイルを読むときは、基本的に次のようにします。

foreach (line in myfile) {
    fields = line.split(",");
    yield return new MyObject {
        Country = fields[0],
        Province = fields[1],
        City = fields[2],
        Street = fields[3],
        //...other fields
    };
}

さて、手元にある実際の質問に: Country、Province、City、Street の文字列をインターンするために使用できます (これらは主な「悪役」であり、質問に関係のない他のいくつかのプロパティがあります)。string.Intern()MyObject

foreach (line in myfile) {
    fields = line.split(",");
    yield return new MyObject {
        Country = string.Intern(fields[0]),
        Province = string.Intern(fields[1]),
        City = string.Intern(fields[2]),
        Street = string.Intern(fields[3]),
        //...other fields
    };
}

これにより、すべての重複文字列が同じ文字列への参照になるため、データセット全体をメモリに保持すると、約 42% のメモリ (テストおよび測定) が節約されます。また、多くの LINQ の.ToDictionary()メソッドで階層構造を作成する場合、それぞれのキー (Country、Province など) を使用します。辞書ははるかに効率的になります。

ただし、使用の欠点の 1 つ (問題ではないパフォーマンスのわずかな損失は別として) はstring.Intern()、文字列がガベージコレクションされなくなることです。しかし、データの処理が終わったら、(最終的には) ガベージをすべて収集したいと思います。

を使用してこのデータを「インターン」することもできDictionary<string, string>ますが、を使用することの「オーバーヘッド」が好きではなくkey、value実際にはにのみ関心がありkeyます。を設定valueするnullか、値として同じ文字列を使用することができます (結果としてとで同じ参照にkeyなりvalueます)。支払うのは数バイトのわずかな代償ですが、それでも代償です。

のようなものは、HashSet<string>私にとってより理にかなっています。ただし、HashSet 内の文字列への参照を取得できません。HashSet に特定の文字列が含まれているかどうかはわかりますが、HashSet 内にある文字列の特定のインスタンスへの参照は取得できません。私はこれのために自分自身を実装することができHashSetましたが、あなたが種類の StackOverflowers を思い付くことができる他の解決策を考えています.

要件：

私の「FileReader」クラスは、IEnumerable<MyObject>
私の「FileReader」クラスは、メモリ使用量を最適化するために（のような）ことをするかもしれませんstring.Intern()
MyObjectクラスは変更できません。Cityクラス、Countryクラスなどを作成せず、それらを単純なプロパティMyObjectではなくプロパティとして公開しますstring
Country目標は、Province、Cityなどの重複文字列のほとんどを重複排除することにより、(より) メモリ効率を高めることです。これがどのように達成されるか (例: 文字列インターン、内部ハッシュセット / コレクション / 何かの構造) は重要ではありません。でも：
データベースにデータを詰め込むか、そのような方向で他のソリューションを使用できることを知っています。この種のソリューションには興味がありません。
速度は二次的な問題にすぎません。もちろん、速ければ速いほど良いですが、オブジェクトの読み取り/反復中のパフォーマンスの（わずかな）低下は問題ありません
これは長時間実行されるプロセス (例: 24 時間 365 日実行されている Windows サービス) であるため、時折、このデータの大量を処理します。文字列インターニングはうまく機能しますが、長期的には、未使用のデータがたくさんある巨大な文字列プールになります
解決策は「シンプル」にしたいと思います。P/Invokes とインラインアセンブリ (誇張されています) を使用して 15 個のクラスを追加することは、努力する価値がありません。コードの保守性は私のリストの上位にあります。

これは「理論的な」質問です。私が尋ねているのは純粋に好奇心/興味からです. 「本当の」問題はありませんが、同様の状況でこれが誰かの問題になる可能性があることがわかります。

例: 次のようなことができます。

public class StringInterningObject
{
    private HashSet<string> _items;

    public StringInterningObject()
    {
        _items = new HashSet<string>();
    }

    public string Add(string value)
    {
        if (_items.Add(value))
            return value;  //New item added; return value since it wasn't in the HashSet
        //MEH... this will quickly go O(n)
        return _items.First(i => i.Equals(value)); //Find (and return) actual item from the HashSet and return it
    }
}

しかし、(重複除去する) 文字列のセットが大きいと、これはすぐに行き詰まります。HashSetまたはDictionaryまたは ...の参照ソースをのぞいて、メソッドの bool を返さずAdd()、内部/バケットで見つかった実際の文字列を返す同様のクラスを構築できます。

今まで思いついた最高のものは次のようなものです：

public class StringInterningObject
{
    private ConcurrentDictionary<string, string> _items;

    public StringInterningObject()
    {
        _items = new ConcurrentDictionary<string, string>();
    }

    public string Add(string value)
    {
        return _items.AddOrUpdate(value, value, (v, i) => i);
    }
}

これには、実際にはキーのみに関心があるキーと値を持つという「ペナルティ」があります。ほんの数バイトですが、支払う代償はわずかです。偶然にも、これによりメモリ使用量も 42% 減少します。string.Intern()yieldsを使用した場合と同じ結果になります。

tolanj は System.Xml.NameTable を思いつきました:

public class StringInterningObject
{
    private System.Xml.NameTable nt = new System.Xml.NameTable();

    public string Add(string value)
    {
        return nt.Add(value);
    }
}

（ロックとstring.Emptyチェックを削除しました（後者はNameTableがすでにそれを行っているためです））

xanatos は CachingEqualityComparer を思いつきました:

public class StringInterningObject
{
    private class CachingEqualityComparer<T> : IEqualityComparer<T> where T : class
    {
        public System.WeakReference X { get; private set; }
        public System.WeakReference Y { get; private set; }

        private readonly IEqualityComparer<T> Comparer;

        public CachingEqualityComparer()
        {
            Comparer = EqualityComparer<T>.Default;
        }

        public CachingEqualityComparer(IEqualityComparer<T> comparer)
        {
            Comparer = comparer;
        }

        public bool Equals(T x, T y)
        {
            bool result = Comparer.Equals(x, y);

            if (result)
            {
                X = new System.WeakReference(x);
                Y = new System.WeakReference(y);
            }

            return result;
        }

        public int GetHashCode(T obj)
        {
            return Comparer.GetHashCode(obj);
        }

        public T Other(T one)
        {
            if (object.ReferenceEquals(one, null))
            {
                return null;
            }

            object x = X.Target;
            object y = Y.Target;

            if (x != null && y != null)
            {
                if (object.ReferenceEquals(one, x))
                {
                    return (T)y;
                }
                else if (object.ReferenceEquals(one, y))
                {
                    return (T)x;
                }
            }

            return one;
        }
    }

    private CachingEqualityComparer<string> _cmp; 
    private HashSet<string> _hs;

    public StringInterningObject()
    {
        _cmp = new CachingEqualityComparer<string>();
        _hs = new HashSet<string>(_cmp);
    }

    public string Add(string item)
    {
        if (!_hs.Add(item))
            item = _cmp.Other(item);
        return item;
    }
}

(私の「Add()インターフェース」に「フィット」するようにわずかに変更されました)

Henk Holterman のリクエストによると:

public class StringInterningObject
{
    private Dictionary<string, string> _items;

    public StringInterningObject()
    {
        _items = new Dictionary<string, string>();
    }

    public string Add(string value)
    {
        string result;
        if (!_items.TryGetValue(value, out result))
        {
            _items.Add(value, value);
            return value;
        }
        return result;
    }
}

~~私の（実際の多くではない）問題を「解決」するための、よりきちんとした/より良い/よりクールな方法があるかどうか疑問に思っています。~~今では十分な選択肢があると思いますウィンク

以下は、単純で短い予備テストのために私が思いついたいくつかの数値です。

最適化され
ていないメモリ: ~4,5Gb
読み込み時間: ~52秒

StringInterningObject (上記のConcurrentDictionaryバリアントを参照)
メモリ: ~2,6Gb
読み込み時間: ~49 秒

string.Intern()
メモリ: ~2,3Gb
読み込み時間: ~45 秒

System.Xml.NameTable
メモリ: ~2,3Gb
読み込み時間: ~41 秒

CachingEqualityComparer
メモリ: ~2,3Gb
読み込み時間: ~58 秒

Henk Holterman の要求によるStringInterningObject (上記の (非並行)Dictionaryバリアントを参照) :メモリ: ~2,3Gb読み込み時間: ~39 秒

数値はあまり決定的なものではありませんが、最適化されていないバージョンの多くのメモリ割り当ては、実際にはどちらかstring.Intern()または上記StringInterningObjectの s を使用するよりも遅くなり、ロード時間が (わずかに) 長くなるようです。~~また、string.Intern()「勝つ」ように見えStringInterningObjectますが、大差ではありません。~~<< 更新を参照してください。

score 3 · Accepted Answer

私はまさにこの要件を持っていて、実際にSOで尋ねましたが、あなたの質問の詳細のようなものはなく、有用な回答はありません. 組み込まれている1 つのオプションは(System.Xml).NameTable です。これは基本的に文字列原子化オブジェクトであり、探しているものです (これらの文字列を App 用に保持しているため、実際には Intern に移動しました)。 -生活）。

if (name == null) return null;
if (name == "") return string.Empty; 
lock (m_nameTable)
{
      return m_nameTable.Add(name);
}

プライベート NameTable で

http://referencesource.microsoft.com/#System.Xml/System/Xml/NameTable.cs,c71b9d3a7bc2d2afは、単純なハッシュテーブルとして実装されていることを示しています。つまり、文字列ごとに 1 つの参照のみを格納しています。

欠点？完全に文字列固有です。メモリ/速度のクロステストを行う場合は、結果を確認したいと思います。私たちはすでに System.Xml を多用していました。

score 3 · Accepted Answer

迷ったらチート！:-)

public class CachingEqualityComparer<T> : IEqualityComparer<T> where  T : class
{
    public T X { get; private set; }
    public T Y { get; private set; }

    public IEqualityComparer<T> DefaultComparer = EqualityComparer<T>.Default;

    public bool Equals(T x, T y)
    {
        bool result = DefaultComparer.Equals(x, y);

        if (result)
        {
            X = x;
            Y = y;
        }

        return result;
    }

    public int GetHashCode(T obj)
    {
        return DefaultComparer.GetHashCode(obj);
    }

    public T Other(T one)
    {
        if (object.ReferenceEquals(one, X))
        {
            return Y;
        }

        if (object.ReferenceEquals(one, Y))
        {
            return X;
        }

        throw new ArgumentException("one");
    }

    public void Reset()
    {
        X = default(T);
        Y = default(T);
    }
}

使用例:

var comparer = new CachingEqualityComparer<string>();
var hs = new HashSet<string>(comparer);

string str = "Hello";

string st1 = str.Substring(2);
hs.Add(st1);

string st2 = str.Substring(2);

// st1 and st2 are distinct strings!
if (object.ReferenceEquals(st1, st2))
{
    throw new Exception();
}

comparer.Reset();

if (hs.Contains(st2))
{
    string cached = comparer.Other(st2);
    Console.WriteLine("Found!");

    // cached is st1
    if (!object.ReferenceEquals(cached, st1))
    {
        throw new Exception();
    }
}

分析した最後の用語を「キャッシュ」する等価比較器を作成しましたEqual:-)

すべてをサブクラスにカプセル化できます。HashSet<T>

/// <summary>
/// An HashSet&lt;T;gt; that, thorough a clever use of an internal
/// comparer, can have a AddOrGet and a TryGet
/// </summary>
/// <typeparam name="T"></typeparam>
public class HashSetEx<T> : HashSet<T> where T : class
{

    public HashSetEx()
        : base(new CachingEqualityComparer<T>())
    {
    }

    public HashSetEx(IEqualityComparer<T> comparer)
        : base(new CachingEqualityComparer<T>(comparer))
    {
    }

    public T AddOrGet(T item)
    {
        if (!Add(item))
        {
            var comparer = (CachingEqualityComparer<T>)Comparer;

            item = comparer.Other(item);
        }

        return item;
    }

    public bool TryGet(T item, out T item2)
    {
        if (Contains(item))
        {
            var comparer = (CachingEqualityComparer<T>)Comparer;

            item2 = comparer.Other(item);
            return true;
        }

        item2 = default(T);
        return false;
    }

    private class CachingEqualityComparer<T> : IEqualityComparer<T> where T : class
    {
        public WeakReference X { get; private set; }
        public WeakReference Y { get; private set; }

        private readonly IEqualityComparer<T> Comparer;

        public CachingEqualityComparer()
        {
            Comparer = EqualityComparer<T>.Default;
        }

        public CachingEqualityComparer(IEqualityComparer<T> comparer)
        {
            Comparer = comparer;
        }

        public bool Equals(T x, T y)
        {
            bool result = Comparer.Equals(x, y);

            if (result)
            {
                X = new WeakReference(x);
                Y = new WeakReference(y);
            }

            return result;
        }

        public int GetHashCode(T obj)
        {
            return Comparer.GetHashCode(obj);
        }

        public T Other(T one)
        {
            if (object.ReferenceEquals(one, null))
            {
                return null;
            }

            object x = X.Target;
            object y = Y.Target;

            if (x != null && y != null)
            {
                if (object.ReferenceEquals(one, x))
                {
                    return (T)y;
                }
                else if (object.ReferenceEquals(one, y))
                {
                    return (T)x;
                }
            }

            return one;
        }
    }
}

WeakReferenceガベージコレクションを妨げる可能性のあるオブジェクトへの無駄な参照がないように、の使用に注意してください。

使用例:

var hs = new HashSetEx<string>();

string str = "Hello";

string st1 = str.Substring(2);
hs.Add(st1);

string st2 = str.Substring(2);

// st1 and st2 are distinct strings!
if (object.ReferenceEquals(st1, st2))
{
    throw new Exception();
}

string stFinal = hs.AddOrGet(st2);

if (!object.ReferenceEquals(stFinal, st1))
{
    throw new Exception();
}

string stFinal2;
bool result = hs.TryGet(st1, out stFinal2);

if (!object.ReferenceEquals(stFinal2, st1))
{
    throw new Exception();
}

if (!result)
{
    throw new Exception();
}

c# - 文字列のインターンと代替について

3 に答える 3

Related

Reference