самый быстрый способ изменить часть массива

Question

самый быстрый способ изменить часть массива

Я хочу выполнить не операцию над блоком непрерывных элементов массива bool, а затем снова прочитать весь массив. Я использую следующий код для выполнения операции.

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];

Это работает нормально, но я пытаюсь увеличить скорость программы. Есть ли лучший способ выполнить ту же операцию?

0

c++performance processing-efficiency

Решение

Другие решения

Поскольку я сделал комментарий об использовании ints (или, действительно, int64), я могу также написать его, и вы сможете оценить, стоит ли оно того. Это было бы что-то вроде этого. Простите за любые ошибки, поскольку я просто вставляю это в браузер, в то время как мои дети смотрят смехотворно грязные субботние и утренние мультфильмы.

// I'm gonna assume 32-bit ints here.  Makes the other maths clearer.
// Sorry about all the '4' and '32' constants =P
const size_t arrLen = 100000 / 4 + 1;
int arr[arrLen];

//This gets filled with your data...
memset((void*)arr, 0, arrLen*4);

cin >> x >> y;
int leftMask = 0xffffffff >> (x % 32);      // "(x & 0x1f)" faster?
int rightMask = ~(0x7fffffff >> (y % 32));  // "(y & 0x1f)" faster?
x /= 32;                                    // "x >>= 5" faster?
y /= 32;                                    // "y >>= 5" faster?

if( x == y )
{
// Intersect the masks
leftMask &= rightMask;
arr[x] = (arr[x] & ~leftMask) | (~arr[x] & leftMask);
}
else if( x < y )
{
// Flip the left and right ends
arr[x] = (arr[x] & ~leftMask) | (~arr[x] & leftMask);
arr[y] = (arr[y] & ~rightMask) | (~arr[y] & rightMask);

// Flip everything in between
for( int i = x+1; i < y; i++ ) {
arr[i] ^= 0xffffffff;  // Or arr[i] = ~arr[i] -- whichever is faster
}
}

Альтернатива для вышеупомянутого цикла, если это имеет какое-либо значение …

// Flip everything in between
for( int *a = arr+x+1, *b = arr+y; a < b; a++ ) {
*a = ~*a;
}

Упражнение состоит в том, чтобы попробовать 64-битные целые числа. Лично я считаю, что этот подход будет быстрее, чем все остальное, за исключением случаев, когда вы переворачиваете только несколько битов.

У меня может быть ошибочная ошибка в правой маске. Если кто-то заметит это, пожалуйста, прокомментируйте. Мозг пуст. знак равно

1

Источник

Accepted Answer

Подумайте об использовании bitset. Сравните производительность — возможно, будет лучше.

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();

Для еще большей оптимизации (пожалуйста, измерьте и не верьте) вы можете использовать собственную версию набора битов<> ЭТО НЕ ПРОВЕРЕННЫЙ КОД:

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

3