.NET的稀疏数组类(译文)
By S.F.
本文链接 https://www.kyfws.com/news/sparse-array-class-for-net/
版权声明 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
- 10 分钟阅读 - 4797 个词 阅读量 0.NET的稀疏数组类(译文)
原文地址:https://www.codeproject.com/Articles/321895/Sparse-Array-class-for-Net
原文作者:Joel Ivory Johnson
译文由本站翻译
前言
.NET的稀疏数组类.
介绍
我需要一个动态增长的稀疏填充数组. “稀疏"意味着在包含非空值的元素之间会有很多包含空值的元素. .Net集合名称空间不包含任何满足此需求的内容.的 ArrayList类动态增长,但是它会为空值和非空值分配相同的元素.我打算在内存有限的设备上使用此代码,因此不会这样做.我结束了自己的课堂来满足这一需求.虽然我最初对代码的需求是"字节"数组,但我还是使代码通用,以便可以与其他数据类型一起使用.
这个班有多大?
因为我将要讨论内存分配,所以我还需要讨论如何对某个实例花费多少内存.这不会占对象分配所消耗的内存的100%.但是它已经足够接近,您可以开始制作了 判断一个对象比另一个对象花费更多的内存还是更少的内存. 有许多大小已知的预定义值类型.这是一些最常见的. 如果您构建一个结构,它也是一个值类型.结构的大小约为其成员大小的总和.这是一个例子.
struct Location
{
public int LocationID; // 4 bytes
public double Latitude; // 4 bytes
public double Longitude; // 4 bytes
public double Elevation; // 4 bytes
}
此结构的大小为16个字节.现在,如果添加引用类型(被定义为类而不是结构的东西)会发生什么?有多大?我将在前面的示例中添加一个字符串.
struct Location
{
public int LocationID; // 4 bytes
public string LocationName; // ?
public double Latitude; // 4 bytes
public double Longitude; // 4 bytes
public double Elevation; // 4 bytes
}
对于参考字段,要考虑两个内存元素.有参考的大小和它指向的对象的大小.可以将上面的示例中的” LocationName"字段想像成将内存地址保存到保存字符串的区域.该内存地址的大小将取决于代码所针对的处理器体系结构类型.如果代码是针对32位系统的JIT编译,则 引用的大小为32位(4字节).如果是针对64位系统的JIT编译,则 引用的大小为64位(8字节).当我仅在台式机上工作时,我将基于64位系统进行计算.但是本文中的代码将在Windows Phone上运行,因此我将两者都考虑在内.对象标头中还有大约8个字节的其他元素.内存中要考虑的其他元素是字符串本身的大小.如果尚未分配字符串,并且元素为null,则要考虑的第二个元素的大小将为零.如果为字符串分配了一个值,则第二个元素将是该字符串消耗的内存. 可能有多个结构引用相同的实例 参考类型.发生这种情况时,您将要确保不对引用类型的实例占用的内存进行多次计数. 现在让我们添加一个数组,看看它对我们的内存计算有什么作用.数组本身是引用类型.因此,对它的引用将消耗的内存量取决于处理器体系结构.
struct Location
{
public int LocationID; // 4 bytes
public string LocationName; // 4/8 bytes + string memory
public double Latitude; // 4 bytes
public double Longitude; // 4 bytes
public double Elevation; // 4 bytes
public int[] SomeRandomArray; // 4/8 bytes + array memory
}
与数组关联的内存大小将是其包含的元素大小的总和.如果数组包含值类型(上面的数组包含" int"值类型),则在初始化数组时分配的内存为sizeof(int
)(4字节)乘以数组中元素的数量.如果数组包含引用类型,则数组消耗的内存将是引用的大小(在32位系统上为4 + 8字节,在64位系统上为8 + 8字节)乘以以下元素的数量:数组可以容纳.这不包括其包含的元素的各个实例化实例的大小.
如果将以上任何内容从"结构"更改为"类",会发生什么?将类型转换为引用类型后,它还将具有一个对象标头.对于struct
,当您声明一个变量时,所有直接成员将要使用的内存都将被分配.对于"类",仅分配用于参考的内存(32位为4字节,64位为8字节).在调用new
之前,不会分配引用类型的成员所需的内存.还要注意,引用类型实例的内存在堆上分配,而值类型实例的内存在堆栈上分配.
外观稀疏和连续的内存分配
如果我们看一下如何为稀疏数组和连续(普通)数组分配内存,那么我需要这样做的原因将更加清楚.举一个过于简化的示例,假设必须分配一个包含40个元素的数组.常规数组将连续分配内存;与数组关联的字节将在同一块内存中.假设我们的稀疏数组一次为五个元素分配内存块.蓝色框下方表示存在非空数据的区域. 一目了然,稀疏阵列占用的内存少于常规阵列.结构中仍然有一些空元素.这是因为它正在为一定范围的索引分配内存.如果在5个块的范围内甚至有一个非空元素,那么所有5个块都有分配.这是否会导致整体分配的内存更少,将取决于稀疏数组的使用模式.当填充的元素彼此紧密地聚集在一起时,它将发挥最佳效果.我们可以一起消除所有空元素吗?我们可以通过减少分配的块的大小来实现.块越小,块内空位置存在的机会就越小.如果为单个元素(仅容纳一个元素的块)分配了内存,那么列表中将只有填充的元素.但这更好吗? 可能是.但是,要想更好地回答这个问题,就目前而言,对于稀疏数组而言,代价仍然是不可见的.在我的实现中,有一个用于保存每个块的结构.
public class ArrayChunk<T>
{
public int StartIndex { get; set; } //4 bytes needed to contain an integer value
public int EndIndex
{
get
{
if (Data == null)
return -1;
return StartIndex + Data.Length-1;
}
}
public T[] Data { get; set; }
}
除了保存块本身元素的数组之外,还有一个字段用于保存数组的起始索引.起始索引占用4个字节的内存.因此,分配给每个块的开销不少于4个字节.考虑一个常规数组和一个稀疏数组,它们都完全填充了100个字节的数据.还假设稀疏数组一次分配10个字节的内存.传统阵列消耗的内存约为100个字节.稀疏数组消耗的内存约为140个字节.如果我将块的大小减小为仅包含2个字节的内存的数据,那么每个块至少需要6个字节.对于完全填充的100个元素集合,这将转换为不少于600个字节.有了这样的结果,您可能想知道为什么还要打扰稀疏数组.但是考虑另一种情况.可以说,数组中只有20个元素填充了10个元素 数组的开头,结尾是10.对于常规阵列,消耗的内存仍将至少为100个字节.对于稀疏数组,大约为28个字节.可能显而易见的是,当该稀疏数组部分填充并且填充的数据项彼此靠近聚集时,将出现最佳情况.
生长
常规阵列无法增长.分配后,其大小是固定的. .Net中还有其他可以增长的集合类,例如List 派生类或MemoryStream类.我的理解是,一旦消耗了所有这些类的内存缓冲区,它将分配一个新的内存缓冲区,其大小是原来的两倍,将所有数据复制到新的缓冲区中,然后丢弃旧的缓冲区稍后由垃圾回收回收.为了确认这一点,我找到了MemoryStream类的源代码.感兴趣的代码如下
//From <a href="https://singularity.svn.codeplex.com/svn/base/
// Libraries/System.IO/MemoryStream.cs">
// https://singularity.svn.codeplex.com/svn/base/Libraries/System.IO/MemoryStream.cs
private bool EnsureCapacity(int value) {
// Check for overflow
if (value < 0)
throw new IOException("IO.IO_StreamTooLong");
if (value > _capacity) {
int newCapacity = value;
if (newCapacity < 256)
newCapacity = 256;
if (newCapacity < _capacity * 2)
class="code-string">color: red;">newCapacity = _capacity * 2;
Capacity = newCapacity;[___strong_>
return true;
}
return false;
}
// Gets and sets the capacity (number of bytes allocated) for this stream.
// The capacity cannot be set to a value less than the current length
// of the stream.
//
//| <include file='doc\MemoryStream.uex' path='docs/doc[@for="MemoryStream.Capacity"]/*' />
public virtual int Capacity {
get {
if (!_isOpen) __Error.StreamIsClosed();
return _capacity - _origin;
}
set {
if (!_isOpen) __Error.StreamIsClosed();
if (value != _capacity) {
if (!_expandable) __Error.MemoryStreamNotExpandable();
if (value < _length) throw new ArgumentOutOfRangeException("value", "ArgumentOutOfRange_SmallCapacity");
if (value > 0) {
[__strong style=<span class="code-string">color: red;">byte[] newBuffer = new byte[value];
if (_length > 0) Buffer.BlockCopy(_buffer, 0, newBuffer, 0, _length);
_buffer = newBuffer;
}
else {
_buffer = null;
}
_capacity = value;
}
}
}
在典型情况下,此行为很好,但我将使用相对较大的缓冲区(与运行代码的设备上的可用内存相比).因此,我更希望为我所想到的程序中出现的最大内存分配量设置上限.还值得一提的是,.Net运行时对"大"对象的处理与对小对象的处理不同.有关更多信息,请查看大对象堆的危险.大对象(大约85,000字节或更大)或与小对象(小于85,000字节)相比分配在单独的堆上.在垃圾回收期间,.Net垃圾回收器将尝试将较小堆中的对象压缩为连续的内存. LOH(大对象堆)中的对象不那么容易处理.从引用的文章中: [.NET 4.5中的LOH中有改进](http://blogs.msdn.com/b/dotnet/archive/2011/10/03/large-object-heap-improvements-in-net-4-5 .aspx).另请注意,在内存受限的设备(例如Windows Phone)上没有LOH.但是,避免碎片化的内存条件仍然有优势.
块的集合
尽管我编写的代码是一种收集类,但是代码仍然依赖于收集类来保存其拥有的块.为此可以使用" List “类之一,也可以使用” Dictionary <T1,T2>“类.我决定使用List <T>
.现在,我谈论” List “类的内存使用模式并不令人怀疑,现在我正在其基础实现中使用它!这是否会导致我上面所述的内存碎片问题?好吧,不,至少没有那么严重. List 包含对ArrayChunk实例的引用.因此这些将是4个字节或8个字节.让我们假设最坏的情况是8个字节.为了宽大对象的边界,数组列表将需要增长到10,000个以上的元素((85,000/8)=使ArrayList变大所需的项目数.85,000是大对象的大小,而8是字节数).存储参考).使数组列表达到此大小所需的元素数量将取决于每个" ArrayChunk"中允许存储的元素数量.当阵列的大小确实足以占据LOH区域时,此方案仍比常规阵列更好,因为占据LOH的内存块小于连续的LOH数组占用的内存块.要素. 对于本文撰写的代码中稀疏数组的功能," Linked''List <T>会是合适的(实际上更合适).我使用的List <T>主要是在列表中向前和向后移动(我编写代码时假设对列表的读写将趋于彼此靠近).我使用了List <T>,因为它似乎更适合我将来计划对此代码进行的一些修改.由于这些计划可能会更改,因此我现在不详细介绍它们.因此,这些计划确实发生了变化,然后我可以将" List <T>"替换为" LinkedList <T>".当我进行更改时,我想确保我不会破坏该类的任何现有行为.该代码的项目还包含一些单元测试,以验证Array
List ``的行为是否与预期没有差异.
测试中
该代码中包含一个小型测试项目.随着时间的流逝,它将变得越来越重要,因为当我在此代码中添加内容时,我想确保自己不会破坏任何已经存在的行为.现在,测试只是检查数组的虚拟大小,确保按预期方式分配或释放内存块,并保留数据.
什么是EmptyValue?
在稀疏数组中,未写入的单元将被视为存在,并且它们包含一些默认值.该默认值存储在EmptyValue''中.该成员有多种用途.如果尝试从未分配的单元中读取,则返回
EmptyValue''.当稀疏数组正在搜索要分配的块时,它将检查该块的内容,以查看其所有元素是否都等于” EmptyValue".当实例化一个新的SparseArray时,通过为它所托管的类型调用默认的构造函数/初始化程序来初始化EmptyValue字段.对于数字类型,这将最终为零值.如果这不适用于您使用的数据类型,则有一个名为IsEmptyValue
的委托,您可以向其分配一个返回" true"的方法,以指示应将值或实例视为空,而`否则为假.
使用代码
此代码的使用与您使用强类型固定大小数组的方式没有太大不同.主要的区别是SparseArray 的上限根据需要增长,以适应对最小位置的写入.从超出上限的位置进行读取不会导致异常.如果有人从大于数组大小的索引读取数据,它将保持不变.但是,如果有人写了一个超出上限的位置,那么该数组将更新其报告的大小,并在需要时分配一个" ArrayChunk".
类接口
使用范例
//Initialize an instance of the array
SparseArray<int> myArray = new SparseArray<int>();
//Populate the array with a few elements
myArray[15] = 23;
myArray[1024] = 2;
//Print the size of the array. Will be 1025 (remember this is a zero based array)
Console.Out.WriteLine("Virtual size of the array: {0}", myArray.Length);
//Read from a position beyond the limit
Console.Out.WriteLine("Value in position 2048 : {0}", myArray[2048]);
//Print the size of the array. Will be 1025 (remember this is a zero based array)
Console.Out.WriteLine("Virtual size of the array: {0}", myArray.Length);
//Show how many chunks the sparse array has.
Console.Out.WriteLine("Chunk count: {0}", myArray.ChunkCount);
//Set the only populated element in the second chunk to zero and then condense the array
myArray[1024] = 0;
myArray.Condense();
//Check the chunk size again. It should be reduced.
Console.Out.WriteLine("Chunk count: {0}", myArray.ChunkCount);
许可
本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。
C# .NET Dev Intermediate 新闻 翻译