تحويل مجموعة إلى مجموعة قليلا

Question

وأنا أكتب قطعة الوقت الحرج من التعليمات البرمجية في C # تتطلب مني أن تحويل اثنين من الأعداد الصحيحة غير الموقعة التي تحدد نطاق شامل في حقل قليلا. مثال:

uint x1 = 3;
uint x2 = 9;
  //defines the range [3-9]
  //                              98  7654 3
  //must be converted to:  0000 0011  1111 1000

وانها قد تساعد على تصور البتات في ترتيب عكسي

والحد الأقصى لقيمة هذا النطاق هي معلمة معينة في وقت التشغيل التي سوف ندعو max_val. لذلك، يجب أن تعرف بأنها مجموعة UInt32 مع حجم يساوي max_val/32 المتغير حقل بت:

UInt32 MAX_DIV_32 = max_val / 32;
UInt32[] bitArray = new UInt32[MAX_DIV_32];

وبالنظر إلى نطاق محدد من قبل x1 المتغيرات وx2، ما هو أسرع وسيلة لتنفيذ هذا التحويل؟

Answer 1

وجرب هذا. حساب مجموعة من البنود مجموعة التي يجب أن تكون مليئة بكل تلك والقيام بذلك عن طريق بالتكرار عبر هذا النطاق. وأخيرا تعيين العناصر في كل من الحدود.

Int32 startIndex = x1 >> 5;
Int32 endIndex = x2 >> 5;

bitArray[startIndex] = UInt32.MaxValue << (x1 & 31);

for (Int32 i = startIndex + 1; i <= endIndex; i++)
{
   bitArray[i] = UInt32.MaxValue;
}

bitArray[endIndex] &= UInt32.MaxValue >> (31 - (x2 & 31));

قد يكون رمز ليست صحيحة 100٪، ولكن يجب أن تعمل هذه الفكرة.

---

وفقط اختباره وجدت ثلاثة البق. حساب في مؤشر بدء مطلوب مؤشر وزارة الدفاع 32 و في نهاية ال 32 يجب أن يكون 31 ومنطقية وبدلا من الاحالة للتعامل مع حالة بداية ونهاية مؤشر كونها نفسه. يجب أن تكون سريعة جدا.

---

وفقط مميزا مع المساواة في توزيع X1 و x2 خلال مجموعة. إنتل كور 2 ديو E8400 3.0 غيغاهرتز، MS VirtualPC مع خادم 2003 R2 على المضيف ويندوز XP.

Array length [bits]           320         160         64
Performance [executions/s]    33 million  43 million  54 million

---

واحد أكثر optimazation س٪ 32 == س و 31 لكنني غير قادر على meassure مكاسب الأداء. بسبب التكرار فقط 10.000.000 في اختباري تقلبات مرتفعة جدا. وأنا على التوالي في VirtualPC جعل الوضع أكثر لا يمكن التنبؤ بها.

Answer 2

وبلدي حل لوضع مجموعة كاملة من البتات في BitArray إلى صواب أو خطأ:

public static BitArray SetRange(BitArray bitArray, Int32 offset, Int32 length, Boolean value)
{

    Int32[] ints = new Int32[(bitArray.Count >> 5) + 1];

    bitArray.CopyTo(ints, 0);

    var firstInt = offset >> 5;
    var lastInt = (offset + length) >> 5;

    Int32 mask = 0;

    if (value)
    {
        // set first and last int
        mask = (-1 << (offset & 31));
        if (lastInt != firstInt)
            ints[lastInt] |= ~(-1 << ((offset + length) & 31));
        else
            mask &= ~(-1 << ((offset + length) & 31));

        ints[firstInt] |= mask;

        // set all ints in between
        for (Int32 i = firstInt + 1; i < lastInt; i++)
            ints[i] = -1;
    }

    else
    {
        // set first and last int
        mask = ~(-1 << (offset & 31));
        if (lastInt != firstInt)
            ints[lastInt] &= -1 << ((offset + length) & 31);
        else
            mask |= -1 << ((offset + length) & 31);

        ints[firstInt] &= mask;

        // set all ints in between
        for (Int32 i = firstInt + 1; i < lastInt; i++)
            ints[i] = 0;

    }

    return new BitArray(ints) { Length = bitArray.Length };

}

Answer 3

ويمكنك أن تحاول:

UInt32 x1 = 3;
UInt32 x2 = 9;
UInt32 newInteger = (UInt32)(Math.Pow(2, x2 + 1) - 1) & 
                   ~(UInt32)(Math.Pow(2, x1)-1);

Answer 4

هل هناك سبب لعدم استخدام فئة System.Collections.BitArray بدلا من UInt32 []؟ وإلا، فما استقاموا لكم فاستقيموا محاولة شيء من هذا القبيل:

int minIndex = (int)x1/32;
int maxIndex = (int)x2/32;
// first handle the all zero regions and the all one region (if any)
for (int i = 0; i < minIndex; i++) {
    bitArray[i] = 0;
}
for (int i = minIndex + 1; i < maxIndex; i++) {
    bitArray[i] = UInt32.MaxValue; // set to all 1s
}
for (int i = maxIndex + 1; i < MAX_DIV_32; i++) {
    bitArray[i] = 0;
}

// now handle the tricky parts
uint maxBits = (2u << ((int)x2 - 32 * maxIndex)) - 1; // set to 1s up to max
uint minBits = ~((1u << ((int)x1 - 32 * minIndex)) - 1); // set to 1s after min

if (minIndex == maxIndex) {
    bitArray[minIndex] = maxBits & minBits;
}
else {
    bitArray[minIndex] = minBits;
    bitArray[maxIndex] = maxBits;
}

Answer 5

وكنت بالملل بما فيه الكفاية لمحاولة القيام بذلك مع مجموعة char واستخدام Convert.ToUInt32(string, int) تحويله إلى uint من قاعدة 2.

uint Range(int l, int h)
{
  char[] buffer = new char[h];
  for (int i = 0; i < buffer.Length; i++)
  {
    buffer[i] = i < h - l ? '1' : '0';
  }
  return Convert.ToUInt32(new string(buffer), 2);
}

وهناك مؤشر بسيط يظهر أن لي طريقة أسرع حوالي 5٪ من Angrey جيم (حتى إذا قمت باستبدال أسير الحرب الثانية مع تحول بعض الشيء).

وربما يكون من الأسهل لتحويل لإنتاج مجموعة uint إذا كان الحد الأعلى هو كبير جدا لتناسب int احد. انها خفي قليلا ولكن أعتقد أنه يعمل.

uint[] Range(int l, int h)
{
  char[] buffer = new char[h];
  for (int i = 0; i < buffer.Length; i++)
  {
    buffer[i] = i < h - l ? '1' : '0';
  }

  int bitsInUInt = sizeof(uint) * 8;
  int numNeededUInts = (int)Math.Ceiling((decimal)buffer.Length /
                                         (decimal)bitsInUInt);
  uint[] uints = new uint[numNeededUInts];
  for (int j = uints.Length - 1, s = buffer.Length - bitsInUInt;
       j >= 0 && s >= 0;
       j--, s -= bitsInUInt)
  {
    uints[j] = Convert.ToUInt32(new string(buffer, s, bitsInUInt), 2);
  }

  int remainder = buffer.Length % bitsInUInt;
  if (remainder > 0)
  {
    uints[0] = Convert.ToUInt32(new string(buffer, 0, remainder), 2);
  }

  return uints;
}

Answer 6

وجرب هذا:

uint x1 = 3;
uint x2 = 9;

int cbToShift = x2 - x1; // 6
int nResult = ((1 << cbToShift) - 1) << x1; 

/*
  (1<<6)-1 gives you 63 = 111111, then you shift it on 3 bits left
*/