Написать функцию swap

@VitekSR · Регистрация: 20.10.2013

Author24 — интернет-сервис помощи студентам

был вот такой код:

C++

for(i = 0; i < n - 1; i++)
    {
        for(j = i + 1; j < n; j++)
        {
            if(p[i].pro < p[j].pro)
            {
            swap (p[i], p[j]);
            }
        }
    }

нужно теперь написать функцию swap, вот мои наброски, но почему то ничего не получается, помогите:

C++

for(i = 0; i < n - 1; i++)
    {
        for(j = i + 1; j < n; j++)
        {
            if(p[i].pro < p[j].pro)
            {
                void swap (p[i].pro, p[j].pro);
                int t = p[i].pro;
                p[i].pro = p[j].pro;
                p[j].pro = t;
            }
        }
    }

ValeryS · 26.03.2014, 17:35

Сообщение от gazlan

Попробуйте обменять два равных значения.

a=5 b=5
a=a^b 5^5=0
b=a^b 0^5=5
a=a^b 0^5=5

попробовал

Добавлено через 1 минуту
с минусами плюсами
a=a+b; 5+5=10
b=a-b; 10-5=5
a=a-b; 10-5=5

@gazlan · 26.03.2014, 17:58

Сообщение от ValeryS

попробовал

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

ValeryS · 26.03.2014, 18:21

Сообщение от gazlan

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

а зачем их тогда менять

@gazlan · 26.03.2014, 18:35

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

И, к слову, "наивный" метод с третьей переменной, обычно, эффективнее.

@DrOffset · 26.03.2014, 18:59

Вариант с прибитым гвоздями xor (или аналогичный) на современных машинах самый дурацкий. Т.к. вносит прямую зависимость операций, что препятствует эффективному параллельному выполнению внутри конвейера. Т.е. при мизерном выигрыше в памяти получаем замедление выполнения. Еще не стоит забывать, что обменивать так можно только целые числа. И еще, рекомендую чаще смотреть на ассемблерный код, который генерит ваш компилятор, не исключено, что он уже и так оптимизировал вариант с временной переменной, до варианта с xor. Во многих гайдланах к современным компиляторам к тому же написано, что не стоит заниматься ручной микрооптимизацией кода, т.к. это может заблокировать более эффективную и обширную оптимизацию компилятора.
Все это естественно не касается тех, кто пишет под встроенные системы, или около того. Там свои законы, и там оправданное применение xor-swap может найтись. Однако это не отменяет профилирования, а значит доказательства того, что именно этот вариант выигрывает по скорости в нашей задаче.
Юзать такое решение по-умолчанию, не очень хорошая идея, но знать про него безусловно полезно.

Tulosba · 26.03.2014, 19:17

Сообщение от DrOffset

но знать про него безусловно полезно.

В первую очередь полезно знать про нежелательность преждевременных оптимизаций, о чем уже, собственно, было сказано выше.
А варианты с ксорами сродни использованию сдвигов вместо деления/умножения на степень двойки. Часто они рассматриваются новичками как некоторое "хакерского" решение (которое якобы должно работать быстрее) без понимания сути происходящего.

ValeryS · 26.03.2014, 19:57

Сообщение от DrOffset

Еще не стоит забывать, что обменивать так можно только целые числа.

это почему еще

C++

void swapD(long long *a, long long *b)
{
*a=*a^*b;
*b=*a^*b;
*a=*a^*b;
}
 
void swapF(int *a, int *b)
{
*a=*a^*b;
*b=*a^*b;
*a=*a^*b;
}
.........................
float fA=10E30f;
float fB=10E-30f;
 
double dA=10E30;
double dB=10E-30;
 
 
swapD((long long*)&dA,(long long*)&dB);
swapF((int*)&fA,(int*)&fB);

прекрасно меняется

DrOffset, Tulosba, я с вами полностью согласен
а это я так, выпендриваюсь

@DrOffset · 26.03.2014, 20:02

Сообщение от ValeryS

а это я так, выпендриваюсь

Зря. Потому что в стандартах С и С++ совершенно не гарантируется, что указатель будет целым числом. И это работает только потому, что на x86 указатели - целые. Но по стандарту твой код - UB.

ValeryS · 26.03.2014, 20:11

Сообщение от DrOffset

Потому что в стандартах С и С++ совершенно не гарантируется,

сошлюсь на Я. Гашека "Похождение бравого солдата Швейка"
"Много что не разрешается, но допускается"

Сообщение от DrOffset

что указатель будет целым числом. И это работает только потому, что на x86 указатели - целые.

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

@DrOffset · 26.03.2014, 20:18

Не по теме:

Сообщение от ValeryS

а где ты указатели увидел?

Да, сори - проглядел. Увидел параметры и перещелкнуло :)

@gazlan · 26.03.2014, 20:19

Обсуждение в MSDN: Stupid Coding Tricks

ValeryS · 26.03.2014, 20:22

gazlan,
я так понял что там неоднозначность из-за точек следования
недавно где то тема такая пролетала и именно с такой конструкцией

C++

1	a ^= b ^= a ^= b;

@gazlan · 26.03.2014, 20:29

Сообщение от ValeryS

неоднозначность из-за точек следования

Там еще и интересные комментарии к статье :-)

@Alex5 · 27.03.2014, 16:00

Сообщение от gazlan

Обсуждение в MSDN: Stupid Coding Tricks

"During a lunch interview, ... wrote on a napkin: a ^= b ^= a ^= b;"
("За завтраком... написал на салфетке ..." )

Прочитал 1-ю строчку и подумал, стоит ли читать дальше?

Автор заметки "Stupid Coding Tricks", видимо, плохо понимает, о чём пишет. Он путает
1) порядок выполнения операций ^=
этот порядок задан однозначно, т.к. a ^= b ^= a ^= b; эквивалентно a ^= (b ^= (a ^= b) );
2) порядок вычисления аргументов (сначала a, потом b или наоборот). Здесь, действительно C++ не даёт никаких гарантий.

Добавлено через 1 час 22 минуты
Здесь (см.пример на C++) ( Алгоритм обмена при помощи исключающего ИЛИ ) (см.пример на C++) объясняется, почему неправильна запись x ^= (y ^= (x ^= y));

ValeryS · 27.03.2014, 16:08

Сообщение от Alex5

Здесь (см.пример на C++)

я не могу найти, где то здесь на форуме, месяца два назад,человек писал, что всегда пользовался
вот такой записью

C++

1	a ^= b ^= a ^= b;

и все работало, но стоило изменить аргументы, то ли с указателя на ссылку то ли наоборот, и все рухнуло

@Alex5 · 27.03.2014, 21:22

Сообщение от ValeryS

месяца два назад,человек писал

Да, в начале февраля рассматривалась эта тема:

Сообщение от Pershin

вторая запись перестает работать, если вынести обмен в функцию
Хотелось бы разобраться. Компилятор gcc 4.6.3.

@taras atavin · 14.03.2015, 15:42

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

Добавлено через 2 минуты

Сообщение от gazlan

Попробуйте обменять два равных значения.

C++

1
2
3

a^=b; // Здесь a обнуляется
b^=a; // Ксор с нолём равен второму операнду, b сохраняет значение
a^=b; // Ксор с нолём равен второму операнду, a восстанавливает значение

Добавлено через 1 минуту

Сообщение от gazlan

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

Тогда сама задача обмена стоять не должна.

Добавлено через 2 минуты

Сообщение от ValeryS

это почему еще

C++

1	void swapD(long long a, long long b)

А ничего, что полное имя long long вообще то long long int?

Добавлено через 2 минуты

Сообщение от ValeryS

void swapF(int *a, int *b)

Указатель есть целое специального вида, предназначенное для хранения адреса функции, или другого данного, то есть для хранения номер байта (трайта).

Нужны комментарии?

Добавлено через 1 минуту

Сообщение от ValeryS

swapF((int*)&fA,(int*)&fB);

А это только при совпадении размеров. И приведение в данном контексте - грязный хак.

MrGluck · 14.03.2015, 17:14

Сообщение от MastAKK

par1 = par1^par2;

Хреновый вариант. Если менять переменные с одним и тем же адресом он их обнулит.

А для шаблонов - попробуйте передать в swap пользовательский тип. Не вышло? Всё дело в том, что данный алгоритм подходит только для типов, у которых определён operator^.

Добавлено через 2 минуты
Мой вариант (С++11)

C++

template <typename T>
void swap(T &a, T &b)
{
    T tmp(std::move(a));
    a = std::move(b);
    b = std::move(tmp);
}

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

@taras atavin · 14.03.2015, 17:54

Сообщение от MrGluck

реновый вариант. Если менять переменные с одним и тем же адресом он их обнулит.

При совпадении адресов имеет одну переменную и задача обмена её местами просто не может существовать.

ValeryS · 14.03.2015, 18:06

Сообщение от taras atavin

А ничего, что полное имя long long вообще то long long int?

вообще то int допускается опускать
long long тоже самое, что и long long int
short тоже самое, что и short int

Сообщение от taras atavin

А это только при совпадении размеров. И приведение в данном контексте - грязный хак.

а я где то утверждал обратное?

Сообщение от ValeryS

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

Добавлено через 1 минуту

Сообщение от taras atavin

Нужны комментарии?

желательно

ValeryS Модератор 8908 / 6677 / 918 Регистрация: 14.02.2011 Сообщений: 23,521
	26.03.2014, 18:21	23
	Сообщение от gazlan Это не будет работать, если оба аргумента разделяют тот же самый адрес. а зачем их тогда менять 0

@DrOffset 18840 / 9839 / 2408 Регистрация: 30.01.2014 Сообщений: 17,280
	26.03.2014, 18:59	25
	Сообщение было отмечено ValeryS как решение Решение Вариант с прибитым гвоздями xor (или аналогичный) на современных машинах самый дурацкий. Т.к. вносит прямую зависимость операций, что препятствует эффективному параллельному выполнению внутри конвейера. Т.е. при мизерном выигрыше в памяти получаем замедление выполнения. Еще не стоит забывать, что обменивать так можно только целые числа. И еще, рекомендую чаще смотреть на ассемблерный код, который генерит ваш компилятор, не исключено, что он уже и так оптимизировал вариант с временной переменной, до варианта с xor. Во многих гайдланах к современным компиляторам к тому же написано, что не стоит заниматься ручной микрооптимизацией кода, т.к. это может заблокировать более эффективную и обширную оптимизацию компилятора. Все это естественно не касается тех, кто пишет под встроенные системы, или около того. Там свои законы, и там оправданное применение xor-swap может найтись. Однако это не отменяет профилирования, а значит доказательства того, что именно этот вариант выигрывает по скорости в нашей задаче. Юзать такое решение по-умолчанию, не очень хорошая идея, но знать про него безусловно полезно. 3

@DrOffset 18840 / 9839 / 2408 Регистрация: 30.01.2014 Сообщений: 17,280
	26.03.2014, 20:02	28
	Сообщение от ValeryS а это я так, выпендриваюсь Зря. Потому что в стандартах С и С++ совершенно не гарантируется, что указатель будет целым числом. И это работает только потому, что на x86 указатели - целые. Но по стандарту твой код - UB. 1

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	26.03.2014, 20:19	31
	Обсуждение в MSDN: Stupid Coding Tricks 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	26.03.2014, 20:29	33
	Сообщение от ValeryS неоднозначность из-за точек следования Там еще и интересные комментарии к статье :-) 0

ValeryS Модератор 8908 / 6677 / 918 Регистрация: 14.02.2011 Сообщений: 23,521
	26.03.2014, 17:35	21
	Сообщение от gazlan Попробуйте обменять два равных значения. a=5 b=5 a=a^b 5^5=0 b=a^b 0^5=5 a=a^b 0^5=5 попробовал Добавлено через 1 минуту с минусами плюсами a=a+b; 5+5=10 b=a-b; 10-5=5 a=a-b; 10-5=5 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	26.03.2014, 17:58	22
	Сообщение от ValeryS попробовал Угу. Запамятовал. Это не будет работать, если оба аргумента разделяют тот же самый адрес. 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	26.03.2014, 18:35	24
	Эта ситуация возможна, когда обмениваются элементы некоторого набора. Поэтому при использования XOR Swap() обязательна проверка на несовпадение адресов. Ссылку с ходу не дам, но парочка громких фэйлов, связанная с использованием этого трюка в DB точно была. И, к слову, "наивный" метод с третьей переменной, обычно, эффективнее. 0

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	26.03.2014, 19:17	26
	Сообщение от DrOffset но знать про него безусловно полезно. В первую очередь полезно знать про нежелательность преждевременных оптимизаций, о чем уже, собственно, было сказано выше. А варианты с ксорами сродни использованию сдвигов вместо деления/умножения на степень двойки. Часто они рассматриваются новичками как некоторое "хакерского" решение (которое якобы должно работать быстрее) без понимания сути происходящего. 2

ValeryS Модератор 8908 / 6677 / 918 Регистрация: 14.02.2011 Сообщений: 23,521
	26.03.2014, 20:11	29
	Сообщение от DrOffset Потому что в стандартах С и С++ совершенно не гарантируется, сошлюсь на Я. Гашека "Похождение бравого солдата Швейка" "Много что не разрешается, но допускается" Сообщение от DrOffset что указатель будет целым числом. И это работает только потому, что на x86 указатели - целые. а где ты указатели увидел? я беру адрес и интерпретирую его содержимое по другому UB. там может быть из за несовпадения размеров плавающих и целочисленных 0

@DrOffset
	26.03.2014, 20:18 #30
	Не по теме: Сообщение от ValeryS а где ты указатели увидел? Да, сори - проглядел. Увидел параметры и перещелкнуло :) 0

@Alex5 1130 / 789 / 232 Регистрация: 12.04.2010 Сообщений: 2,012
	27.03.2014, 16:00	34
	Сообщение от gazlan Обсуждение в MSDN: Stupid Coding Tricks "During a lunch interview, ... wrote on a napkin: a ^= b ^= a ^= b;" ("За завтраком... написал на салфетке ..." ) Прочитал 1-ю строчку и подумал, стоит ли читать дальше? Автор заметки "Stupid Coding Tricks", видимо, плохо понимает, о чём пишет. Он путает 1) порядок выполнения операций ^= этот порядок задан однозначно, т.к. a ^= b ^= a ^= b; эквивалентно a ^= (b ^= (a ^= b) ); 2) порядок вычисления аргументов (сначала a, потом b или наоборот). Здесь, действительно C++ не даёт никаких гарантий. Добавлено через 1 час 22 минуты Здесь (см.пример на C++) ( Алгоритм обмена при помощи исключающего ИЛИ ) (см.пример на C++) объясняется, почему неправильна запись x ^= (y ^= (x ^= y)); 0

@Alex5 1130 / 789 / 232 Регистрация: 12.04.2010 Сообщений: 2,012
	27.03.2014, 21:22	36
	Сообщение от ValeryS месяца два назад,человек писал Да, в начале февраля рассматривалась эта тема: Сообщение от Pershin вторая запись перестает работать, если вынести обмен в функцию Хотелось бы разобраться. Компилятор gcc 4.6.3. 0

@taras atavin 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	14.03.2015, 17:54	39
	Сообщение от MrGluck реновый вариант. Если менять переменные с одним и тем же адресом он их обнулит. При совпадении адресов имеет одну переменную и задача обмена её местами просто не может существовать. 0

ValeryS Модератор 8908 / 6677 / 918 Регистрация: 14.02.2011 Сообщений: 23,521
	14.03.2015, 18:06	40
	Сообщение от taras atavin А ничего, что полное имя long long вообще то long long int? вообще то int допускается опускать long long тоже самое, что и long long int short тоже самое, что и short int Сообщение от taras atavin А это только при совпадении размеров. И приведение в данном контексте - грязный хак. а я где то утверждал обратное? Сообщение от ValeryS я беру адрес и интерпретирую его содержимое по другому UB. там может быть из за несовпадения размеров плавающих и целочисленных Добавлено через 1 минуту Сообщение от taras atavin Нужны комментарии? желательно 0

Написать функцию swap

Решение