PHP challenge 6: Leksikon sortering (update 2)

[MC2]

Siden dabear sin php challenge har vært inaktiv på en stund så tenkte jeg å starte en ny en.

 

Litt om konkurransen

- Hvem som helst kan delta.

- Utfordringene skal hovedsakelig utfordre logisk tenking istedet for kunnskap om språket. Det er uansett en fordel å kunne det grunnleggende.

- Vanskelighetsgraden vil variere. Det er ikke nødvendigvis den første som er enklest.

- Oppgavene kommer at være rimelig små, maks 100 linjer.

- Dere får rundt 3 dager på hver utfordring, med mindre noe annet er sagt.

- Alle besvarelsene sendes inn til meg enten på pm eller mail: [email protected] (foretrekker mail).

- Du har lov å sende inn flere besvarelser med mindre noe annet er sagt.

- Premien er pride, fame and fortune! (ingen penge premier her...)

 

Vinneren av hver konkurranse blir kåret på forskjellige grunnlag, men hovedsakelig fart (blir også lagt vekt på at programmet ditt faktisk fungerer, duh). Dersom det er minimal forskjell på flere besvarelser så blir de postet i denne tråden og alle har lov å si sin mening.

 

Dersom noen har forslag til utfodringer eller spørsmål er det bare å sende pm/mail.

 

 

 

 

Challenge 1 Sortering

Vinner: Ernie med

1 2 3 [b]4[/b] 5 6
7 8 [b]9[/b] 0 1 2
3 4 5 [b]6[/b] 7 8
9 0 1 2 [b]3[/b] 4
5 6 7 8 [b]9[/b] 0
1 2 3 4 5 [b]6[/b]

Funksjonen skal her returnere 4+9+6+3+9+6 = 37

 

Se vedlegg for 4 eksempler på datasett.. 1000x1000, 100x100, 10x10 og 6x6.

 

Hvordan lese datasett?

Følgende funksjon returnerer et 2d array bygd opp som følger: $data[radnummer.. 0 til n-1][element i rad.. 0 til n-1]

function readdata($i) {
foreach (explode("\n", trim(file_get_contents($i))) as $line)
	$data[] = explode(" ", trim($line));

return $data;
}

$data = readdata("10.txt");
print_r($data);

Konkurransen:

Konkurransen deles i to klasser, en for 10x10 og en for 100x100 datasettene, siden man med enkelte fremgangsmåter antagelig ikke vil ha sjanse på 100x100 datasettet med tanke på hastighet. Et 1000x1000 datasett er også vedlagt for de som vil prøve seg på det.

 

Kriterier innen hver klasse er:

1. Korrekt løsning.
   
2. Hastighet.
   
3. Ved lik hastighet så prøves større datasett (f.eks 20x20)..
   

Tidsfrist:

Ca en uke, kl 21:00 søndag 8. desember.

 

Send løsning til peros2k på PM.

 

 

 

Resultatene

 

 

Challenge 6 Leksikon sortering

 

Oppgave

Denne oppgaven er ganske lik den første (sortering av heltall), men her skal dere sortere strenger som i et leksikon. Altså "absolute" kommer før "vodka". For å gjøre det litt mer interessant skal dere ikke sortere korte arrays som sist, men lengre arrays bestående av 1000+ elementer. Din sorteringsalgoritme skal i hvertfall kunne håndtere strenger bestående av store, små bokstaver og tall. Det er selvfølgelig et pluss om den klarer andre tegn også.

 

For å gjøre det litt mer interessant skal algoritmen din oppføre seg som "natsort" (altså Natual Order sorting) istedet for vanlig "sort". (mer om natual order string comparison)

 

Du skal levere en funksjon som skal returnere den sorterte arrayen. Key-value assosiasjoner trenger ikke å beholdes.

 

Frist

Utsatt intill videre

 

Vi kan vel si at denne oppgaven blir benket 29 desember 16:00, men dette er som vanlig ganske flesibelt.

 

Denne oppgaven blir benket av peros2k så alle forslagene sendes på pm til han.

 

 

Update (20.12.2007) Oppgave teksten

Update (29.12.2007) Utsatt

Endret 29. desember 2007 av MC2

[Vikdal]

Jeg melder meg hvertfall på. Bare for å ha litt å pusle med akkurt nå Ikke at jeg ikke har nok å gjøre fra før, men kommer sikkert noen morsomme utfordringer etterhvert

[Ernie]

PS. Bare for å unngå misforståelser; du skal skrive selve "sort" funksjonen i php. Altså, poenget med oppgaven er ikke å levere et skript som bruker bruker en funksjon skrevet av noen andre.

Med andre ord ikke bruke sort(...)?

[MC2]

PS. Bare for å unngå misforståelser; du skal skrive selve "sort" funksjonen i php. Altså, poenget med oppgaven er ikke å levere et skript som bruker bruker en funksjon skrevet av noen andre.

Med andre ord ikke bruke sort(...)?

Hadde vært en ganske kjedelig konkurranse vil jeg anta...

[Vikdal]

Da har jeg sendt inn mitt bidrag. Kjørte noen tester med testkoden over, og fikk litt varierende resultater, så jeg økte til 10000 kjøringer av koden, men det varierte like mye uansett.

 

Oppgir ikke noe tid, da det ikke er noe sammenlikningsgrunnlag likevel pga serveren har litt å si.

 

Lykke til folkens!

[MC2]

Ok, har skrevet om algoritmen som skal brukes for å benke bidragene. Hvis noen har noen bemerkninger er det bare å si i fra.

<?php


/* */
$array = array (
  0 => 38,
  1 => 68,
  2 => 13,
  3 => 33,
  4 => 6,
  5 => 81,
  6 => 5,
  7 => 56,
  8 => 85,
  9 => 20,
  10 => 44,
  11 => 46,
  12 => 39,
  13 => 61,
  14 => 60,
  15 => 29,
  16 => 71,
  17 => 80,
  18 => 84,
  19 => 66,
  20 => 38,
  21 => 61,
  22 => 86,
  23 => 74,
  24 => 3,
);


/* */
class bench {

//	  public $stdev;

	function __construct($func,$arg) {
			$runs = intval(trim(file_get_contents("runs.txt")));

			$times = array();

			for($i = 0; $i < $runs; $i++) {
//					  echo "\n".($i+1);
					$s = microtime(true);


					// code to be run
					$func($arg);



					$t = microtime(true) - $s;
//					  echo ": ".$t;
					$times[] = $t;
			}

//			  $this->stdev = $this->standard_deviation($times);

			echo "\tAverage:			".$this->average($times)."\n";
//			  echo "\tStandard deviation: ".$this->stdev."\n";
			echo "\tMax:				".max($times)."\n";
			echo "\tMin:				".min($times)."\n";
	}

	function average($ar) {
			return  array_sum($ar) / count($ar);
	}/*
	function standard_deviation($array){
			$avg = $this->average($array);
			foreach ($array as $value) {
					$variance[] = pow($value-$avg,2);
			}
			$deviation = sqrt($this->average($variance));
			return $deviation;
	}*/
}

if(count($argv) == 1) {

	echo number_format(intval(trim(file_get_contents("runs.txt"))));

	$fs = glob(dirname(__FILE__)."/1 - sort/*.php");
	$b = array();
	foreach($fs as $f) {
			$a = basename($f,".php");
			echo "\n\n".$a."\n";
			system("php bench_1.php ".$a);
	}
}
else {
	include(dirname(__FILE__)."/1 - sort/".$argv[1].".php");
	new bench($argv[1],$array);
}


?>

[Emancipate]

Lista med tall som skal sorteres var jo veldig kort, da. Resultatene hadde nok blitt mer til å stole på hvis lista hadde 1000 elementer eller mer.

[Emancipate]

Det er forresten ikke lurt å måle gjennomsnittsfart når det går såpass fort per omgang, fordi presisjonen på flyttallene vil gi avrundingsfeil. Det er bedre å plusse sammen alle omgangene (eventuelt unntatt de x sakteste).

 

Og en annen ting: Kan vi sende inn flere bidrag?

[Ernie]

Enig, jeg slet endel med å få testa det og samtidig få stabile resultater. Ved et gjennomsnitt over 10000 kjøringer er jeg nede i forskjeller på 1-2µs, men det er bare med echo av gjennomsnittet, noe jeg også foreslår blir gjennomført. Legger jeg echo for hvert kjøring til blir utslagene opptil 30µs, noe som iallfall hos meg blir betydelig. En annen ting er at ting som minne ikke blir utslagsgivende når man tester slik. Ideelt sett er dette en oppgave man kjører i betydelig raskere språk og dermed har mulighet til å teste med et par 100k elementer, for ikke å si noen millioner.

[Emancipate]

Jeg bruker denne koden for testing:

for ($i=0; $i<10000; $i++) {
$a[$i] = rand(-1000, 1000);
}

$t = 0;
for($i = 0; $i < 50; $i++) {
$s = microtime(true);
min_sortering ( $a );
$t += microtime(true) - $s;
}

Ikke 110% fair, men den kan heller kjøres et par ganger.

 

Jeg bruker forresten ca 2.6 sekunder på å kjøre igjennom den med min egen sorteringsfunksjon (Athlon XP 2400+), noen bedre?

Endret 28. oktober 2007 av tsg1zzn

[MC2]

Problemet er at jeg ikke kan forandre på oppgaven nå. Hadde oppgaven vært at man skal sortere 1000+ heltall hadde folk nok skrevet en annen mer komplisert alogritme.

 

Jeg har også vurdert det med at man får varierte resultater, hvilket er hvorfor jeg prøvde litt med standard deviation. Det er sånn at de tallene lengst "bort fra" gjennomsnittet "har mindre verdi". Er ofte brukt i statistikk osv. Men har noen et bedre forslag på tidtagingen?

 

Har tenkt å kjøre testene på en laptop som kjører minimalt med annet for å minske forstyrrelser. Hvert bidrag blir da kjørt 100 000 x 3 ganger (er litt redd for overoppheting etter at min stasjonære overopphetet under en benking)

 

Ser ikke noen god grunn hvorfor folk ikke kan sende inn flere bidrag.

Endret 28. oktober 2007 av MC2

[Emancipate]

Men har noen et bedre forslag på tidtagingen?

Jeg stemmer for denne kjørt 6 ganger, og resultatet er gjennomsnittet av de 4 beste.

$s = microtime(true);

for($i = 0; $i < 10000; $i++) {

mysort ( $a );

}

$t = microtime(true) - $s;

[Ernie]

Jeg bruker denne koden for testing:

for ($i=0; $i<10000; $i++) {
$a[$i] = rand(-1000, 1000);
}

$t = 0;
for($i = 0; $i < 50; $i++) {
$s = microtime(true);
min_sortering ( $a );
$t += microtime(true) - $s;
}

Ikke 110% fair, men den kan heller kjøres et par ganger.

 

Jeg bruker forresten ca 2.6 sekunder på å kjøre igjennom den med min egen sorteringsfunksjon (Athlon XP 2400+), noen bedre?

1.8s og pusher fortsatt nedover. Tester på laptop med Mobility Athlon 64 2800+.

[Dustwave]

Det er meningsløst å benchmarke en sorteringsalgoritme på 2x elementer, hadde vært mer interessant om man testet på tierpotenser av elementer:

 

f.eks lister av:

10, 100, 1000, 10000 og 100000 elementer.

 

Samt at elementene var tilfeldige tall fra et gitt intervall.

[JohndoeMAKT]

Er det bestemt at det skal være 25 integerverdier og at det er verdiene listet øverst i tråden som blir brukt?

 

Jeg støtter forøvrig Dustwaves forslag, hva med å ha det som neste oppgave?

[Ernie]

Det er meningsløst å benchmarke en sorteringsalgoritme på 2x elementer, hadde vært mer interessant om man testet på tierpotenser av elementer:

 

f.eks lister av:

10, 100, 1000, 10000 og 100000 elementer.

 

Samt at elementene var tilfeldige tall fra et gitt intervall.

Ja, på 25 elementer er det knapt forskjell og man jobber ned på µs-nivå. Jeg har en 3-4 mulige løsninger, alle er nesten dønn like på 25 elementer, men skrur man opp er forskjellene helt vanvittige. En ide hadde vært å teste både forskjellige mengder og "tilstand" på tallene. Dvs. f.eks helt random tall, nesten sorterte tall og helt sorterte tall.

[MC2]

Jeg har allerede planlagt neste oppgave, som faktisk er ganske lik denne, men vi kan godt den først.. vi får se.

 

Jeg skjønner problemet, og ja, det kommer nok være vanskelig å benke nettopp denne oppgaven, men som forklart tidligere så skulle programmene være forholdsvis små og de skulle sortere en hvilken som helst (kanskje dårlig forklart i oppgaven) heltalls liste i stigende rekkefølge. Heltall inkluderer da også negative tall. Hadde oppgaven vært å sortere en liste med 10 000 heltall så hadde folk som allerede har levert skrevet en annen, mer komplisert algoritme. Men under benking så kan det godt tenkes at jeg benker både med korte lister og lange lister. Men hittil under test benking (10 000) kjøringer så gir de oppgavene jeg har fått inn ganske forskjellige resultater ("ganske" er kanskje litt drøyt), dersom vi bruker standard deviation som er mer nøyaktig i denne sammenhengen.

 

Update:

Jeg har planlagt fire oppgaver til, hvorav en av dem kan være vanskelig, en annen veldig vanskelig og en tredje nesten umulig, så om noen har noen forslag til oppgaver er det bare å sende en mail. Også har første posten blitt oppdatert med hvordan oppgaven kommer at bli benket.

Endret 29. oktober 2007 av MC2

[Dustwave]

Jeg skjønner problemet, og ja, det kommer nok være vanskelig å benke nettopp denne oppgaven, men som forklart tidligere så skulle programmene være forholdsvis små og de skulle sortere en hvilken som helst (kanskje dårlig forklart i oppgaven) heltalls liste i stigende rekkefølge. Heltall inkluderer da også negative tall. Hadde oppgaven vært å sortere en liste med 10 000 heltall så hadde folk som allerede har levert skrevet en annen, mer komplisert algoritme. Men under benking så kan det godt tenkes at jeg benker både med korte lister og lange lister. Men hittil under test benking (10 000) kjøringer så gir de oppgavene jeg har fått inn ganske forskjellige resultater ("ganske" er kanskje litt drøyt), dersom vi bruker standard deviation som er mer nøyaktig i denne sammenhengen.

 

Det er absolutt ikke vanskelig å benke den oppgaven, å påstå noe annet er amatørmessig. Men siden input er så lite så har det lite å si hvilken algoritme man velger for å sortere, og tiden avhenger mer på andre faktorer som egentlig ikke burde være tilstede.

Endret 29. oktober 2007 av Dustwave

[MC2]

Bare for å forklare til de som synes at funksjonene skal benkes med lange lister, så er det ugunstig siden oppgaven var å sortere en kort liste, og dette var for å gjøre den forsåvidt enkel. Hadde oppgaven derimot vært å sortere lange lister hadde folk skrevet andre algoritmer som er mer effektive på lange lister mens de er tregere på korte lister. Altså forskjellige algoritmer blir brukt på forskjellig lengde av lister. Det har blitt gjort ganske mye forskning innenfor sortering, men sortering av korte lister er forsatt enkelt. Hvis folk har lyst så kan en fremtidig oppgave godt være å sortere en liste på 1000+ elementer. Det som er interesserant er å se hvilke metoder folk bruker for å sortere raskest.

 

Dustware: Hvordan ville du ha benket denne oppgaven?

[Ernie]

Dustware: Hvis du ikke ser noen forskjell er jeg veldig spent på hvilke algoritmer du prøver deg på. Jeg har iallfall en som peker seg mer eller mindre vanvittig ut uannsett hva jeg finner på. Når jeg tester med koden tsg1zzn sakset inn her ligger jeg nå nede i under 50% dårligere ytelse i forhold til "native" sort.