La clasificación más rápida en BrainF ***

Después de haber implementado QuickSort en BrainF *** , me di cuenta de que probablemente no fue tan rápido. Las operaciones que son O (1) en lenguajes normales (como la indexación de matrices) son significativamente más largas en BF. La mayoría de las reglas de lo que hace una ordenación eficiente se pueden descartar cuando se codifica en una tarpit de Turing.

Así que aquí hay un desafío para implementar la "rutina más rápida BrainF *** Sort Ever Ever". Voy a cronometrar todas las entradas usando el intérprete a continuación. El intérprete utiliza una cinta de 16K de caracteres sin signo. Tanto la cinta como las celdas se envuelven cuando se avanza / incrementa más allá de los límites. Leer el EOF pone un 0 en la celda actual. El tiempo medido incluye tanto el tiempo para analizar el archivo fuente como el tiempo para procesar todos los archivos de entrada. El código más rápido gana.

El vector de prueba será un conjunto de archivos Ascii diseñados para probar casos límite de clasificación, incluidos

• Una lista ya ordenada: "ordenada"

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

• Una lista ordenada inversa: "inversa"

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

• Un archivo que consta de muchas copias de unos pocos valores únicos: "onlynine"

  ibbkninbkrauickabcufrfckbfikfbbakninfaafafbikuccbariauaibiraacbfkfnbbibknkbfankbbunfruarrnrrrbrniaanfbruiicbuiniakuuiubbknanncbuanbcbcfifuiffbcbckikkfcufkkbbakankffikkkbnfnbncbacbfnaauurfrncuckkrfnufkribnfbcfbkbcrkriukncfrcnuirccbbcuaaifiannarcrnfrbarbiuk
  

• Un archivo ascii completamente aleatorio: "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
  

• Un archivo aleatorio en el rango 1..255: "rango completo"

  öè—@œ™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¦Ó 
  

Cada archivo de entrada tiene como máximo 255 bytes.

Aquí está el intérprete. Está escrito para Windows en modo consola, pero debería ser fácil de portar: simplemente reemplácelo read_time()y sysTime_to_ms()con equivalentes específicos de la plataforma.
Uso: 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));
}

Resultados hasta ahora

Aquí está el tiempo promedio de 5 ejecuciones del conjunto completo de vectores:

 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)

Aquí hay un tipo que es al menos 6 veces más rápido que mi clasificación rápida. Es un algoritmo que tendría poco sentido en un lenguaje tradicional, ya que es O (N * m) donde m es el valor máximo de entrada. Después de recopilar la entrada, pasa a través de la matriz, cuenta celdas> 0 y luego disminuye cada una. Luego agrega 1 a las primeras countceldas en el vector de resultados. Repite los pases hasta que el conteo sea 0.
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 
<[<<]>>[.>>]

Algoritmo equivalente C:

 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]);

Aquí hay uno que es 2 veces más rápido. Se basa libremente en el "tipo de espagueti" : establece una cadena de 1s siempre que cada entrada. El valor en cada celda representa el número de hebras al menos tan largas. (Entonces [3,2,1,2] se convierte |4|0|3|0|1|0|0|). Luego comienza a "medir" los hilos e imprime la longitud cada vez que encuentra el final de uno.

>,[ [-[>>+<<-]>+>] <[<<]>,]   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 

Crudo:

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

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

No recuerdo de quién fue la idea de este algoritmo. ¿Quizás el de Bertram Felgenhauer? Provino de discusiones en torno al concurso Brainfuck Golf # 2, hace más de una década.

Este es el más rápido hasta ahora en las entradas de muestra.

Tampoco se limita a entradas de longitud <256, sino que puede manejar entradas arbitrariamente largas.

Ambas cosas también fueron ciertas para las respuestas de Albert, a continuación. Lo bueno de este es que el tiempo de ejecución es O (N) en la longitud de entrada. Sí, esta cosa realmente se ejecuta en tiempo lineal. Ya comió un factor constante de 255 como refrigerio.

Una implementación de ordenación de conteo simple. Cada segmento tiene 3 celdas de ancho, que contiene la entrada actual, un marcador y el recuento de la cantidad de veces que aparece el contador en la entrada.

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
>+[>[<-.+>-]<[->>>+<<<]>>>+]

sin comentarios:

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

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

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