我有一个相当大(500,000)的c#BitArray,我试图得到数组中设置的所有正位的索引.目前我实现这一点：
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上进行lopp并将索引值添加到返回数组中.
这意味着我必须在阵列上执行500,000次循环,而且速度并不快. (大约需要15ms).
我知道BitArray在封面下使用了一个整数数组(我用它来编写GetPositiveCount函数 – 通过我从堆栈中得到的算法),我想知道是否还有一个algorythm这样做呢？
解决方法
如果你能够获得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
编辑：此外值得指出的是,这是一个可以真正受益于多线程的问题.将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％1s和90％0s那么这对你来说运行得更快.
