如何用C_对数组的Int64指示符部分进行排序?

.NET框架有一个array.sort重载,允许指定排序的开始和结束指示符。然而,这些参数只有32位。因此,当描述排序范围的指标只能使用64位数字指定时,我看不到对大数组的一部分进行排序的方法。我想我可以复制和修改框架的排序实现,但这并不理想。

更新:

我创建了两个类来帮助我解决这些和其他大型数组问题。另一个问题是,在我达到内存限制之前很久,我就开始从内存异常中提取内存。我假设这是因为请求的内存可能是可用的,但不是连续的。为此,我创建了一个类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);
    }
  }

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

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