Сообщения без ответов | Активные темы


Список форумов » Специализированные форумы » Программирование

Часовой пояс: UTC + 3 часа




Начать новую тему Новая тема / Ответить на тему Ответить  Сообщений: 50 • Страница 2 из 3 • <  1  2  3  >
  Пред. тема | След. тема 
В случае проблем с отображением форума, отключите блокировщик рекламы
Автор Сообщение
  Halfback

Member
Статус: Не в сети
Регистрация: 14.08.2003
Откуда: Питер
Ray Adams
Цитата:
Кстати может опишет, что же ты этим кодом добиваешся то? А то не понятно что ты хочеш добиться и как сортируеш. Может сперва надо создать массив и только после окончания его создания , сортирнуть , скажем бинарным способом?

Ок. Поясню по пунктам.
1. Вычисляется N! т.е. число возможных перестановок числа 1,2,...,N.
Цитата:
NN:=1;
for i:=1 to N do
begin
NN:= NN*i ;
end;

2. Начинается цикл записи комбинационных чисел в динамический массив a.
Цитата:
for j:=1 to NN do
begin

2.1 Из массива U[1..N]=1,2,..N формирую новый массив R[1..N]= случайной комбинации чисел от 1 до N (т.е. положим было чисо 12345 (N:=5) а стало 34521). Все это делается с помощью кода:
Цитата:
for m:=1 to N do
U[m]:=m;

for v:=N downto 1 do
begin
RR:=Random(v)+1;
R[N-v+1]:=U[RR];
for k:=RR to (v-1) do U[k]:=U[k+1];
end;

2.2 Набор чисел массива R[1..N] преобразую в десятичное число (Т.е. например был массив R[1..N]:=(3,4,5,2,1) а стало чисо S:=34521 или S:=3*10^5 + 4*10^4 + 5*10^3 + 2*10^2 + 1*10^1). Вот код делающий это:
Цитата:
S:=0;
for vv:=1 to N do
S:= S + R[vv]*Trunc(exp((N-vv)*ln(10)));
a[j]:=Trunc(S);

2.3 Теперь надо определить, появлялось ли это число раньше в динамичечком массиве a или нет. Если ДА тогда воззвращаемся к метке Unix2 и формируем численную последовательность РАЗНЫХ чисел заново.
Если же число а[j] не равно ни одному из a[1],a[2],......,a[j-1] то число оставляем в массиве а и пишем его в ListBox'е. Далее продолжаем цикл на этапе j+1. Вот код:
Цитата:
for m:=1 to j-1 do
begin
if a[j]= a[m] then GoTo Unix2 else
end;
ListBox1.Items.Strings[j-1] :=FloatToStr(a[j])+' ['+ FloatToStr(j)+']';

3. Всего циклов NN:=N! и в них заполняется дин. массив а.

_________________
Лучшая зашита - это нападение.

Последний раз редактировалось Halfback 31.08.2004 1:04, всего редактировалось 2 раз(а).

Реклама

Партнер
  Ray Adams

Advanced member
Статус: Не в сети
Регистрация: 09.06.2003
Откуда: USSR
МАМА! :) А можно спросить зачем? :)
P.S. Завтра на работе подумаю над этим делом, тут есть что оптимизировать :)
  Halfback

Member
Статус: Не в сети
Регистрация: 14.08.2003
Откуда: Питер
Ray Adams
Цитата:
МАМА! А можно спросить зачем?

Помнишь фильм "Джентельмены удачи"? Так вот, там есть один эпизод, когда у Василия Алибабаевича спросили "Зачем тебе керосинка?". Он ответил "НАДА"
Немного поправил исходник в предыдушем моем посте.

Avaddon
Цитата:
Все for меняй на while (т.к. у тебя одной из конечных границ есть 1, то все можно свести к банальной проверке на больше/меньше 0).


Может обьяснишь, почему в моем конкретном случае цикл while "лучше" цикла "for"? Ведь колличество циклов у меня строго предопределено....

Добавлено спустя 32 минуты, 35 секунд:
Правильно ли я понял строки?
Цитата:
p := @U;
т.е. р - это индекс массива U.
Цитата:
p^ := m;
равносильно U[m]:=m;
т.о. кусок кода
Цитата:
for m:=1 to N do
U[m]:=m;
преобразился в
Цитата:
p:=@U;
m:=1;
while (N-m)>=0 do
begin
p^:=m;
inc(p);
inc(m);
end;

Так где же тут оптимизации? Ведь мой код меньше твоего. Или я в чем то не прав?

Добавлено спустя 2 часа, 1 минуту, 42 секунды:
Заменил мою часть кода как ты советовал:
Цитата:
for m:=1 to j-1 do
begin
if a[j]= a[m] then GoTo Unix2 else
end;

на
Цитата:
var
p: PShortInt
................
p:=@a;
m:=0;
while (j-1-m)>=0 do
begin
if p^=S then GoTo Unix2;
inc(p);
inc(m);
end;
a[j]:=S;

При N<=7 заработало еще быстрее, но как ставлю N:=8 то вылетает ошибка с указанием на какой-то регистр памяти в моем экзешнике. Менял р на другие целые типы - еще хуже. При N:=7 даже считать не хочет. Вылетает все тажа ошибка. А дальше - еще хуже. Т.о. чем выше ставлю формат целого типа (8 бит, 16 бит и т.д.) тем при меньшем N я могу работать. Что за ерунда?

_________________
Лучшая зашита - это нападение.

  Ray Adams

Advanced member
Статус: Не в сети
Регистрация: 09.06.2003
Откуда: USSR
Потыкал я потыкал, особого прироста не получается. Чисто по приколу попытался вот это кусок кода перекинуть на асм
Код:
          for m:=1 to N do U[m]:=m;

, перекинул, смотрю никакого прироста. Гляну в ассмеблерный код, так Delphi этот кусок намного оптимизированней меня написал, так что лучше и не придумаеш :) (ну разве что совсем уж по извратному :) )

Добавлено спустя 2 минуты, 55 секунд:
Цитата:
var
p: PShortInt
................
p:=@a;
m:=0;
while (j-1-m)>=0 do
begin
if p^=S then GoTo Unix2;
inc(p);
inc(m);
end;
a[j]:=S;

Кстати вот этот код ускоряет работы в три раза! Со старым вариантом было 600-700 тиков при значении 7, с новым вариантом 200-300 :). Так что есть еще куда копать.

Добавлено спустя 2 минуты, 20 секунд:
Но при 8, вылетает. Ща капну дальше.
Во блин на работе сижу и типа делом занимаюсь :)

Добавлено спустя 9 минут, 53 секунды:
А вылетает потому что
Цитата:
while (j-1-m)>=0 do
begin
if p^=S then GoTo Unix2;
inc(p);
inc(m);
end;

В этом коде слишком большие цифры поучаются и операция через указатель слетает к сожалению.
  Avaddon

Member
Статус: Не в сети
Регистрация: 15.04.2004
Откуда: Москва
Halfback
while(x>0) или while(x <> 0) бытрее, потому что транслируется в ассёмблерный код типа
tst eax
jne xxx
что по определению быстрее чем
mov eax,ecx
cmp eax,<число>
jne xxx
(в это транслируется цикл for)
Теперь адресация по указателю быстрее потому что при обращении по индексу m[i] происходит вычисление адреса, а при обращении p^ просто обращение по адресу.
Т.е.
m[i] := 1; транслируется в
mov eax, sizeof(Pointer)
mul i
mov ebx,eax
mov eax,m
add ebx
mov [ebx],1
а p^ := 1;
транслируется в
mov eax,p
mov [ebx],1
(Это все примерная трансляция)






Ошибка у тебя вылетает т.к. ты выходишь за границы массива. Проверь j-1-m равно ли количеству элементов в массиве. И еще не используй <= или >= jne, je или jz предсказываются лучше, чем jle или jge.

Ray Adams
Цитата:
В этом коде слишком большие цифры поучаются и операция через указатель слетает к сожалению.

Большие это в чем и где? Это обычный выход за границы (лишняя итерация)

_________________
Цель жизни - d20 по жизни...

  Ray Adams

Advanced member
Статус: Не в сети
Регистрация: 09.06.2003
Откуда: USSR
Цитата:
if p^=S then GoTo Unix2;

Вот тут вылетает
  Avaddon

Member
Статус: Не в сети
Регистрация: 15.04.2004
Откуда: Москва
Ray Adams
Ик-сепшн, пожайлуста... :)
Скорее всего проблема в arifmetic overflow т.е. S > MaxShortint
Мурзилки! :)
Присвоение адреса указаделю надо делать перед началом цикла!
Код:
N:= 8;
NN:=1;
i := N;
while(i <> 0 ) do begin
  NN:= NN*i ;
  dec(i);
end;

j := 1;
while (NN-J > 0 ) do begin
 m := 1;
 P := @U; // Вот тут!!!
 while(N-m > 0 ) do  begin
  P^ := m;
  inc(m);
  inc(P);
 end;
 v := N;
 while(v <> 0) do begin
  RR:=Random(v);
  Inc(RR);
  R[N-v+1]:=U[RR];
  dec(v);
 end;
 k := RR;
 while (N-k <> 0 ) do begin
  U[k]:=U[k+1];   
  inc(k);
 end;
 inc(j);
end;
  Halfback

Member
Статус: Не в сети
Регистрация: 14.08.2003
Откуда: Питер
Ray Adams
Цитата:
Вот тут вылетает

Каким образом определил?

Добавлено спустя 37 минут, 46 секунд:
Avaddon
Цитата:
v := N;
while(v <> 0) do begin
RR:=Random(v);
Inc(RR);
R[N-v+1]:=U[RR];
dec(v);
end;
k := RR;
while (N-k <> 0 ) do begin
U[k]:=U[k+1];
inc(k);
end;

У тебя ошибка. Дело в том, у меня в этом месте цикл в цикле. А ты два цикла разделил. Вот так надо:
Цитата:
Randomize;
v:=N;
while (v<>0) do
begin
RR:=Random(v);
inc(RR);
R[N-v+1]:=U[RR];
k:=RR;
while (v-1-k)>=0 do
begin
U[k]:=U[k+1];
inc(k);
end;
dec(v);
end;


Ray Adams
Цитата:
В этом коде слишком большие цифры поучаются и операция через указатель слетает к сожалению.

Наверное ты прав. Дело в том, что при N:=8 каждая строка массива а занимает как минимум 21 разряд (1234567) а максимум 23 разряда(7654321), да и N!=8!=40320 занимает 16 разрядов. Но естьу меня идея как это поправить... А сейчас исходник имеет вот такой вид:

Цитата:

procedure TForm1.BitBtn2Click(Sender: TObject);
Label Unix2,Unix1;
var
N,NN: integer;
i,j,v,m,k,vv,w,ii: integer;
S: integer;
RR: integer;
U: array[1..10] of shortint;
R: array[1..10] of shortint;
a: array of integer;
StartTime, sek,min,hour : Integer;
p: PShortInt;

begin
N:= StrToInt(Edit1.Text);

ListBox1.Items.BeginUpdate;
ListBox1.Items.Clear;

// Вычисление N!=NN
NN:=1;
i:=N;
while (i<>0) do
begin
NN:=NN*i;
dec(i);
end;

SetLength(a,NN+1);

j:=1;
while (NN-j+1)<>0 do
begin

Unix2:

// Получение массива U[1..N]:=1,2,..,N
p:=@U;
m:=1;
while (N-m+1)<>0 do
begin
p^:=m;
inc(p);
inc(m);
end;

//
Randomize;
v:=N;
while v<>0 do
begin
RR:=Random(v);
inc(RR);
R[N-v+1]:=U[RR];
k:=RR;
while (v-k)<>0 do
begin
U[k]:=U[k+1];
inc(k);
end;
dec(v);
end;

//
vv:=1;
w:=1;
S:=0;
p:=@R;
while (N-w+1)<>0 do
begin
S:=S + p^*vv;
vv:=vv*10;
inc(w);
inc(p);
end;

m:=1;
while (j-m)<>0 do
begin
if a[m]=S then GoTo Unix2;
inc(m);
end;

a[j]:=S;
inc(j);
end;

// Выведение массива a[1..NN] на ListBox
ii:=1;
while (NN-ii+1)<>0 do
begin
ListBox1.Items.Strings[ii-1] :=FloatToStr(a[ii])+' ['+ FloatToStr(ii)+']';
inc(ii);
end;

ListBox1.Items.EndUpdate;
SetLength(a,1);

Unix1:
end;


Убрал все лишнее. Все >= заменил на <>0 прибавив к условию while(..+1).

_________________
Лучшая зашита - это нападение.

Последний раз редактировалось Halfback 31.08.2004 16:35, всего редактировалось 5 раз(а).

  Ray Adams

Advanced member
Статус: Не в сети
Регистрация: 09.06.2003
Откуда: USSR
Halfback Ну так дебагер на нем и показал мне ошибку :)
  Avaddon

Member
Статус: Не в сети
Регистрация: 15.04.2004
Откуда: Москва
Halfback
Я тут перепахал твой код, результаты исполнения
N = 8 - 3 сек, 40320 итераций
N = 10 - 36288 сек, 3628800 итераций
Оптимизации по размещению данных в памяти не производилось. Если делать - прирост будет 10%.
И еще. Убери из кода всю работу с листбоксом. Это сильно тормозит вычисления.
Заполняй какю-нибудь структуру, а потом разом в листбокс.
Вот тебе пример этого кода. Осталась одня операция по доступу к массиву Вычисление логарифма константы пошло лесом.
Код:
Const
 LN_10 : Real = 2.30258509299405E+0000;
Type
 PShortInt = ^Integer;
Label Unix2;
var
N,NN: integer;
i,j,v,m,k,vv: integer;
S: integer;
RR: integer;
U: array[1..10] of Integer;
R: array[1..10] of Integer;
a: PShortInt;
D: DWORD;
P: PShortInt;
 
begin
N:= 10;
NN:=1;
i := N;
while(i <> 0 ) do begin
  NN:= NN*i ;
  dec(i);
end;
 a := AllocMem(sizeof(Integer)*NN);
j := 1;
while (NN-J > 0 ) do begin
 m := 1;
 P := @U;
 while(N-m > 0 ) do  begin
  P^ := m;
  inc(m);
  inc(P);
 end;
 v := N;
 while(v <> 0) do begin
  RR:=Random(v);
  Inc(RR);
  R[N-v+1]:=U[RR];
  dec(v);
 end;
 k := RR;
 while (N-k <> 0 ) do begin
  U[k]:=U[k+1];   
  inc(k);
 end;
 inc(j);
 S := 0;
 vv := 1;
 P := @R;
 while(N-vv > 0 ) do begin
  S:= S + P^ *Trunc((exp((N-vv)*LN_10)));
  inc(vv);
  inc(P);
 end;
 PShortInt(Integer(a)+Sizeof(Integer)*j)^:=S div 1;
 m := 1;
 p := @a;
 while(j-1-m > 0) do
 begin
  if PShortInt(Integer(a)+Sizeof(Integer)*j)^= P^ then break
  else ;
  inc(m);
 end;
end;
FreeMem(a);

Пользуйся! И изучи особенности работы процессора и памяти. :) Удачи!

Добавлено спустя 5 минут, 47 секунд:
Ray Adams
Нашел время, подправил код, отпрофайлил. Убил все GoTo (за goto в этом форуме надо давать ЖК как за нецензурные слова :) )
Лень было по кэш-линиям раскидывать и оптимизировать по памяти.
Компилятор - FreePascal

_________________
Цель жизни - d20 по жизни...

  Halfback

Member
Статус: Не в сети
Регистрация: 14.08.2003
Откуда: Питер
Avaddon Ray Adams
Как на форму выбросить кол-во итераций?

_________________
Лучшая зашита - это нападение.

  Avaddon

Member
Статус: Не в сети
Регистрация: 15.04.2004
Откуда: Москва
Halfback
До начала цикла ты можешь делать все, что хочешь, на производительность это не скажется.
Или запусти прогрес в отельном потоке

_________________
Цель жизни - d20 по жизни...

  Halfback

Member
Статус: Не в сети
Регистрация: 14.08.2003
Откуда: Питер
Avaddon
Поясни, пожалуйста, следующие строки:
Цитата:
Type
PShortInt = ^Integer;

Цитата:
a: PShortInt;
D: DWORD;
P: PShortInt;

Цитата:
a := AllocMem(sizeof(Integer)*NN);

Цитата:
PShortInt(Integer(a)+Sizeof(Integer)*j)^:=S div 1;

Цитата:
if PShortInt(Integer(a)+Sizeof(Integer)*j)^= P^ then break

Цитата:
FreeMem(a);


Ну с последним вроде понятно. Вроде освобождает память, занятую под массив а.
И как по завершении процесса мне вывести на форму колличество выполненных итераций?

_________________
Лучшая зашита - это нападение.

  Ray Adams

Advanced member
Статус: Не в сети
Регистрация: 09.06.2003
Откуда: USSR
Цитата:
Type
PShortInt = ^Integer;

Ненадо , в Delphi все есть.

a := AllocMem(sizeof(Integer)*NN); - выделение памяти размеров NN интегеров. (криво както звучит)

PShortInt(Integer(a)+Sizeof(Integer)*j)^:=S div 1; - присвоение чере приведение типов
if PShortInt(Integer(a)+Sizeof(Integer)*j)^= P^ then break - тоже самое.
  Avaddon

Member
Статус: Не в сети
Регистрация: 15.04.2004
Откуда: Москва
Ray Adams
Halfback
А div 1 используется вместо вызова Trunc - так на порядки быстрее!
А D: DWORD осталось от вычислялки производительности.. :)
  Halfback

Member
Статус: Не в сети
Регистрация: 14.08.2003
Откуда: Питер
Avaddon
Цитата:
А D: DWORD осталось от вычислялки производительности..

Дык как ты вычислял производительность? Мне бы надо число итераций...

Твой исходник - неправильный, т.к. там есть повторения. Поставь N=2 или 3 и посмотри на результаты тыкая кнопку несколько раз. Но все равно спасибо за старание.

Avaddon
Ray Adams
Оцените мой исходник, но только за GoTo не пинайте, т.к. я испробовал вариант без применения метки но он в среднем оказался медленнее на 30%.

Код:
procedure TForm1.BitBtn2Click(Sender: TObject);
Label Unix2,Unix1;
type
  TDynArray = array[1..362881] of integer;
  TDynSmallArray = array[1..9] of shortint;

var
N,NN: integer;
i,j,v,m,k,vv,w,ii: integer;
S: integer;
RR: integer;
a: ^TDynArray;
R,U,p: ^TDynSmallArray ;
StartTime, sek,min,hour : Integer;

begin
N:= StrToInt(Edit1.Text);
ListBox1.Items.Clear;
ListBox1.Items.BeginUpdate;

// Вычисление N!=NN
NN:=1;
i:=N;
while (i<>0) do
  begin
  NN:=NN*i;
  dec(i);
  end;

GetMem(a,(NN+1)*30);

// Получение массива U[1..N]:=1,2,..,N
  GetMem(U,(N+1)*4);
  m:=1;
  while (N-m+1)<>0 do
    begin
    U^[m]:=m;
    inc(m);
    end; 

j:=1;
while (NN-j+1)<>0 do
  begin
  Unix2:
//
  GetMem(R,(N+1)*4);
  GetMem(p,(N+1)*4);
  p^:=U^;
 Randomize;
  v:=N;
  while v<>0 do
    begin
    RR:=Random(v);
    inc(RR);
    R^[N-v+1]:=p^[RR];
    k:=RR;
    while (v-k)<>0 do
      begin
      p^[k]:=p^[k+1];
      inc(k);
      end;
    dec(v);
    end;
  FreeMem(p,(N+1)*4);
//
  vv:=1;
  w:=1;
  S:=0;
  while (N-w+1)<>0 do
    begin
    S:=S + R^[w]*vv;
    vv:=vv*10;
    inc(w);
  end;
  FreeMem(R,(N+1)*4);

  m:=0;
  while (j-m)<>0 do
    begin
    inc(m);
    if a^[m]=S then GoTo Unix2;
    end;

  a^[j]:=S;
  inc(j);
end;

FreeMem(U,(N+1)*4);

// Выведение массива a[1..NN] на ListBox
ii:=1;
while (NN-ii+1)<>0 do
  begin
  ListBox1.Items.Strings[ii-1] :=FloatToStr(a^[ii])+'  ['+ FloatToStr(ii)+']';
  inc(ii);
  end;

FreeMem(a,(NN+1)*30);

end;
Все лишнее убрал. Ко всем массивам обращался при помощи указателей. Что скажете? Что тут можно еще оптимизировать?

_________________
Лучшая зашита - это нападение.

  Avaddon

Member
Статус: Не в сети
Регистрация: 15.04.2004
Откуда: Москва
Halfback
Цитата:
Дык как ты вычислял производительность? Мне бы надо число итераций...

а разве в NN не число итераций?
Цитата:
Твой исходник - неправильный, т.к. там есть повторения. Поставь N=2 или 3 и посмотри на результаты тыкая кнопку несколько раз. Но все равно спасибо за старание.

Может быть. Я просто брал твои исходник и правил его. Возможно, где-то ошибся. Я не ставил цели правильно реализовать твой алгоритм.

Цитата:
Все лишнее убрал. Ко всем массивам обращался при помощи указателей. Что скажете? Что тут можно еще оптимизировать?

Ты все равно обращаеся ко всем массивам по индексу, а не по вычесленному указателю на элемент массива.

_________________
Цель жизни - d20 по жизни...

  Halfback

Member
Статус: Не в сети
Регистрация: 14.08.2003
Откуда: Питер
Avaddon
Цитата:
Ты все равно обращаеся ко всем массивам по индексу, а не по вычесленному указателю на элемент массива.

Да ладно. Разве a^[j] не обращение через указатель? В литературе написанно именно так.

_________________
Лучшая зашита - это нападение.

  Avaddon

Member
Статус: Не в сети
Регистрация: 15.04.2004
Откуда: Москва
Halfback
a^ - обращение через указатель? a^[j] - обращение по индексу...
Подумай, что будет быстрее:

arrayPtr := @a;
inc(arrayPtr);
или
a^[j] := значение;
?
Дело в том, что при использовании индекса вычисление адреса производится при каждом обращении к массиву.
И как ты понимаешь
mov [eax],значение ; arrayPtr^ := значение
add eax, 4 ; inc(arrayPtr)
будет выполняться быстрее, чем
mov eax, a
mov ebx,j
mul ebx,4
add eax,ebx
mov [eax],значение ; это все - одна сторочка a^[j] := значение

_________________
Цель жизни - d20 по жизни...

  Halfback

Member
Статус: Не в сети
Регистрация: 14.08.2003
Откуда: Питер
Avaddon
Взято с Delphi Russian Knowledge Base from Vit Version 2.2 (http://www.sources.ru/delphi/drkb.zip):
Код:
.......
var
  Form1: TForm1;
{ Создаем переменную типа указатель на ваш тип массива. }
  P: ^TDynamicArray;

procedure TForm1.FormCreate(Sender: TObject);
begin
  P := AllocMem(DynamicArraySizeNeeded * SizeOf(Integer));
{ Как присвоить значение пятому элементу массива. }
  P^[5] := 68;
end;
..........


или

Код:
Распределите память кучи с помощью GetMem. Если вы имеете:

var
  a, b: array[0..30000]: Integer;
то попробуйте:
type
  TBigArray = array[0..30000] of Integer;
var
  a, b: ^TBigArray;
и во внешнем блоке сделайте:
GetMem(a, SizeOf(TBigArray));
GetMem(b, SizeOf(TBigArray));
Также необходимо применять указатели на память вместо ссылок, например взамен:
a[0] := xxx;
необходимо использовать
a^[0] := xxx; 


Что скажешь?......

_________________
Лучшая зашита - это нападение.

Показать сообщения за:  Поле сортировки  
Начать новую тему Новая тема / Ответить на тему Ответить  Сообщений: 50 • Страница 2 из 3 • <  1  2  3  >
-

Список форумов » Специализированные форумы » Программирование

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB | Kolobok smiles © Aiwan