Mikrokonkurs

[Toster]

Jako ze wszyscy lubia duze konkursy ktore zajmuja wiele dni itp itd a ja wole cos malego szybkiego co mozna zrobic w przerwie na hebrate proponuje mala mikro konkursy. Czas okolo 3-4 dni. Problem jest taki:

napisz program ktory generuje tablice 100x100 w ktorym sa losowe wartosci z przecialu 0..299, a nastepnie zlicz liczbe wystapien wartosci w grupach po 25.

 

Proponowany kod wyjsciowy:

[delphi]

procedure Test;

var

wyn2: array[0..299] of integer;

wyn: array[0..11] of integer;

t,y: integer;

map: array[0..99, 0..9] of integer;

begin

RandSeed := 23423;//specjalnie ustawione na sztywno, aby byla powtarzalnosc wynikow !

for t := 0 to 99 do

for y := 0 to 99 do

map[t,y] := Random(100);

 

for t := 0 to 99 do

for y := 0 to 99 do

wyn2[ map[t,y] ] := wyn2[ map[t,y] ] + 1;

 

for t := 0 to 11 do

for y := 0 to 24 do

wyn[t] := wyn[t] + wyn2[y + t * 25];

 

end;

[/cpp]

 

kompilacja pod gcc bez opcji optimize, kompilacja pod delphi ze switchami $R-, $O-

 

Jesli sa chetni czekam do piatku na kody zrodlowe

 

test bedzie polegal na wywolaniu procedury test 10 000 000 i zmierzeniu czasu tej operacji. Wygrywa najszybszy kod.

chetni pisac na toster@ps.pl, z dopiskiem Mikro - konkurs

[Firen]

Chyba sie wdarl maly blad w kodzie rozwiazania do Delphi

 

KODmap[t,y] := Random(100);

 

Nie powinno tu byc 300?

[TSr]

Ciężka sprawa jak dla mnie żeby to przyspieszyć, ale kod już wysłałem B)

[Force]

Rozumiem, że nie można zliczać przy wczytywaniu?

[Toster]

wszystkie chwyty dozwolone.

@Firen, true blad powinno byc 300 pisalem w notatniku

[Force]

I do czego ma wynik zwracać? jest jakaś zmienna zewnętrzna?

I czy tablice dostajemy czy nie?

[Toster]

wynik niech bedzie w tablicy

nie zwracaj jej, tak jak w tych przykladach co podalem

 

ja dopisze pozniej na koniec co trzeba

[Toster]

dzis o 20.00 koniec konkursu, jak narazie zwyciezca przez walkower jest Tsr

[Force]

Wg mnie w tym algorytmie nie da się uzyskać lepszej złożoności niż n^2, przykładowy algorytm powinien mieć złożoność taką aby dało się ją polepszyć, albo nie podawać kodu, tylko co sie daje na wejściu, co sie oczekuje na wyjściu i nich każdy napisze coś. Można zrobić takie co tygodniowe konkursu, że podaje się jakiś problem a i aby każdy mógł coś napisać

[Toster]

zlozonosc alg. to jedno, a implementacja to 2gie. Ten kod mozna mocno poprawic. Kwestja siasc i pokabinowac

[Force]

oj tam, jakaś stała po prostu będzie większa/mniejsza, fajniej dać zadania gdzie można zrobić coś sześciennie ale i też liniowo

[Toster]

Niby tak, ale patrzac na przekroj wieku na forum to moze 2 osoby zlapia cos z algorytmiki na jakims sensownym poziomie. A w taki podejsciu jak zaproponowalem alg. jest prosty jak drut, trzeba tylko dopracowac szczegoly. Ale widac odzew bliski zeru, wiec dam sobie spokoj :|

[Toster]

Konkurs wygram Tsr Jego algorytm byl jedyny... Gratulejszyn

[Blind]

ano, zadania czysto algorytmiczne nie maja duzego wziecia

[TSr]

A szkoda bo to ciekawe co by to mogło przyspieszyć. Ja zmieniłem tablice dwuwymiarowe na jednowymiarowe. Do tego rozbiłem jedno skompilowane wyrażenie na dwa prostsze.

[Toster]

Ponizej zamieszczam wyniki testu bo sa bardzo interesujace (przynajmniej dla mnie)

 

Kod programu do testow:

program Project1;

{$APPTYPE CONSOLE}
{$R-}
{$O+}

uses
 SysUtils, mmsystem, Math;

function Test_Poczatkowy:integer;
var
  wyn2: array[0..299] of integer;
  wyn: array[0..11] of integer;
  t,y: integer;
  map: array[0..99, 0..99] of integer;
begin
  for t := 0 to 299 do
     wyn2[t] := 0;
  for t := 0 to 11 do
     wyn[t] := 0;


  RandSeed := 23423;      //specjalnie ustawione na sztywno, aby byla powtarzalnosc wynikow !
  for t := 0 to 99 do
     for y := 0 to 99 do
        map[t,y] := Random(300);

  for t := 0 to 99 do
     for y := 0 to 99 do
        wyn2[ map[t,y] ] := wyn2[ map[t,y] ] + 1;

  for t := 0 to 11 do
     for y := 0 to 24 do
        wyn[t] := wyn[t] + wyn2[y + t * 25];

  Result := 0;
  for t := 0 to 11 do
     Inc(Result, wyn[t]);
end;


function Test_Tsr:integer;
var
  wyn2: array[0..299] of integer;
  wyn: array[0..11] of integer;
  t,y,a: integer;
  map: array[0..9999] of integer;
begin
  for t := 0 to 299 do
     wyn2[t] := 0;
  for t := 0 to 11 do
     wyn[t] := 0;

  RandSeed := 23423;
  for t := 0 to 9999 do
     map[t] := Random(300);

  for t := 0 to 9999 do
     wyn2[ map[t] ] := wyn2[ map[t] ] + 1;

  for t := 0 to 11 do
     for y := 0 to 24 do
     begin
        a := y + t * 25;
        wyn[t] := wyn[t] + wyn2[a];
     end;

  Result := 0;
  for t := 0 to 11 do
     Inc(Result, wyn[t]);

end;


type
  TMyArray = array[0..99] of integer;

function Test_Tostera:integer;
var
  wyn2: array[0..299] of integer;
  wyn: array[0..11] of integer;
  t,y,a: integer;
  map: array[0..99] of TMyArray;
  tmp: TMyArray;
  pi, pi2: ^Integer;
begin
  for t := 0 to 299 do
     wyn2[t] := 0;
  for t := 0 to 11 do
     wyn[t] := 0;

  RandSeed := 23423;      //specjalnie ustawione na sztywno, aby byla powtarzalnosc wynikow !
  pi := @map[0];
  t := 9999;
  while t >=0 do begin
     pi^ := Random(300);
     Inc(pi);
     dec(t);
  end;

  pi := @map[0];
  t := 9999;
  while t >=0 do begin
     Inc(wyn2[ pi^ ]);
     Inc(pi);
     Dec(t);
  end;
  Pi := @wyn2[0];
  pi2 := @wyn[0];
  t := 11;
  while t >=0 do begin
     y := 24;
     while y >=0 do begin
        Inc(pi2^, pi^);
        Inc(pi);
        Dec(y);
     end;
     Inc(pi2);
     dec(t);
  end;

  Result := 0;
  for t := 0 to 11 do
     Inc(Result, wyn[t]);
end;

var
 tim1, tim2: Cardinal;
 t, u, wyn: integer;
 z: array[0..30] of Double;
 mean, stdDev: Extended;
begin
  for u := 0 to 30 do begin
     tim1 := timeGetTime;
     for t := 0 to 10000 do
        wyn := Test_Tsr;
     tim2 := timeGetTime;
     z[u] := tim2-tim1;
     Writeln('Step ',u, ' wynik:',wyn);
  end;
  MeanAndStdDev(z, Mean, stdDev);
  Writeln('Mean time:',Mean:6:3);
  Writeln('StdDev time:',stdDev:3:3);
  readln;
end.

 

Wyniki:

{$R-}, {$O-}

Poczatkowy:

Mean time:1786.387

StdDev time:6.844

 

Tsr:

Mean time:1524.452

StdDev time:4.877

 

Toster:

Mean time:1466.806

StdDev time:4.354

 

 

{$R-}, {$O+}

Poczatkowy:

Mean time:839.968

StdDev time:3.601

 

Tsr:

Mean time:871.516

StdDev time:5.876

 

Toster:

Mean time:871.903

StdDev time:7.691

 

czary

[TSr]

Widocznie sztuczna inteligencja zaczyna wyprzedzać naturalną

[TSr]

UPDATE:

 

Przeprowadziłem własny pomiar. W programie testowym zmieniłem tylko funkcje mierzącą czas, którą na szybko znalazłem na googlach więc nie mam pewności co do jej jakości.

 

Poczatkowy

Mean time:8043.032

StdDev time:62.215

 

Tsr

Mean time:7760.032

StdDev time:61.437

 

Toster

Mean time:7760.323

StdDev time:68.346

 

Po optymalizacji trzeciego poziomu -O3

 

Poczatkowy

Mean time:7363.226

StdDev time:52.679

 

Tsr

Mean time:7041.097

StdDev time:62.328

 

Toster

Mean time:6958.516

StdDev time:69.451

 

Wyniki na FPC jak widać nie są już takie zaskakujące Widać wyraźną poprawę wydajności po włączeniu optymalizacji.

Toster, na jakim sprzęcie robiłeś testy?

[Toster]

Computer System

Name : PIKUŚ

User Name : Toster

Logon Domain : PIKUŚ

 

Processor(s)

Model : 1x AMD Athlon™ 64 Processor 2800+

Speed : 1.80GHz

Model Number : 2800 (estimated)

Type : Mobile

L2 On-board Cache : 512kB ECC synchronous write-back

 

System Mainboard

Bus(es) : ISA AGP PCI USB

MP Support : 2 CPU(s)

MP APIC : No

System BIOS : American Megatrends Inc. 080011

System Mainboard : MSI MS-6702

System Chipset : VIA Technologies Inc Unknown (0282)

Front Side Bus Speed : 1x 200MHz (200MHz data rate)

Installed Memory : 1024MB

 

Video System

Monitor/Panel : SONY SDM-HS95D DVI-D

Adapter : RADEON 9000 SERIES

Adapter : RADEON 9000 SERIES - Secondary

 

Operating System(s)

Windows System : Microsoft Windows XP Professional Ver 5.01.2600 Dodatek Service Pack 2

[TSr]

Mam niewiele gorszy sprzęt więc jednak dziwne te wyniki. U mnie przejście wykonuje się średnio 7 sekund u Ciebie poniżej 1s.

Sprawdzałem to na procesorze Sempron 2800, 512MB RAM.

[Toster]

hmm.. ciekawe, mozna zrobic wiecej jakis testow porownawczych, bo cos nie chce mi sie wierzyc ze FP zrobil ~7x wolniejszy kod...