Como classificar uma parte de uma matriz com int64 índices em C #?

Question

O framework .Net tem uma sobrecarga Array.Sort que permite especificar os indicies começando e terminando para o tipo de agir. No entanto, estes parâmetros são apenas 32 bits. Então eu não vejo uma maneira de ordenar uma parte de uma grande variedade quando os indicies que descrevem o intervalo de classificação só pode ser especificado usando um número de 64 bits. Acho que eu poderia copiar e modificar a implementação de classificação do quadro, mas isso não é o ideal.

Update:

Eu criei duas classes para me ajudar em torno destas e outras questões de grande matriz. outra Uma dessas questões foi que muito antes de eu cheguei ao meu limite de memória, eu começar a receber OutOfMemoryException de. Estou assumindo que este é porque a memória requerida pode estar disponível, mas não contíguos. Então, para isso, eu criei classe BigArray, que é uma lista genérica, de forma dinâmica considerável de matrizes. Ele tem uma pegada de memória menor do que a classe lista genérica do quadro, e não requer que toda a matriz ser contíguos. Eu não testei o impacto no desempenho, mas tenho certeza que a sua existência.

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

  }

E voltar para a emissão inicial de triagem ... O que eu realmente precisava era uma maneira de agir em cada elemento de uma matriz, em ordem. Mas com esses grandes matrizes, é proibitivo para copiar os dados, classificá-lo, agir sobre ela e, em seguida, descartar a cópia ordenada (a ordem original deve ser mantida). Então, eu criei OrderedOperation classe estática, que permite que você executar uma operação arbitrária em cada elemento de uma matriz não ordenada, em uma ordem de classificação. E fazê-lo com uma pegada de baixa memória (memória de negociação para o tempo de execução aqui).

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

As duas classes podem trabalhar juntos (é assim que eu usá-los), mas eles não têm que. Espero que alguma outra pessoa encontra-los úteis. Mas vou admitir, eles são classes de casos de franja. Perguntas bem-vindos. E se o meu código é uma porcaria, eu gostaria de ouvir dicas também.

Um pensamento final: Como você pode ver na OrderedOperation, estou usando ints e não longos. Atualmente isso é suficiente para mim, apesar da pergunta original que eu tinha (a aplicação está em fluxo, no caso de você não pode dizer). Mas a classe deve ser capaz de longs punho, bem como, em caso de necessidade surgir.

Answer 1

Você vai descobrir que, mesmo no quadro de 64 bits, o número máximo de elementos em uma matriz é int.MaxValue.

Os métodos existentes que levam ou Int64 retorno apenas converter os valores long para Int32 internamente e, no caso de parâmetros, irá lançar uma ArgumentOutOfRangeException se um parâmetro long não é entre int.MinValue e int.MaxValue.

Por exemplo, a propriedade LongLength, que retorna uma Int64, apenas moldes e retorna o valor da propriedade Length:

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

Assim, a minha sugestão seria a de lançar seus indicies Int64 para Int32 e depois chamar uma das sobrecargas Sort existentes.

Answer 2

Desde Array.Copy leva params Int64, você poderia retirar a seção que você precisa para classificar, classificá-lo, em seguida, colocá-lo de volta. Supondo que você está classificando menos de 2 ^ 32 elementos, é claro.

Answer 3

Parece que se você está classificando mais de 2 ^ 32 elementos, então seria melhor para escrever o seu próprio, mais eficiente, tipo algoritmo de qualquer maneira.