Как отсортировать часть массива с указанием int64 в C #? - PullRequest
4 голосов
/ 12 мая 2009

.NET Framework имеет перегрузку 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, я использую целые, а не длинные. В настоящее время этого достаточно для меня, несмотря на первоначальный вопрос, который у меня возник (заявка постоянно меняется, если вы не можете сказать). Но класс должен уметь справляться с длинными, если возникнет такая необходимость.

Ответы [ 3 ]

5 голосов
/ 12 мая 2009

Вы обнаружите, что даже в 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 перегрузок.

1 голос
/ 12 мая 2009

Поскольку Array.Copy принимает параметры Int64, вы можете извлечь раздел, который нужно отсортировать, отсортировать, а затем вернуть обратно. Конечно, если вы сортируете менее 2 ^ 32 элементов.

0 голосов
/ 12 мая 2009

Похоже, если вы сортируете более 2 ^ 32 элементов, тогда было бы лучше написать собственный, более эффективный алгоритм сортировки.

...