修改数组部分的最快方法 [英] fastest way to modify part of array
本文介绍了修改数组部分的最快方法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我想对 bool 数组的连续元素块执行 not 操作,然后读回完整的数组.我正在使用以下代码来执行操作.
I want to perform not operation to a block of continous elements of a bool array and then read back the complete array. I am using the following code to perform the operation.
bool arr[100000]={0};
cin>>x>>y;
for(i=x; i<=y; i++)
arr[i]=!arr[i];
//Some other operations on the array
for(i=0; i<=100000; i++)
arr+=arr[i];
这很好用,但我想提高程序的速度.有没有更好的方法来执行相同的操作?
This works fine but i am trying to increase the speed of the program. Is there a better way to perform the same operation?
推荐答案
考虑使用 bitset.比较性能 - 也许它会更好.
Consider to use bitset. Compare performance - maybe it will be better.
std::bitset<100000> arr;
cin>>x>>y;
for(i=x; i<=y; i++)
arr.flip(i);
//Some other operations on the array
unsigned int carr = arr.count();
为了更优化(请衡量并且不要相信),您可以使用自己的 bitset 版本<>,这是未经测试的代码:
For even more optimized (please measure and don't believe) you can use your own version of bitset<>, THIS IS NOT TESTED CODE:
const size_t arr_bitlen = 100000;
typedef unsigned int arr_type;
const size_t arr_type_size = sizeof(arr_type);
const size_T arr_len = (arr_bitlen + arr_type_size - 1) / arr_type_size;
arr_type arr[arr_len] = { 0 };
cin>>x>>y;
unsigned int x_addr = x / arr_type_size;
unsigned int y_addr = y / arr_type_size;
unsigned int x_bit = x % arr_type_size;
unsigned int y_bit = y % arr_type_size;
if (0 == x_bit)
for (i=x_addr; i<=y_addr; i++)
arr[i] = ~arr[i]; // revert all bits (bools)
else {
// deal with first element in range ( ....xxxx - change only x-s
arr_type x_mask = ((1 << x_bit) - 1) << (arr_type_len - x_bit);
arr[x_addr] ^= x_mask;
for (i = x_bit + 1; i < arr_type_size; ++i)
arr[i] = ~arr[i]; // revert all bits (bools)
}
if (y_bit > 0) // try to invert 0..y_bit in arr[y_addr + 1] by yourself
//Some other operations on the array
see implementation of std::bitset<N>::count() - it is very clever - just copy it
这篇关于修改数组部分的最快方法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文