.NET 字符串类的替代方案

Question

由于我正在规划的应用程序将在内存中保存大量数据，因此我希望有一种“紧凑”的字符串类，至少应该包含字符串格式不大于零终止ASCII版本的字符串。

你知道有没有这样的字符串类实现 - 它应该具有一些类似于原始字符串类的实用函数。

编辑：

我需要对字符串进行排序并能够扫描它们，这只是我将使用的一些操作之一。

理想情况下，它应该与System.String源代码兼容，因此基本搜索和替换操作可以优化应用程序的内存占用。

数字：

我可能会有10个字符串，每个记录最多有30-60个字符，有100k条记录。所以：

100000x10x60=60000000=57兆字符。 为什么不使用60兆字节的RAM来代替120兆字节的RAM？ 操作将更快，所有内容将更加紧密。

将使用树进行搜索，但对于我计划拥有的正则表达式扫描无济于事。

- Daniel Mošmondor

---

@Daniel：您真的需要一次性将所有记录都存储在内存中吗？有没有使用某种嵌入式数据库的原因？每个记录有多大？您实际希望一次性在内存中保存多少条记录？ - Jon Skeet

鉴于你的例子，我肯定不会仅为了区别60MB而这么做。内存比开发人员的时间更便宜...你真的有可能在一台机器上运行，其中60MB的差异是成功和失败之间的区别吗？ - Jon Skeet

老实说，需要将那么多的数据以字符串形式加载到内存中，可能只是设计不佳。 - anthonyvd

@Daniel: 我的 SQL Server Express 实例能够在 200+ MB 数据库的（聚集索引上）执行那个精确查询，并且在不到 10 毫秒的时间内完成。 - BlueRaja - Danny Pflughoeft

这是基于直觉的优化（IBO）。请阅读此描述，了解为什么IBO是错误的。http://thesmithfam.org/blog/2011/02/06/how-to-optimize-your-code/ - J Edward Ellis

Answer 1

编辑：我现在有一篇关于这个主题博客文章，其中详细讨论了更多内容。

---

按照您的数字：

我可以有10万条记录，每条记录最多有10个字符串，每个字符串有30到60个字符。

让我们首先添加对象开销 - 字符串大约占用20个字节（如果我没记错的话-64位CLR上可能更多）加上实际数据，由于不可避免的对象开销和长度。 让我们再做一次数学计算：

使用字符串：100万个对象，每个对象占用20 + 120字节= 140MB

使用新类：100万个对象，每个对象占用20 + 60字节= 80MB

当然仍然有60MB的差异，但是比例上比你预期的要少。你只能节省42％的空间，而不是50％。

现在，您谈到速度更快的事情：考虑到CLR本地上知道string，我怀疑第三方类无法匹配某些操作的速度，并且您必须进行大量工作才能使其他操作的速度相同。不可否认的是，您将拥有更好的缓存一致性，并且如果您可以忽略文化问题，则通过使所有比较按序排序也应该节省一些时间。

为了节省60MB，我不会麻烦自己。这在今天来说是微小的差异-考虑到您需要获得多少更多的客户才能通过进行这种小的节省来弥补使用两种不同字符串类型的显着额外成本。

尽管如此，我还是很想像Edulinq一样实现它，做一个博客项目。但是不要指望在几周或几个月内得出任何结果：）

编辑：我刚想到另一个问题。上面得到的数字实际上是错误的...因为字符串类是特殊的。 它直接在对象中嵌入其数据-与数组以外的任何其他数据类型不同，string实例的大小不固定；它根据其中的数据而变化。

编写自己的AsciiString类，您将无法这样做，必须在类中嵌入数组引用：

public class AsciiString
{
    private readonly byte[] data;
}

这意味着您需要额外的4个或8个字节作为引用（32位或64位CLR），并且每个字符串还需要一个数组对象的额外开销（16个字节，如果我没记错的话）。

如果按照Java的设计方式进行设计，则子字符串可以重用现有的字节数组（两个字符串可以共享），但这样一来，您就需要一个附加的AsciiString内长度和偏移量。您也会失去一些缓存一致性的好处。

您可以仅使用原始字节数组作为数据结构，并编写大量扩展方法来处理它们...但那将是可怕的，因为这样您无法区分普通字节数组和用于表示ASCII字符串的字节数组。

另一种可能性是创建这样一个结构:

struct AsciiString
{
    private readonly byte[] data;
    ...
}

这实际上会让你再次拥有强类型，但你需要考虑诸如：

AsciiString x = new AsciiString();

如果这样做会导致data引用为空。您可以将其视为x是空值，但这将不太符合惯用语。

- Jon Skeet

---

如果数字确实是这样的，那么这件事值得做，你能提供一些需要考虑的指针或注意事项吗？谢谢。 - Daniel Mošmondor

实现自己的字符串类需要考虑注意事项吗？只是实现和测试都需要很多工作量，而且可能获得的收益相对较少。 - Jon Skeet

他是否可以通过使用链表来避免每个对象中数组的开销呢？ - Ziv

@Ziv：不，那会更糟糕。数组开销的大部分原因是它是另一个对象。链表使用了很多对象。 - Jon Skeet

Answer 2

我其实也遇到了类似的问题，但是参数有些不同。我的应用程序处理两种类型的字符串 - 相对较短的字符串长度为60-100个字符，和相对较长的字符串长度在100-1000个字节之间（平均约为300）。

我的用例还必须支持Unicode文本，但实际上只有一小部分字符串包含非英语字符。

在我的用例中，我将每个String属性公开为本地String，但底层数据结构是一个byte[]，保存了Unicode字节。

我的用例还需要搜索和排序这些字符串，获取子字符串和其他常见字符串操作。我的数据集有数百万条记录。

基本实现看起来像这样：

byte[] _myProperty;

public String MyProperty
{

   get 
   { 
        if (_myProperty== null)
            return null;

        return Encoding.UTF8.GetString(value);
   }

   set
   { 
        _myProperty = Encoding.UTF8.GetBytes(value);

   }

}

即使在搜索和排序时进行这些转换，性能损失相对较小（约为10-15%）。

这一段时间内还好，但我想进一步减少开销。下一步是为给定对象中的所有字符串创建一个合并的数组（一个对象将保存1个短字符串和1个长字符串，或4个短字符串和1个长字符串）。所以每个对象只需要一个byte[]，并且每个字符串只需要1个字节（保存其长度始终<256）。即使您的字符串可以更长，则int仍然比byte[]的12-16字节开销更便宜。

这样很大程度上减少了byte[]的开销，并增加了一些复杂性但不会影响性能（编码传递相对于涉及数组复制而言相对昂贵）。

此实现大致如下：

byte _property1;
byte _property2;
byte _proeprty3;

private byte[] _data; 

byte[] data;
//i actually used an Enum to indicate which property, but i am sure you get the idea
private int GetStartIndex(int propertyIndex)
{  

   int result = 0;
   switch(propertyIndex)
   {
       //the fallthrough is on purpose 
       case 2:
          result+=property2;
       case 1:
          result+=property1;

   }

   return result;
}

private int GetLength(int propertyIndex)
{
   switch (propertyIndex)
   {
     case 0:
        return _property1;
     case 1: 
        return _property2;
     case 2:
        return _property3;
   }
    return -1;
}

private String GetString(int propertyIndex)
{
   int startIndex = GetStartIndex(propertyIndex);
   int length = GetLength(propertyIndex);
   byte[] result = new byte[length];
   Array.Copy(data,startIndex,result,0,length);

   return Encoding.UTF8.GetString(result);

}

所以 getter 看起来像这样：

public String Property1
{
   get{ return GetString(0);}
}

设置器的作用类似于-将原始数据复制到两个数组中（从0开始到startIndex，以及从startIndex + length到length之间），然后使用三个数组（dataAtStart + NewData + EndData）创建一个新数组，并将数组的长度设置为适当的局部变量。

我仍然不满意节省的内存和每个属性的手动实现所需的非常艰苦的劳动，因此我构建了一个内存压缩分页系统，使用极快的QuickLZ来压缩完整页面。这使我对时间-内存折衷（本质上是页面大小）有了很多控制。

与更有效的byte[]存储相比，我的用例的压缩率接近50％（！）。我使用大约每页10个字符串的页面大小，并将相似的属性分组在一起（倾向于具有类似数据的属性）。 这增加了额外的10-20％开销（除了仍然需要的编码/解码过程）。分页机制会缓存最近访问的页面，最多可配置大小。 即使没有压缩，该实现也允许您为每个页面设置固定的开销因子。 当前页面缓存实现的主要缺点是，在进行压缩时它不是线程安全的（如果没有压缩，则不存在此问题）。

如果您对压缩的分页机制感兴趣，请让我知道（我一直在寻找开源的借口）。

- NightDweller

Answer 3

替代数据结构

考虑到您希望搜索存储的“字符串”值，我建议您考虑使用Trie结构，例如Patricia Trie或者为了更好地分摊内存，使用有向无环词图（通常称为DAWG）可能会更好。

它们的构建时间较长（尽管它们通常用于底层存储本身相当合理，允许快速的前期构建），即使在它们上的某些操作在算法上优越，您可能会发现在您的实际应用中事实上会变慢，但只要有合理数量的重复，它们确实可以显著减少数据的内存占用。

这些可以被视为.net（和java和许多其他托管语言）提供的字符串去重（内置）的泛化。

如果您特别希望保留字符串的某种词汇排序方式（因此您只需要一次考虑一个字符或代码点），那么Patricia Trie可能是更可取的选择，对DAWG的排序实现将是有问题的。

如果您有特定领域的字符串，则可能适用于替代的、更神秘的解决方案，包括：

运行长度编码和其他形式的压缩。

以随机访问字符串为代价，并且如果输入结果不如预期，则存在使用更多内存的风险。Huffman编码在英文文本上表现良好，并且相当简单，它的优点是字典可以跨所有条目共享，只要字母的频率分布是可比较的。排序将再次变得棘手。

固定长度字符串。

如果您知道字符串很小，并且大小几乎相同（或完全相同），则可以将其存储在固定大小的值中（如果所需字符数在16或更少的范围内，则甚至可以使用结构体（此处使用限制取决于您的精确用法，可能严重依赖于您愿意调整代码以使其与该设计协作）。

- ShuggyCoUk

Answer 4

您可以创建一个新的数据结构来存储这些，但我认为这是过度设计。如果您有每个单词或常用短语的数组，则可以将索引作为每个单词的数组存储。对于每个单词，您需要支付4个字节，但如果每个单词平均为3.6个字符，则平均每个单词可以节省3.2个字节，因为您只需支付每个单词一次2字节/字母的惩罚。但是，为了进行搜索或排序，您将花费大量时间来重建字符串，这会导致性能下降。您可能需要重新考虑如何设计程序，因为有许多使用大量数据并且可以在相对受限制的内存中运行的程序。

- James Black

Answer 5

嗯，这里有个UTF8Encoding类。

//Example from MSDN
using System;
using System.Text;

public class Example
{
   public static void Main()
   {
      Encoding enc = new UTF8Encoding(true, true);
      string value = "\u00C4 \uD802\u0033 \u00AE"; 

      try
      {
         byte[] bytes= enc.GetBytes(value);
         foreach (var byt in bytes)
            Console.Write("{0:X2} ", byt);
         Console.WriteLine();

         string value2 = enc.GetString(bytes);
         Console.WriteLine(value2);
      }
      catch (EncoderFallbackException e)
      {
         //Encoding error
      }                     
   }
}

然而，像Jon所说的那样，如果您想要将它与任何期望字符串（大多数.Net库）的方法一起使用，您仍然需要将其转换回普通的Unicode字符串……如果您提供了更多关于您所尝试做什么的信息，也许我们可以帮助您找到更好的解决方案？

或者，如果你真正需要低层字节数组的非国际化空终止字符串，你最好还是用C++来写。

- BlueRaja - Danny Pflughoeft

---

我同意关于C++的评论。如果我们把内存空间看得像我们在这里所说的那样宝贵，那么一种受控语言将会与你作对。纠结于内存管理细节是低级语言脱颖而出的地方。 - Godeke

Answer 6

你预计会有多少个重复项？如果数组中有很多重复项，你可以考虑实现一个字符串缓存（包装在Dictionary<string, string>周围），它缓存特定字符串的实例，并为你在其中缓存的每个重复字符串返回对该实例的引用。

你可以结合使用检查已经被内部化的字符串，这样如果整个程序有很多共享的字符串，你就总是使用内部化版本。

根据你的数据，这可能比尝试优化每个单独字符串的存储方式更好。

- thecoop

Answer 7

我认为关键在于每个记录都有许多字符串字段...

通过将每个记录的所有字符串字段存储在一个字符数组中，然后使用具有偏移量的int字段，您可以大大减少对象数量。(每个对象在放入任何数据之前的开销约为2个字。)

您的属性随后可以转换为/从标准字符串。垃圾收集器非常擅长处理大量短期存在的垃圾，因此在访问属性时创建大量“tmp”字符串不应成为问题。

(现在，如果许多字符串字段从未更改其值，事情就变得容易得多)

- Ian Ringrose

Answer 8

你可以通过使用一个大的byte[]来存储字符，然后使用该数组中的int偏移量作为你的“字符串”，从而节省每个对象的开销。

- usr

Answer 9

也许一个好的老式字符数组会适合你的需求。

- Steve Wellens

---

每个字符仍将占用2个字节，但不带任何抽象。 - Jon Skeet

Answer 10

这些字符串都是不同的吗？

在大多数真实世界的数据集中，实际上不同字符串的数量可能并不高，如果考虑到字符串池化，那么实际消耗的内存量可能会比你想象的少得多。

- Paul Creasey