Обмен значений двух переменных, не все способы одинаково полезны

16.03.2020 05:41

На всяких курсах по программированию и на собеседованиях есть стандартная задача: есть 2 переменных a и b, нужно поменять местами их значения, подразумевается, что мы должны выпендриться и вместо использования буфера заюзать XOR или математику:

let a = 10;
let b = 20;
let c;

// 1 способ, с использованием буфера
c = a;
a = b;
b = c;

// 2 способ, сложение/вычитание
a = b + a;
b = a - b;
a = a - b;

// 3 способ - XOR
a = a ^ b;
b = b ^ a;
a = b ^ a;

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

Но меня интересует не это, а то, на сколько быстро/медленно эти способы работают. Давайте напишим тестик:

let a = 10;
let b = 20;
let c;

// test - 1
let start = new Date();
for(let ii=0; ii< 10000; ii++)
  for(let i=0; i<1000000; i++) {
    a = a ^ b;
    b = b ^ a;
    a = b ^ a;
  }

let stop = new Date();
let timeDiff = stop - start;
console.log('XOR', start, stop, timeDiff);

// test - 2
start = new Date();
for(let ii=0; ii< 10000; ii++)
  for(let i=0; i<1000000; i++) {
    let cc = a;
    a = b;
    b = cc;
  }

stop = new Date();
timeDiff = stop - start;
console.log('Buffer with local var', start, stop, timeDiff);

// test - 2-2
start = new Date();
for(let ii=0; ii< 10000; ii++)
  for(let i=0; i<1000000; i++) {
    c = a;
    a = b;
    b = c;
  }

stop = new Date();
timeDiff = stop - start;
console.log('Buffer with global var', start, stop, timeDiff);

// test - 3
start = new Date();
for(let ii=0; ii< 10000; ii++)
  for(let i=0; i<1000000; i++) {
    a = b + a;
    b = a - b;
    a = a - b;
  }

stop = new Date();
timeDiff = stop - start;
console.log('Math', start, stop, timeDiff);

Запускаем и смотрим:

И вот у нас уже есть пруфы, что обмен через буфер самый быстрый, даже если будем каждый раз создавать временную переменную. Следом идёт XOR, и потом математика, т.к. в теории, математические операции работаю медленнее, чем побитовые.

А теперь давайте всё это протестируем ещё и на С. Начнём с буфера:

// swaptest_buf.c
#include <stdio.h>
#include <sys/time.h>

long getMicrotime() {
  struct timeval currentTime;
  gettimeofday(¤tTime, NULL);
  return currentTime.tv_sec * (int)1e6 + currentTime.tv_usec;
}

int main() {
  int a = 1;
  int b = 9;
  int c = 0;
  
  long startTime = getMicrotime();
  
  // test 1
  for(int ii=0; ii<10000; ii++) {
    for(int i=0; i<1000000; i++) {
      c = a;
      a = b;
      b = c;
    }
  }
  
  long stopTime = getMicrotime();
  long timeDiff = stopTime - startTime;
  
  printf("a= %d, b= %d
", a, b);
  printf("startTime= %ld, stopTime= %ld, timeDiff= %ld
", startTime, stopTime, (timeDiff/1000));
  
  return 0;
}

Компилим и запускаем:

Результат как-то не впечатлил, в 4 раза медленнее, чем то же самое но на JS. Давайте ка обмажемся оптимизацией:

2.7 секунды против ~6 на JS. На самом деле это означает, что JS офигенно быстро работает, всего-то в 2 раза медленне, чем C с максимально оптимизацией.

Но давайте продолжим, C и XOR:

// swaptest_xor.c
#include <stdio.h>
#include <sys/time.h>

long getMicrotime() {
  struct timeval currentTime;
  gettimeofday(¤tTime, NULL);
  return currentTime.tv_sec * (int)1e6 + currentTime.tv_usec;
}

int main() {
  int a = 1;
  int b = 9;
  
  long startTime = getMicrotime();
  
  // test 1
  for(int ii=0; ii<10000; ii++) {
    for(int i=0; i<1000000; i++) {
      a = a ^ b;
      b = b ^ a;
      a = b ^ a;
    }
  }
  
  long stopTime = getMicrotime();
  long timeDiff = stopTime - startTime;
  
  printf("a= %d, b= %d
", a, b);
  printf("startTime= %ld, stopTime= %ld, timeDiff= %ld
", startTime, stopTime, (timeDiff/1000));
  
  return 0;
}

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

Ну и C и математика:

#include <stdio.h>
#include <sys/time.h>

long getMicrotime() {
  struct timeval currentTime;
  gettimeofday(¤tTime, NULL);
  return currentTime.tv_sec * (int)1e6 + currentTime.tv_usec;
}

int main() {
  int a = 1;
  int b = 9;
  
  long startTime = getMicrotime();
  
  // test 1
  for(int ii=0; ii<10000; ii++) {
    for(int i=0; i<1000000; i++) {
      a = b + a;
      b = a - b;
      a = a - b;
    }
  }
  
  long stopTime = getMicrotime();
  long timeDiff = stopTime - startTime;
  
  printf("a= %d, b= %d
", a, b);
  printf("startTime= %ld, stopTime= %ld, timeDiff= %ld
", startTime, stopTime, (timeDiff/1000));
  
  return 0;
}

Результат аналогичный.

Вывод

На низком уровне, для современных процессоров без разницы что выполнять: MOV/PXOR/FISUB/FIADD, разница в пределах погрешности.

А вот на высоком уровне, как минимум в JS, математика и побитовые операции несут больше издержек, чем простой обмен значениями через буфер.

vk f tw in

vk f tw in

Байтоёбство в javascript

Частенько джбаскриптеры любят называть крестовиков байтоёбами. Типа трахаются они со своими memalloc, байтовыми операция, а нам оно и нахуй не нужно, у нас всё супер высокоуровневенько.

Разборка yamaha thr-5

Собрались как-то 2 айтишника, и от нечего делать разобрали ямаху


(4) Комментариев

Алекс - 16.03.2020 06:18:24
- 0    + 0
А замеряйте C++ std::swap, std::move и ещё для строк. Удивитесь
Алекс - 16.03.2020 06:20:29
- 0    + 0
Кроме того, для сложных данных в C обмен двух значений можно вообще не делать. Просто обменять указатели на них. Вот тут непонятно, есть ли аналоги в JS
Ilya - 16.03.2020 07:42:34
- 0    + 0
Да, в жс можно обменяться указателями. Но только для объектов/массивов.

let a = { name: 'a' }
let b = { name: 'b' }
let c = {};

console.log(a, b, c);

c = a;
a = b;
b = c;

console.log(a, b, c);

Тут будет обмен указателями, а не значениями. В JS если нужно обменяться именно значениями объектов, то нужно явно создавать новый объект и назначать ему свойства через Object.assign()
Ilya - 16.03.2020 07:47:29
- 0    + 0
К сожалению C++ я хреново знаю, но да, будет время, дополню ещё и со свапом. Спасибо!