refresh cnucok 7bit.forum нacлeдuть
  РегистрацияПользователиАдминистраторы и модераторыПоискЧасто задаваемые вопросы На главную

7bit.forum » Техника » Обмен опытом » Оптимизация » Привет, незнакомец [войти|регистрация]
Распечатать страницу
Понравилась тема? Поделитесь с друзьями!
Автор
Сообщение « Предыдущая тема | Следующая тема »
Pashix
Pashix - мужик
Сэр Байт I-степени


Группа: Пользователи

Дата регистрации: 20.03.2005
Сообщения: 94
Кто?: Выпускник

Репутация пользователя :
+10 -2 = 8
Рейтинг сообщения:
+0 -0 = 0
балл   балл


Оптимизация На верх страницы

Старая прикольная задачка. Была в одном из старых журналов "Какер". Развивает мозг =)

Такой вот код (на С/С++): if (x==a) x=b; else x=a;
При этом изначальный x может быть равен только a или b

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

Лично мне на вскидку пришло в голову 2 симпатичных способа оптимизации, но может кто-нить предложит ещё?

04.05.2006 13:27 Pashix оффлайн Послать письмо Pashix Искать сообщения : Pashix
Нарцисс
Нарцисс - мужик
Лорд Гигабайт I-степени




Группа: VIP-Пользователи

Дата регистрации: 20.12.2004
Сообщения: 1598
Кто?: Абитуриент

Репутация пользователя :
+656 -208 = 448
Рейтинг сообщения:
+0 -0 = 0
балл   балл


На верх страницы

тоже два варианта пришли в голову... не знаю, насколько их можно считать оптимизацией)
if(x==(x=b)) x=a;
x=(x==a?b:a);

__________________
I have seen the truth and it doesn't make any sense

04.05.2006 14:04 Нарцисс оффлайн Сайт Нарцисс Искать сообщения : Нарцисс Добавить Нарцисс в адресную книгу AIM : Нет YIM: Тоже нет
Юрик
Юрик - мужик
Его Величество Администратор




Группа: Администраторы

Дата регистрации: 21.06.2004
Сообщения: 3340
Кто?: Выпускник

Репутация пользователя :
+3212 -428 = 2784
Рейтинг сообщения:
+0 -0 = 0
балл   балл

МОИ ФОТКИ!


RE: Оптимизация На верх страницы

цитата:
Pashix пишет
Такой вот код (на С/С++): if (x==a) x=b; else x=a;
При этом изначальный x может быть равен только a или b

x = -x + b + a

__________________
Xριστος ανεστη εκ νεκρων
Θανατω θανατον πατησας.
Και τοις εν τοις μνημασι
Ζωην χαρισαμενος.

04.05.2006 14:16 Юрик оффлайн Искать сообщения : Юрик Добавить Юрик в адресную книгу
Pashix
Pashix - мужик
Сэр Байт I-степени


Группа: Пользователи

Дата регистрации: 20.03.2005
Сообщения: 94
Кто?: Выпускник

Репутация пользователя :
+10 -2 = 8
Рейтинг сообщения:
+0 -0 = 0
балл   балл

Автор темы Автор темы Pashix


На верх страницы

цитата:
Вольная птица пишет
тоже два варианта пришли в голову... не знаю, насколько их можно считать оптимизацией)
if(x==(x=b)) x=a;
x=(x==a?b:a);


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

цитата:
Юрик пишет
x = -x + b + a


Ага. Один есть.

04.05.2006 14:28 Pashix оффлайн Послать письмо Pashix Искать сообщения : Pashix
Юрик
Юрик - мужик
Его Величество Администратор




Группа: Администраторы

Дата регистрации: 21.06.2004
Сообщения: 3340
Кто?: Выпускник

Репутация пользователя :
+3212 -428 = 2784
Рейтинг сообщения:
+0 -0 = 0
балл   балл

МОИ ФОТКИ!


На верх страницы

(x xor a) xor b

__________________
Xριστος ανεστη εκ νεκρων
Θανατω θανατον πατησας.
Και τοις εν τοις μνημασι
Ζωην χαρισαμενος.

04.05.2006 23:23 Юрик оффлайн Искать сообщения : Юрик Добавить Юрик в адресную книгу
zblk
zblk - мужик
Кронпринц Модератор




Группа: Модераторы

Дата регистрации: 04.10.2004
Сообщения: 1022
Кто?: ninja, групп 1337

Репутация пользователя :
+844 -228 = 616
Рейтинг сообщения:
+0 -0 = 0
балл   балл


На верх страницы

цитата:
Юрик пишет
(x xor a) xor b
если я еще не совсем все забыл, в c xor записывается как ^,т.е:

x ^ a ^ b Wink

или ^=... старость - не радость... кстати, пахать будет только с int, вроде...

Сообщение отредактировано 1 раз(а), редактировал zblk , 05.05.2006 в 00:10.

04.05.2006 23:53 zblk оффлайн Искать сообщения : zblk Добавить zblk в адресную книгу
Stan F
Stan F - мужик
Его Величество Администратор


Группа: Администраторы

Дата регистрации: 14.11.2003
Сообщения: 5148
Кто?: ФЮРЕР

Репутация пользователя :
+1897 -840 = 1057
Рейтинг сообщения:
+1 -0 = 1
балл   балл


На верх страницы

цитата:
Выражение является корректным, но абсолютно не оптимизированым.


чушь. на самом деле основное требование к коду - читаемость и сопровождаемость. если еще 1500 таких случаев снизят быстродействие программы на миллисекунд 10 - я рад.

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

цитата:
кстати, пахать будет только с int

по крайней мере предсказуемо =)

__________________

Последний рассвет
Тонкая нить и
Холодная сталь
Поможет забыть мне
Сотрёт глубину
Исчезнет печаль
Прольётся внутри
Моя мёртвая кровь
Развеет твой крик

05.05.2006 00:18 Stan F оффлайн Сайт Stan F Искать сообщения : Stan F Добавить Stan F в адресную книгу
zblk
zblk - мужик
Кронпринц Модератор




Группа: Модераторы

Дата регистрации: 04.10.2004
Сообщения: 1022
Кто?: ninja, групп 1337

Репутация пользователя :
+844 -228 = 616
Рейтинг сообщения:
+0 -0 = 0
балл   балл


На верх страницы

Stan F, не скажи, это выражение вполне можно привинтить к какой-нибудь сортировке, а если будешь сортировать скажем несколько миллионов значений, пускай даже целых, то поневоле будешь каждую букву оптимизировать Wink

05.05.2006 00:35 zblk оффлайн Искать сообщения : zblk Добавить zblk в адресную книгу
Stan F
Stan F - мужик
Его Величество Администратор


Группа: Администраторы

Дата регистрации: 14.11.2003
Сообщения: 5148
Кто?: ФЮРЕР

Репутация пользователя :
+1897 -840 = 1057
Рейтинг сообщения:
+1 -0 = 1
балл   балл


На верх страницы

premature optimization is the root of evil.

Кнут.

Smile

__________________

Последний рассвет
Тонкая нить и
Холодная сталь
Поможет забыть мне
Сотрёт глубину
Исчезнет печаль
Прольётся внутри
Моя мёртвая кровь
Развеет твой крик

05.05.2006 00:50 Stan F оффлайн Сайт Stan F Искать сообщения : Stan F Добавить Stan F в адресную книгу
zblk
zblk - мужик
Кронпринц Модератор




Группа: Модераторы

Дата регистрации: 04.10.2004
Сообщения: 1022
Кто?: ninja, групп 1337

Репутация пользователя :
+844 -228 = 616
Рейтинг сообщения:
+1 -0 = 1
балл   балл


На верх страницы

hardcore optimization is the root of satanizm bezzuba

05.05.2006 00:54 zblk оффлайн Искать сообщения : zblk Добавить zblk в адресную книгу
Юрик
Юрик - мужик
Его Величество Администратор




Группа: Администраторы

Дата регистрации: 21.06.2004
Сообщения: 3340
Кто?: Выпускник

Репутация пользователя :
+3212 -428 = 2784
Рейтинг сообщения:
+0 -0 = 0
балл   балл

МОИ ФОТКИ!


На верх страницы

цитата:
zblk пишет
кстати, пахать будет только с int, вроде...

строго говоря, применять условие if (x==a) к float-переменным (и т.п.) некорректно, т.к. не исключена вероятность небольшой погрешности в разрядной сетке

__________________
Xριστος ανεστη εκ νεκρων
Θανατω θανατον πατησας.
Και τοις εν τοις μνημασι
Ζωην χαρισαμενος.

05.05.2006 01:04 Юрик оффлайн Искать сообщения : Юрик Добавить Юрик в адресную книгу
Юрик
Юрик - мужик
Его Величество Администратор




Группа: Администраторы

Дата регистрации: 21.06.2004
Сообщения: 3340
Кто?: Выпускник

Репутация пользователя :
+3212 -428 = 2784
Рейтинг сообщения:
+0 -0 = 0
балл   балл

МОИ ФОТКИ!


На верх страницы

цитата:
Stan F пишет
на самом деле основное требование к коду - читаемость и сопровождаемость. если еще 1500 таких случаев снизят быстродействие программы на миллисекунд 10 - я рад.

это верно.. приведённые примеры "оптимизации" только запутают братьев по клинку =)

__________________
Xριστος ανεστη εκ νεκρων
Θανατω θανατον πατησας.
Και τοις εν τοις μνημασι
Ζωην χαρισαμενος.

05.05.2006 01:07 Юрик оффлайн Искать сообщения : Юрик Добавить Юрик в адресную книгу
fenixdeveloper
fenixdeveloper - мужик
Герцог Мегабайт II-степени




Группа: Пользователи

Дата регистрации: 07.01.2006
Сообщения: 517
Кто?: Студент, группа 4663

Репутация пользователя :
+325 -239 = 86
Рейтинг сообщения:
+0 -0 = 0
балл   балл

МОИ ФОТКИ!

Предупреждений: 2


На верх страницы

Вариант с использованием XOR (^) здесь самый оптимальный, я не проверял, но насколько знаю XOR будет работать со всеми числовыми значениями (int, double, float ....) идаже с символьными (char), так как char это тоже есть число, только возможно придётся использовать unsigned char

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

__________________
Я - бушующее пламя.
Я не с вами,не за вами.
Я сжигаю и сгораю,
Возрождаюсь,умираю,
Воскрешаю,убиваю,
Вспоминаю,забываю...

Copyright (C) Aith, http://www.jedi-temple.info/gal_poe-aith.htm

05.05.2006 22:17 fenixdeveloper оффлайн Послать письмо fenixdeveloper Искать сообщения : fenixdeveloper
Pashix
Pashix - мужик
Сэр Байт I-степени


Группа: Пользователи

Дата регистрации: 20.03.2005
Сообщения: 94
Кто?: Выпускник

Репутация пользователя :
+10 -2 = 8
Рейтинг сообщения:
+0 -0 = 0
балл   балл

Автор темы Автор темы Pashix


На верх страницы

цитата:
Юрик пишет
x ^ a ^ b


Всё верно. ИМХО самый быстрый способ.

цитата:

чушь. на самом деле основное требование к коду - читаемость и сопровождаемость. если еще 1500 таких случаев снизят быстродействие программы на миллисекунд 10 - я рад.


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

Зависит это от проекта, от цели, которой добивается разработчик. Споры бесполезны.

10.05.2006 10:33 Pashix оффлайн Послать письмо Pashix Искать сообщения : Pashix
Pashix
Pashix - мужик
Сэр Байт I-степени


Группа: Пользователи

Дата регистрации: 20.03.2005
Сообщения: 94
Кто?: Выпускник

Репутация пользователя :
+10 -2 = 8
Рейтинг сообщения:
+0 -0 = 0
балл   балл

Автор темы Автор темы Pashix


На верх страницы

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

Например, вместо: mov ax,0 мы всегда будем писать xor ax,ax, поскольку второй вариант намного быстрее.

10.05.2006 10:54 Pashix оффлайн Послать письмо Pashix Искать сообщения : Pashix
Понравилась тема? Поделитесь с друзьями!
Чтобы отвечать на сообщения и создавать новые темы, необходимо зарегистрироваться. Присоединяйся к нам! :-)
Перейти:

Все вопросы, связанные с деятельностью сайта и форума решаются с руководителем проекта.

powered by [censored] forum
7bit.team © 2001-2016