fredag 25 april 2014

Sorteringsalgoritmer visualiserade med folkdans

Youtube-kanalen AlgoRythmics visar hur olika algoritmer för sortering fungerar genom folkdanser från olika kulturer.

Bubble-sort med Küküllőmenti legényes (ungern)


Merge-sort med Siebenbürgensachsare (tyskland)


Alla danser hittar du på youtube-kanalen.

fredag 10 juni 2011

Skriv var du vill i kommandoraden med ANSI-sekvenser

I över 10 år har jag undrat hur en del kommandoradsprogram gör för att skriva ut något på en specifik position på skärmen istället för (som det brukar var) längst ned i kommandoraden. T.ex. är det många program som visar en progressbar över hur långt en installationen har kommit eller hur mycket som laddats ned av en fil, se t.ex. wget.

Idag tog jag äntligen mod till mig och googlade fram svaret.

Svaret är ANSI escape-sekvenser. Man skriver helt enkelt ut några speciella sekvenser av tecken för att flytta pekaren eller ändra färg etc.

Här är några exempel på escape-sekvenser för att flytta pekarens position:

\033[r;kH - flytta pekaren till rad r och kolumn k
\033[nA - flytta pekaren n positioner uppåt
\033[nB - flytta pekaren n positioner ner
\033[nC - flytta pekaren n positioner höger
\033[nD - flytta pekaren n positioner vänster
\033[s - lagra nuvarande pekar-position
\033[u - återställ lagrad pekar-position
\033[K - sudda allt på raden från pekarens position

Några sekvenser för att formatera text:
\033[1m - fet eller extra stark färg på
\033[4m - understruken text
\033[7m - förgrund och bakgrund byter färg

Några sekvenser för att byta färg på texten:
\033[31m - röd text på svart bakgrund
\033[41m - vit text på röd bakgrund
\033[32m - grön text på svart bakgrund
\033[42m - vit text på grön bakgrund
\033[33m - gul text på svart bakgrund
\033[43m - vit text på gul bakgrund
\033[34m - blå text på svart bakgrund
\033[44m - vit text på blå bakgrund

Fler kommandon och mer info kan du hitta här, här, här och här.

Ett par exempel med PHP

Så för att t.ex. skriva ut något på en viss position i terminalen med php kan man göra en funktion som ser ut såhär:

function echoAt($row,$col){
  echo "\033[s"; //lagra pekarens position
  echo "\033[".$row.";".$col."H"; //flytta pekaren
  echo $text; //skriv ut texten
  echo "\033[u"; //återställ pekarens position
}

Jag skrev även en lite mer komplicerad funktion som ritar ut en progressbar.

function printProgressbar($percentage,$size=50){
   $filled = round($percentage*$size); //hur mycket ska vara ifyllt?
   $info = number_format($percentage*100, 1, '.', '')."%"; //formatera info
   $infoStart = intval($size/2-strlen($info)/2); //vill ha info centrerad

   $output = "\033[s"; //lagra pekarens position
   $output .= "\033[7m"; //invertera färger
   $output .= "\033[35m"; //sätt färg för ifylld del
   $output .= "\033[1000C"; //gå max till höger
   $output .= "\033[".$size."D"; //gå till vänster

   for($i=0; $i<$size; $i++){
      if($i==$filled) $output .= "\033[37m"; //byt färg för ofylld
      if($i>=$infoStart&&$i<$infoStart+strlen($info)){
         $output .= substr($info,$i-$infoStart,1); //skriv ut info
      }else{
         $output .= " ";
      }
   }

   $output .= "\033[u"; //återställ pekarens position

   echo $output;
}

Om du vill testa funktionen men inte har något tidskrävande jobb att använda den till så kan du testa med följande rader:

for($i=0; $i<=1000; $i++){
        usleep(1500);
        printProgressbar($i/1000.0);
}


Så här ser den ut när den kör:



Hoppas du får någon nytta av detta. Jag har själv börjat lägga in progressbarer i alla jobb som tar mer än några sekunder. Ett litet problem är dock att om man loggar utskrifterna från ett jobb och sedan öppnar det i en texteditor (typ vim) så får man massor av ANSI-sekvenser som gör loggen helt oläsbar. Skriver man däremot ut loggen med cat, tail eller liknande så spelas progressbaren upp i repris.

För windows-användare

Sedan windows NT så används inte ANSI i DOS/kommandotolken. Men du kan aktivera det manuellt.

Öppna c:\windows\system32\config.nt
Lägg till följande rad längst ned i filen:
device=%SystemRoot%\system32\ansi.sys
Starta om datorn.

ANSI Art

Har du inga program som behöver progressbars eller andra nyttiga ändamål för denna kunskap så kan du alltid använda ANSI-sekvenser för att skapa konst.

måndag 9 maj 2011

Från latin1 till UTF-8 i PHP och MySql

När jag skapade databasen till Sovrat som senare skulle bli Pusha.se för ganska precis 5 år sedan hade jag inga större kunskaper om encoding. Latin1 (ISO-8859-1) var standard i min MySql-installation så latin1 fick det bli. För ett par veckor sedan tog jag tjuren vid hornen och konverterade allt till utf-8.

Tänkte skriva ned några av de lärdomar jag dragit av konverteringsarbetet. Mest för att jag själv ska komma ihåg det om jag behöver göra det fler gånger och även för att någon annan stackare i samma situation ska få det lite lättare.

Ändra encoding överallt
Det finns ganska många ställen man måste byta encoding på för att det ska få önskad effekt. Man ser inte heller om man gjort rätt förrän man bytt på alla dessa platser. Se till att följande använder utf-8 som encoding:
  • MySql-databasen
    ALTER DATABASE databasnamn CHARACTER SET utf8;
  • Varje databastabell
    ALTER TABLE tabell CHARACTER SET utf8 COLLATE utf8_general_ci ROW_FORMAT = DYNAMIC;
  • Varje kolumn i varje databas
    ALTER TABLE tabell MODIFY COLUMN kolumn VARCHAR(60) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL;
  • PHP-filerna med själva PHP-koden
  • setlocale i PHP
    setlocale(LC_ALL, 'sv_SE.UTF-8', 'sve');
  • Content-Type i HTTP-headern
    header('Content-Type: text/html; charset=UTF-8');
  • Content-Type i HTML-headern
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  • MySql-anslutningen
    mysql_set_charset('utf8',$link);

PHP inte byggt för UTF-8
Av historiska skäl är PHP:s stöd för UTF-8 inte det bästa. T.ex. fungerar nästan ingen av de vanliga strängfunktionerna som strlen(), substr() m.fl. Detta beror på att PHP jobbar med en teckenkodning där varje tecken består av 1 byte medan det i UTF-8 även finns tecken som tar 2 eller 3 byte.

Ett möjligt sätt att ta sig runt detta är att använda utf8_decode() och utf8_encode(). Om du t.ex. vill mäta längden på en sträng som är encodad med utf8 så kan du först decoda den innan du mäter.

$len = strlen(utf8_decode($utf8str));

Vill man klippa en utf8-sträng så decodar man först, klipper och sen encodar man igen.

$utf8str = utf8_encode(substr(utf8_decode($utf8str),0,10));

Ovanstående lösning blir dock ganska snabbt väldigt svårläst och ful och verkar dessutom inte fungera för riktigt konstiga tecken som kräver 3-byte. Vill man ha en snyggare lösning så får man istället använda PHP:s multibyte-funktioner. Dessvärre är mbstring-modulen inte installerad i PHP per default utan du måste själv installera den.

När du väl har mbstring aktiverat så heter alla strängfunktioner precis som tidigare men med mb_ före. T.ex. mb_strlen(), mb_substr(), mb_strtolower() o.s.v.

Vissa strängfunktioner finns tyvärr inte i mbstring men däremot tar dessa funktioner en extra parameter där man kan specificera en encoding. Exempel på sådana funktioner är t.ex. htmlentities(), htmlspecialchars() m.fl.

$text = htmlentities($text,ENT_COMPAT,'UTF-8');

Vissa reguljära uttryck kan förenklas lite när man använder UTF-8. Tidigare var jag tvungen att använda a-zA-Z\xe5\xe4\xf6\xc5\xc4\xd6 för att få med åäöÅÄÖ men efter övergången fungerade det istället bra med a-öA-Ö.

Övrigt
Jag har sett många rekommendationer att man ska köra följande två kommandon så fort anslutningen till MySql har skapats:

mysql_query("SET NAMES 'utf8'");
mysql_query("SET CHARACTER SET utf8");

Det har dock inte varit nödvändigt i mitt fall men det är något att testa om man har problem.

Om man vill slippa ändra till UTF-8 manuellt för varje kolumn i en tabell så ska det fungera att använda följande query istället:

ALTER TABLE tabellnamn CONVERT TO CHARACTER SET utf8;

Jag tyckte dock att det kändes tryggare att konvertera en kolumn i taget. Speciellt då det ibland uppstod konverteringsfel som gjorde att man manuellt var tvungen att fixa någon rad i databasen. När man har väldigt många rader så tar det ett tag att bara konvertera en enda kolumn.

I vissa fall kan det ha betydelse vad för collation man väljer för en kolumn i MySql. Det vanliga är utf8_general_ci men den har vissa brister som t.ex. innebär att åäö sorteras som aao. Vill man ha korrekt sortering kan man använda utf8_unicode_ci eller utf8_bin. Den senare jämför tecknen binärt vilket gör dina querys case sensetive.

Se för allt i världen till att ha backup på allt innan du påbörjar ett konverteringsarbete.

Lycka till!

fredag 4 februari 2011

Varning för NOT-operatorn i MySQL med index

På senare tid har jag ibland använt NOT-operatorn ! i MySQL. T.ex. för att hämta alla registreringar som ännu ej processats:

SELECT * FROM registrations WHERE !processed;

Fältet processed i det här fallet är av typen TINYINT(1) (BOOLEAN).

Idag upptäckte jag till min stora förvåning att om jag lägger ett index på processed så har det ingen som helst effekt om jag använder ! eller NOT för att hitta raderna.

mysql> DESCRIBE SELECT * FROM registrations WHERE !processed;
+------+---------------+------+---------+------+--------+-------------+
| type | possible_keys | key  | key_len | ref  | rows   | Extra       |
+------+---------------+------+---------+------+--------+-------------+
| ALL  | NULL          | NULL | NULL    | NULL | 578614 | Using where |
+------+---------------+------+---------+------+--------+-------------+

Om jag däremot gör en helt vanlig jämförelse med 0 eller FALSE (som egentligen borde vara samma sak) så funkar det bra:

mysql> DESCRIBE SELECT * FROM registrations WHERE processed=FALSE;
+------+----------------+----------------+---------+-------+------+-------+
| type | possible_keys  | key            | key_len | ref   | rows | Extra |
+------+----------------+----------------+---------+-------+------+-------+
| ref  | processedindex | processedindex | 1       | const |    1 |       |
+------+----------------+----------------+---------+-------+------+-------+

I den här tabellen med nästan 600 000 rader tog queryn med ! 0.60 sekunder medan den som använde indexet tog 0.00.

Så kom ihåg! Använd inte "!", "NOT", "IS FALSE" eller liknande utan gör istället jämförelser med =. Även om de logiskt ger samma resultat.

Om någon vet varför det är på detta sätt så får ni gärna skriva en kommentar. Har sökt lite men inte hittat någon information om detta.

Styr webbläsaren med din iPhones gyroskop

Mika Tuupola har gjort ett inspirerande experiment som blandar flera av de senaste och hetaste teknikerna. Han får en HTML5-logga som visas i webbläsaren på hans dator att rotera med hjälp av sin iPhones gyroskop.



Gyroskopet får han tillgång till med iPhones DeviceOrientation API. Kommunikationen mellan webbläsaren och iPhonen sker över en socketanslutning som skapats med WebSocket som är en del av HTML5. Rotationen av loggan görs med 3D Transformationer i CSS3 (endast webkit än så länge).

Testa själv:
Öppna denna länk i safari på din dator
Öppna denna länk i din iPhone med iOS 4.2 eller högre

Läs Mika Tuupola eget blogginlägg om detta.

onsdag 2 februari 2011

Radera aldrig data!

Flickr är en av några få webbtjänster som jag faktiskt betalar för. Jag tycker flickr är snyggt, enkelt att använda och framförallt har det känts tryggt att ha sina fotografier (som kanske är det värdefullaste man har) lagrade i molnet och inte på någon egen hårddisk som kan krascha när som helst. Idag slutade det dock kännas tryggt.

Flickr har råkat radera en betalande flickr-användares konto när de skulle radera någon helt annan som hade laddat upp copyright-skyddat material. Det är ungefär 4000 bilder som dessutom var flitigt inlänkade på andra sajter som har försvunnit. Flickr erbjöd den drabbade kunden 4 års gratis pro-medlemskap som ersättning. Mer om detta finns att läsa hos Techcrunch.

Några saker som man (framförallt flickr) kan lära sig av detta:

1. Det ska aldrig gå att radera information
En webbtjänst bör aldrig innehålla en möjlighet att på riktigt radera information. Inte i admin-gränssnitt, ingenstanns. Man kan ha ett system för att markera saker som raderade så att de döljs för användarna men att på riktigt ta bort informationen finns det absolut ingen anledning till, speciellt inte när lagringsutrymme idag i princip är gratis.

Jag brukar inte ens ge mina mysql-användare rättigheter att köra DELETE-kommandot.

2. Ta backup
Att ta backup på all data åtminstone en gång per dygn borde vara en självklarhet. Speciellt om man har flera miljoner användare.

3. Ge en rimlig kompensation
Om du klantar till det, visa att du tar det på allvar. Ge en kompensation som svider. När flickr erbjuder 4 års pro-medlemskap så förstår alla att det inte kostar dom ett öre. De kan med andra ord klanta till det hur många gånger som helst. De borde istället visa att det här var ett riktigt katastrofalt misstag, händer det igen förtjänar vi inte att få finnas kvar. Jag tycker inte en kompensation på $100 000 hade varit för mycket i det här fallet.

Till sist tycker jag att det är märkligt av flickr att överhuvudtaget stänga av konton för att de innehåller copyright-skyddat material. De borde kanske dölja de aktuella bilderna och varna medlemmen några gånger först innan de bestämmer sig för att radera alla dess bilder för all framtid.

UPPDATERING: Flickr lyckades tillslut återställa personens bilder, så någon backup hade de trots allt. 25 års pro-medlemskap fick han också vilket känns som en rimlig kompensation när de faktiskt fick tillbaka bilderna.

tisdag 10 augusti 2010

Unspecified Error vid användning av pasteHtml i Internet Explorer

Eftersom Internet Explorer saknar stöd för execCommand med parametern "insertHtml" så får man använda sig av pasteHtml istället.

var html = "test";
if (document.selection && document.selection.createRange) {
   var range = document.selection.createRange();
   if (range.pasteHTML) {
      range.pasteHTML(html);
   }
}else{
   document.execCommand("insertHtml", false, html);    
}

Första gången jag använde metoden ovan så fungerade det perfekt. Men idag när jag skulle göra samma sak så fick jag ett "Unspecified error" i Internet Explorer. Inte helt oväntat så är det lite svårt att felsöka ett "Unspecified error". Jag har ägnat halva dagen åt att googla problemet utan resultat. Till slut kom jag fram till att problemet berodde på att man måste ge det aktuella fönstret fokus. I detta fall så gällde det en iframe där jag ville klistra in kod så där såg lösningen ut såhär:

document.getElementById("iframeId").contentWindow.focus();

Förhoppningsvis hittar ni denna lösning i google nu :)