Модераторы: Poseidon, Snowy, bems, MetalFan
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Оптимизация алгоритма. 
V
    Опции темы
Ak47black
  Дата 29.6.2007, 17:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2205
Регистрация: 2.12.2005

Репутация: 1
Всего: 0
Здравствуйте.  smile 
Пишу алгоритм и на первый взляд он кажется безобидным но жрет аш 30-40 % проца при таймере 50ms.
Может чтонибудь предложите.

Попробую пояснить точно что я делаю.
У меня есть общий файл которым пользуются приложение и драйвер.
В программе пользуюсь им при помощи мапинга, тоеть получаю указатель и пользуюсь им на протяжении всей работы программы.
В этом общем файле храниться маска изменений,  размер файла (высота экрана в пикселях)*(длина экрана в пикселях),  тоесть на каждый пиксель по одному байту.
Если пиксель был изменён то байт равняется 1 если нет то 0.
(Маска храниться не перевёрнутой)

Задача :
Из этого файла составить массив координат прямоугольников в которых произошли изменения, при этом нужно получить минимальное их количество.

Я пытаюсь решить эту задачу в два алгоритма.
  • Вначале составить массив изменений по y
  • Склеить из составленного массива итемсы с одинаковыми  left и right параметрами и получить те прямоугольники

Вот что я пытаюсь сделать на деле

Код

var
  i, e, u: Integer;
  found: Boolean;
begin
  for i:= 0 to ScreenWidth*ScreenHeight do // 1 алгоритм
  begin
    if ( ( ShortInt(Pointer(Integer(PosP)+i)^) = 1 ) and (not found) ) then
    begin
        PosArr[PosSize].Left:= i mod ScreenWidth;
        PosArr[PosSize].Top:= i div ScreenWidth;
        found:= True;
    end;

    if ( (( ShortInt(Pointer(Integer(PosP)+i+1)^) = 0 )and( found )) or
          (( i <> 0 )and( (i+1)mod ScreenWidth = 0 )and( found ))
         ) then
    begin
      PosArr[PosSize].Rigth:= i mod ScreenWidth;
      PosArr[PosSize].Bottom:= i div ScreenWidth;
      found:= False;
      Inc(PosSize);
    end;

  end;


  for i:= 0 to PosSize-1 do // 2 алгоритм
  begin
    e:= i+1;
    while (e <= PosSize-2) do
    begin
      if  ((PosArr[i].Left = PosArr[e].Left)and(PosArr[i].Rigth = PosArr[e].Rigth)) then
      begin
        PosArr[i].Bottom:= PosArr[e].Bottom;
        for u:= e to PosSize-2 do
        begin
          PosArr[u]:= PosArr[u+1];
        end;
        PosSize:= PosSize-1;
        e:= e-1;
      end;
      e:= e+1;
    end;
  end;


ScreenWidth, ScreenHeight -  высчитывается при старте программы.
PosSize - длина массива PosArr, так как массив PosArr создаться при старте максимальной длины.
PosP - указатель на память файла, (мапинг).
Код

  TRectEx = record
    Left: Integer;
    Top: Integer;
    Rigth: Integer;
    Bottom: Integer;
  end;

PosArr : array of TRectEx
Может кто сможет что сказать как тут оптимизировать?  smile 
Заранее спасиба.
PM MAIL   Вверх
ivan219
  Дата 29.6.2007, 19:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1121
Регистрация: 19.11.2005
Где: Планета земля

Репутация: 2
Всего: 12
Как вареант предлогаю not found, found поставить первым в проверке, выделить его в отдельный if, Integer(PosP) в отдельную переменную.
Код

if not found then
 if .....
if found then
 if ... or ...

Или даже так:
Код

 if fond then
  begin
    if  ShortInt(Pointer(Integer(PosP)+i)^) = 1  then
     begin
     if ( ShortInt(Pointer(Integer(PosP)+i+1)^) = 0 ) or 
        (( i <> 0 )and( (i+1) mod ScreenWidth = 0 )) then
      begin
       PosArr[PosSize].Rigth:= i mod ScreenWidth;
       PosArr[PosSize].Bottom:= i div ScreenWidth;
       Inc(PosSize);
       found:= False;
      end;
     end;
  end
  else
   begin
       PosArr[PosSize].Left:= i mod ScreenWidth;
       PosArr[PosSize].Top:= i div ScreenWidth;
       found:= True;
   end;

Также:
Код

       i mod ScreenWidth;
       i div ScreenWidth;

выдели в отдельные переменные зачем их 2 раза вычислять.
И помойму вот так будет правильнее:
Код

 for i:= 0 to ScreenWidth*ScreenHeight-1 do

Код

PosSize:= PosSize-1; -> Dec(PosSize);
 e:= e+1; -> Inc(e);


Это сообщение отредактировал(а) ivan219 - 29.6.2007, 19:26


--------------------
Мой первый сайт и моя первая программа!!!!!
PM MAIL ICQ   Вверх
ivan219
  Дата 29.6.2007, 19:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1121
Регистрация: 19.11.2005
Где: Планета земля

Репутация: 2
Всего: 12
Вобщем что-то вроде этого:
Код

var
  i, e, u, I1, I2, I3: Integer;
  found: Boolean;
begin
 I3:=Integer(PosP);
 for i:= 0 to ScreenWidth*ScreenHeight-1 do // 1 алгоритм
  begin
   I1:=i mod ScreenWidth;
   I2:=i div ScreenWidth;

   if found then
    begin
     if (ShortInt(Pointer(I3+i+1)^)=0)or((i<>0)and((i+1) mod ScreenWidth=0) then
      begin
       PosArr[PosSize].Rigth:=I1
       PosArr[PosSize].Bottom:=I2
       Inc(PosSize);
       found:= False;
      end;
    end
   else
    begin
     if ShortInt(Pointer(I3+i)^) = 1 then
      begin
       PosArr[PosSize].Left:= I1
       PosArr[PosSize].Top:= I2
       found:= True;
      end;
    end;
  end;

  for i:= 0 to PosSize-1 do // 2 алгоритм
   begin
    e:= i+1;
    while (e <= PosSize-2) do
     begin
      if (PosArr[i].Left = PosArr[e].Left)and(PosArr[i].Rigth = PosArr[e].Rigth) then
       begin
        PosArr[i].Bottom:= PosArr[e].Bottom;
        for u:= e to PosSize-2 do
         PosArr[u]:= PosArr[u+1];
        Dec(PosSize);
        Dec(e);
       end;
      Inc(i);
     end;
   end;

По поводу этого:
Код

(i<>0)and

обойтись некак нельзя, вобще она нужна только один раз вовсех последующих циклах только тормазит.

Это сообщение отредактировал(а) ivan219 - 29.6.2007, 19:37


--------------------
Мой первый сайт и моя первая программа!!!!!
PM MAIL ICQ   Вверх
Ak47black
Дата 29.6.2007, 20:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2205
Регистрация: 2.12.2005

Репутация: 1
Всего: 0
ivan219, тут может есть какой другой подход есть, этот не особо быстрый чтото.
PM MAIL   Вверх
Ak47black
Дата 29.6.2007, 21:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2205
Регистрация: 2.12.2005

Репутация: 1
Всего: 0
Нашел узкое место
Код

(i+1)mod ScreenWidth = 0
PM MAIL   Вверх
aktuba
Дата 30.6.2007, 03:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Смышленный
***


Профиль
Группа: Завсегдатай
Сообщений: 1915
Регистрация: 24.4.2006
Где: Планета Земля

Репутация: 16
Всего: 38
Цитата

50ms


Жэсть... Это получается, проверка идет 20 раз в секунду???? Для чего??? Думаешь за это время многое может поменяться???

Цитата

(i+1)mod ScreenWidth = 0


А как нашел? Надеюсь не в ручную?  smile Проверь через профайлер - иначе не верь глазам своим...


--------------------
user posted image
PM MAIL WWW Skype   Вверх
Ak47black
Дата 30.6.2007, 11:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2205
Регистрация: 2.12.2005

Репутация: 1
Всего: 0
Код

(i+1)mod ScreenWidth = 0

 smile да это и оказалась единственной грубой ошибкой, теперь всё  smile 



Это сообщение отредактировал(а) Ak47black - 30.6.2007, 11:37
PM MAIL   Вверх
ivan219
  Дата 30.6.2007, 11:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1121
Регистрация: 19.11.2005
Где: Планета земля

Репутация: 2
Всего: 12
Ну а как вышел из этой ситуации???


--------------------
Мой первый сайт и моя первая программа!!!!!
PM MAIL ICQ   Вверх
Ak47black
Дата 30.6.2007, 12:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2205
Регистрация: 2.12.2005

Репутация: 1
Всего: 0
ivan219, еще один написал алгоритм который работает с 
Код

(i+1)mod ScreenWidth = 0

после отбора.
И тем самым сокращает количество использования этого кода.

Это сообщение отредактировал(а) Ak47black - 30.6.2007, 12:11
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Delphi: Общие вопросы"
SnowyMetalFan
bemsPoseidon
Rrader

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Литературу по Дельфи обсуждаем здесь
  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь
  • 90% ответов на свои вопросы можно найти в DRKB (Delphi Russian Knowledge Base) - крупнейшем в рунете сборнике материалов по Дельфи

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Snowy, MetalFan, bems, Poseidon, Rrader.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Delphi: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0555 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.