كيفية فرز جزء من صفيف مع مؤشرات int64 في C #؟

Question

وعلى .NET Framework لديه الزائد Array.Sort أن يسمح احد لتحديد البداية وindicies الختامي لهذا النوع من العمل عليها. لكن هذه المعايير ليست سوى 32 بت. لذلك أنا لا أرى وسيلة لفرز جزء من مجموعة كبيرة عندما indicies التي تصف مجموعة النوع لا يمكن إلا أن تكون محددة باستخدام عدد 64 بت. أعتقد أنني يمكن نسخ وتعديل تنفيذ نوع الإطار، ولكن ليست مثالية.

تحديث:

ولقد خلق طبقتين لمساعدتي حول هذه القضايا وغيرها، مجموعة كبيرة. وكانت إحدى هذه المسألة الأخرى التي قبل فترة طويلة وصلت إلى حد ذاكرتي، وأبدأ الحصول على OutOfMemoryException. أفترض ذلك لأن الذاكرة المطلوبة قد تكون متوفرة ولكن لا متجاورة. حتى لذلك، أنا خلقت طبقة BigArray، وهو، قائمة كبيرة حيوي عامة من المصفوفات. لها أثر الذاكرة أصغر من الطبقة قائمة عامة الإطار، وولا يتطلب أن تكون مجموعة كاملة متجاورة. أنا لم تختبر ضرب الأداء، ولكن أنا متأكد من هناك.

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

  }

وبالعودة إلى قضية الأصلية الفرز ... ما أنا في حاجة حقا كان وسيلة للعمل على كل عنصر من عناصر مجموعة، في النظام. ولكن مع هذه صفائف كبيرة، فمن باهظة لنسخ البيانات وفرزها ذلك، تعمل عليه ثم تجاهل نسخة مرتبة (يجب المحافظة على الترتيب الأصلي). لذلك أنا خلقت OrderedOperation الطبقة ساكنة، والذي يسمح لك لإجراء عملية تعسفية على كل عنصر من عناصر مجموعة لم يتم فرزها، في ترتيب فرزها. وذلك مع بصمة الذاكرة منخفضة (ذاكرة التداول لوقت التنفيذ هنا).

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

والطبقات اثنين يمكن أن تعمل معا (هذه هي الطريقة التي يمكنني استخدامها)، ولكن لم يكن لديهم ل. آمل شخص آخر يجد من المفيد لهم. ولكن أنا أعترف، فهي فصول قضية هامشية. الأسئلة موضع ترحيب. وإذا تمتص قانون بلدي، أود أن أسمع نصائح، أيضا.

واحد نهائي الفكر: كما ترون في OrderedOperation، أنا باستخدام [إينتس] وليس صفقات الشراء. حاليا هذا كاف بالنسبة لي على الرغم من السؤال الأصلي كان (يكون التطبيق في حالة تغير مستمر، في حال كنت لا أستطيع أن أقول). ولكن الطبقة يجب أن تكون قادرة على التعامل مع صفقات الشراء وكذلك، إذا ما دعت الحاجة لذلك.

Answer 1

وستجد أنه حتى في إطار 64 بت، والحد الأقصى لعدد العناصر في مجموعة غير int.MaxValue.

والأساليب الحالية التي تأخذ أو العودة Int64 فقط يلقي القيم long إلى Int32 داخليا، وذلك في حالة من المعلمات، ورمي ArgumentOutOfRangeException إذا معلمة long ليست بين int.MinValue وint.MaxValue.

وعلى سبيل المثال الممتلكات LongLength، والتي ترجع إلى Int64، يلقي عادل وإرجاع قيمة العقار Length:

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

وهكذا اقتراحي سيكون للادلاء indicies Int64 لInt32 ومن ثم استدعاء أحد الزائدة Sort القائمة.

Answer 2

ومنذ Array.Copy يأخذ بارامس Int64، هل يمكن سحب القسم تحتاج إلى ترتيب، النوع، ثم وضعه مرة أخرى. على افتراض انك فرز أقل من 2 ^ 32 عناصر، بطبيعة الحال.

Answer 3

ويبدو أن إذا كنت فرز أكثر من 2 ^ 32 العناصر ثم قد يكون من الأفضل أن تكتب بنفسك وأكثر كفاءة، نوع الخوارزمية على أي حال.