c# - 关于字符串实习和替代方案

标签 c# .net string hashset string-interning

我有一个大文件，它本质上包含如下数据:

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> .但是，其他一些类可能(并且可能会)对此数据进行一些分层 View /结构，例如:

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()实习国家、省、城市和街道字符串(这些是主要的“恶棍”，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()创建层次结构时方法 resp 的键(国家、省等)。字典会更有效率。

但是，使用 string.Intern() 的缺点之一(除了性能略有下降，这不是问题)。是字符串 won't be garbage collected anymore .但是当我处理完我的数据时，我确实希望垃圾收集所有这些东西(最终)。

I could use a Dictionary<string, string> to 'intern' this data但我不喜欢拥有 key 的“开销”和 value实际上，我只对 key 感兴趣.我可以设置 value至 null或者使用与 value 相同的字符串(这将导致 key 和 value 中的引用相同)。只需要支付几个字节的小代价，但它仍然是一个代价。

有点像 HashSet<string>对我来说更有意义。但是，我无法获得对 HashSet 中字符串的引用；我可以查看 HashSet 是否包含特定字符串，但无法获得对 HashSet 中所定位字符串的该特定实例的引用。 I could implement my own HashSet for this ，但我想知道您喜欢 StackOverflowers 可能想出的其他解决方案。

要求:
  • 我的“FileReader”类需要不断暴露 IEnumerable<MyObject>
  • 我的“FileReader”类可能会做一些事情(比如 string.Intern() )来优化内存使用
  • MyObject类(Class)不能改变；我不会做 City类(class)，Country类等并有 MyObject将这些公开为属性而不是简单的 string属性(property)
  • 目标是通过去重 Country 中的大部分重复字符串来提高(更多)内存效率。 , Province , City等等。;这是如何实现的(例如字符串实习、内部哈希集/集合/某物的结构)并不重要。但是:
  • 我知道我可以将数据填充到数据库中或在这个方向上使用其他解决方案；我对这些解决方案不感兴趣。
  • 速度只是次要问题；当然越快越好，但在读取/迭代对象时性能(轻微)损失是没有问题的
  • 由于这是一个长时间运行的进程(例如:Windows 服务 24/7/365)，偶尔会处理大量数据，因此我希望在处理完数据后将数据进行垃圾收集；字符串实习效果很好，但从长远来看，会产生一个巨大的字符串池，其中包含大量未使用的数据
  • 我希望任何解决方案都是“简单的”；添加 15 个带有 P/Invokes 和内联汇编(夸张)的类是不值得的。代码可维护性在我的 list 上很重要。

    • 这更像是一个“理论”问题；我问这纯粹是出于好奇/兴趣。没有“真正的”问题，但我可以看到，在类似的情况下，这对某人来说可能是个问题。

    例如:我可以做这样的事情:

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

    但是对于大量(要删除重复的)字符串，这将很快陷入困境。我可以看看 reference source for HashSet或 Dictionary或者...并构建一个类似的类，它不会为 Add() 返回 bool方法，但在内部/存储桶中找到的实际字符串。

    到目前为止，我能想到的最好的东西是:

    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 和一个值，而我实际上只对 key 感兴趣。虽然只有几个字节，付出的代价很小。巧合的是，这也减少了 42% 的内存使用量；与使用 string.Intern() 时的结果相同产量。

    tolanj came up with System.Xml.NameTable :

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

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

    (我删除了 lock and string.Empty check (后者自 NameTable already does that ))

    xanatos came up with a 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() 接口(interface)”)

    根据 Henk Holterman's request :

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

    我只是想知道是否有一种更整洁/更好/更酷的方法来“解决”我的(不是那么实际的)问题。现在我有足够的选择，我想 wink

    以下是我为一些简单、简短的初步测试得出的一些数字:


    非优化内存:~4,5Gb 加载时间:~52s


    StringInterningObject(见上文，ConcurrentDictionary 变体)内存:~2,6GbLoad 时间:~49s


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


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


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


    StringInterningObject(见上文，(非并发)Dictionary 变体)根据 Henk Holterman's request :内存:~2,3Gb加载时间:~39s

    虽然数字不是很确定，但似乎非优化版本的许多内存分配实际上比使用 string.Intern() 慢得多。或以上 StringInterningObject s 导致(稍微)更长的加载时间。另外，string.Intern()似乎“赢”来自 StringInterningObject但幅度不大； << 查看更新。

    最佳答案

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

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

    在私有(private)名称表上

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

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

    关于c# - 关于字符串实习和替代方案，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29984839/

    上一篇：c# - 对 int 中的单个字节进行操作的最快方法

    下一篇：c# - 在 Startup.cs 中添加 DbContextOptions 而不是注册数据存储

    相关文章：

    c# - 在.NET core 2 MVC应用程序中配置JWT访问 token

    c# - 在 .NET 中逐个节点地比较两个 XML 文件

    c# - 如何获取FireFox新创建的窗口处理程序？

    c - 从 STDIN 读取一行以仅使用 C 提取数字标记

    java - 从文本文件中获取格式化数字的简单方法？

    c# - 无法在 IF 语句中将类型 byte 隐式转换为 bool

    c# - 如果我的类不继承任何东西，为什么我能够覆盖 Equals 方法？

    c# - 转换使用任务的便捷方法

    .net - 没有 MediaTypeFormatter 可用于从媒体类型为 'text/html' 的内容中读取类型的对象

    java - Java是否将文件路径中的多个斜杠 "\\\\\\"视为单个 "\\"？

    ©2024 IT工具网  联系我们