![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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 тестах.
| Номер теста | Правильный ответ | Входной файл |
| 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 как явления)
