OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 19 Июнь, 2025 01:08

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




Начать новую тему Ответить на тему  [ Сообщений: 197 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 10  След.
Автор Сообщение
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 12:16 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
PGR писал(а):
Простейший цикл
Код:
WHILE (i < LEN(a)) & ~(a[i] = f) DO INC(i) END;
заменять функцией???


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 12:22 

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Vlad писал(а):
batyrmastyr писал(а):
О вредных привычках, наверное. Поиск через WHILE проще, универсальнее и, частенько, быстрее. :)


В каком языке? На каком компиляторе?

А разве можно выполнить линейный поиск быстрее, чем этот цикл :)
И тут от языка и компилятора ничего не зависит.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 12:25 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Vlad писал(а):
batyrmastyr писал(а):
О вредных привычках, наверное. Поиск через WHILE проще, универсальнее и, частенько, быстрее. :)


В каком языке? На каком компиляторе? Ужас какой - для "пареподавателя" иметь настолько узкий кругозор и требовать от "обучаемых" того же. И при этом кричать о глубоком кризисе нашего образования.


Вот он где, кругозор-то...

Схема лин. поиска -- это всего лишь схема. Она имеет огромное количество вариаций. Для массивов, частей массивов, файлов, последовательностей всемозвожного рода.
В том числе и в части корректной обработки окончания, которое "стандартная функция" не сделает.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вторник, 29 Май, 2007 12:28 

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Кстати, а что find вернет, если элемент не был найден?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 12:34 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
PGR писал(а):
А разве можно выполнить линейный поиск быстрее, чем этот цикл :)


Можно. Хотя более показательным в этом плане будет алгоритм поиска подстроки в строке, где "наивная" реализация скорее всего будет существенно проигрывать "библиотечной".

PGR писал(а):
И тут от языка и компилятора ничего не зависит.


От языка и компилятора зависит будет ли WHILE быстрее всех других конструкций языка на данном компиляторе.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 12:47 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
info21 писал(а):
Вот он где, кругозор-то...

Схема лин. поиска -- это всего лишь схема. Она имеет огромное количество вариаций. Для массивов, частей массивов, файлов, последовательностей всемозвожного рода.
В том числе и в части корректной обработки окончания, которое "стандартная функция" не сделает.


Кругозор позволяет абстрагироваться от вариаций, а не замыкаться на WHILE, массивах и файлах. В моем примере, функция find вернет "конец последовательности" в том случае, если она ничего не нашла. И этот случай легко корректно и обобщенно обработать просто сравнив результат с "концом последовательности".

P.S. Я не против оберона в образовании. Но кругозор у преподавателя должен быть чуть шире конкретно этого языка. Чтобы не доходило до такого маразма как "всегда используйте WHILE для поиска".


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 12:49 

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Vlad писал(а):
PGR писал(а):
А разве можно выполнить линейный поиск быстрее, чем этот цикл :)


Можно.


:shock: Как??? Опишите пожалуйста алгоритм... :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вторник, 29 Май, 2007 12:56 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
PGR писал(а):
Кстати, а что find вернет, если элемент не был найден?


Веренет "конец последовательности". Реализация может быть какой угодно. Например, в случае массивов это может быть -1 или LEN. Важно то, что проверка результата должна быть такая же универсальная, как и функция find и не зависть от конкретной последовательности. Например, что-то типа:
Код:
i := find(a, f);
IF is_end(i) ...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 13:03 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
PGR писал(а):
:shock: Как??? Опишите пожалуйста алгоритм... :)


С учетом особенностей процессора и конкретного компилятора. Напимер, задействовав какой-нибудь MMX или SSE. Учитывая выравнивание или еще какие особенности. Или если компилятор совсем тупой, то хотя бы на асме "rep stosb".


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 13:07 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
PGR писал(а):
:shock: Как??? Опишите пожалуйста алгоритм... :)


Если хочется поломать голову именно над алгоритмом - попробуй не ходя на goggle написать эффективный поиск подстроки в строке. Или эффекивный поиск в строке любого символа из другой строки.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 13:16 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
PGR писал(а):
:shock: Как??? Опишите пожалуйста алгоритм... :)


Вот еще один алгоритм без цикла, который теоретически на каком-то компиляторе может оказаться быстрее WHILE (извиняюсь за C):
Код:
char *find(char *begin, char *end, char f)
{
    return begin == end ? end
         : *begin == f ? begin
         : find(begin + 1, end, f);
}


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 13:16 

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Vlad писал(а):
PGR писал(а):
:shock: Как??? Опишите пожалуйста алгоритм... :)


С учетом особенностей процессора и конкретного компилятора. Напимер, задействовав какой-нибудь MMX или SSE. Учитывая выравнивание или еще какие особенности. Или если компилятор совсем тупой, то хотя бы на асме "rep stosb".

Это уже дело компилятора -- эффективно представить описанный алгоритм на уровне команд процессора. Речь шла о программе на ЯВУ.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 13:18 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
PGR писал(а):
Это уже дело компилятора -- эффективно представить описанный алгоритм на уровне команд процессора. Речь шла о программе на ЯВУ.


Тогда смотри пример с рекурсией :) Там нет WHILE :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 13:26 

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Vlad писал(а):
PGR писал(а):
:shock: Как??? Опишите пожалуйста алгоритм... :)


Вот еще один алгоритм без цикла, который теоретически на каком-то компиляторе может оказаться быстрее WHILE (извиняюсь за C):

Только теоретически. :)
Если компилятор умеет оптимизировать хвостовую рекурсию, то цикл WHILE и подавно.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 13:34 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
PGR писал(а):
Только теоретически. :)
Если компилятор умеет оптимизировать хвостовую рекурсию, то цикл WHILE и подавно.


Тем не менее. Если это компилятор какого-нибудь функционального языка, то теория очень легко превращается в практику. И если уж придираться к словам, то упоминаемый Сергеем foreach, также имеет все шансы оказаться эффективнее while для C#.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 13:36 

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Vlad писал(а):
Вот еще один алгоритм без цикла, который теоретически на каком-то компиляторе может оказаться быстрее WHILE (извиняюсь за C):
Код:
char *find(char *begin, char *end, char f)
{
    return begin == end ? end
         : *begin == f ? begin
         : find(begin + 1, end, f);
}

За такое решение на ЕГЭ дали бы 2 балла за эффективность :D :D :D


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 13:42 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
PGR писал(а):
За такое решение на ЕГЭ дали бы 2 балла за эффективность :D :D :D


Это был пример. Исключительно для расширения кругозора :) И несмотря на это способный оказаться весьма эффективным (хвостовая рекурсия оптимизмруется современными компиляторами).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 13:42 

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Vlad писал(а):
Тем не менее. Если это компилятор какого-нибудь функционального языка, то теория очень легко превращается в практику.

Только по причине отсутствия оператора WHILE в языке.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 13:46 

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Vlad писал(а):
PGR писал(а):
За такое решение на ЕГЭ дали бы 2 балла за эффективность :D :D :D


Это был пример. Исключительно для расширения кругозора :) И несмотря на это способный оказаться весьма эффективным (хвостовая рекурсия оптимизмруется современными компиляторами).

Об эффективности спорить не буду, а вот с понятностью будет похуже :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Об одной задаче из ЕГЭ
СообщениеДобавлено: Вторник, 29 Май, 2007 13:48 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
PGR писал(а):
Vlad писал(а):
Тем не менее. Если это компилятор какого-нибудь функционального языка, то теория очень легко превращается в практику.

Только по причине отсутствия оператора WHILE в языке.


Остается только задуматься о том, почему такой cупер оператор не добавили в язык ;) Наверное потому, что всякие хаскели придумывали "народные ополченцы" :)


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 197 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 10  След.

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


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

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


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

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