Как я могу поменять значения двух массивов при максимально возможном сохранении памяти?

Question

Два массива должны быть взаимозаменяемы со своими значениями, я ищу способы сделать это без использования третьего массива.Как это можно решить?Я видел некоторые арифметические методы (как показано ниже), чтобы сделать это для целых чисел, но не смог разобраться в моей проблеме с массивами строк.

Answer 1

Если вы собираетесь перебирать массив, вам не нужен новый массив;достаточно только одной временной переменной, и вы можете использовать ее каждую итерацию.

Если любое новое выделение памяти запрещено, то вы можете использовать арифметическое или XOR-решение, если тип данных является целым.*

for(int i = 0; i < 350; ++i)
{
    a[i] = a[i] + b[i];
    b[i] = a[i] - b[i];    
    a[i] = a[i] - b[i];
}
// or
for(int i = 0; i < 350; ++i)
{
    a[i] ^= b[i];
    b[i] ^= a[i];
    a[i] ^= b[i];
}

Наконец, вы всегда можете просто поменять местами указатели массива!

object[] a;
object[] b;
object[] temp;

temp = a;
a = b;
b = temp;

Answer 2

Зачем использовать какие-то нелепые уловки? Разве вы не можете сэкономить один int временный?

for(int i=0;i<350;i++)
{
    std::swap(a[i], b[i]);
}

или

std::swap_ranges(a, a+350, b);

Примечание: на моем компьютере трюк XOR обычно занимает вдвое больше времени, чем просто использование одной временной переменной для обмена.

Answer 3

Ваше решение не работает: на самом деле оно иллюстрирует простую проблему, на которую многие наткнулись.

Описание алгоритмов, как правило, не учитывает конечное представление памяти, которое есть у компьютеров.

В частности, здесь int может содержать только столько битов, и, таким образом, добавление может привести к переполнению , что является неопределенным поведением (на x86 оно выполняется, но на других процессорахэто может вызвать аппаратное исключение).

Существует два правильных (и простых) решения для обмена двумя int:

• int tmp = lhs; lhs = rhs; rhs = tmp;, также известными как swap
• lhs ^= rhs; rhs ^= lhs; lhs ^= rhs;, также известный как трюк XOR

Очевидно, что оба варианта применимы в случае массивов.

Другим более эффективным решением было бы поменять местамисами массивы.

std::swap(a,b);

Примечание: если массивы размещены статически, их невозможно поменять местами напрямую, но вы можете использовать только указатели на статически распределенные массивыи, таким образом, поменяйте местами указатели

Предупреждение: объекты, которые уже имеют ссылку на массивы, не будут уведомлены о свопе, в этом случае у вас нет другого выбора, кроме как поменять их местами.содержание.

Answer 4

Полагаю, вопрос автора - поменять массив, не используя третий массив. Поэтому я думаю, достаточно использовать одну переменную.

int tmp = 0;
for( int i = 0; i < 350; ++i )
{
    tmp = a[i];
    a[i] = b[i];
    b[i] = a[i];
}

зачем использовать некоторые операции xor?

Answer 5

Еще лучше:

for(int i = 0; i < 350; ++i)
{
    a[i] ^= b[i];
    b[i] ^= a[i];
    a[i] ^= b[i];
}

Answer 6

В C ++ вы можете использовать бит xor для с указателями (я предполагаю, что строки char* или wchar_t*).Но на самом деле я не думаю, что одна переменная вредна для вас, и будет лучше просто использовать std::swap.

Answer 7

ЕСЛИ массивы являются целыми, вы можете использовать трюк xor:

for(int i = 0; i < 350; ++i) {
    a[i] = a[i] ^ b[i];
    b[i] = a[i] ^ b[i];
    a[i] = a[i] ^ b[i];
}

никаких временных затрат не требуется