Оптимизировать функцию

[Utkin]

Для своих целей пишу интерпретатор с собственного языка программирования (некоторая смесь Лиспа и Паскаля). Пишу давно и с паузами (своеобразное хобби). Поэтому программа подвержена эффекту Windows (большой объем и низкая эффективность). Нужно оптимизировать одну из наиболее часто встречающихся функций, код которой приводится ниже:

Фрагмент кода:

// Получение элемента массива по индексу
// Располагайте элементы к началу массива, от этого зависит скорость получения элемента
function GetItemMas(Stroka1, razdelitel, Index: String): String;
var
        a, b, c, d, e: String;
        index1, posit: Integer;
begin
        a:=Stroka1;
        b:=GetCeloe(Index);
        d:=razdelitel;
        c:=Sravnenie(b, '0'); // Предварительная проверка

        // Решение при выходе за нижнюю границу массива некорректного индекса
        if (c='равно') or (c='меньше') then
        begin
                // Выход за границу не является ошибкой!!!!
                // ТАМ просто ничего НЕТ!!!!
                result:='';
                Exit;
        end;
        // Если разделитель не указан, значит разделителем является пробел
        if d='' then d:=' ';
        // Берем от разделителя только 1-ый символ
        if length(d)>1 then d:=d[1];
        // Определяем число элементов в массиве
        c:=GetIndexMas(a, d);
        // Проверяем выход индекса за верхнюю границу массива
        e:=Sravnenie(b, c);
        if e='больше' then
        begin
                // Возвращаем то, что находится за границей массива ;-)
                result:='';
                Exit; 
        end;
        // Смотрим число элементов, нужное для прочтения массива
        index1:=StrToInt(b);
        // В цикле отбрасываем элементы
        posit:=pos(d, a);
        // Сначала проверим, положение первого разделителя
        if posit=0 then
        begin
                // Разделителей нет
                If index1=1 then
                begin

                        // если указывает на первый индекс массива
                        result:=a;
                        Exit;
                end;
        end;
        // Дополнительная проверка первого разделителя
        if index1=1 then
        begin
                result:=Before(d, a);
                Exit;
        end;
        // Теперь непосредственно цикл поиска элемента в массиве
        while (posit>0) and (index1>1) do
        begin
                // Откидываем из массива левую часть
                a:=After(a, d);
                // Смещаем индекс
                Dec(index1);
                // Ищем дальше
                posit:=pos(d, a);
        end;
        // Берем элемент до первого разделителя
        a:=Before(d, a);
        // Вовзращаем результат
        result:=a;
end;

Назначение функции – работа со строковыми массивами.
Строковой массив – это строка, значение которой представляет массив элементов, выраженных последовательностью символов и ограниченных специальным разделительным символом. Разделительный символ не может являться элементом массива, аналогично являться частью элемента строкового массива. Число элементов и сами элементы зависят от значения разделительного символа. Индексация производится числами, начинается от '1'. Массив всегда содержит хотя бы один элемент, даже если является пустой строкой (в таком случае элементом массива будет являться пустая строка). Массив имеет бесконечное число элементов.
Если в массиве отсутствует разделительный символ, то считается, что массив состоит из одного элемента.
Пример:
'Уткин Птица Животные'
Примем за разделительный символ пробел, в таком случае элементом с индексом '1' будет являться элемент 'Уткин', элементом с индексом '2', будет являться элемент 'Птица', элемент с индексом '100' будет являться пустой строкой.
Примем за разделительный элемент символ '+', тогда элементом с индексом '1' будет являться ‘Уткин Птица Животные’, элементом с индексом '2' будет являться элемент '' – пустая строка.
Примем за разделительный элемент символ 'е', тогда элементом с индексом '1' будет элемент 'Уткин Птица Животны', элементом с индексом '2' будет являться элемент '' – пустая строка.
Функция основополагающая, поскольку она используется, как для поддержки концепций интерпретатора, так работы самого интерпретатора.
Хочу сразу пресечь бесполезные посты – функция работает со строками, это медленно, но предложения по переходу на другие структуры данных не принимаются (все базовые структуры данных языка – это строки и массивы строк). Тому есть ряд обоснований, в частности, в языке предпологается использование длинной арифметики – разрядность числа не зависит от математического сопроцессора, максимальная абстракция от аппаратных особенностей и пр. Описание иных функций (типа GetCeloe и Sravnenie) должны быть понятны из данного кода и названий самих функций.

[Kotofff]

Раз работа со строками, попробуй модуль QStrings. Вот тут я его предлагал http://programmersforum.ru/showpost....42&postcount=4
Просто там функции реально работают быстрее "обычных". Может выиграешь в скорости.

[Utkin]

Благодарю, но это не совсем то, что нужно. Я имел виду сам алгоритм функции. Возможно есть вариант более быстрого способа выполнить, то что должна делать данная функция? Учтите, на входе (параметр Index) может быть огромное число, число разрядов которого в Cardinal может и не уместится.

[alexBlack]

Насколько я понял, у Вас в цикле и декремент index и отбрасывание части строки и поиск разделителя. Лучше сначала найти оба разделителя, затем выделить часть строки между ними. Грубо, без проверок:

  p1 = scan_from_pos(a, 1, index, d); // разделитель index
  p2 = scan_from_pos(a, p1+1, 1, d);  // следующий разделитель
  a = sub_string(a, p1+1, p2-p1-1)

здесь scan_from_pos - найти в строке a начиная с позиции 1 символ d
с номером index

sub_string - выделение подстроки. Эта часть по времени выполнения не критична. А вот со scan_from_pos при index > max_cardinal придется повозиться. Если просто делать сравнение с d и декремент строкового значения index будет слишком долго. Можно сделать так:

 var c:cardinal;
 while index > 0 do begin
    c = max(max_cardinal, index);

    // поиск в строке символа с номером c
    // с последней найденной позиции

    dec(index, c);
 end;

[Utkin]

Спасибо за помощь. Без проверок не получится. Дело в том, что пользователь может указать в качестве параметра очень длинное число (формально это не является ошибкой), функция должна воспринимать любое число (которое может уместиться в строку).

[Stilet]

Предлагаю такую идею:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    ListBox1: TListBox;
    procedure FormCreate(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;
 rr=array of string;
var
  Form1: TForm1;

implementation

{$R *.dfm}
    procedure parse(s,delim:string;var result:rr);
  var i:integer;
  begin
    setlength(result,length(result)+1);
    i:=1; while i<(length(s)-length(delim)+2) do begin
     result[High(result)]:=result[High(result)]+copy(s,i,length(delim));
     if copy(s,i,length(delim))=delim then     setlength(result,length(result)+1);
     inc(i,length(delim));
    end;
  end;

procedure TForm1.FormCreate(Sender: TObject);
var v:rr;  i:integer;
begin
 parse('Уткин Птица Животные','т',v);
 for i:=low(v) to high(v) do begin
  ListBox1.Items.Add(v[i]);
 end;
end;

end.

Думаю она достаточно быстра и коротка.

[Utkin]

Эта функция работает не совсем так как нужно. Она оставляет разделитель в конце слова, тогда как разделитель там не нужен, он не учитывается ни в одном из элементов массива.
Вот то, что я получил из вашего кода:

// Получение элемента массива по индексу
function GetItemMas(s, delim, Count: string): String;
var

    i, m, d: integer;
    z: Cardinal;                        // счетчик совпадений
    b, a, c, f: String;
begin

    // Инициализация
    result:='';
    b:='';
    m:=0;
    i:=1;


    // Получение входящего параметра
    c:=Trim(Count);

    // Выделение числа из строкового параметра
    // В Cardinal не более 10 разрядов
    If Length(Count)>10 then Exit;

    // Предварительная проверка
    f:=Sravnenie(c, '0');

    // Решение при выходе за нижнюю границу массива некорректного индекса
    if (f='равно') or (f='меньше') then
    begin

       // Выход за границу не является ошибкой!!!!
       // ТАМ просто ничего НЕТ!!!!
       result:='';
       Exit;
    end;

    f:=delim;
    
    // Если разделитель не указан, значит разделителм является пробел
    if f='' then f:=' ';

    // Берем от разделителя только 1-ый символ
    if length(f)>1 then f:=f[1];

    // Получим число
    Val(c, z, i);

    if z=0 then Exit;

    // Посимвольное сканирование
    i:=1;
    while i<(length(s)-1) do
    begin

        // Получаем символ
        a:=copy(s, i, 1);

        // Символ совпадает с разделителем?
        if a=f then
        begin

            // Уменьшаем число совпадений
            Dec(z);

            // Хватит?
            if z=0 then
            begin

              result:=b;
              Exit;
            end;
            b:='';
        end
        ELSE
        begin
            b:=b+a;
     end;

     inc(i);
    end;
  end;

По крайней мере это работает быстрее первоначального варианта . Единственное, что настораживает, это процесс извлечения числа из строки - Val(c, z, i); В тоже время z может быть достигать значений, умещающихся только в Cardinal (теоретически). В хелпе Val работает с Integer и преобразует правильно, но до каких пор правильно?

[mutabor]

Учтите, на входе (параметр Index) может быть огромное число, число разрядов которого в Cardinal может и не уместится.

То что не помещается в Cardinal помещается в Int64.

Val без проблем преобразует числа в диапазоне Int64. В принципе в Дельфи только эта функция и работает с такими числами.

[Utkin]

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

[psycho-coder]

А почему нельзя использовать передачу не всей строки в функцию, а ее адреса?