Отправим Goto на пенсию!
Все кто учил язык BASIC, наверно помнят оператор безусловного перехода GOTO. Почему BASIC? Не только он, конечно, просто в ранних реализациях BASIC (например, Microsoft QuickBasic, входивший в свое время в поставку MS-DOS) он применялся действительно часто. Ведь там не было ни классов, ни операторов обрыва циклов и выполнения вроде Break, Exit, Continue, а также исключений. В современных же языках с полноценными средствами структурного программирования, использование Goto считается крайне дурным тоном, так как затрудняет чтение и делает код непредсказуемым. Доводы против оператора goto четко выписаны в одноименной статье Эдсгера Дейкстры. Но я решил идти не по тропе теоретических изысканий, а показать на практике, что код БЕЗ GOTO может быть не только красивее и логичнее, но и в разы быстрее.
Существовала когда-то библиотека компонентов для Delphi под названием RX Library. Для своего времени это была отличная библиотека, содержала множество полезных компонентов и функций. Со временем библиотека перестала разиваться, теперь она только адаптируется к новым версиям Delphi, для поддержания обратной совместимости (http://rx.delphiplus.org/, http://sourceforge.net/projects/rxlib/). Код этой библиотеки без существенных изменений (кроме названий компонентов) был перенесен в JEDI VCL.
Вместе с множеством полезных RTL-функций была унаследована и функция перевода чисел из десятичной системы счисления в римскую. История этой функции мне неизвестна, но её главной особенностью является наличие оператора безусловного перехода goto (модули rxStrUtils, JvJCLUtils):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | function IntToRoman(Value: Longint): string; Label A500, A400, A100, A90, A50, A40, A10, A9, A5, A4, A1; begin Result := ''; while Value >= 1000 do begin Dec(Value, 1000); Result := Result + 'M'; end; if Value < 900 then goto A500 else begin Dec(Value, 900); Result := Result + 'CM'; end; goto A90; A400: if Value < 400 then goto A100 else begin Dec(Value, 400); Result := Result + 'CD'; end; goto A90; A500: if Value < 500 then goto A400 else begin Dec(Value, 500); Result := Result + 'D'; end; A100: while Value >= 100 do begin Dec(Value, 100); Result := Result + 'C'; end; A90: if Value < 90 then goto A50 else begin Dec(Value, 90); Result := Result + 'XC'; end; goto A9; A40: if Value < 40 then goto A10 else begin Dec(Value, 40); Result := Result + 'XL'; end; goto A9; A50: if Value < 50 then goto A40 else begin Dec(Value, 50); Result := Result + 'L'; end; A10: while Value >= 10 do begin Dec(Value, 10); Result := Result + 'X'; end; A9: if Value < 9 then goto A5 else begin Result := Result + 'IX'; end; Exit; A4: if Value < 4 then goto A1 else begin Result := Result + 'IV'; end; Exit; A5: if Value < 5 then goto A4 else begin Dec(Value, 5); Result := Result + 'V'; end; goto A1; A1: while Value >= 1 do begin Dec(Value); Result := Result + 'I'; end; end; |
Была ли эта функция переведена дословно с языка BASIC или написана с нуля — теперь это не так уж важно. Главное, что в современном программировании GOTO нет места. И эта моя публикация нацелена на то, чтобы в очередной раз это подтвердить. Несмотря на отдельные доводы в пользу оператора GOTO: например, что он обеспечивают лучшую производительность по сравнению со стандартными методами структурного программирования.
Если не смотреть на вышеприведенный код (так как в нем с трудом можно что-то понять, только сбить себя с толку), а задаться целью написать функцию перевода в римскую систему счисления с нуля, то она будет выглядеть примерно так:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | function IntToRoman(Value: Longint): string; type TRomanRec = record Str: string; Amount: Integer end; const Roman: array [1..13] of TRomanRec = ( (Str: 'M'; Amount: 1000), (Str: 'CM'; Amount: 900), (Str: 'D'; Amount: 500), (Str: 'CD'; Amount: 400), (Str: 'C'; Amount: 100), (Str: 'XC'; Amount: 90), (Str: 'L'; Amount: 50), (Str: 'XL'; Amount: 40), (Str: 'X'; Amount: 10), (Str: 'IX'; Amount: 9), (Str: 'V'; Amount: 5), (Str: 'IV'; Amount: 4), (Str: 'I'; Amount: 1) ); var R: TRomanRec; begin Result := ''; for R in Roman do while Value >= R.Amount do begin Result := Result + R.Str; Dec(Value, R.Amount); end; end; |
Здесь реализован простейший алгоритм перевода. Последовательно вычитая из исходного числа значения римских чисел или их сочетаний, мы получаем строковое представление данного числа. Что касается производительности, то эта функция действительно несколько медленнее варианта с GOTO. От 8% до 30% в зависимости от диапазона чисел (чем больше — тем меньше разница, 8% на переводе чисел от единицы до миллиона). Сторонники GOTO радостно возликовали бы на этом месте и успокоились, продолжая использовать функцию с GOTO. Но я как сторонник структурного программирования решил на этом не останавливаться, а проанализировать внимательно алгоритм.
Первое узкое место, которое бросается в глаза — формирование строки в цикле. Мало того, что такая операция является ресурсоемкой, приводя к лишним операциям выделения памяти, она гораздо медленнее, чем простая функция div, которую было бы достаточно выполнить всего один раз для одной римской цифры. Она возвратила бы количество римских чисел, а сформировать строку можно было бы функцией StringOfChar (модуль SysUtils), которая написана на ассемблере и имеет отличную производительность.
Но здесь всплывает иная сложность: как формировать строку из нескольких символов (таких как промежуточные значения CM=900, CD=400 и т.д.). Здесь два варианта: либо писать универсальную функцию, которая будет формировать строку не из символов, а из одинаковых строковых фрагментов, либо отказаться от промежуточных значений. Первый вариант существенно снизит производительность, поэтому возьмемся за другой вариант. В нем не все так сложно, как могло бы показаться на первый взгляд. Если внимательно посмотреть на ряд римских чисел
I, V, X, L, C, D, M
то можно заметить, что отниматься от большего числа могут только числа через одно (на нечетных местах). Это правило не касается только тысячи (M), так как нету большего числа в римской системе счисления. Такой алгоритм несложно реализовать:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | function IntToRomanOptimized(Value: Longint): string; type TRomanRec = record Symbol: Char; Amount: Word; end; const // Отмеченные "+" элементы используются для уменьшения предыдущих значений, // все они на нечетных местах Roman: array [1..7] of TRomanRec = ( (Symbol: 'M'; Amount: 1000), // 1 (Symbol: 'D'; Amount: 500), // 2 (Symbol: 'C'; Amount: 100), // 3 + (Symbol: 'L'; Amount: 50), // 4 (Symbol: 'X'; Amount: 10), // 5 + (Symbol: 'V'; Amount: 5), // 6 (Symbol: 'I'; Amount: 1) // 7 + ); var I: Integer; R: TRomanRec; begin Result := ''; for I := Low(Roman) to High(Roman) do begin R := Roman[I]; if Value >= R.Amount then begin Result := Result + StringOfChar(R.Symbol, Value div R.Amount); Dec(Value, Value div R.Amount * R.Amount); end; if R.Amount > 1 then with Roman[I + Ord(Odd(I)) + 1] do if Value >= R.Amount - Amount then begin Result := Result + Symbol + R.Symbol; Dec(Value, R.Amount - Amount); end; end; end; |
Новый вариант функции готов, теперь перейдем к тестированию производительности. И она не может не радовать! На переводе чисел от 1 до 100 000 оптимизированный вариант работает в 2 раза быстрее, чем с GOTO. На 200 000 — в 3 раза быстрее, на 300 000 — в 4 раза, а на числах до миллиона — более чем в 13 (!) раз быстрее. И это еще раз подтверждает, что GOTO пора на пенсию, время грамотного программирования!
