快速将350m的数字加载到C中的双[]数组中#

你可能已经回答的第一个问题是“这必须预先计算吗?”.是否有一些算法可以使您根据需要计算所需值以避免此问题?假设不…

这只是2.6GB的数据——在64位处理器上,这样的数据量很小,您就不会有问题了。但是,如果你在一台5年前有10年历史的操作系统的电脑上运行,那么它就不是入门级的了,因为这么多的数据会立即填满32位应用程序的可用工作集。

C++中显而易见的一种方法是使用内存映射文件。这使得数据在您的应用程序中看起来像是在RAM中,但是操作系统实际上只在访问数据时才将其位分页,因此很少使用真正的RAM。我不确定你是否能直接从C语言中做这件事,但是你可以很容易地在C++中使用它,然后从C语言访问它。

或者,假设“你同时需要RAM中的所有信息”的问题已经被回答为“是”,那么你就不能使用任何类型的虚拟化方法,所以……

在多个线程中加载不会有帮助-您将受到I/O绑定,因此您将 n 等待数据的线程(并要求硬盘在正在读取的块之间进行查找)而不是一个线程在等待数据(按顺序读取,不进行查找)。所以线程只会引起更多的寻找,因此很可能会使它变慢。(拆分数据可能有帮助的唯一情况是,如果您将数据拆分到不同的物理磁盘,以便可以并行读取不同的数据块-不要在软件中这样做;购买一个RAID阵列)

多线程可能有帮助的唯一地方是在应用程序其余部分启动时在后台进行加载,并允许用户在缓冲区其余部分填充时开始使用已经加载的数据部分,因此用户(希望)在加载数据时不必等待太久。

所以,你可以在一个线程中将数据加载到一个大数组中…

但是,您可以通过压缩数据来大大加快速度。有两种一般方法可以考虑:

• 如果您对数据有所了解,那么您可以发明一种编码方案,使数据更小(因此加载更快)。例如,如果值趋向于彼此接近(例如,假设描述正弦波的数据点-值的范围从非常小到非常大,但每个值仅比上一个值小增量),则可以在不损失原始双精度值的情况下,在浮点中表示“delta”,将数据大小减半。e.如果数据有任何对称或重复,您可能能够利用它(例如,想象存储所有位置来描述一个完整的圆,而不是存储一个象限,并使用一些简单而快速的数学来反映它4次-一种简单的方法来四分之一的数据I/O量)。数据大小的任何减少都会相应地减少加载时间。此外,这些方案中的许多都允许数据在RAM中保持“编码”状态,因此您使用的RAM要少得多,但仍然能够在需要时快速获取数据。

• 或者,您可以使用通用的压缩算法(如deflate)非常容易地包装流。这可能不起作用,但通常在CPU上解压缩数据的成本比通过加载更少的源数据节省的I/O时间要少,因此最终结果是加载速度明显更快。当然,也可以节省磁盘空间。

我做了一个小测试,我绝对推荐使用内存映射文件。 我创建了一个包含350m双值(前面提到的2.6GB)的文件,然后测试将文件映射到内存,然后访问任何元素所需的时间。

在我的笔记本电脑(Win7,.NET 4.0,Core2 Duo 2.0 GHz,4GB RAM)中的所有测试中,映射文件所用的时间不到一秒钟,在这一点上,访问任何元素几乎需要0毫秒(所有时间都在索引的验证中)。 然后我决定浏览所有350m的数字,整个过程花费了大约3分钟(包括分页),所以如果在您的例子中,您必须迭代它们,那么它们可能是另一个选项。

尽管如此,我还是对访问进行了包装,例如出于某些目的,在使用此代码之前,您应该检查很多条件,并且它看起来是这样的

public class Storage<T> : IDisposable, IEnumerable<T> where T : struct
{
    MemoryMappedFile mappedFile;
    MemoryMappedViewAccessor accesor;
    long elementSize;
    long numberOfElements;

    public Storage(string filePath)
    {
        if (string.IsNullOrWhiteSpace(filePath))
        {
            throw new ArgumentNullException();
        }

        if (!File.Exists(filePath))
        {
            throw new FileNotFoundException();
        }

        FileInfo info = new FileInfo(filePath);
        mappedFile = MemoryMappedFile.CreateFromFile(filePath);
        accesor = mappedFile.CreateViewAccessor(0, info.Length);
        elementSize = Marshal.SizeOf(typeof(T));
        numberOfElements = info.Length / elementSize;
    }

    public long Length
    {
        get
        {
            return numberOfElements;
        }
    }

    public T this[long index]
    {
        get
        {
            if (index < 0 || index > numberOfElements)
            {
                throw new ArgumentOutOfRangeException();
            }

            T value = default(T);
            accesor.Read<T>(index * elementSize, out value);
            return value;
        }
    }

    public void Dispose()
    {
        if (accesor != null)
        {
            accesor.Dispose();
            accesor = null;
        }

        if (mappedFile != null)
        {
            mappedFile.Dispose();
            mappedFile = null;
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        T value;
        for (int index = 0; index < numberOfElements; index++)
        {
            value = default(T);
            accesor.Read<T>(index * elementSize, out value);
            yield return value;
        }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        T value;
        for (int index = 0; index < numberOfElements; index++)
        {
            value = default(T);
            accesor.Read<T>(index * elementSize, out value);
            yield return value;
        }
    }

    public static T[] GetArray(string filePath)
    {
        T[] elements;
        int elementSize;
        long numberOfElements;

        if (string.IsNullOrWhiteSpace(filePath))
        {
            throw new ArgumentNullException();
        }

        if (!File.Exists(filePath))
        {
            throw new FileNotFoundException();
        }

        FileInfo info = new FileInfo(filePath);
        using (MemoryMappedFile mappedFile = MemoryMappedFile.CreateFromFile(filePath))
        {
            using(MemoryMappedViewAccessor accesor = mappedFile.CreateViewAccessor(0, info.Length))
            {
                elementSize = Marshal.SizeOf(typeof(T));
                numberOfElements = info.Length / elementSize;
                elements = new T[numberOfElements];

                if (numberOfElements > int.MaxValue)
                {
                    //you will need to split the array
                }
                else
                {
                    accesor.ReadArray<T>(0, elements, 0, (int)numberOfElements);
                }
            }
        }

        return elements;
    }
}

下面是一个如何使用类的示例

Stopwatch watch = Stopwatch.StartNew();
using (Storage<double> helper = new Storage<double>("Storage.bin"))
{
    Console.WriteLine("Initialization Time: {0}", watch.ElapsedMilliseconds);

    string item;
    long index;

    Console.Write("Item to show: ");
    while (!string.IsNullOrWhiteSpace((item = Console.ReadLine())))
    {
        if (long.TryParse(item, out index) && index >= 0 && index < helper.Length)
        {
            watch.Reset();
            watch.Start();
            double value = helper[index];
            Console.WriteLine("Access Time: {0}", watch.ElapsedMilliseconds);
            Console.WriteLine("Item: {0}", value);
        }
        else
        {
            Console.Write("Invalid index");
        }

        Console.Write("Item to show: ");
    }
}

更新 我添加了一个静态方法来将文件中的所有数据加载到数组中。显然,这种方法最初需要花费更多的时间(在我的笔记本电脑上需要1到2分钟),但在这之后,访问性能就是您对.NET的期望。如果必须经常访问数据,此方法应该很有用。

使用非常简单

double[] helper = Storage<double>.GetArray("Storage.bin");

高温高压

听起来您实际上不太可能将其放入内存中的一个连续数组中,所以您并行加载的方式取决于实际的数据结构。

(附录:Lukeh在评论中指出,clr中的对象大小实际上存在一个硬的2GB限制。这在 this other SO question )

假设您从一个磁盘读取整个内容,那么并行化磁盘读取可能是一个坏主意。如果在加载这些数字时或之后需要对它们进行任何处理,那么您可能需要考虑在从磁盘读取数据的同时并行运行这些数据。

在典型情况下,加载速度会受到从硬盘驱动器加载数据的存储速度的限制。

如果您希望它更快,您需要使用更快的存储,例如多个硬盘驱动器加入到一个RAID方案中。

如果您的数据可以合理压缩,那么就这样做。尝试寻找一种算法,它将使用尽可能多的CPU功率——小于这个值,您的外部存储速度将是限制因素;大于这个值,您的CPU速度将是限制因素。如果您的压缩算法可以使用多个内核,那么多线程就很有用。

如果您的数据在某种程度上是可预测的,那么您可能需要想出自定义压缩方案。例如,如果连续的数字彼此接近,您可能希望存储数字之间的差异——这可能有助于压缩效率。

你真的需要双精度吗?也许浮球可以做到?也许你不需要全套的双打?例如,如果需要完整的53位尾数精度,但只需要存储介于-1.0和1.0之间的数字,则可以尝试通过不在全范围内存储指数来切掉每个数字的几个位。

把这条平行线 坏的 除非你在固态硬盘上运行。限制因素是磁盘IO——如果运行两个线程,头部将在被读取的两个区域之间来回跳跃。这将比任何可能的并行加速都要慢得多。

记住驱动器是 机械的 与处理器相比,设备速度非常慢。如果你能做一百万个指令,以避免一个单一的头部寻求,你仍然会走在前面。

另外,一旦文件在磁盘上,请确保对磁盘进行碎片整理,以确保它在一个连续块中。

这对我来说不是个好主意。350000000*8字节=2800000000字节。即使你设法避免 OutOfMemoryException 过程 可以 无论如何都要换入/换出页面文件。您也可以将数据保留在文件中,并根据需要加载较小的卡盘。关键是因为你 可以 分配那么多内存并不意味着你 应该 .

使用合适的磁盘配置,跨磁盘拆分为多个文件是有意义的——然后在单独的线程中读取每个文件会很好地工作(如果您有一些条带性——raid-whatever:),那么从具有多个线程的单个文件中读取文件是有意义的。

不过,我认为你在用一个物理磁盘进行这种尝试,是在无中生有。

刚刚看到了这一点:.NET 4.0支持 memory mapped files . 这将是一种非常快速的方法,并且不需要支持并行化等。