Come ordinare una parte di un array con gli indici Int64 in C #?

Question

Il framework .Net ha un sovraccarico Array.Sort che permette di specificare la partenza e indicies finali per l'ordinamento di agire su. Tuttavia questi parametri sono solo a 32 bit. Quindi non vedo un modo per ordinare una parte di una grande matrice quando le indicies che descrivono la gamma tipo possono essere specificati solo utilizzando un numero a 64 bit. Suppongo che potrei copiare e modificare l'implementazione specie del quadro, ma che non è l'ideale.

Aggiornamento:

Ho creato due classi di aiutarmi intorno a questi e altri problemi di grandi array. altro Uno di questi è stato molto tempo prima di arrivare al mio limite di memoria, comincio ottenere OutOfMemoryException di. Sto assumendo questo è perché la memoria richiesta può essere disponibile ma non contigui. Quindi, per questo, ho creato classe BigArray, che è un generico, considerevole elenco dinamico degli array. Ha un ingombro di memoria più piccola di classe elenco generico del quadro, e non richiede che l'intero array essere contigue. Non ho ancora testato il calo di prestazioni, ma sono sicuro che c'è.

  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 tornando alla questione originaria di smistamento ... Quello che ho veramente bisogno era un modo di agire su ogni elemento di un array, in ordine. Ma con tali grandi array, è proibitivo per copiare i dati, specie esso, agire su di esso e quindi eliminare la copia filtrate (l'ordine originale deve essere mantenuto). Così ho creato OrderedOperation classe statica, che consente di eseguire un'operazione arbitraria su ciascun elemento di un array non ordinato, in un modo ordinato. E farlo con una bassa impronta di memoria (memory negoziazione per il tempo di esecuzione qui).

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

Le due classi possono lavorare insieme (è così che io li uso), ma non è necessario. Spero che qualcun altro li trova utili. Ma lo ammetto, sono classi case frangia. Domande benvenuto. E se il mio codice fa schifo, mi piacerebbe sentire punte, troppo.

Un pensiero finale: Come si può vedere nel OrderedOperation, sto usando int e non Longs. Attualmente questo è sufficiente per me, nonostante la domanda iniziale che ho avuto (l'applicazione è in continuo mutamento, nel caso in cui non si può dire). Ma la classe dovrebbe essere in grado di gestire anela così, in caso di necessità.

Answer 1

Troverete che anche sul quadro a 64 bit, il numero massimo di elementi di un array è int.MaxValue.

I metodi esistenti che prendono o restituiscono Int64 appena lanciato i long valori Int32 internamente e, nel caso di parametri, si genera un ArgumentOutOfRangeException se un parametro int.MinValue non è tra < => e LongLength.

Ad esempio la Length proprietà, che restituisce un Sort, appena getta e restituisce il valore della proprietà <=>:

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

Quindi il mio suggerimento sarebbe quello di lanciare i vostri <=> indicies a <=> e quindi chiamare uno degli overload esistenti <=>.

Answer 2

Dal Array.Copy prende params Int64, si potrebbe tirare fuori la sezione è necessario ordinare, selezionare, poi rimetterlo. Supponendo che si sta smistamento meno di 2 ^ 32 elementi, naturalmente.

Answer 3

Sembra come se si ordina più di 2 ^ 32 elementi allora sarebbe meglio scrivere il proprio, più efficienti, specie algoritmica comunque.