EditWYSIWYGAttachPrintable
r2 - 10 Jun 2006 - 14:32:37 - OrloVYou are here: TWiki >  Refaldevel Web > ForJavaProgrammer

Рефал для программиста на Java

Пока пример.

На странице http://nuclight.livejournal.com/111696.html на примере некоторой небольшой задачи (проверка соответствия строки шаблону) сравнивается производительность труда программиста на Pascal и на Java.

Итоги таковы:

  • решение задачи на Pascal потребовало у автора 1.5 часа и занимает 116 строк;
  • решение задачи на Java потребовало 3 часа и занимает 270 строк.

Можно спорить о корректности подобных исследований, однако несомненно, что для некоторых задач Java является слишком тяжеловесным языком, навязывая программисту достаточно неповоротливую модель мышления.

Поскольку обсуждаемая задача состоит в обработке символьной информации, возникает естественное желание воспользоваться для её решения языком Рефал, особенно удобным в подобных случаях.

Приведём формулировку задачи:

Во входном файле две ASCII-строки, одна состоит только из больших латинских букв, в другой могут встречаться большие латинские буквы и еще два спецсимвола - * (звездочка) и ? (знак вопроса). Строки могут иметь длину от 1 до 255 символов, быть в файле в произвольном порядке (но их всего две, формат входных данных корректен). Строку только с буквами назовем словом. Строка со спецсимволами - шаблон, в котором "?" и "*" играют роль символов подстановки по правилам, идентичным wildcards в именах файлов в DOS или Unix-shell, т.е. "?" заменяет собой ровно один произвольный символ, а "*" заменяет собой любое количество произвольных символов - 0 или более (т.е. может заменять и пустую строку). Программа должна выдать ответ YES, если слово подпадает под шаблон (match'ит его), либо NO в противном случае.

У меня решение задачи на Рефале Плюс отняло 20 минут (полностью от начала чтения условия до окончательной версии кода). Занимает 25 строк (см. match.rf).

Вот как выглядит основная функция программы, занимающаяся сопоставлением строки с шаблоном:

1 $func? Match e.word (e.pattern) = ; 2 3 Match \{ 4 t1 e2 (t1 e3) = <Match e2 (e3)>; 5 t1 e2 ('?' e3) = <Match e2 (e3)>; 6 e1 ('*' e3) = { e1 : e11 e12, <Match e12 (e3)>; }; 7 /*empty*/ () = /*yes*/; 8 };

Функция Match принимает в качестве первого аргумента слово, и в качестве второго — шаблон. Расшифруем её определение:

  • строка 4: если первый символ строки совпадает с первым символом шаблона, то сопоставлять остаток строки с остатком шаблона;
  • строка 5: если следующий символ шаблона — '?', то первый символ строки нас не интересует; сопоставлять дальше;
  • строка 6: если следующий символ шаблона — '*', то попробовать разбить строку на две части таким образом, чтобы вторая часть сопоставилась с остатком шаблона;
  • если разбить строку таким образом не удалось, то аварийно завершить работу функции (это обеспечивают фигурные скобки в строке 6); никакие другие варианты сопоставления рассматриваться не будут;
  • строка 7: если всё, что осталось — пустая строка и пустой шаблон, то сопоставление прошло успешно; завершить работу;
  • если осталось что-то другое (никакое из предложений не сработало), то завершить работу неуспехом; если в шаблоне встречались '*', то перебор вариантов сопоставления будет продолжен.

Как видно, Рефал позволяет записать данный алгоритм коротко и ясно. Мало того, при попытке подумать, как подойти к решению данной задачи на Рефале, этот алгоритм выписывается совершенно естественным образом.

Единственным неочевидным местом являются фигурные скобки в строке 6. По сути они означают следующее: если строку не удаётся сопоставить с шаблоном, какую бы её часть мы не отводили на '*', то работа заканчивается (даже если до этого в шаблоне были ещё '*'). Действительно, если хвост строки не сопоставляется с шаблоном, то какое бы мы не отнимали у него начало (с помощью предыдущих '*'), сопоставление не сможет завершиться успешно.

-- OrloV - 09 Jun 2006

Show attachmentsHide attachments
Topic attachments
I Attachment Action Size Date Who Comment
javajava RunMatch.java manage 0.8 K 10 Jun 2006 - 03:33 OrloV Пример запуска рефальской функции Match из Java
elserf match.rf manage 0.4 K 10 Jun 2006 - 14:31 OrloV Решение задачи на Рефале Плюс
elserfi match.rfi manage 0.1 K 10 Jun 2006 - 03:30 OrloV Интерфейс функции Match на Рефале Плюс
Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r6 | r4 < r3 < r2 < r1 | More topic actions...
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback