оптимизация работы алгоритма по времени Ansistring

Jude
Дата: 12.05.2011 12:31:14
Здравствуйте, уважаемые знатоки!
Ansistring - тут лежит строчка, которую надо обработать. (думаю
, что точно не widestring )
есть простой алгоритм обработки, который за определенное кол-во операций из 1 Ansichar делает что-то типа числа (byte?)
которые потом нужно для всей строки просуммировать.
стоит задача оптимизации по времени.

ну вот побежал я задачу решать.

сходу как-то получилось 2 направления:
1) сделать поинтер и гнать его до конца строки:
var p,Pmax: PansiChar; 
  sum:integer;
begin
  p := MyAnsistring[1];
  Pmax := p+sizeof(MyAnsistring);
  sum:=0;
  while integer(p)<integer(Pmax) do
  begin
    inc(sum,AlgoritmForAnsiChar(p^));
    inc(p)
  end; 
2) сделать массив mass[0..255]of byte и заполнить его готовыми решениями для AlgoritmForAnsiChar и потом
inc(sum,mass[byte(p^)]);
3) ну и чуть позже подумал сделать комбинированно 1 и 2 исходя из оценки что дольше: найти и заполнить массив из п.2 + расчитать стринг длинной Н или считать все байты стринга Н по п.1

И вот тут застрял малость. дебагер говорит, что во что компилится в режиме трассировки если CPU включить. вроде можно посчитать количество команд, который он трассировкой бежит...
есть конечно вариант ставить getticcount - но он тут не спасет - объемы малые. разве что попытаться тестирования ради раздуть все байты на 32битные переменные (по 4 шт в каждую), тогда и словарик подтянется к 4 GB и его можно будет ощутимо по времени строить(дабы иметь возможность сравнить), только delphi7 на такое ругается - говорит 2 gb потолок.

уверен, что есть уже не раз опробованные решения как с таким бороться - но я их не знаю. Не посоветуете? книги/статьи?

пока нашел очень умное про О(N) но исходя из написанного там у меня все три варианта O(N)

Спасибо.

п.с. еще думал типа кусать стринг на куски по , скажем 2 MB и делать под каждый кусок поток-нить(thread) и по окончании плевать message в главное окно, которое и суммировать все эти циферки. Если я правильно понял, это вроде даст преимущество на многоядерном проце. - но пока не разобрался.

п.п.с. = понимаю, что просто посчитать точки по трассировке не верно, особенно когда есть call т.к. не известно, сколько там еще будет лопатить до ret

п.п.п.с = прошу простить за сумбурный пост - не выспался.
defecator
Дата: 12.05.2011 12:41:50
На первый взгляд, из всех трех вариантов первый самый простой.
Если есть возможность, код из AlgoritmForAnsiChar перетащить в цикл - можно будет сэкономить на вызове функции.
defecator
Дата: 12.05.2011 12:43:08
Да, и первый алгоритм какой-то странный.
Мне так кажется, что там есть ошибка, и не одна
defecator
Дата: 12.05.2011 12:55:47
Ну вот, например, алгоритм тебе:

var
   Str : AnsiString ; { тут тестовая строка }

   Addr : DWORD ;
   Sel,Sum : LongInt ;
begin
     Str := 'The big string' ;

     Addr := DWORD(@Str[1]) ; Sum := 0 ;
     
     for Sel := 0 to Length(Str)-1 do
      Inc(Sum,AlgoritmForAnsiChar(AnsiChar(Pointer(Addr+Sel)^))) ;
end;
Jude
Дата: 12.05.2011 13:16:05
defecator
Ну вот, например, алгоритм тебе:

var
   Str : AnsiString ; { тут тестовая строка }

   Addr : DWORD ;
   Sel,Sum : LongInt ;
begin
     Str := 'The big string' ;

     Addr := DWORD(@Str[1]) ; Sum := 0 ;
     
     for Sel := 0 to Length(Str)-1 do
      Inc(Sum,AlgoritmForAnsiChar(AnsiChar(Pointer(Addr+Sel)^))) ;
end;


спасибо.
Ошибок в моем варианте много. Рабочий пример остался дома - то что было выше - что смог вспомнить для иллюстрации рисовал.

если не затруднит немного теории:

допустим есть 20-30 "шагов" в алгоритме AlgoritmForAnsiChar - и он вернет результат.
а стринг длинной, 2мегабайта.
т.е. вроде как должно быть 30 * 2*1024*1024 = много шагов до решения. и еще операция по сумме должна кушать
скажем 3 "шага" т.е. + 3*(2*1024*1024-1).
если я беру данные из заранее посчитанного массива:
допустим 5 операций *2*1024*1024, то тут я выигрываю время, даже если строю сам массив 30*256 шагов
т.е. 30*256+5*2*1024*1024 меньше чем 30 * 2*1024*1024 + 3*(2*1024*1024-1).
как бы тут я немного смогу выиграть, если для стрингра более 2МБ возьму вариант 2.

я верно понимаю?
Judo
Дата: 12.05.2011 13:27:20
Jude
если я беру данные из заранее посчитанного массива:


А время на подготовку этого самого массива считали?
Jude
Дата: 12.05.2011 13:42:32
Judo
Jude
если я беру данные из заранее посчитанного массива:


А время на подготовку этого самого массива считали?


Jude
даже если строю сам массив 30*256 шагов
Judo
Дата: 12.05.2011 13:46:12
тогда первый способ быстрее, чем тратить время на промежуточное копирование байтов в какие то свои массивы.
Буфер дает ускорение если к нему обращаются не один раз
Jude
Дата: 12.05.2011 13:48:45
Judo
тогда первый способ быстрее, чем тратить время на промежуточное копирование байтов в какие то свои массивы.
Буфер дает ускорение если к нему обращаются не один раз

а как это можно посчитать/замерить кроме gettickcount?
Judo
Дата: 12.05.2011 13:49:58
Jude
Judo
тогда первый способ быстрее, чем тратить время на промежуточное копирование байтов в какие то свои массивы.
Буфер дает ускорение если к нему обращаются не один раз

а как это можно посчитать/замерить кроме gettickcount?


зачем? если это в принципе быстрее....