Каков самый быстрый способ поменять местами значения в C?

Номер 2 часто называют «умным» способом сделать это. На самом деле это, скорее всего, медленнее, так как скрывает явную цель программиста - перестановку двух переменных. Это означает, что компилятор не может оптимизировать его для использования фактических операций ассемблера для обмена. Он также предполагает возможность побитового xor над объектами.

Придерживайтесь пункта 1, это самый общий и наиболее понятный своп, который легко шаблонизировать / обобщать.

Этот раздел википедии довольно хорошо объясняет проблемы: http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice

Первый быстрее, потому что поразрядные операции, такие как xor, обычно очень трудно визуализировать для читателя.

Быстрее конечно, что самое главное;)

Единственный способ действительно узнать это - протестировать его, и ответ может даже отличаться в зависимости от того, на каком компиляторе и какой платформе вы работаете. Современные компиляторы В самом деле хороши в оптимизации кода в наши дни, и вам никогда не следует пытаться перехитрить компилятор, если вы не докажете, что ваш способ действительно быстрее.

С учетом сказанного, вам лучше иметь чертовски вескую причину, чтобы выбрать №2 вместо №1. Код в №1 гораздо более читабелен, поэтому его всегда следует выбирать первым. Переходите к пункту 2 только в том случае, если вы можете доказать, что вы необходимость, чтобы внести это изменение, и если вы это сделаете - прокомментируйте его, чтобы объяснить, что происходит и почему вы сделали это неочевидным способом.

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

Метод XOR не работает, если a и b указывают на один и тот же адрес. Первый XOR очистит все биты в адресе памяти, на который указывают обе переменные, поэтому, как только функция вернет (* a == * b == 0), независимо от начального значения.

Более подробная информация на странице Wiki: Алгоритм замены XOR

Хотя маловероятно, что эта проблема возникнет, я всегда предпочитаю использовать метод, который гарантированно работает, а не умный метод, который дает сбой в неожиданные моменты.

Если вы можете использовать какой-нибудь встроенный ассемблер и сделать следующее (псевдо-ассемблер):

PUSH A
A=B
POP B

Вы сэкономите много времени на передачу параметров и код исправления стека и т. д.

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

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

В любом случае, вашим узким местом, скорее всего, будет неэффективный алгоритм или несоответствующая структура данных (или накладные расходы на связь), чем то, как вы меняете номера.

Чтобы ответить на ваш вопрос, как указано, потребуется изучить тайминги инструкций конкретного процессора, на котором будет выполняться этот код, что, следовательно, потребует от меня сделать кучу предположений относительно состояния кешей в системе и кода сборки, испускаемого компилятор. Это было бы интересным и полезным упражнением с точки зрения понимания того, как на самом деле работает выбранный вами процессор, но в реальном мире разница будет незначительной.

Я просто поместил оба свопа (как макросы) в рукописную быструю сортировку, с которой я играл. Версия XOR была намного быстрее (0,1 секунды), чем версия с временной переменной (0,6 секунды). Однако XOR повредил данные в массиве (вероятно, тот же адрес, о котором упоминал Ant).

Так как это была быстрая сортировка с большим количеством опорных точек, скорость версии XOR, вероятно, обусловлена ​​тем, что большие части массива были одинаковыми. Я попробовал третью версию подкачки, которая была самой простой для понимания и имела то же время, что и единственная временная версия.

acopy=a;
bcopy=b;
a=bcopy;
b=acopy;

[Я просто помещаю операторы if вокруг каждого свопа, чтобы он не пытался поменяться сам с собой, а XOR теперь занимает то же время, что и другие (0,6 секунды)]

На современном процессоре вы можете использовать следующее при сортировке больших массивов и не увидите разницы в скорости:

void swap (int *a, int *b)
{
  for (int i = 1 ; i ; i <<= 1)
  {
    if ((*a & i) != (*b & i))
    {
      *a ^= i;
      *b ^= i;
    }
  }
}

Действительно важная часть вашего вопроса - «почему?» часть. Теперь, возвращаясь на 20 лет назад к 8086 дням, вышеупомянутое было бы настоящим убийцей производительности, но на последнем Pentium это было бы сравнимо по скорости с теми двумя, которые вы опубликовали.

Причина кроется в памяти и не имеет ничего общего с процессором.

Скорость процессора по сравнению со скоростью памяти выросла астрономически. Доступ к памяти стал основным узким местом в производительности приложений. Все алгоритмы подкачки будут тратить большую часть своего времени на ожидание выборки данных из памяти. Современные ОС могут иметь до 5 уровней памяти:

• Уровень кэша 1 - работает с той же скоростью, что и ЦП, имеет незначительное время доступа, но мал
• Уровень кэша 2 - работает немного медленнее, чем L1, но больше и требует больших накладных расходов для доступа (обычно данные сначала нужно переместить на L1)
• Уровень кэша 3 - (не всегда присутствует) Часто внешний по отношению к ЦП, медленнее и больше, чем L2
• ОЗУ - основная системная память, обычно реализует конвейер, поэтому есть задержка в запросах на чтение (ЦП запрашивает данные, сообщение отправляется в ОЗУ, ОЗУ получает данные, ОЗУ отправляет данные в ЦП)
• Жесткий диск - когда не хватает оперативной памяти, данные выгружаются на HD, что очень медленно и не контролируется процессором как таковым.

Алгоритмы сортировки ухудшают доступ к памяти, поскольку они обычно обращаются к памяти очень неупорядоченным образом, что приводит к неэффективным накладным расходам на выборку данных из L2, RAM или HD.

Итак, оптимизация метода подкачки действительно бессмысленна - если он вызывается всего несколько раз, то любая неэффективность скрывается из-за небольшого количества вызовов, если он вызывается много, то любая неэффективность скрывается из-за количества промахов кеша (где ЦП должен получать данные из L2 (единицы циклов), L3 (десятки циклов), ОЗУ (сотни циклов), HD (!)).

Что вам действительно нужно сделать, так это посмотреть на алгоритм, вызывающий метод подкачки. Это нетривиальное упражнение. Хотя нотация Big-O полезна, O (n) может быть значительно быстрее, чем O (log n) для малых n. (Я уверен, что об этом есть статья CodingHorror.) Кроме того, многие алгоритмы имеют вырожденные случаи, когда код делает больше, чем необходимо (использование qsort для почти упорядоченных данных может быть медленнее, чем пузырьковая сортировка с ранней проверкой). Итак, вам нужно проанализировать свой алгоритм и данные, которые он использует.

Это приводит к тому, как анализировать код. Профилировщики полезны, но вам нужно знать, как интерпретировать результаты. Никогда не используйте один прогон для сбора результатов, всегда усредняйте результаты по множеству выполнений - потому что ваше тестовое приложение могло быть выгружено на жесткий диск ОС на полпути. Всегда профилировать выпуск, оптимизированные сборки, профилировать отладочный код бессмысленно.

Что касается исходного вопроса - что быстрее? - это похоже на попытку выяснить, быстрее ли Ferrari, чем Lambourgini, глядя на размер и форму крыльевого зеркала.

Для тех, кто наткнулся на этот вопрос и решил использовать метод XOR. Вам следует подумать о встраивании своей функции или использовании макроса, чтобы избежать накладных расходов на вызов функции:

#define swap(a, b)   \
do {                 \
    int temp = a;    \
    a = b;           \
    b = temp;        \
} while(0)

Что касается @Harry: Никогда не реализуйте функции как макросы по следующим причинам:

1. Тип безопасности. Здесь ничего нет. Следующее сообщение генерирует предупреждение только при компиляции, но не выполняется во время выполнения:

   float a=1.5f,b=4.2f;
   swap (a,b);
   

   Шаблонная функция всегда будет правильного типа (и почему вы не рассматриваете предупреждения как ошибки?).

   Обновлено: Поскольку в C нет шаблонов, вам нужно написать отдельный своп для каждого типа или использовать какой-то хакерский доступ к памяти.

2. Это подмена текста. Во время выполнения происходит сбой следующего (на этот раз без предупреждений компилятора):

   int a=1,temp=3;
   swap (a,temp);
   

3. Это не функция. Таким образом, его нельзя использовать в качестве аргумента для чего-то вроде qsort.

4. Составители умны. Я имею в виду действительно умный. Сделано действительно умными людьми. Они могут встраивать функции. Даже во время ссылки (что еще умнее). Не забывайте, что встраивание увеличивает размер кода. Большой код означает большую вероятность промаха кеша при выборке инструкций, что означает более медленный код.

5. Побочные эффекты. У макросов есть побочные эффекты! Учитывать:

   int &f1 ();
   int &f2 ();
   void func ()
   {
     swap (f1 (), f2 ());
   }
   

   Здесь f1 и f2 будут вызываться дважды.

   Обновлено: версия C с неприятными побочными эффектами:

   int a[10], b[10], i=0, j=0;
   swap (a[i++], b[j++]);
   

Макросы: Просто сказать нет!

Обновлено: вот почему я предпочитаю определять имена макросов в ЗАПИСИ, чтобы они выделялись в коде как предупреждение, которое следует использовать с осторожностью.

РЕДАКТИРОВАТЬ2: Чтобы ответить на комментарий Лиана Новаша:

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

bytes = C(p) + C(f)

где C () дает количество произведенных байтов, C (f) - байты для функции, а C (p) - байты для «служебного» кода, преамбулы и заключительной части, которые компилятор добавляет к функции (создавая и уничтожение фрейма стека функции и т. д.). Теперь для вызова функции f требуется C (c) байтов. Если функция вызывается n раз, то общий размер кода равен:

size = C(p) + C(f) + n.C(c)

Теперь давайте встроим функцию. C (p), служебное значение функции, становится равным нулю, поскольку функция может использовать стековый фрейм вызывающей стороны. C (c) также равен нулю, поскольку теперь нет кода операции вызова. Но f воспроизводится везде, где был вызов. Итак, теперь общий размер кода:

size = n.C(f)

Теперь, если C (f) меньше C (c), то общий размер исполняемого файла будет уменьшен. Но если C (f) больше, чем C (c), то размер кода будет увеличиваться. Если C (f) и C (c) похожи, вам также необходимо рассмотреть C (p).

Итак, сколько байтов производят C (f) и C (c). Ну, простейшей функцией C++ будет геттер:

void GetValue () { return m_value; }

который, вероятно, сгенерирует четырехбайтовую инструкцию:

mov eax,[ecx + offsetof (m_value)]

что составляет четыре байта. Стоимость вызова составляет пять байт. Итак, есть общая экономия размера. Если функция более сложная, скажем, индексатор («return m_value [index];») или вычисление («return m_value_a + m_value_b;»), тогда код будет больше.

Я бы не стал делать это с указателями, если вам не нужно. Компилятор не может оптимизировать их очень хорошо из-за возможности сглаживание указателя (хотя, если вы можете ГАРАНТИРОВАТЬ, что указатели указывают на неперекрывающиеся местоположения, GCC по крайней мере имеет расширения для оптимизации).

И я бы вообще не стал делать этого с функциями, так как это очень простая операция и накладные расходы на вызов функции значительны.

Лучший способ сделать это - использовать макросы, если вам нужна чистая скорость и возможность оптимизации. В GCC вы можете использовать встроенный typeof() для создания гибкой версии, которая работает с любым встроенным типом.

Что-то вроде этого:

#define swap(a,b) \
  do { \
    typeof(a) temp; \
    temp = a; \
    a = b; \
    b = temp; \
  } while (0)

...    
{
  int a, b;
  swap(a, b);
  unsigned char x, y;
  swap(x, y);                 /* works with any type */
}

С другими компиляторами или если вам требуется строгое соответствие стандарту C89 / 99, вам придется сделать отдельный макрос для каждого типа.

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

На мой взгляд, подобные локальные оптимизации следует рассматривать только как тесно связанные с платформой. Это имеет огромное значение, если вы компилируете это на 16-битном компиляторе uC или на gcc с x64 в качестве цели.

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

Все ответы с наивысшими оценками на самом деле не являются окончательными "фактами" ... это люди, которые спекулируют!

Вы можете окончательно знать наверняка, какой код требует меньше инструкций сборки для выполнения, потому что вы можете посмотреть на выходную сборку, сгенерированную компилятором, и увидеть, какая из них выполняется с меньшим количеством инструкций сборки!

Вот код c, который я скомпилировал с флагами "gcc -std = c99 -S -O3 lookingAtAsmOutput.c":

#include <stdio.h>
#include <stdlib.h>

void swap_traditional(int * restrict a, int * restrict b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void swap_xor(int * restrict a, int * restrict b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

int main() {
    int a = 5;
    int b = 6;
    swap_traditional(&a,&b);
    swap_xor(&a,&b);
}

Вывод ASM для swap_traditional () занимает >>> 11

.globl swap_traditional
    .type   swap_traditional, @function
swap_traditional:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    12(%ebp), %ecx
    pushl   %ebx
    movl    (%edx), %ebx
    movl    (%ecx), %eax
    movl    %ebx, (%ecx)
    movl    %eax, (%edx)
    popl    %ebx
    popl    %ebp
    ret
    .size   swap_traditional, .-swap_traditional
    .p2align 4,,15

Вывод ASM для swap_xor () занимает >>> 11

.globl swap_xor
    .type   swap_xor, @function
swap_xor:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %ecx
    movl    12(%ebp), %edx
    movl    (%ecx), %eax
    xorl    (%edx), %eax
    movl    %eax, (%ecx)
    xorl    (%edx), %eax
    xorl    %eax, (%ecx)
    movl    %eax, (%edx)
    popl    %ebp
    ret
    .size   swap_xor, .-swap_xor
    .p2align 4,,15

Сводная информация о выходе сборки:
swap_traditional () принимает 11 инструкций swap_xor () принимает 11 инструкций

Вывод:
Оба метода используют одинаковое количество инструкций для выполнения и, следовательно, имеют примерно одинаковую скорость на этой аппаратной платформе.

Извлеченный урок:
Когда у вас есть небольшие фрагменты кода, просмотр вывода asm полезен для быстрой итерации вашего кода и создания самого быстрого (то есть с наименьшим количеством инструкций) кода. И вы можете сэкономить время даже потому, что вам не нужно запускать программу при каждом изменении кода. Вам нужно только запустить изменение кода в конце с помощью профилировщика, чтобы показать, что ваши изменения кода выполняются быстрее.

Я часто использую этот метод для тяжелого кода DSP, которому нужна скорость.

Если ваш компилятор поддерживает встроенный ассемблер и ваша цель - 32-битная x86, то инструкция XCHG, вероятно, лучший способ сделать это ... если вы действительно так заботитесь о производительности.

Вот метод, который работает с MSVC++:

#include <stdio.h>

#define exchange(a,b)   __asm mov eax, a \
                        __asm xchg eax, b \
                        __asm mov a, eax               

int main(int arg, char** argv)
{
    int a = 1, b = 2;
    printf("%d %d --> ", a, b);
    exchange(a,b)
    printf("%d %d\r\n", a, b);
    return 0;
}

void swap(int* a, int* b)
{
    *a = (*b - *a) + (*b = *a);
}

// Мой C немного заржавел, поэтому я надеюсь, что * правильно понял :)

Еще один красивый способ.

#define Swap( a, b ) (a)^=(b)^=(a)^=(b)

Преимущество

Нет необходимости в вызове функции и удобстве.

Недостаток:

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

Никогда не понимал ненависти к макросам. При правильном использовании они могут сделать код более компактным и читаемым. Я считаю, что большинство программистов знают, что макросы следует использовать с осторожностью, важно дать понять, что конкретный вызов является макросом, а не вызовом функции (все заглавные буквы). Если SWAP(a++, b++); является постоянным источником проблем, возможно, программирование не для вас.

По общему признанию, уловка xor удобна в первые 5000 раз, когда вы ее видите, но все, что он действительно делает, - это временная экономия за счет надежности. Глядя на сгенерированную выше сборку, она сохраняет регистр, но создает зависимости. Также я бы не рекомендовал xchg, поскольку он подразумевает префикс блокировки.

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

#define SWAP(type, a, b) \
    do { type t=(a);(a)=(b);(b)=t; } while (0)

void swap(size_t esize, void* a, void* b)
{
    char* x = (char*) a;
    char* y = (char*) b;
    char* z = x + esize;

    for ( ; x < z; x++, y++ )
        SWAP(char, *x, *y);
}

Для современных архитектур ЦП метод 1 будет быстрее, а также с большей удобочитаемостью, чем метод 2.

В современных архитектурах ЦП метод XOR значительно медленнее, чем использование временной переменной для подкачки. Одна из причин заключается в том, что современные процессоры стремятся выполнять инструкции параллельно через конвейеры команд. В технике XOR входные данные для каждой операции зависят от результатов предыдущей операции, поэтому они должны выполняться в строго последовательном порядке. Если эффективность вызывает огромное беспокойство, рекомендуется протестировать скорость как техники XOR, так и перестановки временных переменных в целевой архитектуре. Посетите здесь для получения дополнительной информации.

Редактировать: Метод 2 - это способ замена на месте (т.е. без использования дополнительных переменных). Чтобы завершить этот вопрос, я добавлю еще одну замену на месте с помощью +/-.

void swap(int* a, int* b)
{
    if (a != b) // important to handle a/b share the same reference
    {
        *a = *a+*b;
        *b = *a-*b;
        *a = *a-*b;
    }
}

Приведенный ниже фрагмент кода сделает то же самое. Этот фрагмент является оптимизированным способом программирования, так как не использует никакую третью переменную.

  x = x ^ y;
  y = x ^ y;
  x = x ^ y;

х = х + у- (у = х);

float x; cout << "X:"; cin >> x;
float y; cout << "Y:" ; cin >> y;

cout << "---------------------" << endl;
cout << "X = " << x << ", Y = " << y << endl;
x=x+y-(y=x);
cout << "X = " << x << ", Y = " << y << endl;