استخراج بعض متواليات من طول التعسفي من byte[] مجموعة بكفاءة
https://stackoverflow.com/questions/3846711
-
27-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أنا أبحث عن الطريقة الأكثر فعالية استخراج (غير موقعة) بت متواليات من طول التعسفي (0 <= طول <= 16) في الموقف التعسفي.الهيكل العظمي الطبقة تظهر كيف الحالية تنفيذ أساسا يعالج المشكلة:
public abstract class BitArray {
byte[] bytes = new byte[2048];
int bitGet;
public BitArray() {
}
public void readNextBlock(int initialBitGet, int count) {
// substitute for reading from an input stream
for (int i=(initialBitGet>>3); i<=count; ++i) {
bytes[i] = (byte) i;
}
prepareBitGet(initialBitGet, count);
}
public abstract void prepareBitGet(int initialBitGet, int count);
public abstract int getBits(int count);
static class Version0 extends BitArray {
public void prepareBitGet(int initialBitGet, int count) {
bitGet = initialBitGet;
}
public int getBits(int len) {
// intentionally gives meaningless result
bitGet += len;
return 0;
}
}
static class Version1 extends BitArray {
public void prepareBitGet(int initialBitGet, int count) {
bitGet = initialBitGet - 1;
}
public int getBits(int len) {
int byteIndex = bitGet;
bitGet = byteIndex + len;
int shift = 23 - (byteIndex & 7) - len;
int mask = (1 << len) - 1;
byteIndex >>= 3;
return (((bytes[byteIndex] << 16) |
((bytes[++byteIndex] & 0xFF) << 8) |
(bytes[++byteIndex] & 0xFF)) >> shift) & mask;
}
}
static class Version2 extends BitArray {
static final int[] mask = { 0x0, 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF,
0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
public void prepareBitGet(int initialBitGet, int count) {
bitGet = initialBitGet;
}
public int getBits(int len) {
int offset = bitGet;
bitGet = offset + len;
int byteIndex = offset >> 3; // originally used /8
int bitIndex = offset & 7; // originally used %8
if ((bitIndex + len) > 16) {
return ((bytes[byteIndex] << 16 |
(bytes[byteIndex + 1] & 0xFF) << 8 |
(bytes[byteIndex + 2] & 0xFF)) >> (24 - bitIndex - len)) & mask[len];
} else if ((offset + len) > 8) {
return ((bytes[byteIndex] << 8 |
(bytes[byteIndex + 1] & 0xFF)) >> (16 - bitIndex - len)) & mask[len];
} else {
return (bytes[byteIndex] >> (8 - offset - len)) & mask[len];
}
}
}
static class Version3 extends BitArray {
int[] ints = new int[2048];
public void prepareBitGet(int initialBitGet, int count) {
bitGet = initialBitGet;
int put_i = (initialBitGet >> 3) - 1;
int get_i = put_i;
int buf;
buf = ((bytes[++get_i] & 0xFF) << 16) |
((bytes[++get_i] & 0xFF) << 8) |
(bytes[++get_i] & 0xFF);
do {
buf = (buf << 8) | (bytes[++get_i] & 0xFF);
ints[++put_i] = buf;
} while (get_i < count);
}
public int getBits(int len) {
int bit_idx = bitGet;
bitGet = bit_idx + len;
int shift = 32 - (bit_idx & 7) - len;
int mask = (1 << len) - 1;
int int_idx = bit_idx >> 3;
return (ints[int_idx] >> shift) & mask;
}
}
static class Version4 extends BitArray {
int[] ints = new int[1024];
public void prepareBitGet(int initialBitGet, int count) {
bitGet = initialBitGet;
int g = initialBitGet >> 3;
int p = (initialBitGet >> 4) - 1;
final byte[] b = bytes;
int t = (b[g] << 8) | (b[++g] & 0xFF);
final int[] i = ints;
do {
i[++p] = (t = (t << 16) | ((b[++g] & 0xFF) <<8) | (b[++g] & 0xFF));
} while (g < count);
}
public int getBits(final int len) {
final int i;
bitGet = (i = bitGet) + len;
return (ints[i >> 4] >> (32 - len - (i & 15))) & ((1 << len) - 1);
}
}
public void benchmark(String label) {
int checksum = 0;
readNextBlock(32, 1927);
long time = System.nanoTime();
for (int pass=1<<18; pass>0; --pass) {
prepareBitGet(32, 1927);
for (int i=2047; i>=0; --i) {
checksum += getBits(i & 15);
}
}
time = System.nanoTime() - time;
System.out.println(label+" took "+Math.round(time/1E6D)+" ms, checksum="+checksum);
try { // avoid having the console interfere with our next measurement
Thread.sleep(369);
} catch (InterruptedException e) {}
}
public static void main(String[] argv) {
BitArray test;
// for the sake of getting a little less influence from the OS for stable measurement
Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
while (true) {
test = new Version0();
test.benchmark("no implementaion");
test = new Version1();
test.benchmark("Durandal's (original)");
test = new Version2();
test.benchmark("blitzpasta's (adapted)");
test = new Version3();
test.benchmark("MSN's (posted)");
test = new Version4();
test.benchmark("MSN's (half-buffer modification)");
System.out.println("--- next pass ---");
}
}
}
يعمل هذا, ولكن أنا أبحث عن أكثر الحلول كفاءة (أداء الحكمة).صفيف بايت هو ضمان أن تكون صغيرة نسبيا بين عدد قليل بايت بحد أقصى من ~1800 بايت.مجموعة قراءة بالضبط مرة واحدة (تماما) بين كل استدعاء الأسلوب قراءة.ليست هناك حاجة لأي تدقيق الأخطاء في getBits () ، مثل تتجاوز مجموعة إلخ.
يبدو أن سؤالي الأول أعلاه ليست واضحة بما فيه الكفاية.قليلا "تسلسل" من N بت أشكال صحيح من N بت و أنا بحاجة إلى استخراج تلك الأعداد الصحيحة مع الحد الأدنى من النفقات العامة.انا لا استخدم سلاسل القيم إما أن تستخدم كما بحث مؤشرات أو مباشرة الاحتياطي الفيدرالي في بعض الحسابات.وذلك أساسا, الهيكل العظمي هو مبين أعلاه هي الدرجة الحقيقية و getBits() التوقيع يدل على مدى بقية رمز يتفاعل معها.
Extendet المثال التعليمات البرمجية في microbenchmark ، وشملت blitzpasta الحل (الثابتة في عداد المفقودين بايت اخفاء).على القديم AMD مربع اتضح كما ~11400ms vs ~38000ms.لمعلوماتك:في فرق مودولو العمليات التي تقتل الأداء.إذا قمت باستبدال /8 مع >>3 و %8 مع &7, سواء الحلول هي قريبة جدا من بعضها البعض (jdk1.7.0ea104).
يبدو أن هناك بعض الالتباس حول ما العمل.أول الأصلي بعد التعليمة البرمجية الموجودة في المثال تضمنت قراءة() الأسلوب للإشارة إلى أين ومتى بايت العازلة امتلأ.هذا ضاعت عندما كان رمز تحولت إلى microbench.أعيد عرض هذا قليلا أكثر وضوحا.الفكرة هي للتغلب على جميع الإصدارات الحالية من خلال إضافة أخرى فرعية من BitArray التي تحتاج إلى تنفيذ getBits() و prepareBitGet () ، وهذه الأخيرة قد تكون فارغة. لا تغيير القياس أن تعطي الحل الخاص بك ميزة ، يمكن فعل نفس الشيء لجميع الحلول القائمة ، مما يجعل هذا تماما الصورية الأمثل!(حقا!!)
أضفت Version0 الذي لا يفعل شيئا ولكن زيادة bitGet الدولة.فإنه يعود دائما 0 للحصول على فكرة تقريبية كيف كبيرة القياسي النفقات العامة.فقط هناك للمقارنة.
أيضا ، في تعديل على MSN فكرة تم إضافة (Version3).للحفاظ على الأشياء عادلة وقابلة للمقارنة على كل المنافسين ، صفيف بايت ملء هو الآن جزء من المعيار ، وكذلك خطوة تحضيرية (انظر أعلاه).أصلا MSN الحل لم تفعل ذلك حسنا, لقد كان هناك الكثير من النفقات العامة في إعداد الباحث[] العازلة.أخذت الحرية تحسين الخطوة قليلا ، التي تحولت إلى منافس شرس :) قد تجد أيضا أن كنت دي معقدة التعليمات البرمجية الخاصة بك قليلا.الخاص بك getBit() يمكن تلخيصها في 3-بطانة ، وربما حلق واحد أو اثنين في المئة.أنا تعمدت فعل ذلك للحفاظ على رمز للقراءة لأن الإصدارات الأخرى ليست المكثف ممكن إما (مرة أخرى على القراءة).
الختام (المثال التعليمات البرمجية أعلاه تحديث تشمل الإصدارات استنادا إلى جميع الاشتراكات المعمول بها).على القديم AMD مربع (الشمس JRE 1.6.0_21) ، أنها تأتي كما يلي:
V0 لا implementaion أخذت 5384 ms
V1 Durandal في (الأصل) أخذت 10283 ms
V2 blitzpasta هو (مقتبس) أخذت 12212 ms
V3 MSN (نشر) أخذت 11030 ms
V4 MSN (نصف العازلة تعديل) أخذت 9700 ms
ملاحظات:في هذا المعيار المتوسط 7.5 بت المنال في الدعوة إلى getBits () ، كل بت فقط قراءة مرة واحدة.منذ V3/V4 دفع ارتفاع تكلفة التهيئة ، فإنها تميل إلى إظهار أفضل وقت التشغيل السلوك مع أكثر أقصر جلب (وبالتالي أسوأ أقرب إلى أقصى 16 متوسط جلب حجم يحصل).لا يزال, V4 يبقى قليلا قبل جميع الآخرين في كل السيناريوهات.في التطبيق الفعلي ، ذاكرة التخزين المؤقت الخلاف يجب أن تؤخذ في الحسبان ، حيث المساحة الإضافية اللازمة V3/v4 قد يزيد ذاكرة التخزين المؤقت يفتقد إلى نقطة حيث V0 سيكون خيارا أفضل.إذا كان الصفيف هو أن اجتاز أكثر من مرة, V4 ينبغي تفضيل ، لأنه جلب أسرع من كل و المكلفة التهيئة المطفأة بعد قبضة من تمر.
المحلول
حسنا, اعتمادا على مدى تريد أن تذهب إلى أسفل مرة مقابلالذاكرة انظر من رأى ، يمكنك تخصيص طاولة جانبية من كل 32-بت في كل 16 بت تعويض ومن ثم القيام قناع التحول استنادا إلى 16 بت الإزاحة:
byte[] bytes = new byte[2048];
int bitGet;
unsigned int dwords[] = new unsigned int[2046];
public BitArray() {
for (int i=0; i<bytes.length; ++i) {
bytes[i] = (byte) i;
}
for (int i= 0; i<dwords.length; ++i) {
dwords[i]=
(bytes[i ] << 24) |
(bytes[i + 1] << 16) |
(bytes[i + 2] << 8) |
(bytes[i + 3]);
}
}
int getBits(int len)
{
int offset= bitGet;
int offset_index= offset>>4;
int offset_offset= offset & 15;
return (dwords[offset_index] >> offset_offset) & ((1 << len) - 1);
}
يمكنك تجنب المتفرعة (بتكلفة أربعة أضعاف الذاكرة الخاصة بك البصمة).و هو يبحث حتى القناع حقا أن أسرع بكثير من (1 << ليون) - 1?
نصائح أخرى
إذا كنت ترغب فقط غير موقعة بت تسلسل كما int.
static final int[] lookup = {0x0, 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
/*
* bytes: byte array, with the bits indexed from 0 (MSB) to (bytes.length * 8 - 1) (LSB)
* offset: index of the MSB of the bit sequence.
* len: length of bit sequence, must from range [0,16].
* Not checked for overflow
*/
static int getBitSeqAsInt(byte[] bytes, int offset, int len){
int byteIndex = offset / 8;
int bitIndex = offset % 8;
int val;
if ((bitIndex + len) > 16) {
val = ((bytes[byteIndex] << 16 | bytes[byteIndex + 1] << 8 | bytes[byteIndex + 2]) >> (24 - bitIndex - len)) & lookup[len];
} else if ((offset + len) > 8) {
val = ((bytes[byteIndex] << 8 | bytes[byteIndex + 1]) >> (16 - bitIndex - len)) & lookup[len];
} else {
val = (bytes[byteIndex] >> (8 - offset - len)) & lookup[len];
}
return val;
}
إذا كنت تريد كسلسلة (تعديل مارجوس' الإجابة).
static String getBitSequence(byte[] bytes, int offset, int len){
int byteIndex = offset / 8;
int bitIndex = offset % 8;
int count = 0;
StringBuilder result = new StringBuilder();
outer:
for(int i = byteIndex; i < bytes.length; ++i) {
for(int j = (1 << (7 - bitIndex)); j > 0; j >>= 1) {
if(count == len) {
break outer;
}
if((bytes[byteIndex] & j) == 0) {
result.append('0');
} else {
result.append('1');
}
++count;
}
bitIndex = 0;
}
return result.toString();
}
فقط أتساءل لماذا لا يمكنك استخدام java.util.BitSet;
أساسا ما يمكنك القيام به هو قراءة كل البيانات byte[], وتحويله إلى الثنائية في string شكل استخدام سلسلة من المرافق مثل .substring() للقيام بهذا العمل.كما سيعمل هذا bit sequences > 16.
دعونا نقول لديك 3 بايت: 1, 2, 3 و تريد استخراج بت سلسلة من 5 إلى 16 بت.
رقم ثنائي
1 00000001
2 00000010
3 00000011
مثال التعليمة البرمجية:
public static String getRealBinary(byte[] input){
StringBuilder sb = new StringBuilder();
for (byte c : input) {
for (int n = 128; n > 0; n >>= 1){
if ((c & n) == 0)
sb.append('0');
else sb.append('1');
}
}
return sb.toString();
}
public static void main(String[] args) {
byte bytes[] = new byte[]{1,2,3};
String sbytes = getRealBinary(bytes);
System.out.println(sbytes);
System.out.println(sbytes.substring(5,16));
}
الإخراج:
000000010000001000000011
00100000010
السرعة:
لقد فعلت testrun على 1m مرات على الكمبيوتر استغرق 0.995 s, لذا معقول سريع جدا:
رمز لتكرار اختبار نفسك:
public static void main(String[] args) {
Random r = new Random();
byte bytes[] = new byte[4];
long start, time, total=0;
for (int i = 0; i < 1000000; i++) {
r.nextBytes(bytes);
start = System.currentTimeMillis();
getRealBinary(bytes).substring(5,16);
time = System.currentTimeMillis() - start;
total+=time;
}
System.out.println("It took " +total + "ms");
}
تريد في معظم 16 بت ، التي اتخذت من صفيف من البايت.16 بت يمكن أن تمتد في أكثر من 3 بايت.إليك الحل:
int GetBits(int bit_index, int bit_length) {
int byte_offset = bit_index >> 3;
return ((((((byte_array[byte_offset]<<8)
+byte_array[byte_offset+1])<<8)
+byte_array[byte_offset+2]))
>>(24-(bit_index&7)+bit_length))))
&((1<<bit_length)-1);
}
[مجربة]
إذا كنت تسمي هذا الكثير يجب أن precompute 24 بت القيم 3 متصلا بايت, وتخزين تلك إلى int array.
سوف نلاحظ أنه إذا كنت الترميز هذا في C على x86, حتى أنك لا تحتاج إلى precompute 24 بت مجموعة ؛ ببساطة الوصول إلى طريق الشركة المصرية للاتصالات مجموعة في الرغبة في تعويض 32 بت القيمة.X86 سوف تفعل محاذاتها جلب ما يرام.[المعلق الإشارة إلى أن endianess ماكس هذا الأمر, لذلك ليس جوابا حسنا تفعل 24 بت.]
منذ جافا 7 BitSet لديه toLongArray الطريقة التي أعتقد أنها سوف تفعل بالضبط ما السؤال يسأل عن:
int subBits = (int) bitSet.get(lowBit, highBit).toLongArray()[0];
هذا له ميزة أنه يعمل مع تسلسل أكبر من رجات أو يتوق.فقد العيب أداء جديد BitSet كائن يجب أن يكون تم تخصيص مجموعة جديدة كائن إلى عقد النتيجة.
سيكون من المثير للاهتمام حقا أن نرى كيف يقارن هذا مع أساليب أخرى في المعيار.
