![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
Если переписать обычную программу с использованием ООП, она станет занимать в 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 тестах.
Номер теста | Правильный ответ | Входной файл |
1 | YES | ASDFAASDASDAAASDASDASD ASDFAASDASDAAASDASDASD |
2 | YES | * ASDFAASDASDAAASDASDASD |
3 | YES | ASDFAASDASDAAASDASDASD A?DF?A*ASD*ASDA?DASD |
4 | NO | ASDFAASASDAAASDASDASD ASDFAASDADAAASDASDASD |
5 | YES | *************************************************************************************** EKRUGHXCMJGHDFKJGHDFKJGHDFKGHWIERYCNKVBRKDFHGHJOOSJDFGHTASERFHASDGVFJSDGFJSDFG |
6 | YES | 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 |
7 | YES | 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? |
8 | YES | GBBPLHFMQKBOLBGVLENLOLWQWLOJFKVYPWPTSAFYIPOYVCPJKQBVYRPNKGYDNHVSTJLSMBUQPESMVKVMNHLLGEGYLDIVSRHCPNNGEKLULTWDKWQGTWBQWYNFWFXUMDTYSJAUSRNGBOTYPLBUXCHOTRABWATMQLGDNREQQBIEAAXHLDMELHTALOERTJIOYKCIEBKSVHYHBTMSYYTIRUEMVJJSGMVXGVCHNWGQVSOSFYGXGECEQSKHMOVJFUFQHTK *B*C*D*E*F*G*H*I*J*K |
9 | NO | FTWLREGFKOXPTCXIKXKUDGLXYPLPNWEFHFAYVCILXXUTAMSTFIEUBWRGKRBDANAHYOWMDOEJXMWEXSDELIYMOOWSDTEVVQGJTYPYWLQIUUFTHIALEGRWPSPIVFILDACRWJHEDHNGESIOSUOLGGGWQKJGOUTWTLGIIOHLFDOIULPVCWIDGFTXOFNJLRJIUYRJUEAADPGKWLWCDFJFPYPHWIKVCFOAHMXVWPBOJXCQTPUAPPAMLCCVNMDKFEMNGER *S*T*E*E*R*V*X*L*S*E |
10 | NO | 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?? |
Приложение 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, а на таком низком количестве строк разница в их числе уже не играет статистически значимой роли.
Ссылки по теме:
- DNS Message Decoding: A Case Study Comparing Java and Common Lisp
- Peter Norvig: Lisp as an Alternative to Java
- Erann Gat: Lisp vs Java
- Lutz Prechelt. An empirical comparison of C, C++, Java, Perl, Python, Rexx, and Tcl for a search/string-processing program.
- Африканец. Заметки про Жабу. Часть 1. (критика языка Java)
- Африканец. Заметки про Жабу. Часть 2. (критика Java как явления)
no subject
Date: 2006-05-07 08:18 pm (UTC)no subject
Date: 2006-05-07 11:13 pm (UTC)no subject
Date: 2006-05-08 05:00 am (UTC)Более того, совершенно забыта кроссплатформенность результрующего кода JAVA.
Сравнение по определению некорректно.
no subject
Date: 2006-05-08 09:13 am (UTC)Что-нибудь на порядок более сложное на паскале заняло бы два дня, а на яве все те же три часа.
(no subject)
From:Не катит
From:Re: Не катит
From:Re: Не катит
From:Re: Не катит
From:Re: Не катит
From:Re: Не катит
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:Спорить тут не стоит)
From:Re: Спорить тут не стоит)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:Как у тебя все сложно!
Date: 2006-05-08 07:54 am (UTC)Так это ж функциональщина :)
Date: 2006-05-08 09:19 am (UTC)>Как у тебя все сложно!
Я правильно понял, что у тебя половина проги разбирает, какая из строк - шаблон? (у меня на паскале это 6 строк)
> Можешь добавить еще вариант на Objective Caml:
Сколько времени заняло?
Re: Так это ж функциональщина :)
From:Re: Так это ж функциональщина :)
From:Re: Так это ж функциональщина :)
From:Re: Так это ж функциональщина :)
From:А если отбросить все лишнее...
Date: 2006-05-08 09:08 am (UTC)Re: А если отбросить все лишнее...
Date: 2006-05-08 11:25 am (UTC)Re: А если отбросить все лишнее...
From:Re: А если отбросить все лишнее...
From:Re: А если отбросить все лишнее...
From:Re: А если отбросить все лишнее...
From:Re: А если отбросить все лишнее...
From:Re: А если отбросить все лишнее...
From:Re: А если отбросить все лишнее...
From:Re: А если отбросить все лишнее...
From:Re: А если отбросить все лишнее...
From:Re: А если отбросить все лишнее...
From:Re: А если отбросить все лишнее...
From:no subject
Date: 2006-05-08 09:23 am (UTC)<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>
no subject
Date: 2006-05-08 09:26 am (UTC)Да, для полноты - 1057 байт.
(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2006-05-08 09:38 am (UTC)no subject
Date: 2006-05-08 03:48 pm (UTC)Зачем я должен отказываться от фичи? Посмотри на решения на других языках в соседних комментах, с их фичами - еще гораздо меньше получилось.
(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2006-05-08 11:33 am (UTC)no subject
Date: 2006-05-08 12:26 pm (UTC)(no subject)
From:(no subject)
From:no subject
Date: 2006-05-08 05:03 pm (UTC)файл 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 минут.
Язык - С/С++
no subject
Date: 2006-05-08 05:19 pm (UTC)gcc version 3.4.2 [FreeBSD] 20040728
И совать всё в один файл - плохая идея, у меня уже под кучу отдельных заточено.
(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:p.s.
From:Re: p.s.
From:Re: p.s.
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:А у Вас указатель убежал !
From:no subject
Date: 2006-05-08 05:12 pm (UTC)Язык - 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");
}
}
}
Где ж я вам компилер C# возьму...
Date: 2006-05-08 05:22 pm (UTC)> Но думаю ошибки есть, так как в процессе написания встречал ситуации, когда у меня была явная ошибка, а тесты этого не выявляли.
Например?
Re: Где ж я вам компилер C# возьму...
From:Re: Где ж я вам компилер C# возьму...
From:Re: Где ж я вам компилер C# возьму...
From:no subject
Date: 2006-05-08 06:46 pm (UTC)no subject
Date: 2006-05-08 07:00 pm (UTC)Там кстатии в урле имя файла убери, в листинге каталога еще несколько увидишь. Там есть обсуждение этих статей. Плюс надо учитывать, что написано оно лет эдак 6 назад, если не раньше.
(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:Да
From:Re: Да
From:Re: Да
From:Re: Да
From:no subject
Date: 2006-05-08 07:13 pm (UTC)Кстати, помимо скорости написания кода очень важно еще:
а) повторная используемость кода (например, написанное выше на Паскале будет работать только с однобайтными символами, а решение на C++ наверняка представляло бы шаблон, который можно в том числе для wide chars использовать - хоть UCS-2, хоть UCS-4)
б) читабельность написанного кода. проще читать - проще (дешевле) поддерживать
no subject
Date: 2006-05-08 07:53 pm (UTC)б) приведенное решение на жабе как раз-таки отличается меньшей читабельностью от варианта на паскале
(no subject)
From:Scheme
Date: 2006-05-08 07:22 pm (UTC)Re: Scheme
Date: 2006-05-08 07:24 pm (UTC)Re: Scheme
From:Re: Scheme
From:Re: Scheme
From:Re: Scheme
From:Решение на InteLib Lisp'е
Date: 2006-05-08 08:09 pm (UTC)40 строк, 950 символов, с нуля чуть меньше 40 минут, включая исправление баги в InteLib'е и пересборку InteLib'а, соответственно :) (оказалось, lfgets я ни разу еще не использовал, и в ней-то как раз бага и притаилась). Пойду теперь делать исправленный релиз InteLib'а (за номером 0.5.78).
P.S. Тесты все проходят, естественно. Заработало со второй попытки (при первой попытке была забыта проверка на одновременную пустоту образца и слова).
А если скобочки на отдельных строках убрать, будет 28
Date: 2006-05-09 08:22 am (UTC)Re: А если скобочки на отдельных строках убрать, будет 28
From:no subject
Date: 2006-05-09 12:36 pm (UTC)разрешено, то проще сделать так:
26 строк, 782 байта :)
no subject
Date: 2006-05-09 12:38 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2006-05-10 07:01 am (UTC)Программу на Java можно переписать в том же стиле, что и программу на C - то есть, как маленькое решение маленькой задачи. То же самое справедливо относительно программы на Pascal-е.
no subject
Date: 2006-05-10 09:33 am (UTC)(no subject)
From:no subject
Date: 2006-05-12 07:22 am (UTC)Программа решает немного более общую задачу (определяет, "пересекаются" ли два регулярных выражения). Меня немного смутил тезис Строки могут иметь длину от 1 до 255 символов, быть в файле в произвольном порядке (но их всего две, формат входных данных корректен). Впрочем, как я заметил, большинство приведенных решений этот момент вообще игнорируют, а среди тестов нет примера, когда обе строки являются шаблонами - например, "a*" и "*b". Модифицировать ее понятно как (добавить к "состояниям парсера" флажок: какую из строк мы взялись интерпретировать как шаблон).
no subject
Date: 2006-05-13 11:18 am (UTC)По приведенному решению - это что вообще и как работает?! На решение оригинальной задачи - не похоже. У меня, вообще говоря, возникают сомнения насчет допустимости использования готовых объектов для связных списков, но и без этого, оно даже не компилируется:
(no subject)
From:(no subject)
From:о-ооо
From:Re: о-ооо
From:(no subject)
From:no subject
Date: 2006-05-14 09:38 pm (UTC)no subject
Date: 2006-05-16 07:57 am (UTC)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";
no subject
Date: 2006-05-18 12:19 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:некорректный пример
Date: 2006-05-17 11:15 am (UTC)P. S. /me поклонник Явы, но из за отсутствия нормальных ява машин под BSD приходится пока использовать другие языки.
Re: некорректный пример
Date: 2006-05-20 12:01 pm (UTC)Это, вообще говоря, очень странно, когда преимущества языка проявляются только в очень больших задачах. Особенно если учесть, что чем больше проект, тем меньше непосредственная роль языка. Так что эти преимущества, если они есть, обеспечены совсем не языком.
>/me поклонник Явы
Очень зря.
>но из за отсутствия нормальных ява машин под BSD
diablo-jdk ж недавно вышел, официально сертифицированный.
Re: некорректный пример
From:Re: некорректный пример
From:Re: некорректный пример
From:no subject
Date: 2006-07-07 07:12 pm (UTC)Посему если в условии задачи запрещено обрщаться именно к этой мощи, то тогда джава однозначно проиграет. И вообще, язык проигрывать будет тем больше, чем болеее он объектный.
Вот Вы сказали, что на всех языках есть готовые библиотеки для поиска подпадания строки под шаблон, а также разные библиотеки для других задач. Да, это так. Можно ещё добавить, что на многих языках таких библиотек по нескольку, ни одна из них не может удовлетворить полностью и их трудно изучить и запомнить, что они делают и так далее.
Но в джаве ситуация иная. Если есть какая-то библиотека, если она построена грамотно, то вероятность того, что она не подойдёт или что её нельзя будет масштабировать, меньше, чем в других языках.
Ну ведь согласитесь, это ненормально, когда всегда и везде прогроммисты используют одни и те же алгоритмы поиска, замены, связанных списков и так далее, но каждый раз кодят эти алгоритмы заново! Поэтому, когда появилась библиотека stdlib в Си++ и набор коллекция в Джава, полностью удовлетворительных, произошёл прорыв. Теперь это нелепо, если вы будете кодить свой собственный вектор или собственную карту соответствий. Просто, легко и удовлетворительно использовать готовые! Не всякий язык сопособен предоставить такое решение. И Джава -- способна.
no subject
Date: 2007-12-08 07:42 pm (UTC)Насколько я помню, встроенный в String матчер, имелся ещё в Java 1.0.
Java API - это часть языка. Запрет использовать стандартные библиотеки нелеп, к тому же кое-что придётся разрешить, ибо иначе не написать ни строчки (например, уже main() требует класс String, который уже содержит матчер).
Это уже не говоря о том, что избранные критерии "сравнения языков" никуда не годятся и ни на что не похожи.
Говорю всё это как человек, около 10 лет писавший (в т.ч.) на различых Паскалях, но последнее время - в основном только на Java (этим я хочу сказать не то, что Java лучше или хуже, а то, что имею представление об обоих предметах).
(no subject)
From:no subject
Date: 2007-12-08 07:31 pm (UTC)Дальше можно было и не читать...
no subject
Date: 2007-12-08 08:01 pm (UTC)Автор знаком с Java только поверхностно. Это видно, впрочем, и по коду.
Странно, что не было никем замечено, что программу на паскале можно перевести в аналогичную программу с меньшим количеством строк просто заменой синтаксиса паскаля на синтаксис Java (они практически изоморфны).
(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2007-12-08 08:01 pm (UTC)http://denspb.spb.ru/Sample.java
30 строк, поддержка многих тестов во входном файле.
1160 байт.
8 минут + 2 минуты на отладку.
А идеологически правильно решение с Pattern/Mathcer Вам уже привели.
no subject
Date: 2007-12-08 08:14 pm (UTC)Истинность a[i][j] — подходят ли первые i символов первой строки к первым j символам второй строки.
Решение товарища
(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2007-12-08 10:39 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2007-12-09 05:36 am (UTC)no subject
Date: 2007-12-10 11:45 am (UTC)Во-вторых, не будьте голословными, ткните этим самым пальцем, где тут кто не умеет программировать.
(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From: