Progblemet #8 - Bruteforce - Programmering och digitalt skapande

2013-03-19 23:23

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Emacs lisp

Detta problem går att lösa relativt enkelt i det språk som används för att skriva macros och liknande i Emacs, inte alls lika snabbt som C eller Java men går ändå att köra "abcdefg" med max längd satt till 7 på runt 5s.

(defun flatten (list-of-lists)
  (apply #'append list-of-lists))

(defun mult(char-set n &optional prefix)
  (if (zerop n)
      nil
    (flatten
     (mapcar
      (lambda (c)
        (let ((new-string (concat prefix (string c))))
          (cons new-string (mult char-set (1- n) new-string ))))
      char-set))))

(mult "abc" 3)

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Rapportera Redigera

Citera flera Citera

2013-03-19 23:28

Permalänk

anon81912

Inaktiv

Registrerad: Feb 2006

●

Den skarpsynte kan observera att om man tar bort "plussen" ur javakoden så att man slipper bygga strängar så kommer programmet att exekvera MYCKET MYCKET snabbare, säkert på en tusendel av tiden.

Detta beror på att det tar väldigt lång tid att bygga strängar i java, då de skapas och läggs i en pool, som eventuellt kollas igenom. Använd istället StringBuilder eller System.out.print() för att kunna konkatenera snabbare :).

Gör man så så borde lösningen ta ungefär lika lång tid som varianten i C

Rapportera Redigera

Citera flera Citera

2013-03-20 10:18

Permalänk

Yoshman

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Skrivet av anon81912:

Den skarpsynte kan observera att om man tar bort "plussen" ur javakoden så att man slipper bygga strängar så kommer programmet att exekvera MYCKET MYCKET snabbare, säkert på en tusendel av tiden.

Detta beror på att det tar väldigt lång tid att bygga strängar i java, då de skapas och läggs i en pool, som eventuellt kollas igenom. Använd istället StringBuilder eller System.out.print() för att kunna konkatenera snabbare :).

Gör man så så borde lösningen ta ungefär lika lång tid som varianten i C

Dold text

Gå till inlägget

Skrev om Java-koden så här

public class JavaProd {
    static String charset = "abcdefghi";
    static int maxLength = 9;
    static int amount = 0;

    public static void main(String[] args) {
        if (args.length > 0) {
            charset = args[0];
            maxLength = Integer.parseInt(args[1]);
        }
        long delta = System.nanoTime();
        closure(new StringBuilder(""), 0);
        delta = (System.nanoTime() - delta)/1000000;
        System.out.println("took " + delta + " ms.");
        System.out.println("generated " + amount + " Strings.");
    }

    static void closure(StringBuilder current, int currentLen) {
        //System.out.println(current);                                                                                                                                                                                                      
        amount++;
        if (currentLen < maxLength) {
            for (int i = 0; i < charset.length(); ++i) {
                current.append(charset.charAt(i));
                closure(current, currentLen + 1);
                current.deleteCharAt(currentLen);
            }
        }
    }
}

Dold text

$ java -server JavaProd 
took 3174 ms.
generated 435848050 Strings.

Det är nu snabbare än C, men Java-varianten "fuskar" i det att totala resultatet aldrig sparas (något som orsakar CPU-cache pollution i C varianten). Men nog kan man säga att de är mer eller mindre lika snabba nu. Blir lite sugen på att ta reda på hur snabbt det blir i C#, min erfarenhet är att sedan Java6 så blir CPU-bundna program signifikant snabbare i Java jämfört med C#.

Edit: gick att snabba upp mer än första versionen som använde StringBuilder, nu är det snabbare än min C-version.

Senast redigerat 2013-03-20 18:08

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Rapportera Redigera

Citera flera Citera

2013-03-21 15:42

Permalänk

anon81912

Inaktiv