Mal wieder Zeit

So, jetzt finde ich langsam wieder ein bisschen Zeit mich um mein Blog zu kümmern. Das nutze ich gleich mal um ein Stück Code zu posten, was mich schon länger fasziniert.

Es ist eigentlich nur kurz, aber ich fordere jeden heraus selbst herauszufinden, was es tut, ohne es vorher zu kompilieren.

#include <stdio.h>

struct values {
int a;
char b;
short c;
double d;
int* e;
};

int main() {
int i = 0;
struct values val;
val.a = 1819043144;
val.b = 111;
val.c = 8236;
val.d = 17772928018443055750142378752
9445406531473442920180139133343049801
2916652608327063483957532130480119417
0146354883598704890228200485135295197
79571104209539432448.000000;
val.e = &i;

char* pointer = (char *) &val;
printf("%s\n", pointer);
return 0;
}

Die Programmiersprache ist (offensichtlich) C. Die Zahl hinter 'val.d' muss selbstverständlich auf eine Zeile - die hab ich nur der besseren Lesbarkeit halber umgebrochen.

Wer rausgefunden hat was dieses Programm macht und seine Hypothese überprüfen will: übersetzen lässt es sich einfach mit

gcc -Wall $DATEINAME


Man beachte, dass - trotz "Warn-Parameter" '-Wall' keine Warnungen ausgestoßen werden. Man kann mit C und Pointern halt wunderbar kryptische Sachen schreiben :)

Algorithmen - Teil 1: Quicksort

Neulich hab ich versucht, den Unterschied zwischen funktionalen und imperativen Programmiersprachen zu erklären und dabei festgestellt, dass man das am besten anhand von Beispielcode machen kann. Darum habe ich angefangen Quicksort in drei Programmiersprachen (C, Python, Haskell) zu implementieren. Da Perl und Ruby populäre Sprachen sind, die mich schon länger interessieren, sind die heute auch gleich dazugekommen - eine willkommene Gelegenheit für mich, diese beiden Sprachen näher kennenzulernen und gleichzeitig die Unterschiede und Gemeinsamkeiten der einzelnen Sprachen aufzuzeigen.

Bevor's losgeht noch ein paar kurze Bemerkungen:
Die Aufgabe ist mit Hilfe von Quicksort ein Integer-Array aufsteigend zu sortieren. Dabei habe ich nur in C eine In-Place Sortierung implementiert.
Als Pivot-Element wird das erste Element gewählt und mit 'p' bezeichnet. 'a' bezeichnet das Array und 'l' und 'r' stehen für den "linken" (kleineren) sowie den "rechten" (größeren) Teil des Arrays.
Die gezählten verwendeten Codezeilen beziehen sich nur auf die Funktion selber - zusätzliche Zeilen, die zur Ausführung benötigt werden (main()-Funktion, etc.) werden nicht gezählt.
Also, los gehts:

C

• LOC: 16
• Bemerkungen: In-Place Sortierung, längste Implementierung

#include <stdio.h>
void qsort(int a[], int len) {
    if (len == 0) return;
    int p = a[0];
    int l = 0;
    int r = len-1;
    while (l < r) {
        if (a[l] > a[r]) {
            int tmp = a[l];
            a[l] = a[r];
            a[r] = tmp;
        }
        (a[l] == p) ? r-- : l++;
    }
    qsort(a, l);
    qsort(&a[l+1], len-l-1);
}

int main(int argc, char** argv) {
    int i = 0;
    int test[10] = {6, 4, 9, 1, 2, 5, 3, 8, 7, 0};
    qsort(test, 10);
    printf("[");
    for (i = 0; i < 9; i++) {
        printf("%d, ", test[i]);
    }
    printf("%d]\n", test[9]);
}

Python

• LOC: 9
• Bemerkungen: Verständlicher Ternary-Operator

def qsort(a):
    if (a == []):
        return []
    p = a.pop()
    l = []
    r = []
    for e in a:
        l.append(e) if (e < p) else r.append(e)
    return qsort(l) + [p] + qsort(r)

Haskell

• LOC: 3
• Bemerkungen: Kürzeste Implementierung

qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (p:xs) = qsort([l | l <- xs, l < p]) \\
  ++ [p] ++ qsort([r | r <- xs, r > p])

(letzte Zeile zur Lesbarkeit umgebrochen)

Perl

• LOC: 11
• Bemerkungen: Abgefahrenste Syntax

#!/usr/bin/env perl
sub qsort {
    my @l = ();
    my @r = ();
    my @a = @_;
    return () if (@a == 0);
    my $p = shift @a;
    foreach (@a) {
        ($_ < $p) ? (@l[++$#l] = $_) : (@r[++$#r] = $_);
    }
    return (qsort(@l), $p, qsort(@r));
}

print qsort(1, 4, 3, 5, 2, 9, 8, 0, 6, 7);
print "\n"

Ruby

• LOC: 13
• Bemerkungen: Python nicht unähnlich

#!/usr/bin/env ruby
def qsort(a)
    if !a.empty?
        p = a.shift
        l = Array.new
        r = Array.new
        a.each do |e|
            e < p ? l.push(e) : r.push(e)
        end
        (qsort(l) << p) + qsort(r)
    else
        Array.new
    end
end

puts qsort([4, 1, 6, 3, 8, 7, 2, 5, 9, 0])

Die Python- und Haskell-Module habe ich im jeweiligen Interpreter (Hugs bzw. die Python-Konsole) geladen.
Bemerkenswert: C hat die längste Implementierung, ist aber dafür In-Place. Haskell schießt dafür am entgegengesetzten Ende den Vogel ab, mit nur drei Zeilen (von denen die erste noch nicht einmal dringend nötig ist). Und das Perl-Statement

($_ < $p) ? (@l[++$#l] = $_) : (@r[++$#r] = $_);

finde ich dermaßen abgefahren, dass ich mir überlege das auszudrucken und an die Wand zu hängen. Ich habe selten dermaßen viele Sonderzeichen in einer Codezeile gesehen!
Wenn ich Zeit habe, werd ich auch noch Java-Code schreiben. Ansonsten überleg ich mir, was der nächste Algorithmus wird. Dijkstra vielleicht...

Avahi-patch for bash_completion

I wrote a small patch to allow the programmable bash-completion to complete hosts found via Avahi for commands like ping, ssh, scp, etc.

Reactiontime suffers somewhat - but that seems to be the fault of avahi-browse, which takes a while to return all recognized hosts.

Requirements: avahi-daemon has to be running and avahi-browse has to be available via $PATH. And of course, the programmable bash-completion by Ian MacDonald has to be installed :)

Patch follows in clear text. Usage:
(as user root)
cd /etc/
patch < /pfad/zu/avahi-hosts.patch

That should do it. Please tell me if there are any problems :)

----8< Cut and save as avahi-hosts.patch >8----

--- bash_completion 2006-03-01 17:20:18.000000000 +0100
+++ bash_completion_patched 2007-08-26 17:24:12.000000000 +0200
@@ -2410,7 +2410,7 @@
_known_hosts()
{
local cur curd ocur user suffix aliases global_kh user_kh hosts i host
- local -a kh khd config
+ local -a kh khd config avahi_hosts avahi_available avahi_browse

COMPREPLY=()
cur=${COMP_WORDS[COMP_CWORD]}
@@ -2522,6 +2522,24 @@
COMPREPLY=( $( compgen -A hostname -S "$suffix" -- $cur ) )
fi

+ # append recognized avahi hosts
+ # Check, whether avahi is running and avahi-browse is available
+ avahi_available=`pidof avahi-daemon`
+ avahi_browse=`which avahi-browse`
+ if [[ -n "$avahi_available" && -n "$avahi_browse" ]]; then
+ avahi_hosts=`avahi-browse -t _workstation._tcp -r | grep hostname | sed -e 's/.*\[//' | sed -e 's/\].*//'`
+ # convert to lower case to get unique hostnames
+ cur=`echo "$cur" | tr [:upper:] [:lower:]`
+ avahi_hosts=`echo "$avahi_hosts" | tr [:upper:] [:lower:]`
+ # Filter relevant results
+ avahi_hosts=`echo "$avahi_hosts" | grep $cur`
+ COMPREPLY=( ${COMPREPLY[@]} $avahi_hosts )
+ fi
+ # apply suffix
+ for (( i=0; i < ${#COMPREPLY[@]}; i++ )); do
+ COMPREPLY[i]=$user${COMPREPLY[i]}$suffix
+ done
+
return 0
}
complete -F _known_hosts traceroute traceroute6 tracepath tracepath6 \

----8< Cut and save as avahi-hosts.patch >8----

Have fun :)

Avahi-Patch für bash_completion

(This post is also available in english)

Hab einen kleinen Patch geschrieben, um der programmierbaren Bash-Vervollständigung beizubringen, bei Kommandos wie ping, ssh, scp, etc. auf Hosts zu vervollständigen, die via Avahi gefunden wurden.

Die Reaktionszeit steigt dabei ein wenig - das liegt aber an avahi-browse, welches sich ein bisschen Zeit läßt mit der Angabe der gefundenen Hosts.

Voraussetzungen: avahi-daemon muss laufen und avahi-browse muss via $PATH verfügbar sein. Und die programmierbare Bash-Vervollständigung von Ian MacDonald muss natürlich installiert sein :)

Patch folgt im Klartext. Benutzung:
(als Benutzer root)
cd /etc/
patch < /pfad/zu/avahi-hosts.patch

Das sollte es tun. Bei Problemen bitte melden :)

----8< Ausschneiden und als avahi-hosts.patch speichern >8----

--- bash_completion 2006-03-01 17:20:18.000000000 +0100
+++ bash_completion_patched 2007-08-26 17:24:12.000000000 +0200
@@ -2410,7 +2410,7 @@
_known_hosts()
{
local cur curd ocur user suffix aliases global_kh user_kh hosts i host
- local -a kh khd config
+ local -a kh khd config avahi_hosts avahi_available avahi_browse

COMPREPLY=()
cur=${COMP_WORDS[COMP_CWORD]}
@@ -2522,6 +2522,24 @@
COMPREPLY=( $( compgen -A hostname -S "$suffix" -- $cur ) )
fi

+ # append recognized avahi hosts
+ # Check, whether avahi is running and avahi-browse is available
+ avahi_available=`pidof avahi-daemon`
+ avahi_browse=`which avahi-browse`
+ if [[ -n "$avahi_available" && -n "$avahi_browse" ]]; then
+ avahi_hosts=`avahi-browse -t _workstation._tcp -r | grep hostname | sed -e 's/.*\[//' | sed -e 's/\].*//'`
+ # convert to lower case to get unique hostnames
+ cur=`echo "$cur" | tr [:upper:] [:lower:]`
+ avahi_hosts=`echo "$avahi_hosts" | tr [:upper:] [:lower:]`
+ # Filter relevant results
+ avahi_hosts=`echo "$avahi_hosts" | grep $cur`
+ COMPREPLY=( ${COMPREPLY[@]} $avahi_hosts )
+ fi
+ # apply suffix
+ for (( i=0; i < ${#COMPREPLY[@]}; i++ )); do
+ COMPREPLY[i]=$user${COMPREPLY[i]}$suffix
+ done
+
return 0
}
complete -F _known_hosts traceroute traceroute6 tracepath tracepath6 \

----8< Ausschneiden und als avahi-hosts.patch speichern >8----

Viel Spass :)