Gå til innhold

PHP challenge 6: Leksikon sortering (update 2)

MC2

Av MC2
i Programmering og webutvikling

Anbefalte innlegg

Ernie

Ernie

Skrevet
Skrevet (endret)

Bare jeg som synes PHP bruker skremmende mye minne på oppgaven her? Etter å ha lest inn 100x100-tabellen sitter jeg med et nåværende bruk på ca2.6MB og peak på ca3.1MB. Ren matematikk skal tilsi at tabellen egentlig skal ta 10kB (lagret som int) eller i verstefall 20kB (lagret som char).

Endret av Ernie
Lenke til kommentar

Videoannonse

Videoannonse
Annonse
Ernie

Ernie

Skrevet
Skrevet 

$a = readtable('100.txt');
echo memory_get_peak_usage(true)."\n";
echo memory_get_usage(true)."\n";

Skrev en int-versjon, men den bruker minimalt mindre minne på peak og samme nivå ved måling. Det i seg selv sier meg at det er noe galt et sted though :hmm:

Lenke til kommentar
-morten

-morten

Skrevet
Skrevet

Du må nesten spesifisere helt nøyaktig hva det er vi skal lage i opg 5... :)

 

Skal vi lage findmax($filnavn) eller findmax($data)?

Og hvis sistnevnte, skal vi da også lage $data = readdata($filename), eller skal alle bruke den du skrev tidligere?

 

Er ganske stor forskjell på disse tre, for fil-IO er jo treigt som fy...

 

Jeg syns findmax($filnavn) hadde vært best, så blir det litt mer variasjon. Og at man kan ha flere hjelpefunksjoner hvis man vil, feks din readdata().

Lenke til kommentar
peros2k

peros2k

Skrevet
Skrevet
Du må nesten spesifisere helt nøyaktig hva det er vi skal lage i opg 5... :)

 

Skal vi lage findmax($filnavn) eller findmax($data)?

Og hvis sistnevnte, skal vi da også lage $data = readdata($filename), eller skal alle bruke den du skrev tidligere?

 

Er ganske stor forskjell på disse tre, for fil-IO er jo treigt som fy...

 

Jeg syns findmax($filnavn) hadde vært best, så blir det litt mer variasjon. Og at man kan ha flere hjelpefunksjoner hvis man vil, feks din readdata().

Vi sier at begge er lovlig vi. Dersom noen leverer findmax($data) så benker jeg med tiden det tar å gjøre findmax(readdata($filename)); .. for å gjøre det rettferdig med de som har findmax($filename);

Lenke til kommentar
Ernie

Ernie

Skrevet
Skrevet (endret)

Noen som har testet på 1000x1000? Klart å dytte det såvidt under 20sek nå (testet på på en AMD Athlon 64 X2 4600+). Det er en enslig kjøring vel og merke, og uten innlesing. Underveis har PHP allokert småpene 315MB.

 

Red.: Etter litt nærmere ettertanke var det ganske klønete kodet, og plutselig ble alt så utrolig mye bedre :p Dog peak på 305MB noe jeg synes er rimelig kraftig overkill. Hadde jeg skrevet det i C++ hadde jeg da vitterlig klart meg med 20-30MB maks :hmm:

 

Red.: Helt ute av trening merker jeg. Er jo «no problem» å få minnebruken under 1MB, selv i PHP.

Endret av Ernie
Lenke til kommentar
gxi

gxi

Skrevet
Skrevet

Neste challenge kan kanskje bestå av et eller annet stort som normalt sett vil kreve mye minne å utføre, så kan konkurransen være å få utført det på kortest tid og med minst minneforbruk, hvor vekten ligger på minneforbruk. Det kunne vært morsomt.

Lenke til kommentar
peros2k

peros2k

Skrevet
Skrevet

Her er resultatene for challenge 5:

 

I utgangspunktet 3 deltagere, Ernie, Morten og Rask. Men jeg satte sammen en jeg også (måtte ha noe for å sjekke om funksjonene gav rette resultater), så tok den med for å få en ekstra deltager.

 

Er imponert over løsningene som ble levert, jeg hadde forventet meg "brute force" løsninger, men alle bruker en eller annen form for dynamisk programmering og er algoritmemessig veldig like. Alle løsningene var veldig kjappe, så det ble kun benket med 1000x1000, da det var nesten umulig å se forskjell på mindre datasett.

Alle funksjonene ble benket 20 ganger, 5 ganger på 4 forskjellige 1000x1000 datasett. Har regnet ut min/max/snitt for hver funksjon:

morten:
Average: 1.85514963865
Min: 1.48964595795
Max: 2.03804707527

ernie:
Average: 2.44923468828
Min: 1.95941901207
Max: 2.71855115891

peros:
Average: 3.15243154764
Min: 2.49068784714
Max: 3.47440481186

rask:
Average: 4.20622769594
Min: 3.37160301208
Max: 4.61887001991

 

Morten er med andre ord vinner, med en funksjon som også bruker veldig lite minne.

 

Kodene ser litt forskjellig ut, men gjør omtrent samme ting..

 

Morten:

 

function morten($file) {
	$f = fopen($file, 'r');
	$max = explode(' ', rtrim(fgets($f)));
	while ($line = rtrim(fgets($f))) {
			$nmax = array(); $i = 0;
			foreach (explode(' ', $line) as $num) {
					$h = $max[$i-1];
					if ($max[$i] > $h) $h = $max[$i];
					if ($max[$i+1] > $h) $h = $max[$i+1];
					$nmax[$i++] = $h + $num;
			}
			$max = $nmax;
	}
	return max($max);
}

 

Ernie:

 

function ernie($file)
{
$fp = fopen($file, 'r');
$line = fgets($fp);
$data = explode(' ', trim($line));
$size = count($data);
$best = array();

$max = $size - 1;
//Building best for first row
for($i = 0; $i < $size; $i+=1)
{
	$lastBest[$i] = (int)$data[$i];
}

//Looping from row 0 to n-1
for ($row = 1; $row !== $size; $row +=1)
{
	$line = fgets($fp);
	$data = explode(' ', trim($line));
	//Looping from col 0 to n-1
	for ($col = 0; $col !== $size; $col +=1)
	{
		//Current column is on the very left side, might be useful to cut
		// col 0 in row-1 out
		if ($col === 0)
		{
			if ($lastBest[0] > $lastBest[1])
			{
				$best[$col] = max($lastBest[0], $lastBest[1])
									+(int)$data[0];
			}
			else
			{
				$best[$col] = $lastBest[1]+(int)$data[0];
			}
		}
		//Current column is on the very right side, might be useful to cut
		// col n-1 in row-1 out
		elseif ($col === $max)
		{
			if ($lastBest[$max] > $lastBest[$max-1])
			{
				$best[$col] = max($lastBest[$max], $lastBest[$max-1])
									+(int)$data[$max];
			}
			else
			{
				$best[$col] = $lastBest[$max-1]+(int)$data[$max];
			}
		}
		else
		{
			$best[$col] = max($lastBest[$col-1],
							  $lastBest[$col],
							  $lastBest[$col+1])
								+ (int)$data[$col];
		}
	}
	$lastBest = $best;
}
fclose($fp);
//Returning highest best path from last row
return max($best);
}

 

Rask:

 

function rask($data) {
	function maxnmbr($key, $comparr, $size) {
			if($key-1 < 0) {
					return max($comparr[$key], $comparr[$key+1]);
			} elseif($key+1 > $size-1) {
					return max($comparr[$key], $comparr[$key-1]);
			} else {
					return max($comparr[$key-1], $comparr[$key], $comparr[$key+1]);
			}
	}

	$size = count($data[0]);

	for ($i=1; $i<$size; $i++) {
			foreach($data[$i] as $key => $nmbr) {
					$maxnmbr = maxnmbr($key, $data[$i-1], $size);
					$data[$i][$key] = ($nmbr + $maxnmbr);
			}
			unset($data[$i-1]);
	}
	return max($data[$size-1]);

}

 

peros2k:

 

function peros(&$data) {
	for($i = 0; $i < count($data); $i++)
			for ($y = 0; $y < count($data[$i]); $y++)
					$data[$i][$y] += max($data[$i-1][$y-1], $data[$i-1][$y], $data[$i-1][$y+1]);
	return max($data[count($data)-1]);
}

 

Lenke til kommentar
-morten

-morten

Skrevet
Skrevet (endret)

Weee :)

Hehe, alle endte opp med samme algoritme ja.. Skal vel ikke så mye grubling til før man skjønner at permutasjoner ikke helt er tingen her. :)

Erfaringene mine var forøvrig at foreach er raskere enn for ($i < count(array)), og max() er raskere enn manuelt med for-loops, men tregere enn if-er på 3 elementer. Og rtrim() er naturlig nok en tanke raskere enn trim().

 

Grunnen til at PHP spiser minne, er at PHP sine arrays egentlig er hashtabeller med litt ekstra stæsj for rask traversering. Det krever en del metadata, så hvert element bruker (såvidt jeg kan se) ca 40 byte i tillegg til selve dataene og nøkkelen. Dessuten må en hashtabell ha mange flere elementer enn det den faktisk bruker til å lagre data. Og når tabellen fylles opp må den øke størrelsen, som er kostbart (må allokere nytt minne og flytte dataene). Derfor tar man gjerne i litt skikkelig, og feks dobler størrelsen. Og er det allerede stort, så er jo en dobling ganske mye.

Så dermed ender du fort opp med å bruke myyyye mer minne enn du ville gjort ved å bruke et array i C ;)

Endret av -morten
Lenke til kommentar
Peter

Peter

Skrevet
Skrevet

Interessante løsninger, men "peneste" løsning vil jeg definitivt si var peros2k sin.

Hadde vært veldig interessant å se den løsningen gjøre oppgaven slik som de to raskeste, nemlig ved å bare loope over dataene èn gang og forkaste gamle data underveis.

Lenke til kommentar
MC2

MC2

Skrevet
  • Forfatter
Skrevet

Ma si at dette har vaert en kul oppgave! Skulle gjerne ha deltatt selv.

 

Er det noen som har noen forslag for neste? Jeg har i det siste holdt pa mye med bilder, sa det kunne ha vaert en artig ide a gjore noe image recognition-aktig, men det er tross alt ganske vanskelig. (sorry for at de norske tegnene mangler, men prover ut handwriting-recognition pa tableten)

Lenke til kommentar
grimjoey

grimjoey

Skrevet
Skrevet (endret)

har noen forslag.

 

tall/geo:

primtallgenerator

 

grafikk (eneste tillatte innebygde bilde funksjoner er imagecolorallocate, imagecreate, imagedestroy, imagegif og imageline(img, x, y, x, y) aka imagedot()):

3d rendrer

raskeste linje (kanskje med anti alias)

raskeste sirkel

osv...

 

andre ting:

analog klokke

 

edit: la til ordet "bilde" linje 6

Endret av grimjoey
Lenke til kommentar
grimjoey

grimjoey

Skrevet
Skrevet

btw: kan noen forklare meg hvordan svaret i oppgave 5 klarer å finne stien som gir høyst mulig verdi (som var en del av oppgaven)?

 

for meg ser det ut som den begynner til venstre i første linje. så sjekker -1 0 og 1 indexen i neste. velger det høyeste tallet av de og fortsetter nedover med samme logikk. så dersom tallmatrisen ser slik ut:

 

1 2 3 4 5 6 7 8 9
3 2 1 4 5 6 7 8 9
3 2 1 4 5 6 7 8 9
3 2 1 4 5 6 7 8 9
3 2 1 4 5 6 7 8 9
3 2 1 4 5 6 7 8 9
3 2 1 4 5 6 7 8 9
3 2 1 4 5 6 7 8 9
3 2 1 4 5 6 7 8 9

 

ville den funnet 1+3+3+3+3+3+3+3+3 = 28, mens riktig svar er 9x9 = 81.

dersom en av svarene gikk ut i fra høyeste tallet i øverste linje kunne man fått en felle som:

 

1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 1 2 3
9 8 7 6 5 4 1 2 3
9 8 7 6 5 4 1 2 3
9 8 7 6 5 4 1 2 3
9 8 7 6 5 4 1 2 3
9 8 7 6 5 4 1 2 3
9 8 7 6 5 4 1 2 3
9 8 7 6 5 4 1 2 3

 

og den ville ikke funnet "riktige" bane.

 

er det noe jeg har missforstått?

Lenke til kommentar

Opprett en konto eller logg inn for å kommentere

Du må være et medlem for å kunne skrive en kommentar

Opprett konto

Det er enkelt å melde seg inn for å starte en ny konto!

Start en konto

Logg inn

Har du allerede en konto? Logg inn her.

Logg inn nå
Gå til emneliste

  • Hvem er aktive   0 medlemmer

    • Ingen innloggede medlemmer aktive
×
×
  • Opprett ny...