¿Cómo ordenar una parte de una matriz con índices int64 en C#?

Question

El marco .Net tiene una sobrecarga Array.Sort que permite especificar los índices inicial y final para que actúe la clasificación.Sin embargo, estos parámetros son sólo de 32 bits.Por lo tanto, no veo una manera de ordenar una parte de una matriz grande cuando los índices que describen el rango de clasificación solo se pueden especificar usando un número de 64 bits.Supongo que podría copiar y modificar la implementación de clasificación del marco, pero eso no es lo ideal.

Actualizar:

He creado dos clases para ayudarme con estos y otros problemas de gran variedad.Otro problema de este tipo fue que mucho antes de llegar a mi límite de memoria, empiezo a recibir OutOfMemoryException.Supongo que esto se debe a que la memoria solicitada puede estar disponible pero no contigua.Entonces, para eso, creé la clase BigArray, que es una lista de matrices genérica y de tamaño dinámico.Tiene una huella de memoria menor que la clase de lista genérica del marco y no requiere que toda la matriz sea contigua.No he probado el impacto en el rendimiento, pero estoy seguro de que está ahí.

  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();
    }

  }

Y volviendo al tema original de la clasificación...Lo que realmente necesitaba era una manera de actuar sobre cada elemento de una matriz, en orden.Pero con matrices tan grandes, es prohibitivo copiar los datos, ordenarlos, actuar en consecuencia y luego descartar la copia ordenada (se debe mantener el orden original).Entonces creé la clase estática OrderedOperation, que le permite realizar una operación arbitraria en cada elemento de una matriz sin clasificar, en un orden ordenado.Y hágalo con una huella de memoria baja (aquí intercambia memoria por tiempo de ejecución).

  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);
    }
  }

Las dos clases pueden funcionar juntas (así es como las uso), pero no es necesario.Espero que alguien más los encuentre útiles.Pero lo admito, son clases de casos marginales.Se aceptan preguntas.Y si mi código apesta, también me gustaría recibir sugerencias.

Un último pensamiento:Como puedes ver en OrderedOperation, estoy usando enteros y no largos.Actualmente eso es suficiente para mí a pesar de la pregunta original que tenía (la aplicación está cambiando, en caso de que no lo sepas).Pero la clase también debería poder manejar posiciones largas, en caso de que surgiera la necesidad.

Answer 1

Descubrirá que incluso en el marco de 64 bits, el número máximo de elementos en una matriz es int.MaxValue.

Los métodos existentes que toman o regresan Int64 simplemente lanza el long valores a Int32 internamente y, en el caso de parámetros, arrojará un ArgumentOutOfRangeException si un long El parámetro no está entre int.MinValue y int.MaxValue.

Por ejemplo el LongLength propiedad, que devuelve un Int64, simplemente lanza y devuelve el valor de Length propiedad:

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

Entonces mi sugerencia sería emitir tu Int64 indicios de Int32 y luego llamar a uno de los existentes Sort sobrecargas.

Answer 2

Desde Array.Copy toma params Int64, se podía sacar la sección que necesita para ordenar, clasificar, a continuación, poner de nuevo. Suponiendo que estés clasificación de menos de 2 ^ 32 elementos, por supuesto.

Answer 3

Parece como si está ordenando más de 2 ^ 32 elementos, entonces sería mejor para escribir su propia, más eficiente, más o menos de algoritmos de todos modos.