OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Пятница, 31 Октябрь, 2025 03:34

Сообщения без ответов | Активные темы


Список форумов » Разное » Другие вопросы по программированию

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  Страница 1 из 2
  [ Сообщений: 27 ]  На страницу 1, 2  След.
  Версия для печати Пред. тема | След. тема 
Автор Сообщение
Vlad
 Заголовок сообщения: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 08:15 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Поскольку тема "правильных" циклов по-прежнему волнует участников данного форума, то предлагаю переписать "по Дейкстре" знаменитый Duff's device: http://en.wikipedia.org/wiki/Duff%27s_device
Код:
dsend(to, from, count)
char *to, *from;
int count;
{
    int n = (count + 7) / 8;
    switch (count % 8) {
    case 0: do { *to = *from++;
    case 7:      *to = *from++;
    case 6:      *to = *from++;
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
               } while (--n > 0);
    }
}


Естественно с максимальной оптимизацией для неоптимизируещего компилятора (каковым является BB). Т.е. минимизировать количество проверок и переходов.

P.S. Не флейма ради :) Просто всегда считал, что "правильно" эту экзотику не перисать. Но может чего упустил (глядишь и сюда можно цикл Дейкстры приятнуть :)
Вернуться к началу
 Профиль  
 
Валерий Лаптев
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 08:23 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Vlad писал(а):
Поскольку тема "правильных" циклов по-прежнему волнует участников данного форума, то предлагаю переписать "по Дейкстре" знаменитый Duff's device: http://en.wikipedia.org/wiki/Duff%27s_device
Код:
dsend(to, from, count)
char *to, *from;
int count;
{
    int n = (count + 7) / 8;
    switch (count % 8) {
    case 0: do { *to = *from++;
    case 7:      *to = *from++;
    case 6:      *to = *from++;
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
               } while (--n > 0);
    }
}


Естественно с максимальной оптимизацией для неоптимизируещего компилятора (каковым является BB). Т.е. минимизировать количество проверок и переходов.

P.S. Не флейма ради :) Просто всегда считал, что "правильно" эту экзотику не перисать. Но может чего упустил (глядишь и сюда можно цикл Дейкстры приятнуть :)


Я когда этот ужас у Страуструпа увидел, подумал - совсем сиплюсники с ума спрыгнули! Такой кошмар в проге писать... :)
Вернуться к началу
 Профиль  
 
Александр Ильин
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 08:40 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2463
Откуда: Россия, Томск
Код:
PROCEDURE UnwindedLoop (from, to, count);
VAR c: INTEGER;
BEGIN
   c := cound DIV 8;
   WHILE c > 0 DO
      to^ := from^; INC (from);
      to^ := from^; INC (from);
      to^ := from^; INC (from);
      to^ := from^; INC (from);
      to^ := from^; INC (from);
      to^ := from^; INC (from);
      to^ := from^; INC (from);
      to^ := from^; INC (from);
      DEC (c)
   END;
   c := count MOD 8;
   WHILE c > 0 DO
      to^ := from^; INC (from);
      DEC (c)
   END
END UnwindedLoop;
Прыжок в середину "развёрнутого" цикла заменён на дополнительный цикл по остатку от деления. По сравнению с Duff's device больше на 1..8 проверок.
Вернуться к началу
 Профиль  
 
Vlad
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 08:41 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Валерий Лаптев писал(а):
Я когда этот ужас у Страуструпа увидел, подумал - совсем сиплюсники с ума спрыгнули! Такой кошмар в проге писать... :)


Этот девайс придумали сишники, С++ в том году только появился на свет ;) Плюшники перепишут его на темплейтах, со всеми делами ;)
Вернуться к началу
 Профиль  
 
Vlad
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 08:45 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Александр Ильин писал(а):
Прыжок в середину "развёрнутого" цикла заменён на дополнительный цикл по остатку от деления. По сравнению с Duff's device больше на 1..8 проверок.


Принято. Но может быть можно как-нибудь "развернуть" эти 1..8 проверок? :)
Вернуться к началу
 Профиль  
 
Александр Ильин
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 08:51 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2463
Откуда: Россия, Томск
Vlad писал(а):
Принято. Но может быть можно как-нибудь "развернуть" эти 1..8 проверок? :)
Можно сделать и одну проверку, конечно, если уж очень сильно хочется:
Код:
PROCEDURE UnwindedLoop (from, to, count);
VAR c: INTEGER;
BEGIN
   c := cound DIV 8;
   WHILE c > 0 DO
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      DEC (c)
   END;
   CASE count MOD 8 OF
   | 7:
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^
   | 6:
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^
   | 5:
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^
   | 4:
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^
   | 3:
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^
   | 2:
      to^ := from^; INC (from);      to^ := from^
   | 1:
      to^ := from^
   | 0:
   END
END UnwindedLoop;
Вернуться к началу
 Профиль  
 
Александр Ильин
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 08:57 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2463
Откуда: Россия, Томск
Vlad писал(а):
Просто всегда считал, что "правильно" эту экзотику не перисать. Но может чего упустил (глядишь и сюда можно цикл Дейкстры приятнуть :)
Ну как, "правильно" получается?
Вернуться к началу
 Профиль  
 
Vlad
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 09:02 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Александр Ильин писал(а):
Можно сделать и одну проверку, конечно, если уж очень сильно хочется:


Я имел ввиду как-нибудь не в лоб :) Т.е. не "дублируя" присваивания в исходном тексте. Вот бы еще на ДРАКОНе кто-нибудь забабахал... Но я подозреваю, что там чуда тоже не будет (будет 7 отдельных веток).
Вернуться к началу
 Профиль  
 
Vlad
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 09:08 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Александр Ильин писал(а):
Vlad писал(а):
Просто всегда считал, что "правильно" эту экзотику не перисать. Но может чего упустил (глядишь и сюда можно цикл Дейкстры приятнуть :)
Ну как, "правильно" получается?


Да понятно, что можно переписать через нормальные циклы. Но изюминка теряется :) Вместо изюминки просто развернутый ручками код...
Вернуться к началу
 Профиль  
 
Александр Ильин
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 09:23 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2463
Откуда: Россия, Томск
Vlad писал(а):
не "дублируя" присваивания в исходном тексте.
Можно пойти на компромисс и вдвое сократить число дополнительных проверок (с 1..8 до 1..4), не так сильно увеличив объём исходника. В первом варианте было на 1 операцию присваивания больше, чем в сишном оригинале, во втором - на 28, здесь - на 7:
Код:
PROCEDURE UnwindedLoop (from, to, count);
VAR c: INTEGER;
BEGIN
   c := cound DIV 8;
   WHILE c > 0 DO
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
      DEC (c)
   END;
   c := count MOD 8;
   IF c # 0 THEN
      IF c DIV 4 # 0  THEN
         to^ := from^; INC (from);      to^ := from^; INC (from);
         to^ := from^; INC (from);      to^ := from^; INC (from);
      END;
      c := c MOD 4;
      IF c DIV 2 # 0 THEN
         to^ := from^; INC (from);      to^ := from^; INC (from);
      END;
      IF ODD(c) THEN
         to^ := from^
      END
   END
END UnwindedLoop;
Вернуться к началу
 Профиль  
 
Александр Ильин
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 09:33 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2463
Откуда: Россия, Томск
Vlad писал(а):
Да понятно, что можно переписать через нормальные циклы. Но изюминка теряется :) Вместо изюминки просто развернутый ручками код...
Там изюминка в том, что организован цикл с 8 точками входа. На ассемблере такое допустимо, но стурктурные языки не должны такого допускать, насколько я понимаю. Что же вы подразумевали под "правильной" реализацией, если не "нормальные" структурные циклы? Вот вам решение "по Дейкстре", даже в нескольких вариантах.
Вернуться к началу
 Профиль  
 
Рэйлвэй Каген
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 10:00 

Зарегистрирован: Воскресенье, 04 Ноябрь, 2007 23:01
Сообщения: 151
Vlad писал(а):
Вот бы еще на ДРАКОНе кто-нибудь забабахал... Но я подозреваю, что там чуда тоже не будет (будет 7 отдельных веток).
Почему отдельных? Думаю, лесенка видна явно.
Вложение:
2.png
2.png [ 7.21 КБ | Просмотров: 12860 ]


Вернуться к началу
 Профиль  
 
Alexey Veselovsky
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 10:09 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Если несколько точек входа... То быть может сопрограммы чем помогут?
В Модуле они вроде есть, сопрограммы эти.
Вернуться к началу
 Профиль  
 
Valery Solovey
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 12:04 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Там написано очень сложно, поэтому я не уверен, что понимаю правильно, но это похоже на вечный цикл.
Вернуться к началу
 Профиль  
 
Александр Ильин
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 13:46 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2463
Откуда: Россия, Томск
Valery Solovey писал(а):
Там написано очень сложно, поэтому я не уверен, что понимаю правильно, но это похоже на вечный цикл.
Где сложно написано? В сишном оригинале?
Вернуться к началу
 Профиль  
 
Александр Ильин
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 13:50 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2463
Откуда: Россия, Томск
Чуть более "регулярный" вариант концовки:
Код:
   c := count MOD 8;
   IF ODD(c) THEN
      to^ := from^; INC (from);
   END;
   c := c DIV 2;
   IF ODD(c) THEN
      to^ := from^; INC (from);      to^ := from^; INC (from);
   END;
   c := c DIV 2;
   IF ODD(c) THEN
      to^ := from^; INC (from);      to^ := from^; INC (from);
      to^ := from^; INC (from);      to^ := from^; INC (from);
   END
Число проверок ровно на 3 больше, чем в Duff's device.
Вернуться к началу
 Профиль  
 
Valery Solovey
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 15:29 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Да, я про сишный вариант. В нём count не меняется, значит n или равно нулю или не будет нулевым никогда.
Вернуться к началу
 Профиль  
 
Александр Ильин
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 15:38 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2463
Откуда: Россия, Томск
Valery Solovey писал(а):
Да, я про сишный вариант. В нём count не меняется, значит n или равно нулю или не будет нулевым никогда.
Инструкция "--n" внутри while уменьшает значение n на единицу. После входа в цикл count уже не при делах.


Последний раз редактировалось Александр Ильин Среда, 06 Май, 2009 15:41, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
Geniepro
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 15:40 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Valery Solovey писал(а):
Да, я про сишный вариант. В нём count не меняется, значит n или равно нулю или не будет нулевым никогда.

Ну как же? n постоянно уменьшается же, значит этот цикл проработает конечное время...

Вообще же это из серии какой длины нужна верёвка, что бы выстрелить себе в голову с максимальным разрушительным эффектом...
Вернуться к началу
 Профиль  
 
Valery Solovey
 Заголовок сообщения: Re: Duff's device vs Дейкстра
СообщениеДобавлено: Среда, 06 Май, 2009 15:43 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Только теперь заметил, оказывается n инициализируется вне цикла.
Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  Страница 1 из 2
  [ Сообщений: 27 ]  На страницу 1, 2  След.

Список форумов » Разное » Другие вопросы по программированию

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2025, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB