Archive for april, 2010

Valborgsfirande

april 30, 2010

Glad Valborg kära läsare. Ikväll skall eldar brinna landet över och våren hälsas välkommen. Jag ska umgås med vänner utanför Älmhult (eller var det Alvesta, jag kommer aldrig ihåg) och planerar ha det skoj. Ett par charmiga hundar kommer också närvara, samt en skock får… Tanken är att elda lite och äta lite god mat, det kanske låter konservativt men ni vet väl hur jag är?

Det är lite tråkigt att jag kommer missa pappas framträdande med Levar manskör, men min kära syster ska filma det hela och lägga upp det på youTube sedan.

Binärsökning

april 28, 2010

Bloggen The Reinvigorated Programmer gav för ett par dagar sedan dess läsare i uppdrag att skriva en binär sök-algoritm i valfritt språk utan att testa (för annat än syntax-fel) och sedan skicka in. Detta pga en undersökning som visade på att endast 10% av programmerare kan producera en buggfri binär sök-algoritm.

Jag gjorde ett försök och i slutänden kom jag fram till följande funktion:

int binSearch(int a[], int size, int target)
{
  int lowPos = 0, highPos = (size - 1), middlePos = (highPos / 2);
  int returnVal = -1;
  while ((lowPos <= highPos) && (a[middlePos] != target))
  {
    middlePos = (lowPos + highPos) / 2;

    if (target > a[middlePos])
      lowPos =   middlePos + 1;
    else
      highPos =  middlePos - 1;
  }

  if (a[middlePos] == target)
    returnVal = middlePos;

  return returnVal;
}

syntax highlighted by Code2HTML, v. 0.9.1

En binär sökning söker igenom en sorterad lista värden och tittar ifall mittenvärdet är högre eller mindre (eller lika med) det sökta värdet, sedan halveras listan till den halva som bör innehålla det sökta värdet (t.ex övre halvan om mittenvärdet är 16 och det sökta värdet är 20). Detta upprepas tills mittenvärdet är lika med det sökta värdet eller den kvarvarande listan är tom.

Tyvärr fixade jag det inte på första försöket (och är inte hundra på att funktionen är buggfri) utan behövde testa och se att min rutin inte fungerade. Jag hamnade i ett så kallat off-by-one-läge, dvs att sökningen stannade ett ifrån det sista elementet (som borde innehålla det sökta värdet ifall det finns i listan).

Nyckeln var att inse att ett mittenelementet som inte är lika med det sökta värdet kan exkluderas. Detta leder till att delningen av listan blir

    if (target > a[middlePos])
      lowPos =   middlePos + 1;
    else
      highPos =  middlePos - 1;

Detta tog mer tid att klura ut än jag vill erkänna, men jag var nöjd när jag äntligen förstod vad och framför allt varför.

The Reinvigorated Programmer håller just nu på att gå igenom lite mer formella metoder för att beskriva algoritmer, det är kul att läsa. hitintills har han gått igenom invarianser och gränsfunktioner. Det är intressant att lära sig lite mer om algoritm-design, jag försöker skriva vad jag vill göra på papper innan jag programmerar men de här metoderna gör det möjligt att bevisa att man gör rätt.

I övrigt är det också en trevlig blogg, mycket programmering men också recensioner av de nya Doctor Who-avsnitten. Jag rekommenderar den varmt.

Ifall någon som kan lite om binär sök-algoritmen snubblar in skulle jag uppskatta att samtliga fel i koden ovan pekades ut.

Minneshantering

april 16, 2010

Säker minneshantering i C har alltid varit problematiskt, via slashdot hittade jag två blogginlägg om ämnet (del ett, del två). Del ett visar hur man undviker NULL-pekare-undantag och del två visar hur NULL-pekare-undantag kan utnyttjas för att få förhöjda privilegier i ett Linux-system. Första inlägget ger också lite information om hur operativsystem generellt hanterar minne och varför.

This was true for every program, including the operating system itself. You can probably guess what goes wrong here: suppose that Microsoft Word is storing your document at address 700 in memory. Now, you’re browsing the web, and a bug in Internet Explorer causes it to start scribbling over random memory and it happens to scribble over memory around address 700. Suddenly, bam, Internet Explorer takes Word down with it. It’s actually even worse than that: a bug in IE can even take down the entire operating system.

This was widely regarded as a bad move…

Liftarens guide referenser vinner alltid poäng hos mig!

Jag jobbar helt utan virtuellt minne i den produkt jag arbetar med på jobbet och vi har inte hittat på några fiffiga funktioner för att generera undantag. hårdvaran har dock vissa skydd inbyggd i hårdvaran som hindrar vår processor att skriva över allt för viktiga delar i minnet, samt meddelar när något gått horribelt fel. Detta genererar Abort-undantag och Undef-undantag som vi fångar upp och visar upp en felskärm med information om vilken typ av fel som inträffat, och ännu viktigare var felet inträffat. Skärmen är en kopia av Amigans Guru Meditation-skärm, svart med en röd blinkande ram med viktig (och dessutom kryptisk) information högst upp. Om vi sköter våra kort rätt kommer ingen kund någonsin se den (igen) men det känns bra att det finns referenser till retro-hårdvara bakom kulisserna.

Guru meditation

Guru Meditation