如何在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中看到的那样,我使用的是int而不是long.目前这对我来说已经足够了,尽管我遇到了原始问题(应用程序不断变通,如果您无法分辨).但是,如果需要,班级也应该能够处理多头.

Answer 1

您会发现即使在64位框架上,数组中的最大元素数也是如此int.MaxValue.

采用或返回的现有方法Int64只是将long值转换为Int32内部,并且在参数的情况下,将抛出ArgumentOutOfRangeExceptionif long参数不在int.MinValue和之间int.MaxValue.

例如LongLength,返回an 的属性Int64只是强制转换并返回Length属性的值:

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

所以我的建议是将你的指标投射Int64到Int32然后调用其中一个现有的Sort重载.