Schnellste Sortierung in BrainF ***

Nachdem ich QuickSort in BrainF *** implementiert hatte , wurde mir klar, dass es wahrscheinlich nicht so schnell war. Operationen, die in normalen Sprachen O (1) sind (wie die Array-Indizierung), sind in BF erheblich länger. Die meisten Regeln für eine effiziente Sortierung können beim Codieren in einem Turing-Tarpit aus dem Fenster geworfen werden .

Es ist also eine Herausforderung, die "schnellste BrainF *** Sortierroutine aller Zeiten" zu implementieren. Ich werde alle Einträge mit dem Interpreter unten zeitlich festlegen. Der Interpreter verwendet ein 16-KB-Band mit vorzeichenlosen Zeichen. Sowohl das Band als auch die Zellen werden umbrochen, wenn die Grenzen überschritten werden. Das Lesen des EOF setzt eine 0 in die aktuelle Zelle. Die gemessene Zeit umfasst sowohl die Zeit zum Analysieren der Quelldatei als auch die Zeit zum Verarbeiten aller Eingabedateien. Der schnellste Code gewinnt.

Der Testvektor besteht aus einer Reihe von ASCII-Dateien, die zum Testen der Sortierung von Kantenfällen, einschließlich, entwickelt wurden

• Eine bereits sortierte Liste: "bestellt"

  &#33;"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
  

• Eine umgekehrt sortierte Liste: "umgekehrt"

  ~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#"!
  

• Eine Datei, die aus vielen Kopien einiger eindeutiger Werte besteht: "onlynine"

  ibbkninbkrauickabcufrfckbfikfbbakninfaafafbikuccbariauaibiraacbfkfnbbibknkbfankbbunfruarrnrrrbrniaanfbruiicbuiniakuuiubbknanncbuanbcbcfifuiffbcbckikkfcufkkbbakankffikkkbnfnbncbacbfnaauurfrncuckkrfnufkribnfbcfbkbcrkriukncfrcnuirccbbcuaaifiannarcrnfrbarbiuk
  

• Eine völlig zufällige ASCII-Datei: "random"

  'fQ`0R0gssT)70O>tP[2{9' 0.HMyTjW7-!SyJQ3]gsccR'UDrnOEK~ca 'KnqrgA3i4dRR8g.'JbjR;D67sVOPllHe,&VG"HDY_'Wi"ra?n.5nWrQ6Mac;&}~T_AepeUk{:Fwl%0`FI8#h]J/Cty-;qluRwk|S U$^|mI|D0\^- csLp~`VM;cPgIT\m\(jOdRQu#a,aGI?TeyY^*"][E-/S"KdWEQ,P<)$:e[_.`V0:fpI zL"GMhao$C4?*x
  

• Eine zufällige Datei über den Bereich 1..255: "wholerange"

  öè—@œ™S±ü¼ÓuǯŠf΀n‚ZÊ,ˆÖÄCítÚDý^öhfF†¬I÷xxÖ÷GààuÈ©ÈÑdàu.y×€ôã…ìcÑ–:*‰˜IP¥©9Ä¢¬]Š\3*\®ªZP!YFõ®ÊÖžáîÓ¹PŸ—wNì/S=Ìœ'g°Ì²¬½ÕQ¹ÀpbWÓ³
  »y  »ïløó„9k–ƒ~ÕfnšÂt|Srvì^%ÛÀâû¯WWDs‰sç2e£+PÆ@½ã”^$f˜¦Kí•òâ¨÷ žøÇÖ¼$NƒRMÉE‹G´QO¨©l¬k¦Ó 
  

Jede Eingabedatei hat höchstens 255 Bytes.

Hier ist der Dolmetscher. Es ist für console-Modus von Windows geschrieben, soll aber einfach zu portieren sein: einfach ersetzen read_time()und sysTime_to_ms()mit plattformspezifischen Äquivalente.
Verwendung: bftime program.bf infile1 [infile2 ...]

#include <windows.h>
#include <stdio.h>

#define MS_PER_SEC  1000.0f
#define MAXSIZE  (0x4000)
#define MAXMASK  (MAXSIZE-1)

typedef  __int64 sysTime_t;
typedef unsigned char Uint8;
typedef unsigned short Uint16;

typedef struct instruction_t {
   Uint8 inst;
   Uint16 pair;
} Instruction;

Instruction prog[MAXSIZE] = {0};
Uint8 data[MAXSIZE] = {0};
const Uint8 FEND = EOF;

sysTime_t read_time() {
    __int64 counts;
    QueryPerformanceCounter((LARGE_INTEGER*)&counts);
    return counts;
}

float sysTime_to_ms(sysTime_t timeIn) {
    __int64 countsPerSec;
    QueryPerformanceFrequency((LARGE_INTEGER*)&countsPerSec);
    return (float)timeIn * MS_PER_SEC / (float)countsPerSec;
}

int main(int argc, char* argv[])
{
   FILE* fp;
   Uint8 c;
   Uint16 i = 0;
   Uint16 stack = 0;
   sysTime_t start_time;
   sysTime_t elapsed=0,delta;

   if (argc<3) exit(printf("Error: Not Enough Arguments\n"));
   fp = fopen(argv[1],"r");
   if (!fp) exit(printf("Error: Can't Open program File %s\n",argv[1]));

   start_time=read_time();
   while (FEND != (c = fgetc(fp)) && i <MAXSIZE) {
      switch (c)  {
      case '+': case '-': case ',': case '.': case '>': case '<':
         prog[++i].inst = c;
         break;
      case '[': 
         prog[++i].inst = c;
         prog[i].pair=stack;
         stack = i;
         break;
      case ']': 
         if (!stack) exit(printf("Unbalanced ']' at %d\n",i));
         prog[++i].inst = c;
         prog[i].pair=stack;
         stack = prog[stack].pair;
         prog[prog[i].pair].pair=i;
         break;
      }
   }
   if (stack) exit(printf("Unbalanced '[' at %d\n",stack));
   elapsed = delta = read_time()-start_time;
   printf("Parse Time: %f ms\n", sysTime_to_ms(delta));

   for (stack=2;stack<argc;stack++) {
      Instruction *ip = prog;
      fp = fopen(argv[stack],"r");
      if (!fp) exit(printf("Can't Open input File %s\n",argv[stack]));
      printf("Processing %s:\n", argv[stack]);
      memset(data,i=0,sizeof(data));

      start_time=read_time();
      //Run the program
      while (delta) {
         switch ((++ip)->inst) {
         case '+': data[i]++; break;
         case '-': data[i]--; break;
         case ',': c=getc(fp);data[i]=(FEND==c)?0:c; break;
         case '.': putchar(data[i]);  break;
         case '>': i=(i+1)&MAXMASK;   break;
         case '<': i=(i-1)&MAXMASK;   break;
         case '[': if (!data[i]) ip = prog+ip->pair; break;
         case ']': if (data[i])  ip = prog+ip->pair;  break;
         case 0: delta=0; break;
         }
      }
      delta = read_time()-start_time;
      elapsed+=delta;
      printf("\nProcessing Time: %f ms\n", sysTime_to_ms(delta));
   }
   printf("\nTotal Time for %d files: %f ms\n", argc-2, sysTime_to_ms(elapsed));
}

Bisherige Ergebnisse

Hier ist die durchschnittliche Zeit von 5 Durchläufen des vollständigen Vektorsatzes:

 Author    Program      Average Time    Best Set          Worst Set
 AShelly   Quicksort    3224.4 ms       reverse (158.6)   onlynine (1622.4) 
 K.Randall Counting     3162.9 ms       reverse (320.6)   onlynine  (920.1)
 AShelly   Coinsort      517.6 ms       reverse  (54.0)   onlynine  (178.5) 
 K.Randall CountingV2    267.8 ms       reverse  (41.6)   random     (70.5)
 AShelly   Strandsort    242.3 ms       reverse  (35.2)   random     (81.0)

Hier ist eine Sorte, die mindestens 6x schneller ist als meine Quicksort. Es ist ein Algorithmus, der in einer traditionellen Sprache wenig Sinn macht, da es sich um O (N * m) handelt, wobei m der maximale Eingabewert ist. Nach dem Sammeln der Eingabe durchläuft sie das Array, zählt Zellen> 0 und dekrementiert dann jede einzelne. Es addiert dann 1 zu den ersten countZellen im Ergebnisvektor. Es wiederholt die Durchläufe, bis die Zählung 0 ist.
BF:

Get Input
>,[>>+>,]   
Count values GT 0 and decrement each
<[<[<<<+>>>-]<[-<<+>>>]>[<]<<]
While count: add 1 to results
<[[[<<+>>-]<+<-]
Seek back to end of input
>[>>]>>>[>>>]
Repeat counting step
<<<[<[<<<+>>>-]<[-<<+>>>]>[<]<<]<]
Seek to far end of results and print in reverse order 
<[<<]>>[.>>]

C äquivalenter Algorithmus:

 uchar A[MAX]={0}; uchar R[MAX]={0}; int count,i,n=0;
 while (A[n++]=getchar()) ;
 do { 
   count = 0;
   for (i=0; i<n; i++) count += (A[i]) ? (A[i]-->0) : 0;
   for (i=0; i<count; i++) R[i]++; 
 } while (count>0);
 for (i=0; R[i]; i++) ;
 for (i--; i>=0; i--) putchar(R[i]);

Hier ist einer, der 2x so schnell ist. Es basiert lose auf "Spaghetti-Sortierung" : Es legt eine Zeichenfolge von 1s fest, solange jede Eingabe erfolgt. Der Wert in jeder Zelle gibt die Anzahl der Stränge an, die mindestens so lang sind. (So ​​wird [3,2,1,2] |4|0|3|0|1|0|0|). Anschließend werden die Stränge "gemessen" und die Länge jedes Mal ausgedruckt, wenn das Ende eines Strangs gefunden wird.

>,[ [-[>>+<<-]>+>] <[<<]>,]   build strand of 1s for each input
+>[>+<-]>[                    while there are strands
  >[>+<<->-]                  do any strands end here?
  <[<<.>>-]                   print length of all that do  
  <<[>>+<<-]>>+>>]            shift right 1; inc length 

Roh:

>,[[-[>>+<<-]>+>]<[<<]>,]+>[>+<-]>[>[>+<<->-]<[<<.>>-]<<[>>+<<-]>>+>>]

>>+>,[->+>,]<[<[<<]<[.<[<<]<]>>[+>->]<<]

Ich erinnere mich nicht, wessen Idee dieser Algorithmus war. Vielleicht das von Bertram Felgenhauer? Dies ergab sich aus den Diskussionen um den Brainfuck Golf Contest # 2 vor über einem Jahrzehnt.

Dies ist die bisher schnellste Einstellung für die Sample-Eingänge.

Es ist auch nicht auf Eingaben mit einer Länge <256 beschränkt, sondern kann beliebig lange Eingaben verarbeiten.

Beides traf auch auf Alberts Antworten zu. Das Schöne an diesem ist, dass die Laufzeit O (N) in der Eingabelänge ist. Ja, das Ding läuft tatsächlich in linearer Zeit. Als Zwischenmahlzeit aß es bereits einen konstanten Faktor von 255.

Eine einfache Zählsortierung. Jeder Bucket ist 3 Zellen breit und enthält die aktuelle Eingabe, eine Markierung und die Anzahl, wie oft der Zähler in der Eingabe angezeigt wird.

process input
,[

while input is not zero
[

decrement input
-

copy input over to next bucket
[->>>+<<<]

mark next bucket as not the first
>>>>+<

repeat until input is zero
]

increment count for this bucket
>>+

rewind using markers
<[-<<<]<

process next input
,]

generate output
>+[>[<-.+>-]<[->>>+<<<]>>>+]

ohne Kommentare:

,[[-[->>>+<<<]>>>>+<]>>+<[-<<<]<,]>+[>[<-.+>-]<[->>>+<<<]>>>+]

>,[>+>,]+[<[<-<]>>[<[>>]>[<->[>>]<.<[<<]]>>]<<<<<+]

>>+>,[>+>,]<[[<-<]>+>+[>]>[[-<<[[>>+<<-]<]>>]>-.+[>]>]<<]