Wie ein Teil eines Arrays mit int64 Indizes in C # sortieren?

Question

Das .NET Framework verfügt über eine Array.Sort Überlastung, dass man die Start- und End-indicies für die Art zu handeln, auf angeben können. Allerdings sind diese Parameter nur 32 Bit. So sehe ich nicht einen Weg, um einen Teil eines großen Array zu sortieren, wenn die Indices, die den Sortierbereich beschreiben nur angegeben werden, können eine 64-Bit-Nummer. Ich glaube, ich könnte das der Rahmen der Art Implementierung kopieren und ändern, aber das ist nicht ideal.

Update:

Ich habe zwei Klassen erstellt mich um diese und andere große Array-Problemen zu helfen. Ein anderes solches Problem war, dass lange bevor ich zu meinem Speicherlimit bekam, beginne ich OutOfMemoryException des bekommen. Ich gehe davon aus das ist, weil der angeforderte Speicher verfügbar sein kann, aber nicht zusammenhängend. Also für das, habe ich Klasse BigArray, die eine generische, dynamisch ansehnliche Liste von Arrays ist. Es hat einen kleineren Speicherbedarf als die generische Liste Klasse Rahmen und erfordert nicht, dass die gesamte Anordnung zusammenhängend sein. Ich habe nicht die Leistung getroffen getestet, aber ich bin sicher, dass sein dort.

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

  }

Und wieder auf die ursprüngliche Ausgabe des Sortierens bekommen ... Was ich wirklich brauchte, war ein Weg für jedes Element eines Arrays zu handeln, um. Aber mit so großen Arrays, ist es untragbar, die Daten zu kopieren, sortieren sie, auf ihn einwirken und dann verwirft die sortierte Kopie (die ursprüngliche Reihenfolge eingehalten werden muss). Also habe ich statische Klasse OrderedOperation, die Sie eine beliebige Operation auf jedes Element eines unsortierten Array, in einer sortierten Reihenfolge ausführen können. Und dies mit einem geringen Speicherbedarf (Handelsspeicher für die Ausführungszeit hier).

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

Die beiden Klassen zusammenarbeiten können (das ist, wie ich sie verwenden), aber sie müssen nicht. Ich hoffe, dass jemand anderes sie nützlich findet. Aber ich gebe zu, sie sind fringe Fallklassen. Fragen willkommen. Und wenn mein Code saugt, ich möchte Tipps hören, auch.

Ein letzter Gedanke: Wie Sie OrderedOperation sehen können, ich bin mit ints und nicht sehnt. Zur Zeit ist, dass ausreichend für mich trotz der ursprünglichen Frage hatte ich (die Anwendung im Fluss ist, falls Sie nicht sagen können). Aber die Klasse sollte in der Lage sein, sehnt sich zu handhaben und sollte die Notwendigkeit entstehen.

Answer 1

Sie werden feststellen, dass auch auf den 64-Bit-Rahmen, die maximale Anzahl der Elemente in einem Array ist int.MaxValue.

Die bestehenden Methoden, die Int64 nehmen oder Rückkehr nur die long Werte werfen intern Int32 und im Falle von Parametern wird eine ArgumentOutOfRangeException auslösen, wenn ein long Parameter nicht zwischen int.MinValue und int.MaxValue ist.

Zum Beispiel der LongLength Eigenschaft, die ein Int64 zurückzugibt, nur wirft und gibt den Wert der Length Eigenschaft:

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

Also mein Vorschlag wäre Ihre Int64 indicies zu gieße Int32 und rufen Sie dann eine der vorhandenen Sort Überlastungen.

Answer 2

Da Array.Copy Int64 params nimmt, können Sie den Abschnitt, den Sie sortieren müssen herausziehen, sortieren sie, es dann wieder einsetzen. Angenommen, Sie sind das Sortieren von weniger als 2 ^ 32 Elemente, natürlich.

Answer 3

Scheint, wie wenn Sie mehr als 2 ^ 32 Elemente Sortierung dann wäre es am besten Ihre eigene, effizienter zu schreiben, eine Art ohnehin Algorithmus.