c# - 如何在 C# 中使用 int64 索引对数组的一部分进行排序？

Question

.Net 框架有一个 Array.Sort 重载，它允许指定要执行的排序的开始和结束索引。但是这些参数只有 32 位。因此，当描述排序范围的索引只能使用 64 位数字指定时，我看不到对大型数组的一部分进行排序的方法。我想我可以复制和修改框架的排序实现，但这并不理想。

更新:

我创建了两个类来帮助我解决这些问题和其他大型数组问题。另一个这样的问题是，在我达到内存限制之前很久，我就开始出现 OutOfMemoryException。我假设这是因为请求的内存可能可用但不连续。因此，为此，我创建了 BigArray 类，这是一个通用的、可动态调整大小的数组列表。它比框架的通用列表类占用内存更小，并且不需要整个数组是连续的。我没有测试性能影响，但我确定它在那里。

  public class BigArray<T> : IEnumerable<T>
  {
    private long capacity;
    private int itemsPerBlock;
    private int shift;
    private List<T[]> blocks = new List<T[]>();

    public BigArray(int itemsPerBlock)
    {
      shift = (int)Math.Ceiling(Math.Log(itemsPerBlock) / Math.Log(2));
      this.itemsPerBlock = 1 << shift;
    }

    public long Capacity
    {
      get
      {
        return capacity;
      }
      set
      {
        var requiredBlockCount = (value - 1) / itemsPerBlock + 1;
        while (blocks.Count > requiredBlockCount)
        {
          blocks.RemoveAt(blocks.Count - 1);
        }
        while (blocks.Count < requiredBlockCount)
        {
          blocks.Add(new T[itemsPerBlock]);
        }
        capacity = (long)itemsPerBlock * blocks.Count;
      }
    }

    public T this[long index]
    {
      get
      {
        Debug.Assert(index < capacity);
        var blockNumber = (int)(index >> shift);
        var itemNumber = index & (itemsPerBlock - 1);
        return blocks[blockNumber][itemNumber];
      }
      set
      {
        Debug.Assert(index < capacity);
        var blockNumber = (int)(index >> shift);
        var itemNumber = index & (itemsPerBlock - 1);
        blocks[blockNumber][itemNumber] = value;
      }
    }

    public IEnumerator<T> GetEnumerator()
    {
      for (long i = 0; i < capacity; i++)
      {
        yield return this[i];
      }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
      return this.GetEnumerator();
    }

  }

回到最初的排序问题……我真正需要的是一种按顺序对数组的每个元素进行操作的方法。但是对于如此大的数组，复制数据、排序、操作然后丢弃排序副本(必须保持原始顺序)是禁止的。所以我创建了静态类 OrderedOperation，它允许您按排序顺序对未排序数组的每个元素执行任意操作。并以低内存占用量执行此操作(此处以内存换取执行时间)。

  public static class OrderedOperation
  {
    public delegate void WorkerDelegate(int index, float progress);

    public static void Process(WorkerDelegate worker, IEnumerable<int> items, int count, int maxItem, int maxChunkSize)
    {
      // create a histogram such that a single bin is never bigger than a chunk
      int binCount = 1000;
      int[] bins;
      double binScale;
      bool ok;
      do
      {
        ok = true;
        bins = new int[binCount];
        binScale = (double)(binCount - 1) / maxItem;
        int i = 0;
        foreach (int item in items)
        {
          bins[(int)(binScale * item)]++;
          if (++i == count)
          {
            break;
          }
        }
        for (int b = 0; b < binCount; b++)
        {
          if (bins[b] > maxChunkSize)
          {
            ok = false;
            binCount *= 2;
            break;
          }
        }
      } while (!ok);

      var chunkData = new int[maxChunkSize];
      var chunkIndex = new int[maxChunkSize];
      var done = new System.Collections.BitArray(count);
      var processed = 0;
      var binsCompleted = 0;
      while (binsCompleted < binCount)
      {
        var chunkMax = 0;
        var sum = 0;
        do
        {
          sum += bins[binsCompleted];
          binsCompleted++;
        } while (binsCompleted < binCount - 1 && sum + bins[binsCompleted] <= maxChunkSize);
        Debug.Assert(sum <= maxChunkSize);
        chunkMax = (int)Math.Ceiling((double)binsCompleted / binScale);
        var chunkCount = 0;
        int i = 0;
        foreach (int item in items)
        {
          if (item < chunkMax && !done[i])
          {
            chunkData[chunkCount] = item;
            chunkIndex[chunkCount] = i;
            chunkCount++;
            done[i] = true;
          }
          if (++i == count)
          {
            break;
          }
        }
        Debug.Assert(sum == chunkCount);
        Array.Sort(chunkData, chunkIndex, 0, chunkCount);
        for (i = 0; i < chunkCount; i++)
        {
          worker(chunkIndex[i], (float)processed / count);
          processed++;
        }
      }
      Debug.Assert(processed == count);
    }
  }

这两个类可以一起工作(这就是我使用它们的方式)，但它们不是必须的。我希望其他人发现它们有用。但我承认，它们是边缘案例类。欢迎提问。如果我的代码很糟糕，我也想听听提示。

最后一个想法:正如您在 OrderedOperation 中看到的，我使用的是整数而不是长整数。目前这对我来说已经足够了，尽管我有最初的问题(应用程序在不断变化，以防你不知道)。但如果需要，该类也应该能够处理多头。

Answer 1

你会发现即使在 64 位框架上，数组中元素的最大数量也是 int.MaxValue。

接受或返回 Int64 的现有方法只是在内部将 long 值转换为 Int32，对于参数，将抛出ArgumentOutOfRangeException 如果 long 参数不在 int.MinValue 和 int.MaxValue 之间。

例如 LongLength 属性，它返回一个 Int64，只是转换并返回 Length 属性的值:

public long LongLength
{
    get { return (long)this.Length; }    // Length is an Int32
}

所以我的建议是将您的 Int64 索引转换为 Int32，然后调用现有的 Sort 重载之一。