Progblemet #1

Och för att visa tanken lite så kommer här en lösning på samma problem i C

#include <stdio.h>

/* Detta är funktionen som beräknar nästa värde i serien, 
   (n & 1) blir 0 om talet är jämt och 1 om det är udda */
inline unsigned nxt(unsigned n)
{
    if (n & 1)
        return 3 * n + 1;
    return n / 2;
}

/* Beräknar längden på serien som produceras av talet 'n'. 
   Funktionen är rekursiv och villkoret för
   för att vara klar är att man nått talet 1 */
unsigned seq_len(unsigned n, unsigned len)
{
    if (n == 1)
        return len;
    return seq_len(nxt(n), len + 1);
}

/* Beräknar längden på den längsta serie från 1 till 'limit'. Funktionen ger
   längden som resultat och sparar värdet som gav den längden på platsen
   som 'max_n' pekar på */
unsigned longest_seq(unsigned limit, unsigned *max_n)
{
    unsigned n;
    unsigned maxlen = 0;

    for (n = 1; n <= limit; n++) {
        unsigned l = seq_len(n, 1);
        if (l > maxlen) {
            maxlen = l;
            *max_n = n;
        }
    }
    return maxlen;
}

int main(int argc, char *argv[])
{
    unsigned limit = 1000000;
    unsigned len;
    unsigned n;

    len = longest_seq(limit, &n);
    printf("Longest sequence is %u elements when N = %u\n", len, n);
}

Körtid: 0.2s / Core i7 2600 / 64-bitars Ubuntu 12.04

Här har jag löst problemet med att ge två returvärden i longest_seq med att ge längden som en "vanligt" returvärde och ge värdet som producerar den sekvens genom att ta adressen till den variabel där jag ska spara resultatet.

Även här används rekursion i seq_len och rekursionen är s.k. svansrekursion som alla vettiga kompilatorer kommer skriva om till en vanlig loop så man kommer inte spränga stacken.

Är det någon annan som har lust att visa upp lösningar i andra språk?

Ok, så låt oss köra med lösningarna inuti SPOLER-taggen.

Det ska inte finnas några regler för HUR saker ska vara implementerat, men om ni gjort en lösning i säg C# som är inspirerad av en lösning i ett annat språk, skriv då det så personer som vill jämföra hur ungefär samma sak ser i dessa två språk vet detta.

Min C och min Clojure version ovan hade ju nästan identisk logik, man skulle kunna skriva om longest_seq så den blir rekursiv och då är det verkligen samma program skrivet i två olika språk.

Vissa kanske känner till editorn Emacs, roade mig att skriva om C lösningen i Emacs interna scriptspråk, elisp

(defun nxt (n)
  "Returns the number following n in the sequence"
  (if (oddp n)
      (1+ (* 3 n))
    (/ n 2)))

(defun seq-len (initial-n)
  "Returns the sequence length produce by the initial value n"
  (let ((len 1)
        (n initial-n))
    (while (> n 1)
      (setq len (1+ len)
            n (nxt n)))
    len))

(defun longest-seq (limit)
  "Returns a alist ((:len . L) (:n . N)) where L is the length of the longest                                                                                                                                                               
   sequence and N is the initial value"
  (let ((n limit)
        (max-n 0)
        (max-len 0))
    (while (not (zerop n))
      (let ((len (seq-len n)))
        (if (> len max-len)
            (setq max-n n
                  max-len len))
        (setq n (1- n))))
    (list (cons :len max-len) (cons :n max-n))))

(insert (format "\nAnsver: %s" (longest-seq 1000000)))

Körtid: 52s / Core i7 2600 / 64-bitars Ubuntu 12.04

Som ni ser så påminner elisp och Clojure en hel del om varandra, vilket inte är så konstigt då båda är dialekter av Lisp. Lite uppenbara sker som skiljer sig är att functionen "inc" heter "1+" i elisp, funktionen definieras med "defn" i Clojure och "defun" i elisp. Funktioner som testat om argumentet uppfyller ett krav eller ej (eng. Functional predicate ) slutar med "?" i Clojure, odd?, medan de slutar på "p" i elisp oddp. Detta är endast en konvension och i de flesta "vanliga" språk som C, C#, Java etc så skulle man typiskt kallat funktionen för is_odd.

Det är lite krångligare att hantera s.k. associativa listor i Emacs
I Clojure så kan man göra en C#/Java/C++ "map" på detta sätt
{:key1 value1 :key2 value2}

och vill jag läsa ut värdet motsvarande :key2 så gör man bara
({:key1 value1 :key2 value2} :key2) -> value2

Motsvarande sak i Emacs går via något som kallas "alists" och en "alist" är en vanlig länkad lista där elementen är par av nyckel/värde. Så ovan blir
'((:key1 . value1) (:key2 . value2))

notera att det är en punkt mellan nyckel och värde. för att läsa ut ett värde använder man funktionen "assoc-default",
(assoc-default :key2 '((:key1 . value1) (:key2 . value2))) -> value2

Och vill ni köra detta program i Emacs, så skriv ner det i en fil, läs in filen och kör Emacs kommandot "eval-buffer" (M-x eval-buffer).

Edit: måste nog designa om Emacs programmet en del. Emacs fixar inte svansrekursion så ibland smäller alltihop för anropsdjupet blir för stor... Jaja, dax att lura ut hur man gör en iterativ lösning i Elisp. Elisp är inte precis något jag sitter och hackar dagligen

Edit2: Har skrivit om elisp versionen så den är iterativ så den korrekt kan hantera stora tal. Så här lärde även jag mig något nytt, rekursion och elisp är en dålig kombination. Men notera hur Lisp och iterativa lösningar inte riktigt gillar varandra, Clojure versionen är enklare en elisp versionen.

En Clojure variant av VirtualIntent #6 första Python implementation

(defn nxt [n]
  (if (odd? n) (inc (* 3 n)) (quot n 2)))

(defn seq-len [n len]
  (if (<= n 1) len (recur (nxt n) (inc len))))

(println (reduce (fn [R r] (if (> (r :len) (R :len)) r R))
                 (map (fn [n] {:len (seq-len n 1) :n n}) (range 1000000))))

Körtid: 5.6s / Core i7 2600 / 64-bits Ubuntu 12.04

Hmm, gör ett undantag i detta fall då det är så pass enkelt med Python. Men var därför jag förslog att man bara skriver vilket OS och CPU man kört på, då får folk ändå ett fingervisning om hastigheten och jag slipper köra allas lösningar, .Net finns ju inte ens på Linux även om alla C# exempel säkert kommer fungera i Mono

Första versionen
Körtid: 34.9s / Core i7 2600 / 64-bitars Ubuntu 12.04

Andra versionen
Körtid: 2.4s / Core i7 2600 / 64-bitars Ubuntu 12.04

Här kommer en version av programmet i Erlang. Erlang skiljer sig ganska mycket från programspråk som C# och Java då det saknar stöd för loopar och liknande, man får i stället använda sig av s.k. pattern-matching och rekursion. Fördelarna med Erlang är att det är lätt att skriva program som använder många CPU-kärnor och framförallt är det lätt att skriva program som hanterar extrema mängder samtida session.

Erlang används bl.a. av Ericsson i de system som håller reda på mobilsamtal. Facebook använder Erlang till sin chat-funktion som håller reda på över 100 miljoner samtida användare (försök göra det i Java/C#...).

Just denna uppgift vi tittar på här är inget som visar upp styrkorna i Erlang då programmet inte använder sig av mer än en Erlang "process".

Version med ganska mycket kommenterar då jag gissar att få någonsin sett Erlang tidigare.

% namnet på modulen, bör matcha namnet på filen och om man använder
% funktioner i denna modul från andra moduler så refererar man till
% funktionerna som 'erl:longest_seq(123)'
-module(erl).

% Lista på vilka funktioner som ska vara synliga utanför denna
% modul. /1 på slutet talar om att funktionen i fråga tar 1 argument    
% vilket är sant för både longest_seq som tar en integer och main som
% tar en lista av strängar (argumenten till programmet).
-export([longest_seq/1,main/1]).

% Man kan sätta restriktioner på argument i Erlang och dessa läses
% uppifrån och ner, första som blir sant används. Så vi kör 'N div 2'
% om 'N band 1 == 0' (band -> bitwise and) är sant.
nxt(N) when N band 1 == 0 -> N div 2;
nxt(N) -> 3 * N + 1.

% Erlang har också något som kallas 'pattern matching' på argument och
% även dessa testas uppifrån och ner. I detta fall körs första         
% varianten av funktionen om första argumentet är '1'.
seq_len(1, Len) ->
    Len;
seq_len(N, Len) ->
    seq_len(nxt(N), Len + 1).

% Denna kommer väljas om man anropar 'seq_len' med endast ett
% argument.
seq_len(N) ->
   seq_len(N, 1).

% Detta är en funktion som 'lists:foldr' kommer anrop för varje värde
% mellan 1 till Limit. Returvärde från denna är längden på den längsta
% serie. Firsta funktionen används om 'Len < MaxLen' är sant, annars
% väljer man den andra.
select_longest_seq({Len,_}, {MaxLen,MaxN}) when Len < MaxLen ->
    {MaxLen,MaxN};
select_longest_seq(T, _) ->
    T.

% Räknar ut längsta sekvensen från 1 till Limit och svarar med en
% tupel på formen {MaxLen,N}. Detta görs genom att generera en lista
% med 'lists:seq' från 1 till Limit, starta med tupel {0,0} och sedan
% skicka varje {Len, N} tupel till funktionen man har som första
% argument. Erlang kräver att man har 'fun' som prefix och att man
% specificerar funktionens rank (antal argument) eftersom det är
% tillåtet att skriva flera funktioner med samma namn men olika antal
% argument, se 'seq_len' ovan t.ex.                      
longest_seq(Limit) ->
    lists:foldr(fun select_longest_seq/2, {0,0}, [{seq_len(N), N} || N <- lists:seq(1, Limit)]).

main([Arg]) ->
    io:fwrite("~p~n", [longest_seq(1000000)]),
    halt(0).

och en version utan kommentarer så man får en känslas för hur kompakt koden är. Notera att jag inte alls försökt skriva den kortast möjliga versionen, utan skriva en version där varje del är trivial

-module(erl).
-export([longest_seq/1,main/1]).

nxt(N) when N band 1 == 0 -> N div 2;
nxt(N) -> 3 * N + 1.

seq_len(1, Len) ->
    Len;
seq_len(N, Len) ->
    seq_len(nxt(N), Len + 1).

seq_len(N) ->
   seq_len(N, 1).

select_longest_seq({Len,_}, {MaxLen,MaxN}) when Len < MaxLen ->
    {MaxLen,MaxN};
select_longest_seq(T, _) ->
    T.

longest_seq(Limit) ->
    lists:foldr(fun select_longest_seq/2, {0,0}, [{seq_len(N), N} || N <- lists:seq(1, Limit)]).

main([Arg]) ->
    io:fwrite("~p~n", [longest_seq(1000000)]),
    halt(0).

Runtime: 4.9s / Core i7 2600 / 64-bit Ubuntu 12.04

Notera att effektivitet inte alls är i nivå med C, men heltalsaritmetik är inte Erlangs styrka utan stryka är väldigt fin skalbarhet på program som utföra massivt med I/O.

Detta är ett exempel på pattern matching

seq_len(1, Len) ->
    Len;
seq_len(N, Len) ->
    seq_len(nxt(N), Len + 1).

första versionen körs om första argumentet är exakt 1 och funktionen ger då resultatet motsvarande värdet på "Len". Annars körs den andra versionen. Endast EN av en serie av funktioner med samma namn körs vid varje anrop. Notera att ";" avslutar den första och "." avslutar en grupp matchingar för samma funktionsnamn.

Scala är ett språk som körs ovanpå en Java virtuell maskin och Scala-kod kan utan problem använda metoder och klasser som är skrivna i Java. Scala är ett VÄLDIGT stort språk med väldigt många finesser, fler än både C++ och C# som även de har väldigt stora och komplexa språk (om man verkligen vill lära sig HELA språket).

Trots att Scala har så mycket finesser i språket så brukar program skrivna i Scala vara ungefär lika effektiva som motsvarande program skrivet i Java, d.v.s programmen körs relativt snabbt, är nog bara språk som C, C++, Go och Fortran som i genomsnitt genererar snabbare program

Samma sak här som ovan, första versionen med kommentarer den andra utan.

object Main extends App {
    // Ger nästa tal i sekvensen
    def nxt(n: Long): Long =
                if ((n & 1) == 0) n / 2 else 3 * n + 1

    // Beräknar längden på sekvensen som tal n genererar. Scala kommer
    // skriva om svansrekursiva funktioner som en vanlig iteration så 
    // denna funktion kan inte "spränga" stacken. 
    def seqLen(n: Long, len: Int): Int =
                if (n <= 1) len else seqLen(nxt(n), len + 1)
    def seqLen(n: Long): Int =
                seqLen(n, 1)

    // Genererar en lista av Int från 1 till limit. Kör sedan en
    // funktion på varje element i den listan som producerar en ny
    // lista men en tupel (längd, tal), detta görs av 'map'. Denna
    // reduceras sedan till att endast vara (längd, tal) för det          
    // element som har största värdet på längd, vilket är vad som ges
    // som returvärde
    def longestSeq(limit: Int): (Int, Int) =
                (1 to limit).map(n => (seqLen(n), n)).reduceLeft((a, b) => if (a._1 > b._1) a else b)

    // Eftersom mitt objekt utökar 'App' så kommer allt jag lägger 
    // direkt under definitionen av objektet att köras vid start
    Console.println(longestSeq(1000000))
}

och utan kommentarer

object Main extends App {
    def nxt(n: Long): Long =
		if ((n & 1) == 0) n / 2 else 3 * n + 1

    def seqLen(n: Long, len: Int): Int =
		if (n <= 1) len else seqLen(nxt(n), len + 1)
    def seqLen(n: Long): Int =
		seqLen(n, 1)

    def longestSeq(limit: Int): (Int, Int) =
		(1 to limit).map(n => (seqLen(n), n)).reduceLeft((a, b) => if (a._1 > b._1) a else b)

    Console.println(longestSeq(1000000))
}

Körtid: 0.74s / Core i7 2600 / 64-bitars Ubuntu 12.04

Väldig kompakt, men personligen tycker jag Scala kod kan vara lite väl kompakt. Implementationen av "longestSeq" tar en stund att bena ut men är däremot väldigt enkel att skriva. Då kod normalt sett läses långt fler gånger än den skrives så är det HELT FEL att optimera för att det ska gå fort att skriva.

Scala är lite som C++ i det att man har så många finesser till sitt förfogande att det är lätt att börja använda onödigt avancerade konstruktioner bara därför att det går och att det sparade två rader, men resultatet blir något som andra har svårt att förstå.

Men rätt använt är Scala ett väldigt trevligt och kraftfullt språk!

Detta är ett väldigt nytt språk, 1.0 presenterades så sent som i våras. Tanken bakom detta språk är att skapa ett "modernt C". Skrapar man lite på ytan så ser man att Go delar många egenskaper med Erlang i det att båda språket gör det lätt att skapa program som hanterar MASSOR med samtida sessioner. Då Google står som huvudsponsor för Go så är detta fokus kanske inte så förvånande. Go är dock ett helt öppet språk som Google inte kontrollerar eller "äger".

Har inte använt Go speciellt länge, men detta språk är nog min nya favorit. Einstein sade att man ska förenkla saker så långt det bara går, men inte längre och Go är designat med just denna filosofi. Man har inte funderat: vad kan vi lägga dit (som i C++, C# och Scala) utan i stället: vad är det minimala som måste finnas för att språken ändå ska vara lätt att använda.

Go har inte objekt, ändå stödjer det alla konstruktioner som OO-språk har. Go har inte destruktorer (som C++), men stödjer ändå RAII , Go har inte exception (som om man tänker till lite är "goto" på steroider och lider av många problem som "goto" lider av). Det är väldigt lätt att använda bibliotek skrivna i C från Go, men till skillnad från C så har Go automatisk minneshantering precis som Java/C# m.fl.

Version med kommentarer

package main

import "fmt"

// 'Måsvingar' är ett krav i Go. Anledningen är att man konstaterat    
// att väldigt många buggar i C/C++/C#/Java kommer just av missade     
// måsvingar, ofta kombinerad med felaktig indentering så det ser ut   
// som om det är rätt. Även placeringen av måsvingarna är ett krav,    
// något många verkar ha problem med, men när man jobbar på stora      
// kodbaser så är det av stort värde att saker ser ungefär lika ut så  
// tyker själv det är bra, trots att jag normal inte placerar          
// måsvingar på det sätt som Go kräver.                                
func nxt(n uint) uint {
    if n & 1 == 0 {
        return n / 2;
    }
    return 3 * n + 1;
}

// Go tillåter att man namnger returvärdet i                           
// funktionsdeklarationen. Ett 'return' utan argument avslutar         
// funktionen genom att använda värdet på den variabel man skrev som   
// returvärde i funktionshuvudet.                                      
func seq_len(initial_n uint) (l uint) {
    l = 1
    for n := initial_n; n > 1; n = nxt(n) {
        l++
    }
    return
}

// Funktioner i Go kan ha flera returvärden. Väldigt många             
// standardfunktioner i Go använder detta för att skicka data + felkod
// vilket gör att undantag (exceptions) varken stöds eller behövs.     
func longest_seq(limit uint) (max_len, max_n uint) {
    max_len = 0
    for n := uint(1); n <= limit; n++ {
        l := seq_len(n)
        if l > max_len {
            max_len = l
            max_n = n
        }
    }
    return
}

func main() {
    fmt.Println(longest_seq(1000000))
}

version utan kommentarer

package main
import "fmt"

func nxt(n uint) uint {
	if n & 1 == 0 {
		return n / 2;
	}
	return 3 * n + 1;
}

func seq_len(initial_n uint) (l uint) {
	l = 1
	for n := initial_n; n > 1; n = nxt(n) {
		l++
	}
	return
}

func longest_seq(limit uint) (max_len, max_n uint) {
	max_len = 0
	for n := uint(1); n <= limit; n++ {
		l := seq_len(n)
		if l > max_len {
			max_len = l
			max_n = n
		}
	}
	return
}

func main() {
	fmt.Println(longest_seq(1000000))
}

Körtid: 0.40s / Core i7 2600 / 64-bitars Ubuntu 12.04

Som ni ser är det bara C som är mer effektivt än Go och målet är att Go i slutändan ska vara inom några procent av prestandan i C, få se hur det går med det målet.

Knappast den kortaste versionen, men personligen tycker jag Go och Python (som är ett av de språk som man använt som influens) är bland de språk som är lättast att läsa vad andra har skrivit, i alla fall Python-kod där folk låter bli de lite mer avancerade konstruktionerna (något som Go också helt saknar).

Sorry att jag "stal" Scala. Har som mål att lära mig grunderna i ett nytt språk varje år och kört det ganska länge, så kan lösa den här typen av problem i väldigt många språk. Men kommer undvika att själv göra lösningar i de språk jag märker att det kommer in lösningar till ändå i framtida progblemet. Kommer fokusera på lösningar i C och "udda" språk som Erlang och Go.

Fin optimering du fick till där, nu var inte riktigt meningen att det skulle bli ett "benchmark race", men hey detta är SWEC och jag känner att min världsbild om att inget (förutom C++ om man skriver C kod) kan komma nära C krackelerar lite. Så här är en version som använder alla trådar på min Core i7 för att beräkna detta (precis som du gör med ".par").

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef uint64_t num_t;

inline num_t nxt(num_t n)
{
    if (n & 1)
        return 3 * n + 1;
    return n / 2;
}

unsigned seq_len(num_t n, unsigned len)
{
    if (n == 1)
        return len;
    return seq_len(nxt(n), len + 1);
}

unsigned longest_seq(num_t limit, num_t *max_n)
{
    unsigned maxlen = 0;

#pragma omp parallel
    {
        num_t    private_maxn = 0;
        unsigned private_maxlen = 0;
        num_t    n;

#pragma omp for
        for (n = 1; n <= limit; n++) {
            unsigned l = seq_len(n, 1);
            if (l > private_maxlen) {
                private_maxlen = l;
                private_maxn = n;
            }
        }
#pragma omp critical
        if (maxlen < private_maxlen)
        {
            maxlen = private_maxlen;
            *max_n = private_maxn;
        }
    }
    return maxlen;
}

int main(int argc, char *argv[])
{
    num_t    limit = atoi(argv[1]);
    num_t    n;
    unsigned len;

    len = longest_seq(limit, &n);
    printf("Longest sequence is %u elements when N = %u\n", len, (unsigned)n);
    return EXIT_SUCCESS;
}

Körtid: 0.04s / Core i7 2600 / Ubuntu 12.04

Att hitta lösningen upp till för tal upp till 100 miljoner (Longest sequence is 950 elements when N = 63728127) har
Körtid: 4.9s / Core i7 2600 / Ubuntu 12.04

För att förklara var "#pragma omp" saker gör. Dessa är OpenMP extensioner. "#pragma omp parallel" kommer göra så att blocket som följer körs på alla CPU-trådar som finns. "#pragma omp for" säger, dela upp denna for-loop på alla tillgängliga trådar. För att undvika lås i den kritiska pathen så beräknar jag en dellösning på varje tråd som jag sparar "private_xxx" variablerna.

När jag kommer till raden som säger "#pragma omp critical" så har NÅGON tråd rätt svar (finns en kopia av "private_xxx" per tråd) och programmet kliver då in en ett block som trådarna kör en och en, den "kritiska" delen. Kanske inte så dumt att visa detta ändå så folk få ser hur ett så här pass enkelt problem ändå blir ganska komplicerat så fort man blandar in flera trådar.

En naiv variant att göra detta multi-trådat hade varit att köra "for" loopen parallellt och skydda uppdateringen av "maxlen" med en kritisk region. En sådan lösning blir LÅNGSAMMARE än att köra saker på en tråd, ganska mycket långsammare.

Men detta kanske är lite överkurs