nuclight: (Default)
[personal profile] nuclight
 Если переписать обычную программу с использованием ООП, она станет занимать в 2 раза больше места.
Автор неизвестен

К Java есть множество обоснованных нареканий, в частности, низкая скорость работы и большое потребление памяти, не говоря уже о других недостатках. Однако в наше время это не столь критично, а гораздо более важной считается производительность труда программиста (проекты нынче большие и сложные, на разработку следует тратить времени меньше). И здесь, как утверждается, Java должна давать большой выигрыш - легкий в изучении язык, на котором можно быстро разрабатывать программы (сравнительно с предыдущими языками, конечно).
Вот это утверждение я и решил проверить. Способ простой - ставим задачу, и реализуем её на двух языках, замеряя затраченное на разработку и отладку время, а заодно и размер результирующего исходного кода (памятуя о том, что производительность труда программиста в строках в час в промышленных условиях достаточно постоянна и почти не зависит от языка программирования). Причем реализовывать должны два разных человека, чтобы при повторной реализации на дргуом языке не получилось простого портирования алгоритма (что будет быстрее разработки с нуля) с влиянием другого языка.
Итак, взял я задачу, которую сделал незадолго до того (время было известно), нашел программиста на Java, которому было нечего делать, так что он согласился поучаствовать в эксперименте, дал ему условие задачи, и началось.

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

Решение на Паскале.
Я решил эту задачу в условиях олимпиады, наиболее подходящим из разрешенных компиляторов был Borland Pascal. Решил особо не торопясь, за 1 час написав код (в это время входило и продумывание алгоритма, разделять их не будем), еще за полчаса полностью отладив (вообще говоря, для олимпиады это недопустимо долго, что еще раз подчеркивает больший практический характер задачи). Размер полученного исходника составил 116 строк, 2 килобайта, набран полностью вручную (редактор у паскаля очень простой). Исходный текст приведен в приложении 2 (должен без изменений компилироваться на Delphi).

Решение на Java. Выводы.
Задача была решена за 3 часа суммарного чистого времени (написание и долгая отладка), полученный исходник класса, решающего задачу, занимает 270 строк и 8 с лишним килобайт. Надо отметить, что совсем уж высокоуровневые средства были, согласно условию задачи, запрещены, например StringTokenizer, использованный для разбивки строки шаблона по символам "*" (впрочем, его ручная реализация занимает всего 33 строки - см. функцию splitByChar в конце листинга). Несмотря на это, программа изобилует абстракциями - итераторы, ArrayList'ы, и т.п.
Таким образом, можно сделать вывод - использование ООП в стиле Java на широком классе задач примерно в два раза менее эффективно с точки зрения производительности труда программиста, нежели использование для этих целей обыкновенного структурного программирования на традиционных языках.

Замечание о корректности эксперимента.
Наиболее интересным вопросом является, конечно же, насколько полученным выводам можно доверять, что напрямую вытекает из корректности условий проведения эксперимента. Что, если с одной стороны программист несравненно более высокой квалификации, нежели другой, и именно этим и обусловлена существенно большая скорость разработки, а вовсе не свойствами языка и т.п.? Судите сами. С одной стороны - студент 4 курса, почти с голыми руками - простой редактор, старый язык. С другой стороны - программист с 6-летним опытом разработки на Java, вооруженный мощной визуальной средой (Idea), позволяющей парой нажатией клавиш вставлять шаблоны кода, автодополнением, и прочими удобствами редактирования.
Отдельный вопрос - как это проходило. Поздно вечером он начал, через 70 минут был готов первый 160-строчный вариант, еще 30 минут его отлаживали, пока не нашли серьезные ошибки, плюс алгоритм имел экспоненциальную сложность. На следующий день он был занят, затем ночью ему приснился правильный алгоритм, который был потом днем воплощен в жизнь и отлажен. Причем в конце мне пришлось поделиться теми тремя тестами, где алгоритм давал ошибку (да, на олимпиадах так не делают, но для здесь это не важно). В результате за 4 часа (все, конечно же, постоянно отвлекались) был готов правильный вариант. Затем посчитали суммарное чистое время на разработку и отладку, получилось 100+50+30 минут против моих 60+30 минут (см. логи канала #freebsd (в RusNet) за 24-25 апреля).
Полагаю, что одно в достаточной степени компенсирует другое, и в результате его опыт программирвания с одной стороны и мой олимпиадный опыт с другой (и то, задача выбивается из олимпиадных, за неё мало кто взялся на той олимпиаде, когда я её решал) были в равных условиях.





Приложение 1. Исходный текст на Java. Файл rx.java, 270 строк, 8420 байт.
  1  import java.io.LineNumberReader;
  2  import java.io.FileReader;
  3  import java.io.File;
  4  import java.util.ArrayList;
  5  import java.util.Iterator;
  6
  7  public class rx
  8  {
  9      private String patternFromFile;
 10      private String stringFromFile;
 11
 12      public static void main(String[] args) throws Exception
 13      {
 14          long l = System.currentTimeMillis();
 15          rx instance = new rx(args[0]);
 16          boolean b = false;
 17          try
 18          {
 19              b = instance.check();
 20          }
 21          catch (Exception e)
 22          {
 23          }
 24          System.out.println("Match = " + b);
 25          l = System.currentTimeMillis() - l;
 26          System.out.println("Spent time = " + l);
 27      }
 28
 29      private boolean check() throws Exception
 30      {
 31          System.out.println("stringFromFile = " + stringFromFile);
 32          System.out.println("patternFromFile = " + patternFromFile);
 33
 34          if(stringFromFile.indexOf("*") >-1 || stringFromFile.indexOf("?") >-1 )
 35          {
 36              while(stringFromFile.indexOf("**") > -1)
 37                  stringFromFile = stringFromFile.replaceAll("\\*\\*","\\*");
 38              return check(patternFromFile, stringFromFile);
 39          }
 40          while(patternFromFile.indexOf("**") > -1)
 41              patternFromFile = patternFromFile.replaceAll("\\*\\*","\\*");
 42          return check(stringFromFile, patternFromFile);
 43      }
 44
 45      private boolean check(String string, String pattern) throws Exception
 46      {
 47          if(string.equals("") || pattern.equals(""))
 48          {
 49              return string.equals(pattern) || pattern.equals("*");
 50          }
 51
 52          ArrayList patternElements = new ArrayList();
 53          ArrayList tokens = splitByChar(pattern,'*', true);
 54
 55          int countOfSymbolsPattern = 0;
 56          int countOfAsterisks = 0;
 57          int countOfSymbolsString = string.length();
 58
 59          for (Iterator iterator = tokens.iterator(); iterator.hasNext();)
 60          {
 61              String s = (String) iterator.next();
 62              if(s.equals("*"))
 63              {
 64                  countOfAsterisks++;
 65              }
 66              else
 67              {
 68                  countOfSymbolsPattern += s.length();
 69              }
 70              patternElements.add(s);
 71          }
 72
 73          //trivial
 74          if((countOfAsterisks == 0 && countOfSymbolsPattern != countOfSymbolsString) ||
 75                  (countOfSymbolsPattern > countOfSymbolsString))
 76          {
 77              return false;
 78          }
 79
 80          if(patternElements.size() == 1)
 81          {
 82              String s2 = (String) patternElements.get(0);
 83              if(!s2.equals("*"))
 84              {
 85                  return match(string, s2);
 86              }
 87              else
 88              {
 89                  return true;
 90              }
 91          }
 92          else
 93          if(patternElements.size() == 2)
 94          {
 95              String s1 = (String) patternElements.get(0);
 96              String s2 = (String) patternElements.get(1);
 97              if(s1.equals("*"))
 98              {
 99                  if(string.length() >= s2.length())
100                  {
101                      return match(string.substring(string.length() - s2.length()), s2);
102                  }
103                  else
104                  {
105                      return false;
106                  }
107              }
108              else
109              {
110                  if(s2.equals("*"))
111                  {
112                      if(string.length() >= s1.length())
113                      {
114                          return match(string.substring(string.length() - s1.length()), s1);
115                      }
116                      else
117                      {
118                          return false;
119                      }
120                  }
121              }
122          }
123
124          boolean previousWasAsterisk = false;
125          for (int curPatternIndex = 0; curPatternIndex < patternElements.size(); curPatternIndex++)
126          {
127              String curPattern = (String) patternElements.get(curPatternIndex);
128              if(!curPattern.equals("*"))
129              {
130                  //then founding all possible occurences
131                  ArrayList positions = findPositions(string, curPattern);
132                  if(positions.size() == 0)
133                  {
134                      throw new Exception("not found any matches");
135                  }
136                  if(previousWasAsterisk)
137                  {
138                      for (Iterator iterator1 = positions.iterator(); iterator1.hasNext();)
139                      {
140                          Integer integer = (Integer) iterator1.next();
141                          int index = integer.intValue();
142
143                          boolean b1 = curPatternIndex < patternElements.size() - 2;
144                          if(b1)
145                          {
146                              String s2 = string.substring(index + curPattern.length());
147                              String pattern2 = getPatternRange(curPatternIndex + 1, patternElements.size(), patternElements);
148                              boolean check = check(s2, pattern2);
149                              if(check)
150                                  return check;
151                          }
152                          else
153                          {
154                              return string.endsWith(curPattern);
155                          }
156                      }
157                      return false;
158                  }
159                  else
160                  {
161                      Integer integer = (Integer) positions.get(0);
162                      int index = integer.intValue();
163                      if(index != 0)
164                      {
165                          return false;
166                      }
167
168                      if(index + curPattern.length() <= string.length() && curPatternIndex < patternElements.size() - 1)
169                      {
170                          String s2 = string.substring(index + curPattern.length());
171                          String pattern2 = getPatternRange(curPatternIndex + 1, patternElements.size(), patternElements);
172                          return check(s2, pattern2);
173                      }
174                  }
175
176                  previousWasAsterisk = false;
177              }
178              else
179              {
180                  previousWasAsterisk = true;
181              }
182          }
183
184          return previousWasAsterisk;
185      }
186
187      private String getPatternRange(int start, int end, ArrayList patternElements)
188      {
189          StringBuffer stringBuffer = new StringBuffer();
190          for(int i = start; i < end; i++)
191          {
192              stringBuffer.append((String) patternElements.get(i));
193          }
194          return stringBuffer.toString();
195      }
196
197      private ArrayList findPositions(String string, String s)
198      {
199          ArrayList positions = new ArrayList();
200          if(string.length() < s.length())
201          {
202              return positions;
203          }
204          for(int i=0; i<= string.length() - s.length(); i++)
205          {
206              if(match(string.substring(i, i + s.length()), s))
207              {
208                  positions.add(new Integer(i));
209              }
210          }
211          return positions;
212      }
213
214      private boolean match(String s1, String s2)
215      {
216          char[] chars1 = s1.toCharArray();
217          char[] chars2 = s2.toCharArray();
218          for (int i = 0; i < chars1.length; i++)
219          {
220              char c = chars1[i];
221              if ((c != '?' && chars2[i] != '?' && chars2[i] != c))
222              {
223                  return false;
224              }
225          }
226          return true;
227      }
228
229      public rx(String filename) throws Exception
230      {
231          LineNumberReader lnr = new LineNumberReader(new FileReader(new File(filename)));
232          stringFromFile = lnr.readLine();
233          patternFromFile = lnr.readLine();
234          lnr.close();
235      }
236
237      public ArrayList splitByChar(String str, char token, boolean includeToken)
238      {
239          ArrayList arrayList = new ArrayList();
240          char[] chars = str.toCharArray();
241          StringBuffer sb = new StringBuffer();
242          for (int i = 0; i < chars.length; i++)
243          {
244              char aChar = chars[i];
245              if(aChar == token)
246              {
247                  String s = sb.toString();
248                  if(!s.equals(""))
249                  {
250                      arrayList.add(s);
251                  }
252                  sb = new StringBuffer();
253                  if(includeToken)
254                  {
255                      arrayList.add("" + token);
256                  }
257              }
258              else
259              {
260                  sb.append(aChar);
261              }
262
263          }
264          if(!sb.toString().equals(""))
265          {
266              arrayList.add(sb.toString());
267          }
268          return arrayList;
269      }
270  }



Приложение 2. Исходный текст на Паскале (BP 7.0). Файл f.pas, 116 строк, 2048 байт.
  1  program vgu2k6f;
  2  label _e;
  3  var
  4    wrd,pat,t: string;
  5    pa,pv,tp: byte;
  6    y: boolean;
  7
  8  function matchv(pat,wrd: string): boolean;
  9  var i: byte;
 10  begin
 11  matchv:=false;
 12  if pat='*' then
 13  begin
 14    matchv:=true;
 15    exit;
 16  end;
 17  if length(pat)<>length(wrd) then
 18    exit;
 19  for i:=1 to length(pat) do
 20  begin
 21    if pat[i]='?' then
 22      continue;
 23    if pat[i]<>wrd[i] then
 24      exit;
 25  end;
 26  matchv:=true;
 27  end;
 28
 29  function posi(pat,wrd: string): byte;
 30  var
 31    i,j,l: byte;
 32  begin
 33  posi:=0; l:=length(pat);
 34  if pos('?',pat)=0 then
 35  begin
 36    posi:=pos(pat,wrd);
 37    exit;
 38  end;
 39  if length(wrd)<l then
 40    exit;
 41  for i:=1 to length(wrd)-l+1 do
 42    if matchv(pat,copy(wrd,i,l)) then
 43      begin
 44        posi:=i;
 45        break;
 46      end;
 47  end;
 48
 49  begin
 50  Assign(input,'input.txt'); Assign(output,'output.txt');
 51  Reset(input); Rewrite(output);
 52  readln(wrd);
 53  readln(pat);
 54  if (pos('*',wrd)>0) or (pos('?',wrd)>0) then
 55  begin
 56    t:=pat;
 57    pat:=wrd;
 58    wrd:=t;
 59  end;
 60  y:=false;
 61  while pos('**',pat)>0 do
 62    delete(pat,pos('**',pat),1);
 63  while wrd<>'' do
 64  begin
 65    pa:=pos('*',pat);
 66    pv:=pos('?',pat);
 67    if (pa=0) and (pv=0) then
 68    begin
 69      if pat=wrd then
 70        y:=true;
 71      goto _e;
 72    end;
 73    if pv=1 then
 74    begin
 75      delete(wrd,1,1);
 76      delete(pat,1,1);
 77      continue;
 78    end;
 79    if pa>1 then
 80    begin
 81      t:=copy(pat,1,pa-1);
 82      if not matchv(t,copy(wrd,1,pa-1)) then
 83        goto _e;
 84      delete(wrd,1,pa-1);
 85      delete(pat,1,pa-1);
 86      continue;
 87    end;
 88    {the only left case is '*' at pat[1]}
 89    delete(pat,1,1);
 90    if length(pat)=0 then {pat was '*' so will match anything}
 91    begin
 92      y:=true;
 93      goto _e;
 94    end;
 95    pa:=pos('*',pat);
 96    if pa=0 then
 97    begin
 98      if matchv(pat,copy(wrd,length(wrd)-length(pat)+1,length(pat))) then
 99        y:=true;
100      goto _e;
101    end;
102    t:=copy(pat,1,pa-1);
103    tp:=posi(t,wrd);
104    if tp=0 then
105      goto _e;
106    delete(wrd,1,tp+length(t)-1);
107    delete(pat,1,pa-1);
108  end;
109  if matchv(pat,wrd) then
110    y:=true;
111  _e: if y then
112    writeln('YES')
113  else
114    writeln('NO');
115  Close(input); Close(output);
116  end.




Приложение 3. Тесты к задаче. Корректное решение должно выдавать правильные ответы на всех 10 тестах.
Номер тестаПравильный ответВходной файл
1YESASDFAASDASDAAASDASDASD
ASDFAASDASDAAASDASDASD
2YES*
ASDFAASDASDAAASDASDASD
3YESASDFAASDASDAAASDASDASD
A?DF?A*ASD*ASDA?DASD
4NOASDFAASASDAAASDASDASD
ASDFAASDADAAASDASDASD
5YES***************************************************************************************
EKRUGHXCMJGHDFKJGHDFKJGHDFKGHWIERYCNKVBRKDFHGHJOOSJDFGHTASERFHASDGVFJSDGFJSDFG
6YESXPTTWIBEKDWXNVGWBJYWFKSKSEVGDANIEIJYRDVHDEGSAYNAFGWPONMUEPYDVGKYYFRRXTJBEQJBKEPAAJPMGKHAAULXMFICHKJRKDJTCKKFMXTGGFTMMIMOXES
X?T?WIBEK?W*N??W?J?W?KSKS?V*DA?IEIJ??DVHDEG?AYN?F*WP???U???*V?K?YF?*?TJB*Q?*KEPAAJP?G*?AAU???FI*??JR?DJ??KK?*X?G?FT?M??O*?S
7YESIQSRXRKBLUBOSDCXTXDMFHOFFJDGTFPYBXEXAMLODHYSIGCPPTRCJJBHMQPLXBUCJKEUKOPXYSWFUPBEIJIUJRXPFRCDQUDBNGDSGWOYVYVWGVBPXIJEUPJHHAUPQWNIAYUVEVPPLQTBRNKLVLONTYIQOTYNUMBYPFKGFFRYCYMFDCMUSSBEXCGYMVOWYUXRJULUCGICYWTHTYVKMJHBKSGRJUNYXCN
IQ??XR??LUB???C?TX?MF?O?FJDGTFP?BX?X*MLOD???IG?P???CJJ??MQPLXB*CJ?*???PXY*W*?PBEI??UJ?X??RCDQ*D?*G?*?WOY?YV???*??????PJ???*???*I?YUV?V?PL?T?RNKLV?ON?YI????NUMB?PF*?FF*YC??F??MU??BE?C???V??Y?X?JUL????C*W??T?VK*JH?KS?R*U?Y?C?
8YESGBBPLHFMQKBOLBGVLENLOLWQWLOJFKVYPWPTSAFYIPOYVCPJKQBVYRPNKGYDNHVSTJLSMBUQPESMVKVMNHLLGEGYLDIVSRHCPNNGEKLULTWDKWQGTWBQWYNFWFXUMDTYSJAUSRNGBOTYPLBUXCHOTRABWATMQLGDNREQQBIEAAXHLDMELHTALOERTJIOYKCIEBKSVHYHBTMSYYTIRUEMVJJSGMVXGVCHNWGQVSOSFYGXGECEQSKHMOVJFUFQHTK
*B*C*D*E*F*G*H*I*J*K
9NOFTWLREGFKOXPTCXIKXKUDGLXYPLPNWEFHFAYVCILXXUTAMSTFIEUBWRGKRBDANAHYOWMDOEJXMWEXSDELIYMOOWSDTEVVQGJTYPYWLQIUUFTHIALEGRWPSPIVFILDACRWJHEDHNGESIOSUOLGGGWQKJGOUTWTLGIIOHLFDOIULPVCWIDGFTXOFNJLRJIUYRJUEAADPGKWLWCDFJFPYPHWIKVCFOAHMXVWPBOJXCQTPUAPPAMLCCVNMDKFEMNGER
*S*T*E*E*R*V*X*L*S*E
10NORNAMYJEXRJBUHLQXGXULVRRYMKSHQNKSEYWVARUGUNUCTRLYDSQLXXNSTFBNLQSOPHIKMULYODHKFSMHTPHEVSGUPYVIWXQQGTOJYCAIRPVLYLMQCDAHRUQLWQS
R*A?YJ*XRJ?UHXQ???*L?RRYM?SHQN*SEY???RUG?*?C?RLY*SQ????*T?BNLQ?OPHI?MULYOD?KHS?HTPHEVSGUP?VIWXQQJTO?YC*IR?*???*?CDA*R?OSW??




Приложение 4. Иллюстративный материал: решения на других языках.
Мне прислали несколько решений той же задачи на других языках - приводятся здесь исключительно для справки.

Файл ilya666.ml, 24 строки, 908 байт. Точное время не установлено (менее часа).
Язык - Objective Caml (функциональный).
let rec is_it_pattern lst =
  match lst with
  | []      -> false
  | '*' :: tl -> true
  | '?' :: tl -> true
  |  _  :: tl -> is_it_pattern tl
;;
let rec check pattern_word =
  match pattern_word with
  | ([], []) -> true
  | ([], w::wtl)  -> false
  | ('?' :: ptl, w :: wtl)-> check (ptl, wtl)
  | ('?' :: ptl, [])-> false
  | (('*' :: ptl as pattern), (w :: wtl as word))
  -> check (ptl, word) || check (pattern, wtl)
  | ('*' :: ptl, [])-> check (ptl, [])
  | ( p  :: ptl, w :: wtl)-> (p = w) && check (ptl, wtl)
  | ( p  :: ptl, [])-> false
;;
let input, output = open_in "input.txt", open_out "output.txt";;
let read_line () = Stream.npeek 255 (Stream.of_string (input_line input));;
let first, second  = read_line(), read_line();;
let pattern_word = if (is_it_pattern first) then (first, second) else (second, first);;
let _ = output_string output (if check (pattern_word) then "YES" else "NO");;


Файл trux.c, 56 строк, 1085 байт. Время 45 минут.
Компилятор - gcc.
 1  #include <stdio.h>
 2  #include <string.h>
 3
 4  FILE *f;
 5  char s1[258], s2[258];
 6  int prov (int p1, int p2);
 7
 8  int prov (int p1, int p2)
 9  {
10    for (; s1[p1] != '\0' && s2[p2] != '\0';) {
11      if (s1[p1] == '?') {
12        p1++;
13        p2++;
14      }
15      else if (s1[p1] == '*') {
16        for (; s1[p1] == '*'; p1++);
17        int b;
18        for (; s2[p2] != '\0'; p2++) {
19          for (; s2[p2] != s1[p1] && s1[p1] != '?' && s2[p2] != '\0'; p2++);
20            if (s2[p2] == '\0' && s1[p1] != '\0')
21              return 0;
22            if (s2[p2] == '\0' && s1[p1] == '\0')
23              return 1;
24            if (prov (p1, p2))
25              return 1;
26        }
27      } else {
28        if (s1[p1] == s2[p2]) {
29          p1++;
30          p2++;
31        }
32        else
33          return 0;
34      }
35    }
36    if (s1[p1] == '\0' && s2[p2] == '\0')
37      return 1;
38    else
39      return 0;
40  }
41
42  int main ()
43  {
44    f = fopen ("input.txt", "r");
45    fgets (s1, 257, f);
46    fgets (s2, 257, f);
47    int b = prov (0, 0);
48    if (!b) {
49      char s[258];
50      strcpy (s, s1);
51      strcpy (s1, s2);
52      strcpy (s2, s);
53      b = prov (0, 0);
54    }
55    printf ("\n%s\n", (b) ? "YES" : "NO");
56  }


Также были присланы решения на Haskell (тоже функциональный язык) - 20 минут, 15 строк, без ввода-вывода,
и фрагменты решений на Питоне. Все они не проверялись, так как представляют собой портирование основной функции check из решения на OCaml, а на таком низком количестве строк разница в их числе уже не играет статистически значимой роли.



Ссылки по теме:
Page 1 of 2 << [1] [2] >>

Date: 2006-05-07 08:18 pm (UTC)
From: [identity profile] kincajou.livejournal.com
наверное, для каждой задачи есть язык более подходящий, нежели чем любые другие

Date: 2006-05-07 11:13 pm (UTC)
netch: (Default)
From: [personal profile] netch
Видишь, как влияет отсутствие goto :)

Date: 2006-05-08 05:00 am (UTC)
From: [identity profile] ariokh-dark.livejournal.com
Выводы - чушь. Ибо писать такую мелочь на JAVA _для сравнения_ - это из пушки по воробьям.

Более того, совершенно забыта кроссплатформенность результрующего кода JAVA.
Сравнение по определению некорректно.

Date: 2006-05-08 09:13 am (UTC)
From: [identity profile] metaclass.livejournal.com
Компиляторов паскаля тоже хватает для разных платформ. А вообще конечно, сравнение показывает только то, что писать простые вещи на Java - крутое извращение.
Что-нибудь на порядок более сложное на паскале заняло бы два дня, а на яве все те же три часа.

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2006-05-08 11:58 am (UTC) - Expand

Не катит

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 12:09 pm (UTC) - Expand

Re: Не катит

From: [identity profile] thesz.livejournal.com - Date: 2006-05-08 12:40 pm (UTC) - Expand

Re: Не катит

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 06:30 pm (UTC) - Expand

Re: Не катит

From: [identity profile] thesz.livejournal.com - Date: 2006-05-08 08:05 pm (UTC) - Expand

Re: Не катит

From: [identity profile] http://users.livejournal.com/__kas__/ - Date: 2006-05-09 04:49 am (UTC) - Expand

Re: Не катит

From: [identity profile] thesz.livejournal.com - Date: 2006-05-09 11:42 am (UTC) - Expand

(no subject)

From: [identity profile] denspb.livejournal.com - Date: 2007-12-08 08:59 pm (UTC) - Expand

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2007-12-09 12:04 pm (UTC) - Expand

(no subject)

From: [identity profile] denspb.livejournal.com - Date: 2007-12-10 11:29 am (UTC) - Expand

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2007-12-10 02:04 pm (UTC) - Expand

(no subject)

From: [identity profile] denspb.livejournal.com - Date: 2007-12-10 02:27 pm (UTC) - Expand

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2007-12-10 02:42 pm (UTC) - Expand

(no subject)

From: [identity profile] denspb.livejournal.com - Date: 2007-12-10 03:03 pm (UTC) - Expand

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2007-12-10 03:13 pm (UTC) - Expand

(no subject)

From: [identity profile] denspb.livejournal.com - Date: 2007-12-10 03:44 pm (UTC) - Expand

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2007-12-10 04:16 pm (UTC) - Expand

(no subject)

From: [identity profile] denspb.livejournal.com - Date: 2007-12-10 04:44 pm (UTC) - Expand

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2007-12-11 09:42 am (UTC) - Expand

(no subject)

From: [identity profile] denspb.livejournal.com - Date: 2007-12-11 12:58 pm (UTC) - Expand

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2007-12-11 02:16 pm (UTC) - Expand

(no subject)

From: [identity profile] denspb.livejournal.com - Date: 2007-12-11 02:57 pm (UTC) - Expand

(no subject)

From: [identity profile] thesz.livejournal.com - Date: 2007-12-11 03:03 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 03:33 pm (UTC) - Expand

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 06:36 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 07:02 pm (UTC) - Expand

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 07:07 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 08:03 pm (UTC) - Expand

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 08:16 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-09 08:10 am (UTC) - Expand

(no subject)

From: [identity profile] metaclass.livejournal.com - Date: 2006-05-09 08:23 am (UTC) - Expand

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2007-12-10 08:15 am (UTC) - Expand

(no subject)

From: [identity profile] metaclass.livejournal.com - Date: 2007-12-10 11:27 am (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 03:21 pm (UTC) - Expand

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 06:28 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 07:47 pm (UTC) - Expand

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 08:11 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-09 08:16 am (UTC) - Expand

(no subject)

From: [identity profile] metaclass.livejournal.com - Date: 2006-05-09 08:38 am (UTC) - Expand

(no subject)

From: [identity profile] s1m.livejournal.com - Date: 2006-05-12 08:42 pm (UTC) - Expand

(no subject)

From: [identity profile] s1m.livejournal.com - Date: 2006-05-12 08:39 pm (UTC) - Expand

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 06:38 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 07:02 pm (UTC) - Expand

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 07:05 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 08:06 pm (UTC) - Expand

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 08:20 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-09 08:27 am (UTC) - Expand

(no subject)

From: [identity profile] metaclass.livejournal.com - Date: 2006-05-09 08:42 am (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-09 09:02 am (UTC) - Expand

(no subject)

From: [identity profile] alex-mq0.livejournal.com - Date: 2007-12-08 06:51 pm (UTC) - Expand

(no subject)

From: [identity profile] zurtax.livejournal.com - Date: 2007-12-10 07:51 am (UTC) - Expand

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2007-12-10 08:14 am (UTC) - Expand

(no subject)

From: [identity profile] zurtax.livejournal.com - Date: 2007-12-11 08:47 am (UTC) - Expand

Как у тебя все сложно!

Date: 2006-05-08 07:54 am (UTC)
From: [identity profile] ilya666.livejournal.com
Можешь добавить еще вариант на Objective Caml:
let input = open_in "input.txt";;
let output = open_out "output.txt";;

type element = Alpha of char | Asterisk | Question;;

let char_to_element chr = 
  match chr with
  | '?' -> Question
  | '*' -> Asterisk
  |  _  -> Alpha chr
;;

let element_to_char elm = 
  match elm with 
  | Question -> '?'
  | Asterisk -> '*'
  | Alpha chr -> chr
;;

let rec parse stream = 
  try 
    let hd = char_to_element(Stream.next stream) in
    let tl = parse stream in
    hd :: tl 
  with Stream.Failure -> []
;;

let rec is_it_pattern lst = 
  match lst with
  | []		   -> false
  | Asterisk :: tl -> true
  | Question :: tl -> true
  | Alpha a  :: tl -> is_it_pattern tl
;;

let rec check pattern_word =
  match pattern_word with 
  | ([], []) 			-> true
  | ([], w::wtl)  		-> false
  | (Alpha p  :: ptl, w :: wtl) -> (p = w) && check (ptl, wtl)
  | (Alpha p  :: ptl, []) 	-> false
  | (Question :: ptl, w :: wtl) -> check (ptl, wtl)
  | (Question :: ptl, []) 	-> false
  | ((Asterisk :: ptl as pattern), (w :: wtl as word)) 
  				-> check (ptl, word) || check (pattern, wtl)
  | (Asterisk :: ptl, [])	-> check (ptl, [])
;;

let read_parsed_line () = parse (Stream.of_string (input_line input));;
let first = read_parsed_line();;
let second = read_parsed_line();;

let map lst = List.map element_to_char lst;;
let result = if (is_it_pattern first) then check (first, map second) else check (second, map first);;
let _ = output_string output (if result then "YES" else "NO");;
From: [identity profile] nuclight.livejournal.com
Сравнивать это с насквозь императивной жабой как-то не совсем корректно.

>Как у тебя все сложно!

Я правильно понял, что у тебя половина проги разбирает, какая из строк - шаблон? (у меня на паскале это 6 строк)

> Можешь добавить еще вариант на Objective Caml:

Сколько времени заняло?
From: [identity profile] ilya666.livejournal.com
let rec is_it_pattern lst = 
  match lst with
  | []	      -> false
  | '*' :: tl -> true
  | '?' :: tl -> true
  |  _  :: tl -> is_it_pattern tl
;;
let rec check pattern_word =
  match pattern_word with 
  | ([], []) 			-> true
  | ([], w::wtl)  		-> false
  | ('?' :: ptl, w :: wtl)	-> check (ptl, wtl)
  | ('?' :: ptl, [])		-> false
  | (('*' :: ptl as pattern), (w :: wtl as word)) 
  				-> check (ptl, word) || check (pattern, wtl)
  | ('*' :: ptl, [])		-> check (ptl, [])
  | ( p  :: ptl, w :: wtl)	-> (p = w) && check (ptl, wtl)
  | ( p  :: ptl, [])		-> false
;;
let input, output = open_in "input.txt", open_out "output.txt";;
let read_line () = Stream.npeek 255 (Stream.of_string (input_line input));;
let first, second  = read_line(), read_line();;
let pattern_word = if (is_it_pattern first) then (first, second) else (second, first);;
let _ = output_string output (if check (pattern_word) then "YES" else "NO");;
From: [identity profile] gromozeka.livejournal.com
красиво! А как будет работать программа, если паттерн - несколько звездочек, а строка состоит из нескольких тысяч символов? :o) Мне почему-то кажется, что программа зароется в рекурсию.

Date: 2006-05-08 09:23 am (UTC)
From: [identity profile] lord-trux.livejournal.com
vim/g++, 45 минут на всё про всё - 67 строк:
#include 
[Error: Irreparable invalid markup ('<stdio.h>') in entry. Owner must fix manually. Raw contents below.]

vim/g++, 45 минут на всё про всё - 67 строк:
<pre>
#include <stdio.h>
#include <string.h>

FILE *f;
char s1[258], s2[258];
int prov (int p1, int p2);

int
prov (int p1, int p2)
{
for (; s1[p1] != '\0' && s2[p2] != '\0';)
{
if (s1[p1] == '?')
{
p1++;
p2++;
}
else if (s1[p1] == '*')
{
for (; s1[p1] == '*'; p1++);
int b;
for (; s2[p2] != '\0'; p2++)
{
for (; s2[p2] != s1[p1] && s1[p1] != '?' && s2[p2] != '\0';
p2++);
if (s2[p2] == '\0' && s1[p1] != '\0')
return 0;
if (s2[p2] == '\0' && s1[p1] == '\0')
return 1;
if (prov (p1, p2))
return 1;
}
}
else
{
if (s1[p1] == s2[p2])
{
p1++;
p2++;
}
else
return 0;
}
}
if (s1[p1] == '\0' && s2[p2] == '\0')
return 1;
else
return 0;
}

int
main ()
{
f = fopen ("vhod.str", "r");
fgets (s1, 257, f);
fgets (s2, 257, f);
int b = prov (0, 0);
if (!b)
{
char s[258];
strcpy (s, s1);
strcpy (s1, s2);
strcpy (s2, s);
b = prov (0, 0);
}
printf ("\n%s\n", (b) ? "YES" : "NO");
}
</pre>

Date: 2006-05-08 09:26 am (UTC)
From: [identity profile] lord-trux.livejournal.com
Оформление сбилось :-(
Да, для полноты - 1057 байт.

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 12:16 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 03:42 pm (UTC) - Expand

(no subject)

From: [identity profile] lord-trux.livejournal.com - Date: 2006-05-08 04:17 pm (UTC) - Expand

Date: 2006-05-08 09:38 am (UTC)
From: [identity profile] ariokh-dark.livejournal.com
Кстати, перепиши то же самое на Pascal, только без goto

Date: 2006-05-08 03:48 pm (UTC)
From: [identity profile] nuclight.livejournal.com
Пусть эту прогамму и переписать без goto, и на десяток строк не увеличится, но вот в настоящих задачах конечных автоматов и всяческих разбора/компиляции goto весьма полезен.
Зачем я должен отказываться от фичи? Посмотри на решения на других языках в соседних комментах, с их фичами - еще гораздо меньше получилось.

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 06:32 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 07:04 pm (UTC) - Expand

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 07:13 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 07:53 pm (UTC) - Expand

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 07:59 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 08:15 pm (UTC) - Expand

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 08:32 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-09 08:02 am (UTC) - Expand

(no subject)

From: [identity profile] fktrc.livejournal.com - Date: 2006-06-28 05:40 am (UTC) - Expand

Date: 2006-05-08 11:33 am (UTC)
From: [identity profile] ex-ex-zhuzh.livejournal.com
все соревнование, конечно, полная ерунда, но вот вам хаскель до кучи, шоб было

isPat ('?':_) = True
isPat ('*':_) = True
isPat (x:xs)  = isPat xs
isPat _       = False

match []           []         = True
match ('?':ps)     (_:ws)     = match ps ws
match pat@('*':ps) wrd@(_:ws) = match ps wrd || match pat ws
match "*"          []         = True
match (p:ps)       (w:ws)     = p == w && match ps ws
match _            _          = False

main = do
  s1 <- getLine
  s2 <- getLine
  let res = if isPat s1 then match s1 s2 else match s2 s1
  putStrLn $ if res then "YES" else "NO"

Date: 2006-05-08 12:26 pm (UTC)
From: [identity profile] ex-ex-zhuzh.livejournal.com
Эх, ошибку нашел, опозорился.

isPat ('?':_) = True
isPat ('*':_) = True
isPat (x:xs)  = isPat xs
isPat _       = False

match []           []         = True
match ('?':ps)     (_:ws)     = match ps ws
match pat@('*':ps) wrd@(_:ws) = match ps wrd || match pat ws
match ('*':ps)     []         = match ps []
match (p:ps)       (w:ws)     = p == w && match ps ws
match _            _          = False

main = do
  s1 <- getLine
  s2 <- getLine
  let res = if isPat s1 then match s1 s2 else match s2 s1
  putStrLn $ if res then "YES" else "NO"

(no subject)

From: [identity profile] ilya666.livejournal.com - Date: 2006-05-09 11:06 am (UTC) - Expand

(no subject)

From: [identity profile] kozodoev.livejournal.com - Date: 2006-05-10 04:20 am (UTC) - Expand

Date: 2006-05-08 05:03 pm (UTC)
From: [identity profile] http://users.livejournal.com/_winnie/
программа:

#include <iostream>
#include <string>

//10:16
bool match(const char *word, char const *pattern)
{
    if (!*pattern) return !*word;
    if (*word == *pattern || *pattern == '?') return match(word+1, pattern+1);
    if (*pattern != '*') return false;
    while (*word)  if (match(word++, pattern+1)) return true;
    return match(word, pattern+1);
}
//10:22


int main(int argc, char *argv[])
{
    std::string s1, s2;
    while(std::cin >> s1 >> s2) //что бы не запускать на каждом файле, берётся по по две строчки из одного.
        std::cout << ((match(s1.c_str(), s2.c_str()) || match(s2.c_str(), s1.c_str())) ? "YES" : "NO") <<'\n';
}






файл input.txt:
ASDFAASDASDAAASDASDASD
ASDFAASDASDAAASDASDASD

*
ASDFAASDASDAAASDASDASD

ASDFAASDASDAAASDASDASD
A?DF?A*ASD*ASDA?DASD

ASDFAASASDAAASDASDASD
ASDFAASDADAAASDASDASD

***************************************************************************************
EKRUGHXCMJGHDFKJGHDFKJGHDFKGHWIERYCNKVBRKDFHGHJOOSJDFGHTASERFHASDGVFJSDGFJSDFG

XPTTWIBEKDWXNVGWBJYWFKSKSEVGDANIEIJYRDVHDEGSAYNAFGWPONMUEPYDVGKYYFRRXTJBEQJBKEPAAJPMGKHAAULXMFICHKJRKDJTCKKFMXTGGFTMMIMOXES
X?T?WIBEK?W*N??W?J?W?KSKS?V*DA?IEIJ??DVHDEG?AYN?F*WP???U???*V?K?YF?*?TJB*Q?*KEPAAJP?G*?AAU???FI*??JR?DJ??KK?*X?G?FT?M??O*?S

IQSRXRKBLUBOSDCXTXDMFHOFFJDGTFPYBXEXAMLODHYSIGCPPTRCJJBHMQPLXBUCJKEUKOPXYSWFUPBEIJIUJRXPFRCDQUDBNGDSGWOYVYVWGVBPXIJEUPJHHAUPQWNIAYUVEVPPLQTBRNKLVLONTYIQOTYNUMBYPFKGFFRYCYMFDCMUSSBEXCGYMVOWYUXRJULUCGICYWTHTYVKMJHBKSGRJUNYXCN
IQ??XR??LUB???C?TX?MF?O?FJDGTFP?BX?X*MLOD???IG?P???CJJ??MQPLXB*CJ?*???PXY*W*?PBEI??UJ?X??RCDQ*D?*G?*?WOY?YV???*??????PJ???*???*I?YUV?V?PL?T?RNKLV?ON?YI????NUMB?PF*?FF*YC??F??MU??BE?C???V??Y?X?JUL????C*W??T?VK*JH?KS?R*U?Y?C?

GBBPLHFMQKBOLBGVLENLOLWQWLOJFKVYPWPTSAFYIPOYVCPJKQBVYRPNKGYDNHVSTJLSMBUQPESMVKVMNHLLGEGYLDIVSRHCPNNGEKLULTWDKWQGTWBQWYNFWFXUMDTYSJAUSRNGBOTYPLBUXCHOTRABWATMQLGDNREQQBIEAAXHLDMELHTALOERTJIOYKCIEBKSVHYHBTMSYYTIRUEMVJJSGMVXGVCHNWGQVSOSFYGXGECEQSKHMOVJFUFQHTK
*B*C*D*E*F*G*H*I*J*K

FTWLREGFKOXPTCXIKXKUDGLXYPLPNWEFHFAYVCILXXUTAMSTFIEUBWRGKRBDANAHYOWMDOEJXMWEXSDELIYMOOWSDTEVVQGJTYPYWLQIUUFTHIALEGRWPSPIVFILDACRWJHEDHNGESIOSUOLGGGWQKJGOUTWTLGIIOHLFDOIULPVCWIDGFTXOFNJLRJIUYRJUEAADPGKWLWCDFJFPYPHWIKVCFOAHMXVWPBOJXCQTPUAPPAMLCCVNMDKFEMNGER
*S*T*E*E*R*V*X*L*S*E

RNAMYJEXRJBUHLQXGXULVRRYMKSHQNKSEYWVARUGUNUCTRLYDSQLXXNSTFBNLQSOPHIKMULYODHKFSMHTPHEVSGUPYVIWXQQGTOJYCAIRPVLYLMQCDAHRUQLWQS
R*A?YJ*XRJ?UHXQ???*L?RRYM?SHQN*SEY???RUG?*?C?RLY*SQ????*T?BNLQ?OPHI?MULYOD?KHS?HTPHEVSGUP?VIWXQQJTO?YC*IR?*???*?CDA*R?OSW??


Время - около 40 минут.
Язык - С/С++

Date: 2006-05-08 05:19 pm (UTC)
From: [identity profile] nuclight.livejournal.com
Не компилируется.
gcc version 3.4.2 [FreeBSD] 20040728

И совать всё в один файл - плохая идея, у меня уже под кучу отдельных заточено.

(no subject)

From: [identity profile] http://users.livejournal.com/_winnie/ - Date: 2006-05-08 08:34 pm (UTC) - Expand

(no subject)

From: [identity profile] http://users.livejournal.com/_winnie/ - Date: 2006-05-09 05:30 am (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-09 07:54 am (UTC) - Expand

(no subject)

From: [identity profile] ex-croco667.livejournal.com - Date: 2006-05-09 10:48 am (UTC) - Expand

p.s.

From: [identity profile] ex-croco667.livejournal.com - Date: 2006-05-09 10:50 am (UTC) - Expand

Re: p.s.

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-09 11:03 am (UTC) - Expand

Re: p.s.

From: [identity profile] gromozeka.livejournal.com - Date: 2006-05-09 01:47 pm (UTC) - Expand

(no subject)

From: [identity profile] ex-croco667.livejournal.com - Date: 2006-05-09 10:46 am (UTC) - Expand

(no subject)

From: [identity profile] ilya666.livejournal.com - Date: 2006-05-09 11:08 am (UTC) - Expand

(no subject)

From: [identity profile] aruslan.livejournal.com - Date: 2006-05-09 02:50 pm (UTC) - Expand

(no subject)

From: [identity profile] dottedmag.livejournal.com - Date: 2006-05-17 02:03 pm (UTC) - Expand

(no subject)

From: [identity profile] laial-narrin.livejournal.com - Date: 2012-10-03 04:21 pm (UTC) - Expand

(no subject)

From: [identity profile] dims12.livejournal.com - Date: 2006-07-07 07:35 pm (UTC) - Expand

Date: 2006-05-08 05:12 pm (UTC)
From: [identity profile] glebedev.livejournal.com
Написал за 32 минуты программу, которая проходит все тесты. Но думаю ошибки есть, так как в процессе написания встречал ситуации, когда у меня была явная ошибка, а тесты этого не выявляли.

Язык - C#

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace ConsoleApplication3
{
class Program
{
static bool Comparer(string word, string pattern)
{
int wpos = 0;
int ppos = 0;
while (wpos < word.Length && ppos < pattern.Length)
{
if (pattern[ppos] == '*' || pattern[ppos] == '?')
{
int chars = 0;
bool bwilds = false;
while (ppos < pattern.Length)
{
if (pattern[ppos] == '*')
{
bwilds = true;
++ppos;
}
else if (pattern[ppos] == '?')
{
++chars;
++ppos;
}
else
break;
}
if (ppos >= pattern.Length)
return true;
wpos += chars;
if (wpos > word.Length)
return false;
int newpos;
if (bwilds)
{
while (wpos < word.Length && (newpos = word.IndexOf(pattern[ppos], wpos)) > 0)
{
if (Comparer(word.Substring(newpos), pattern.Substring(ppos)))
return true;
wpos = newpos + 1;
}
return false;
}
}
if (pattern[ppos] != word[wpos])
return false;
++ppos;
++wpos;
}
if (wpos == word.Length && ppos == pattern.Length)
return true;
if (wpos == word.Length)
{
while (ppos < pattern.Length)
{
if (pattern[ppos] != '?' && pattern[ppos] != '*')
return false;
++ppos;
}
return true;
}
return false;
}
static void CompareFile(string name)
{
StreamReader reader = new StreamReader(name);
string pattern,word;

try
{
for (; ; )
{
pattern = reader.ReadLine();
word = reader.ReadLine();
if (word.IndexOfAny(new char[] { '?', '*' }) >= 0)
{
string a = pattern;
pattern = word;
word = a;
}
if (Comparer(word, pattern))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
} catch
{
}
}
static void Main(string[] args)
{
CompareFile(@"D:\1.txt");
}
}
}
From: [identity profile] nuclight.livejournal.com
А нельзя было это в <pre></pre> обернуть? Всё форматирование ж съехало.

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

Например?

Date: 2006-05-08 06:46 pm (UTC)
From: [identity profile] ariokh-dark.livejournal.com
Кстати, убрал бы ты ссылку на этого Африканца, а то там бред такой, что ой просто!

Date: 2006-05-08 07:00 pm (UTC)
From: [identity profile] nuclight.livejournal.com
А в чем бред заключается?
Там кстатии в урле имя файла убери, в листинге каталога еще несколько увидишь. Там есть обсуждение этих статей. Плюс надо учитывать, что написано оно лет эдак 6 назад, если не раньше.

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 07:02 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 08:08 pm (UTC) - Expand

(no subject)

From: [identity profile] ariokh-dark.livejournal.com - Date: 2006-05-08 08:19 pm (UTC) - Expand

(no subject)

From: [identity profile] ex-croco667.livejournal.com - Date: 2006-05-08 08:28 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-09 08:05 am (UTC) - Expand

(no subject)

From: [identity profile] http://users.livejournal.com/d_m_/ - Date: 2007-12-08 08:06 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2007-12-10 11:53 am (UTC) - Expand

(no subject)

From: [identity profile] anatoliy.livejournal.com - Date: 2006-05-08 07:13 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-08 07:50 pm (UTC) - Expand

(no subject)

From: [identity profile] anatoliy.livejournal.com - Date: 2006-05-08 08:15 pm (UTC) - Expand

Да

From: [identity profile] anatoliy.livejournal.com - Date: 2006-05-08 07:01 pm (UTC) - Expand

Re: Да

From: [identity profile] http://users.livejournal.com/d_m_/ - Date: 2007-12-08 07:55 pm (UTC) - Expand

Re: Да

From: [identity profile] anatoliy.livejournal.com - Date: 2007-12-09 05:32 am (UTC) - Expand

Re: Да

From: [identity profile] http://users.livejournal.com/d_m_/ - Date: 2007-12-09 08:35 am (UTC) - Expand

Date: 2006-05-08 07:13 pm (UTC)
From: [identity profile] sraider.livejournal.com
Как уже кто-то сказал - выводов из этого вообще никаких нельзя сделать. Выполнение одной задачи программистами наверняка разного уровня, да еще и всего один раз...

Кстати, помимо скорости написания кода очень важно еще:
а) повторная используемость кода (например, написанное выше на Паскале будет работать только с однобайтными символами, а решение на C++ наверняка представляло бы шаблон, который можно в том числе для wide chars использовать - хоть UCS-2, хоть UCS-4)
б) читабельность написанного кода. проще читать - проще (дешевле) поддерживать

Date: 2006-05-08 07:53 pm (UTC)
From: [identity profile] nuclight.livejournal.com
а) могло бы, но приведенные здесь решения этого почему-то не сделали, кроме того, такие изменения не столь сложны
б) приведенное решение на жабе как раз-таки отличается меньшей читабельностью от варианта на паскале

(no subject)

From: [identity profile] sraider.livejournal.com - Date: 2006-05-08 08:18 pm (UTC) - Expand

Scheme

Date: 2006-05-08 07:22 pm (UTC)
From: [identity profile] rmrfchik.livejournal.com
Тоже на scheme. rx.scm (http://justnews.ru/rx.scm.html). Фтыкайте ;)

Re: Scheme

Date: 2006-05-08 07:24 pm (UTC)
From: [identity profile] rmrfchik.livejournal.com
ЭЭ, там только содержательная часть. Т.е. вызывать (matcher "строка раз" "строка двас")

Re: Scheme

From: [identity profile] ex-croco667.livejournal.com - Date: 2006-05-08 08:15 pm (UTC) - Expand

Re: Scheme

From: [identity profile] rmrfchik.livejournal.com - Date: 2006-05-09 05:41 am (UTC) - Expand

Re: Scheme

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-09 07:51 am (UTC) - Expand

Re: Scheme

From: [identity profile] rmrfchik.livejournal.com - Date: 2006-05-09 09:44 am (UTC) - Expand

Решение на InteLib Lisp'е

Date: 2006-05-08 08:09 pm (UTC)
From: [identity profile] ex-croco667.livejournal.com
Хороший повод поразмяться, тем более что команда местных функциональщиков Лисп вниманием обошла.

(defun ispattern (list) 
    (cond ((null list) nil)
          ((eql (car list) #\*) t)
          ((eql (car list) #\?) t)
          (t (ispattern (cdr list)))
    )
)

(defun starmatch (word restpat)
    (cond
        ((match word restpat) t)
        ((null word) nil)
        ((starmatch (cdr word) restpat) t)
        (t nil)
    )
)

(defun match (word pattern)
    (cond 
        ((null pattern) (null word))
        ((eql (car pattern) #\?)
            (if (null word) nil (match (cdr word) (cdr pattern)))
        )
        ((eql (car pattern) #\*)
            (starmatch word (cdr pattern))
        )
        ((eql (car pattern) (car word))
            (match (cdr word) (cdr pattern))
        )
        (t nil)
    )
)

(defun main ()
    (let ((line1 (string2list (lfgets *standard-input*)))
          (line2 (string2list (lfgets *standard-input*)))
         )
        (if (ispattern line1) (match line2 line1) (match line1 line2))
    )
)


40 строк, 950 символов, с нуля чуть меньше 40 минут, включая исправление баги в InteLib'е и пересборку InteLib'а, соответственно :) (оказалось, lfgets я ни разу еще не использовал, и в ней-то как раз бага и притаилась). Пойду теперь делать исправленный релиз InteLib'а (за номером 0.5.78).

P.S. Тесты все проходят, естественно. Заработало со второй попытки (при первой попытке была забыта проверка на одновременную пустоту образца и слова).
From: [identity profile] nuclight.livejournal.com
Да, я уже сам было подумывал, не попробовать ли на Лиспе. Кстати, что, как плюсовый специалист, скажешь о самом коротком приведенном решении на C++ ? Какое-то оно чересчур короткое :)

Date: 2006-05-09 12:36 pm (UTC)
From: [identity profile] gin-nnov.livejournal.com
Ну если уж вот это:
37                  stringFromFile = stringFromFile.replaceAll("\\*\\*","\\*");

разрешено, то проще сделать так:
public class Matcher {
	static boolean match(String pattern, String word) {
		String goodPattern = pattern.replaceAll("\\*", ".*");
		goodPattern = "\\A" + goodPattern.replaceAll("\\?", ".?") + "\\z";
		
		return word.matches(goodPattern);
	}
	
	static boolean matchFromFile(String filename) throws java.io.IOException{
		java.io.File f = new java.io.File(filename);
		java.io.BufferedReader breader = new java.io.BufferedReader(
						new java.io.FileReader(f));
		String line1  = breader.readLine();
		String line2  = breader.readLine();
		
		return Matcher.match(line2, line1);
	}
	
	static public void main(String[] a) {
		try {
			System.out.println(Matcher.matchFromFile(a[0]));
		} catch (java.io.IOException ioe) {
			ioe.printStackTrace();
		}
	}
}


26 строк, 782 байта :)

Date: 2006-05-09 12:38 pm (UTC)
From: [identity profile] gin-nnov.livejournal.com
По времени решение заняло 11 минут.

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-09 03:02 pm (UTC) - Expand

(no subject)

From: [identity profile] gin-nnov.livejournal.com - Date: 2006-05-09 07:50 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-13 11:00 am (UTC) - Expand

(no subject)

From: [identity profile] gin-nnov.livejournal.com - Date: 2006-05-13 12:10 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-13 01:06 pm (UTC) - Expand

(no subject)

From: [identity profile] ex-soundwell971.livejournal.com - Date: 2006-05-20 09:13 am (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-20 11:51 am (UTC) - Expand

Date: 2006-05-10 07:01 am (UTC)
From: [identity profile] diam-2003.livejournal.com
Боюсь, это не самые лучшие примеры.

Программу на Java можно переписать в том же стиле, что и программу на C - то есть, как маленькое решение маленькой задачи. То же самое справедливо относительно программы на Pascal-е.

Date: 2006-05-10 09:33 am (UTC)
From: [identity profile] ilya666.livejournal.com
Но почему-то этого никто не сделал.

(no subject)

From: [identity profile] diam-2003.livejournal.com - Date: 2006-05-10 11:25 am (UTC) - Expand

Date: 2006-05-12 07:22 am (UTC)
From: [identity profile] diam-2003.livejournal.com
Решение на Java. 5 минут в Eclipse, 49 строк кода.

Программа решает немного более общую задачу (определяет, "пересекаются" ли два регулярных выражения). Меня немного смутил тезис Строки могут иметь длину от 1 до 255 символов, быть в файле в произвольном порядке (но их всего две, формат входных данных корректен). Впрочем, как я заметил, большинство приведенных решений этот момент вообще игнорируют, а среди тестов нет примера, когда обе строки являются шаблонами - например, "a*" и "*b". Модифицировать ее понятно как (добавить к "состояниям парсера" флажок: какую из строк мы взялись интерпретировать как шаблон).

package stringmatcher;

import java.io.*;
import java.util.*;

public class StringMatcher {

    public static class IntInt { 
        public int i, j;

        public IntInt(int i, int j) {
            this.i = i;
            this.j = j;
        } 
    }
    
    public static boolean match(String s1, String s2) {
        int n1 = s1.length();
        int n2 = s2.length();
        Queue q = new LinkedList();
        q.add(new IntInt(0, 0));
        while (!q.isEmpty()) {
            IntInt p = q.poll();
            if (p.i==n1 && p.j==n2) 
                return true;
            else if (p.i==n1 || p.j==n2)
                continue;
            else if (s1.charAt(p.i)=='*' || s2.charAt(p.j)=='*') {
                q.add(new IntInt(p.i, p.j+1));
                q.add(new IntInt(p.i+1, p.j));
                q.add(new IntInt(p.i+1, p.j+1));
            }
            else if (s1.charAt(p.i)=='?' || s2.charAt(p.j)=='?' || s1.charAt(p.i) == s2.charAt(p.j))
                q.add(new IntInt(p.i+1, p.j+1));            
        }
        return false;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(new File("input.txt")));
        String s1 = reader.readLine();
        String s2 = reader.readLine();
        if (match(s1, s2)) 
            System.out.println("YES");
        else 
            System.out.println("NO");
    }

}


Date: 2006-05-13 11:18 am (UTC)
From: [identity profile] nuclight.livejournal.com
Я даже и не знаю, как это можно было не понять, и как можно было не заметить, что практически все приведенные решения это учитывают - определяют, какая из строк является шаблоном, а какая нет, и соответствующим образом вызывают процедуру матчинга (зачем какие-то флажки ставить, когда можно поменять аргументы местами).

По приведенному решению - это что вообще и как работает?! На решение оригинальной задачи - не похоже. У меня, вообще говоря, возникают сомнения насчет допустимости использования готовых объектов для связных списков, но и без этого, оно даже не компилируется:

StringMatcher.java:23: incompatible types
found   : java.lang.Object
required: stringmatcher.StringMatcher.IntInt
            IntInt p = q.poll();
                             ^
Note: StringMatcher.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error

(no subject)

From: [identity profile] diam-2003.livejournal.com - Date: 2006-05-15 07:22 am (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-16 06:07 am (UTC) - Expand

о-ооо

From: [identity profile] comrade-che.livejournal.com - Date: 2006-05-16 08:26 am (UTC) - Expand

Re: о-ооо

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-20 12:13 pm (UTC) - Expand

(no subject)

From: [identity profile] denspb.livejournal.com - Date: 2007-12-08 08:18 pm (UTC) - Expand

Date: 2006-05-14 09:38 pm (UTC)
From: [identity profile] yanis.livejournal.com
что-то на Яве код какой-то левый . Кстати, На Си решение строчек в 10 уместится

Date: 2006-05-16 07:57 am (UTC)
From: [identity profile] iamjaph.livejournal.com
# 11 минут, влючая прогон тестов и чтение задачи (может все не дочитал :-) ).
use strict;
use warnings;

my ($pattern, $text) = <>;
($pattern, $text) = ($text, $pattern) if $text =~ /[?*]/;
my $re = $pattern;
foreach ($re) {
s/\?/.?/g;
s/\*/.*/g;
}
print $text =~ m/$re/ ? "YES" : "NO", "\n";

Date: 2006-05-18 12:19 pm (UTC)
From: [identity profile] oal.livejournal.com
Тут (http://oal.livejournal.com/202368.html?thread=369024#t369024) -- на перле-же, но гораздо страшнее. :)

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2006-05-20 11:54 am (UTC) - Expand

(no subject)

From: [identity profile] what-me.livejournal.com - Date: 2006-05-21 01:42 pm (UTC) - Expand

(no subject)

From: [identity profile] bealex.livejournal.com - Date: 2007-12-08 07:41 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2007-12-10 10:51 am (UTC) - Expand

некорректный пример

Date: 2006-05-17 11:15 am (UTC)
From: [identity profile] ospf-ripe.livejournal.com
приемущества Явы проявляются только в очень больших задачах. Так что ничего удивительного, что данную задачу на Яве решать хуже.

P. S. /me поклонник Явы, но из за отсутствия нормальных ява машин под BSD приходится пока использовать другие языки.

Re: некорректный пример

Date: 2006-05-20 12:01 pm (UTC)
From: [identity profile] nuclight.livejournal.com
>приемущества Явы проявляются только в очень больших задачах. Так что ничего удивительного, что данную задачу на Яве решать хуже.

Это, вообще говоря, очень странно, когда преимущества языка проявляются только в очень больших задачах. Особенно если учесть, что чем больше проект, тем меньше непосредственная роль языка. Так что эти преимущества, если они есть, обеспечены совсем не языком.

>/me поклонник Явы

Очень зря.

>но из за отсутствия нормальных ява машин под BSD

diablo-jdk ж недавно вышел, официально сертифицированный.

Date: 2006-07-07 07:12 pm (UTC)
From: [identity profile] dims12.livejournal.com
Я тоже считаю, что выводы некорректны. Джава сильна именно тем, что упорядочивает процесс написания библиотек одними людьми и их использование и усовершенствование другими. Вообще, сама идеология ООП, по сути, для этого и нужна. Это -- идеология "чёрных ящиков", которые производить может один, а использовать другой.

Посему если в условии задачи запрещено обрщаться именно к этой мощи, то тогда джава однозначно проиграет. И вообще, язык проигрывать будет тем больше, чем болеее он объектный.

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

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

Ну ведь согласитесь, это ненормально, когда всегда и везде прогроммисты используют одни и те же алгоритмы поиска, замены, связанных списков и так далее, но каждый раз кодят эти алгоритмы заново! Поэтому, когда появилась библиотека stdlib в Си++ и набор коллекция в Джава, полностью удовлетворительных, произошёл прорыв. Теперь это нелепо, если вы будете кодить свой собственный вектор или собственную карту соответствий. Просто, легко и удовлетворительно использовать готовые! Не всякий язык сопособен предоставить такое решение. И Джава -- способна.

Date: 2007-12-08 07:42 pm (UTC)
From: [identity profile] http://users.livejournal.com/d_m_/
+1
Насколько я помню, встроенный в String матчер, имелся ещё в Java 1.0.
Java API - это часть языка. Запрет использовать стандартные библиотеки нелеп, к тому же кое-что придётся разрешить, ибо иначе не написать ни строчки (например, уже main() требует класс String, который уже содержит матчер).

Это уже не говоря о том, что избранные критерии "сравнения языков" никуда не годятся и ни на что не похожи.

Говорю всё это как человек, около 10 лет писавший (в т.ч.) на различых Паскалях, но последнее время - в основном только на Java (этим я хочу сказать не то, что Java лучше или хуже, а то, что имею представление об обоих предметах).

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2007-12-10 11:02 am (UTC) - Expand

Date: 2007-12-08 07:31 pm (UTC)
From: [identity profile] http://users.livejournal.com/d_m_/
>>> К Java есть множество обоснованных нареканий, в частности, низкая скорость работы

Дальше можно было и не читать...

Date: 2007-12-08 08:01 pm (UTC)
From: [identity profile] krlz.livejournal.com
+1
Автор знаком с Java только поверхностно. Это видно, впрочем, и по коду.

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

(no subject)

From: [identity profile] http://users.livejournal.com/d_m_/ - Date: 2007-12-08 08:11 pm (UTC) - Expand

(no subject)

From: [identity profile] http://users.livejournal.com/d_m_/ - Date: 2007-12-08 08:26 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2007-12-10 09:33 am (UTC) - Expand

Date: 2007-12-08 08:01 pm (UTC)
From: [identity profile] denspb.livejournal.com
Ну, если брать инструмент за самую тяжёлую часть, то, пожалуй, микроскопом гвоздь будет забить проще, чем молотком.
http://denspb.spb.ru/Sample.java
30 строк, поддержка многих тестов во входном файле.
1160 байт.
8 минут + 2 минуты на отладку.
А идеологически правильно решение с Pattern/Mathcer Вам уже привели.

Date: 2007-12-08 08:14 pm (UTC)
From: [identity profile] denspb.livejournal.com
На всякий случай : это решение базируется на динамическом программировании.
Истинность a[i][j] — подходят ли первые i символов первой строки к первым j символам второй строки.
Решение товарища [livejournal.com profile] diam_2003 выше аналогично по идее, но вместо прямоугольной таблицы использует очередь, так что при большом количестве "звёздочек" у него будет потребляться слишком много памяти (правда это лечится ещё хранением множества посещённых "точек").

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2007-12-10 11:25 am (UTC) - Expand

(no subject)

From: [identity profile] denspb.livejournal.com - Date: 2007-12-10 11:56 am (UTC) - Expand

(no subject)

From: [identity profile] antilamer.livejournal.com - Date: 2007-12-08 08:37 pm (UTC) - Expand

(no subject)

From: [identity profile] denspb.livejournal.com - Date: 2007-12-08 08:56 pm (UTC) - Expand

(no subject)

From: [identity profile] http://users.livejournal.com/d_m_/ - Date: 2007-12-08 09:34 pm (UTC) - Expand

(no subject)

From: [identity profile] denspb.livejournal.com - Date: 2007-12-09 07:17 am (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2007-12-10 11:08 am (UTC) - Expand
(deleted comment)

Date: 2007-12-08 10:39 pm (UTC)
From: [identity profile] http://users.livejournal.com/d_m_/
Религия, преподносимая тут, запрещает регэкспы (см. исходный пост)
(deleted comment)

(no subject)

From: [identity profile] http://users.livejournal.com/d_m_/ - Date: 2007-12-09 12:15 am (UTC) - Expand
(deleted comment)

(no subject)

From: [identity profile] http://users.livejournal.com/d_m_/ - Date: 2007-12-09 12:20 am (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2007-12-10 11:14 am (UTC) - Expand

Date: 2007-12-09 05:36 am (UTC)
From: [identity profile] mr-aleph.livejournal.com
Вы сначала программировать научитесь, а потом уже начинайте попу с пальцем сравнивать и делать выводы о диаметре луны...

Date: 2007-12-10 11:45 am (UTC)
From: [identity profile] nuclight.livejournal.com
Во-первых, ознакомьтесь с http://nuclight.livejournal.com/111696.html?thread=462416#t462416

Во-вторых, не будьте голословными, ткните этим самым пальцем, где тут кто не умеет программировать.

(no subject)

From: [identity profile] mr-aleph.livejournal.com - Date: 2007-12-10 01:21 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2007-12-10 05:01 pm (UTC) - Expand

(no subject)

From: [identity profile] mr-aleph.livejournal.com - Date: 2007-12-10 06:07 pm (UTC) - Expand

(no subject)

From: [identity profile] nuclight.livejournal.com - Date: 2007-12-11 09:48 am (UTC) - Expand
Page 1 of 2 << [1] [2] >>

February 2017

S M T W T F S
   1 234
567891011
12131415161718
19202122232425
262728    

Style Credit

Expand Cut Tags

No cut tags
Page generated Aug. 18th, 2025 05:30 pm
Powered by Dreamwidth Studios