0 / 1 / 4
Регистрация: 20.10.2013
Сообщений: 270
|
|||||||||||
1 | |||||||||||
Написать функцию swap26.03.2014, 14:26. Показов 12359. Ответов 73
Метки нет (Все метки)
был вот такой код:
0
|
26.03.2014, 14:26 | |
Ответы с готовыми решениями:
73
Заменить функцию swap Чем можно заменить функцию swap? Массив: Описать функцию swap(A,B), меняющую местами максимальные элементы матриц А и В. Напишите функцию Swap(a, b), аргументами которой могут быть числа любого типа |
26.03.2014, 18:35 | 24 |
Эта ситуация возможна, когда обмениваются элементы некоторого набора. Поэтому при использования XOR Swap() обязательна проверка на несовпадение адресов. Ссылку с ходу не дам, но парочка громких фэйлов, связанная с использованием этого трюка в DB точно была.
И, к слову, "наивный" метод с третьей переменной, обычно, эффективнее.
0
|
18840 / 9839 / 2408
Регистрация: 30.01.2014
Сообщений: 17,280
|
|
26.03.2014, 18:59 | 25 |
Сообщение было отмечено ValeryS как решение
Решение
Вариант с прибитым гвоздями xor (или аналогичный) на современных машинах самый дурацкий. Т.к. вносит прямую зависимость операций, что препятствует эффективному параллельному выполнению внутри конвейера. Т.е. при мизерном выигрыше в памяти получаем замедление выполнения. Еще не стоит забывать, что обменивать так можно только целые числа. И еще, рекомендую чаще смотреть на ассемблерный код, который генерит ваш компилятор, не исключено, что он уже и так оптимизировал вариант с временной переменной, до варианта с xor. Во многих гайдланах к современным компиляторам к тому же написано, что не стоит заниматься ручной микрооптимизацией кода, т.к. это может заблокировать более эффективную и обширную оптимизацию компилятора.
Все это естественно не касается тех, кто пишет под встроенные системы, или около того. Там свои законы, и там оправданное применение xor-swap может найтись. Однако это не отменяет профилирования, а значит доказательства того, что именно этот вариант выигрывает по скорости в нашей задаче. Юзать такое решение по-умолчанию, не очень хорошая идея, но знать про него безусловно полезно.
3
|
:)
4773 / 3267 / 497
Регистрация: 19.02.2013
Сообщений: 9,046
|
|
26.03.2014, 19:17 | 26 |
В первую очередь полезно знать про нежелательность преждевременных оптимизаций, о чем уже, собственно, было сказано выше.
А варианты с ксорами сродни использованию сдвигов вместо деления/умножения на степень двойки. Часто они рассматриваются новичками как некоторое "хакерского" решение (которое якобы должно работать быстрее) без понимания сути происходящего.
2
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
|
||||||
26.03.2014, 19:57 | 27 | |||||
это почему еще
DrOffset, Tulosba, я с вами полностью согласен а это я так, выпендриваюсь
0
|
18840 / 9839 / 2408
Регистрация: 30.01.2014
Сообщений: 17,280
|
|
26.03.2014, 20:02 | 28 |
Зря. Потому что в стандартах С и С++ совершенно не гарантируется, что указатель будет целым числом. И это работает только потому, что на x86 указатели - целые. Но по стандарту твой код - UB.
1
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
|
|
26.03.2014, 20:11 | 29 |
сошлюсь на Я. Гашека "Похождение бравого солдата Швейка"
"Много что не разрешается, но допускается" а где ты указатели увидел? я беру адрес и интерпретирую его содержимое по другому UB. там может быть из за несовпадения размеров плавающих и целочисленных
0
|
DrOffset
|
26.03.2014, 20:18
#30
|
0
|
26.03.2014, 20:19 | 31 |
Обсуждение в MSDN: Stupid Coding Tricks
0
|
1130 / 789 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
|
|
27.03.2014, 16:00 | 34 |
Автор заметки "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
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
|
||||||
27.03.2014, 16:08 | 35 | |||||
я не могу найти, где то здесь на форуме, месяца два назад,человек писал, что всегда пользовался
вот такой записью
0
|
1130 / 789 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
|
|
27.03.2014, 21:22 | 36 |
0
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
||||||
14.03.2015, 15:42 | 37 | |||||
Ксор переполняет каждый бит и гарантированно. В данной задаче это не критично, так как переполнение строго парно и исправляет само себя, но беда ксора в неприменимости к большинству типов.
Добавлено через 2 минуты
Тогда сама задача обмена стоять не должна. Добавлено через 2 минуты А ничего, что полное имя long long вообще то long long int? Добавлено через 2 минуты Добавлено через 1 минуту А это только при совпадении размеров. И приведение в данном контексте - грязный хак.
0
|
Форумчанин
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
|
||||||
14.03.2015, 17:14 | 38 | |||||
Хреновый вариант. Если менять переменные с одним и тем же адресом он их обнулит.
А для шаблонов - попробуйте передать в swap пользовательский тип. Не вышло? Всё дело в том, что данный алгоритм подходит только для типов, у которых определён operator^. Добавлено через 2 минуты Мой вариант (С++11)
0
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
14.03.2015, 17:54 | 39 |
При совпадении адресов имеет одну переменную и задача обмена её местами просто не может существовать.
0
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
|
|
14.03.2015, 18:06 | 40 |
вообще то int допускается опускать
long long тоже самое, что и long long int short тоже самое, что и short int а я где то утверждал обратное? Добавлено через 1 минуту желательно
0
|
14.03.2015, 18:06 | |
14.03.2015, 18:06 | |
Помогаю со студенческими работами здесь
40
Создать функцию SWAP, преобразующую заглавные буквы передаваемой ей строки в строчные и наоборот Написать функцию, которая, в зависимости от выбора пользователя вызывает соответствующую функцию Написать функцию, которая могла бы передать значение в другую функцию не могу разобраться как написать функцию сортировки и исправить функцию добавления в стек Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |