Comment trier une partie d'un tableau avec des indices de int64 en C #?

Question

Le framework .Net a une surcharge Array.Sort qui permet de spécifier le début et de fin indicies pour le tri à agir. Cependant, ces paramètres ne sont que 32 bits. Je ne vois donc pas un moyen de trier une partie d'un large éventail lorsque les indicies qui décrivent la plage de tri ne peuvent être spécifiées à l'aide d'un numéro de 64 bits. Je suppose que je pourrais copier et modifier la mise en œuvre de tri de cadre, mais ce n'est pas idéal.

Mise à jour:

J'ai créé deux classes pour me aider autour de ces questions et d'autres grandes tableaux. Une autre question aussi était que longtemps avant que je suis arrivé à ma limite de mémoire, je commence à obtenir OutOfMemoryException de. Je suppose que c'est parce que la mémoire requise peut être disponible mais non contigus. Donc, pour cela, j'ai créé la classe Bigarray, qui est une liste générique, dynamique importante de tableaux. Il a une plus petite empreinte mémoire que la classe de liste générique du cadre, et ne nécessite pas que l'ensemble du réseau soit contigu. Je ne l'ai pas testé le succès de la performance, mais je suis sûr que son là.

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

  }

Et pour en revenir à la question initiale de tri ... Ce que je avais vraiment besoin était un moyen d'agir sur chaque élément d'un tableau, dans l'ordre. Mais avec ces grands tableaux, il est prohibitif pour copier les données, les trier, agir sur elle et jeter (doit être maintenu l'ordre d'origine) la copie triée. Donc, j'ai créé OrderedOperation de classe statique, ce qui vous permet d'effectuer une opération arbitraire sur chaque élément d'un tableau non trié, dans un ordre de tri. Et le faire avec une faible empreinte mémoire (mémoire de négociation pour le temps d'exécution ici).

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

Les deux classes peuvent travailler ensemble (ce qui est la façon dont je les utilise), mais ils ne sont pas obligés. J'espère que quelqu'un d'autre les trouve utiles. Mais je l'avoue, ce sont des classes de cas marginaux. Questions de bienvenue. Et si mon code suce, je voudrais entendre des conseils aussi.

Une dernière pensée: Comme vous pouvez le voir dans OrderedOperation, j'utilise ints et ne désire ardemment. À l'heure actuelle qui est suffisant pour moi, malgré la question initiale, j'ai eu (l'application est en pleine mutation, au cas où vous ne pouvez pas dire). Mais la classe doit être capable de gérer languit ainsi, en cas de besoin.

Answer 1

Vous trouverez que même sur le cadre 64 bits, le nombre maximum d'éléments dans un tableau est int.MaxValue.

Les méthodes existantes qui prennent ou reviennent simplement jeter les Int64 valeurs à long interne et Int32, dans le cas des paramètres, va jeter un si un paramètre ArgumentOutOfRangeException n'est pas entre int.MinValue < => et LongLength.

Par exemple, la propriété Length, qui retourne un Sort, juste et renvoie la jette valeur de la propriété <=>:

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

Donc, ma suggestion serait de jeter vos indicies à <=> puis appeler <=> l'une des surcharges existantes <=>.

Answer 2

Depuis Array.Copy prend params Int64, vous pouvez retirer la section que vous devez trier, trier, puis le remettre. En supposant que vous êtes le tri moins de 2 ^ 32 éléments, bien sûr.

Answer 3

On dirait que si vous triez plus de 2 ^ 32 éléments, il serait alors préférable d'écrire votre propre, plus efficace, l'algorithme de tri de toute façon.