关于字符串实习和替代

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
    };
}

现在,手头上的实际问题:我能使用string.Intern()实习生的国家,省,市,人和街串(这些是主要的"vilains"时,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()方法创建分层结构时,分别为(国家,省等)的密钥.字典会更有效率.

然而,使用的一个缺点(除了性能的轻微损失,这不是问题)string.Intern()是字符串将不再被垃圾收集.但是,当我完成我的数据时,我确实希望收集所有垃圾(最终).

我可以使用Dictionary<string, string>'实习'这个数据,但我不喜欢拥有一个key和value我在哪里的"开销" ,实际上,只对这个数据感兴趣key.我可以设置valueto 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/7/365的Windows服务),偶尔会处理大量此类数据,我希望在完成后对数据进行垃圾收集; string interning工作得很好,但从长远来看,会产生一个包含大量未使用数据的巨大字符串池
• 我希望任何解决方案都"简单"; 使用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的引用源或者......并构建一个类似的类,它不会为Add()方法返回bool,而是在internals/bucket中找到实际的字符串.

我能想到的最好的东西是:

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);
    }
}

具有Key 和 Value 的"惩罚",其中我实际上只对Key感兴趣.只需几个字节,支付的价格很小.顺便说一句,这也减少了42%的内存使用量; 与使用string.Intern()产量时相同的结果.

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
加载时间:~52s

StringInterningObject(见上文,ConcurrentDictionary变体)
内存:~2,6Gb
加载时间:~49 秒

string.Intern()
内存:~2,3Gb
加载时间:~45s

System.Xml.NameTable
内存:~2,3Gb
加载时间:~41s

CachingEqualityComparer
内存:~2,3Gb
加载时间:~58s

StringInterningObject(见上文,(非并发)Dictionary变体)按照Henk Holterman的要求:
内存:~2,3Gb
加载时间:~ 39s

虽然数字不是很明确,但似乎非优化版本的许多内存分配实际上比使用string.Intern()上述任何一个或更慢的速度慢,StringInterningObject这导致(稍微)更长的加载时间.而且,string.Intern()似乎是"赢" StringInterningObject而不是大幅度; <<查看更新.

Answer 1

我确实有这个要求，并且确实提出了这样的要求，但是没有像你的问题的细节那样的信息，没有有用的答复。内置的一个选项是(System.Xml).NameTable，它基本上是一个字符串原子化对象，这就是您正在寻找的，我们有（我们实际上已转移到 Intern，因为我们确实为 App 保留了这些字符串-生活）。

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

在私有名称表上

http://referencesource.microsoft.com/#System.Xml/System/Xml/NameTable.cs,c71b9d3a7bc2d2af显示其作为简单哈希表实现，即每个字符串仅存储一个引用。

缺点？是它完全特定于字符串的。如果您对内存/速度进行交叉测试，我有兴趣查看结果。我们已经大量使用 System.Xml，如果您不这样做的话，当然可能看起来不太自然。