c# bitarray的正位索引
本文关键字：索引 bitarray | 更新日期: 2023-09-27 18:08:46
我有一个c# BitArray，长度相当大(500,000)，我试图获得数组中设置的所有正位的索引。目前我通过以下方式实现:
public int[] GetIndexesForPositives()
{
var idIndexes = new int[GetPositiveCount + 1];
var idx = 0;
for (var i = 0; i < Length; i++)
{
if (Get(i))
{
idIndexes[idx++] = i;
}
}
return idIndexes;
}
我创建一个已知正位大小的空数组，然后遍历bitarray并将索引值添加到返回数组。
这意味着我必须在数组上执行500,000次循环，这并不是很快。(耗时约15ms).
我知道BitArray在掩护下使用整数数组(我用它来编写GetPositiveCount函数-通过我从堆栈上得到的算法)，我想知道是否有一个算法来做到这一点?
如果您可以从BCL中替换出BitArray，而使用"roll your own"，那么您可以做得更好。这里有一些你可以做的事情:
- 跳过没有位集的64块
- 对于确实有位的64块，只枚举1位而不是使用
x & (x - 1)和您最喜欢的快速2log在这里找到的所有位(使用朴素的64步方法不会提供任何加速) - 保留一个额外的bitarray，用于存储每个64位块是否为非零。应用从子弹头2到的技术， bitarray一次跳过整个范围的零。
- 为巨大的位数组递归应用子弹头3
这四种方法只有在期望bitarray是稀疏的情况下才有帮助，如果它不是稀疏的，最坏的情况仍然是O(n)。如果项目3被应用到顶部是一个单一的ullong，那么它可以在0(1)内确定整个bitarray是否为空。
如果您能够获得BitArray底层的int数组，这将提供更好的性能:
假设您不知道所设置的位数:
public static int[] GetIndexesForPositives()
{
var idIndexes = new List<int>();
System.Reflection.FieldInfo field = data.GetType().GetField("m_array", System.Reflection.BindingFlags.NonPublic | System.Reflection.BindingFlags.Instance);
int[] values = field.GetValue(data) as int[];
for (var i = 0; i < values.Length; i++)
{
int _i = values[i];
if (_i != 0)
{
for (var j = 0; j < 32; j++)
{
if ((_i & (1 << j)) != 0)
{
idIndexes.Add(i * 32 + j);
}
}
}
}
return idIndexes.ToArray();
}
如果你知道所设置的位数，你可以这样做:
public static int[] GetIndexesForPositives(int length)
{
var idIndexes = new int[length];
var idx = 0;
System.Reflection.FieldInfo field = data.GetType().GetField("m_array", System.Reflection.BindingFlags.NonPublic | System.Reflection.BindingFlags.Instance);
int[] values = field.GetValue(data) as int[];
for (var i = 0; i < values.Length; i++)
{
int _i = values[i];
if (_i != 0)
{
for (var j = 0; j < 32; j++)
{
if ((_i & (1 << j)) != 0)
{
idIndexes[idx++] = i * 32 + j;
}
}
}
}
我的测试让这两个方法比你的方法工作得快，即使是一个不知道返回数组有多大的方法。
我使用5000万条记录的随机BitArray测试的结果:
1) 25001063 records found in 50000000, took 1415.5752ms
2) 25001063 records found in 50000000, took 1099.67ms
3) 25001063 records found in 50000000, took 1045.6862ms
4) 25001063 records found in 50000000, took 745.7762ms"
1) is your code but using an arraylist instead of using some `GetPositiveCount` to get the output length.
2) is your code
3) is my (revised) first example
4) is my (revised) second example
edit:此外，值得指出的是，这是一个问题，可以真正受益于多线程。将ByteArray分解为4个部分，这样就有4个线程可以同时运行检查数据。
编辑:我知道这已经被接受了，但是如果你知道大多数时候你的列表会非常稀疏，你可以做另一点来提高性能:
for (var j = 0; j < 32; j++)
{
if (_i == 0)
break;
if ((_i & (1)) != 0)
{
idIndexes.Add(i * 32 + j);
}
_i = _i >> 1;
}
当列表的填充率>40%或更多时，它会稍微慢一些，但是如果你知道列表总是会有10%的1和90%的0，那么它会运行得更快。
我会这样做:
public int[] GetIndexesForPositives()
{
var idIndexes = new LinkedList<int>();
for (var i = 0; i < Length; i++)
{
if (Get(i))
{
idIndexes.Add(i);
}
}
return idIndexes.ToArray();
}
如果这仍然是不可接受的(因为您在执行ToArray时再次遍历索引)，只需为结果数组使用相同的大小并返回找到的索引的长度:
public int GetIndexesForPositives(out int[] indizes)
{
indizes = new int[Length];
var idI = 0;
for (var i = 0; i < Length; i++)
{
if (Get(i))
{
indizes[idI++] = i;
}
}
return idI;
}
根据你是真的需要所有的索引还是只需要部分，你甚至可以考虑这样做(但如果你需要每个部分，它会降低性能-请自己做一些分析):
public IEnumerable<int> GetIndexesForPositives()
{
for (var i = 0; i < Length; i++)
{
if (Get(i))
{
yield return i;
}
}
}
这是假设你的Get(i)正在做它的工作，并且你的数组是不可变的
迭代了500,000次。直观地说:如果每个位都设置好了，那么你需要生成一个包含500,000个元素的数组。你可以通过访问底层字节或int来减少外部迭代的次数8或32倍，但你仍然需要迭代比特。即使是包含256个元素的查找表也无济于事，因为您必须添加位索引。
然而，如果你有很多零比特(当然希望你这样做)，那么优化是简单地调整循环计数器8或32，如果底层字节/int为0。因为您知道Get()将返回0。另外，使用List<>来避免getpositivecount的开销。
完全消除对这个数组的需要，并惰性地检索下一个设置为1的位将是目前为止最好的方法。
@Seph在https://stackoverflow.com/a/7415891/264022的回答真的很好，但它可以做得更快一点。
- 首先计算比特数
- 展开内循环(每次检查4位)2 b。创建一个构造，以便JIT生成一个跳转表，而不是一堆if(这成为唯一不可预测的分支)
- 使用安全的c#指针魔法避免越界检查
结果比@Seph已经快的版本快了3-4倍。
public static int[] GetIndexesForPositives(ulong[] _array)
{
var thisArray = _array;
var c2 = 0ul;
for (var i = 0; i < thisArray.Length; i++)
{
var v = thisArray[i];
//from http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
v = v - ((v >> 1) & (ulong)~(ulong)0/3); // temp
v = (v & (ulong)~(ulong)0/15*3) + ((v >> 2) & (ulong)~(ulong)0/15*3); // temp
v = (v + (v >> 4)) & (ulong)~(ulong)0/255*15; // temp
var c = (ulong) (v * ((ulong) ~(ulong) 0 / 255)) >> (sizeof(ulong) - 1) * 8; // count
c2 += c;
}
if (c2 == 0) return Array.Empty<int>();
var idIndexes = new int[c2];
ref var idxref = ref idIndexes[0];
for (var i = 0; i < thisArray.Length; i++)
{
var v = thisArray[i];
for (var j = 0; j < 64; j += 4)
{
if (v == 0)
break;
var b = ((byte)v) & 0b1111;
var actualIndex = i * 64 + j;
switch (b)
{
case 0: break;
case 0b001:
idxref = (actualIndex);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
case 0b010:
idxref = (actualIndex+1);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
case 0b011:
idxref = (actualIndex);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+1);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
case 0b100:
idxref = (actualIndex + 2);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
case 0b101:
idxref = (actualIndex);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+2);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
case 0b110:
idxref = (actualIndex+1);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+2);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
case 0b111:
idxref = (actualIndex);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+1);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+2);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
case 0b1000:
idxref = (actualIndex+3);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
case 0b1001:
idxref = (actualIndex);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+3);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
case 0b1010:
idxref = (actualIndex+1);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+3);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
case 0b1011:
idxref = (actualIndex);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+1);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+3);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
case 0b1100:
idxref = (actualIndex + 2);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+3);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
case 0b1101:
idxref = (actualIndex);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+2);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+3);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
case 0b1110:
idxref = (actualIndex+1);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+2);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+3);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
case 0b1111:
idxref = (actualIndex);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+1);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+2);
idxref = ref Unsafe.Add(ref idxref, 1);
idxref = (actualIndex+3);
idxref = ref Unsafe.Add(ref idxref, 1);
break;
}
v >>= 4;
}
}
return idIndexes;
}