Re: Как закодировать?

From

Andrew Ezhguroff ()

To

Pavel P

Date

2002-10-10T12:23:39Z

Area

RU.ALGORITHMS

 <ao2fd4$dik$1@host.talk.ru> <ao2qp5$2a62$1@ddt.demos.su>
From: "Andrew Ezhguroff" <eandr@com2com.ru>

Привет! "Pavel P" <vprin@indiainfo.com>  сообщил(а):

 PP> Еще для организации циклов. А подавляющее большиство задач
 PP> к этому и сводиться: циклы, преобразования, обработка списков
 PP> и деревьев.

Понятно, что циклы и рекурсия взаимозаменяемы. Но я говорю о другом - о том,
что некоторые алгоритмы "прозрачнее" в рекурсивном виде, а некоторые - в
циклическом.

Но при этом "прозрачность" не гарантирует эффективность:

Классический пример (не уверен, что правильно разобрался с синтаксисом
языка) прозрачности при абсолютной неэффективности (во всяком случае при
реализации в лоб; или Haskell умеет хранить промежуточные результаты и
использовать их для оптимизации?):

Fib 0 = 1
Fib 1 = 1
Fib x = Fib (x-1) + Fib (x-2)

 PP> Си не всегда интерпретаторы то догоняет. Perl со строками
 PP> быстрее чем С работает в области регулярных выражений.

Программа, написанная на Си, работает с регулярными выражениями быстрее, чем
Си? Забавная шутка...

 PP> То что с предпоследного это понятно. Но статик ведет к тому
 PP> что при вызове этой функции из двух паралельных thread'ов
 PP> с большой вероятностью получишь не то что ждешь.

Но Си - не многопоточный язык (вероятно, к счастью - судя по тому, во что
превратили многозадачность в Аде). В этом отношении лямбда-языки скорее
всего имеют преимущество (во всяком случае Хоор для описания взаимодействия
процессов использовал Лисп).

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

  static char  Buf[CHAR_BIT*sizeof(int)+1];
         char *Tmp = Buf+(sizeof(Buf)-1);

меняем на (появился явный '\0'):

  char  Buf[CHAR_BIT*sizeof(int)+1];
  char *Tmp = Buf+(sizeof(Buf)-1);
  *Tmp='\0';

, а

  return Tmp;

меняем (для gcc) на:

  return strdup(Tmp);

, либо (более стандартный вариант):

  return strcpy((new char[sizeof(Buf)-(Buf-Tmp)]), Tmp);

Разумеется, этот вариант несколько медленнее (хотя и не слишком). И память,
выделенную по strdup, или new, придется явно освобождать...

 >> Краткость - это только для ленивых.
 >> Прозрачность - это скорее для статей и учебников. В реальном
 >> программировании "прозрачность" в значительной степени обеспечивается
 >> комментариями (что автоматически снимает требование "краткости").
 PP> И то и другое незаменимо при поддержке и развитии большого
 PP> проекта.

Прозрачность - да. Хотя при выборе между прозрачностью и эффективностью,
скорее предпочтут эффективность. Но вот что касается краткости - не
согласен... Или ты не об этом,

 PP> Сортировка та же рекурсия, но конечная :)

Быстрая сортировка - да. Но ИМХО, большинство сортировок куда понятнее в
"циклическом", чем в рекурсивном варианте.

С уважением, Андрей.


-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.Mail.Ru (2:5020/400)