Classificação mais rápida em BrainF ***

15

Depois de implementar o QuickSort no BrainF *** , percebi que provavelmente não era tão rápido. Operações que são O (1) em idiomas normais (como indexação de matriz) são significativamente mais longas no BF. A maioria das regras para o que faz uma classificação eficiente pode ser lançada pela janela quando você estiver codificando um tarpit de Turing.

Então, aqui está um desafio para implementar a "Rotina de classificação Brainest *** mais rápida de todos os tempos". Cronometrarei todas as entradas usando o intérprete abaixo. O intérprete usa uma fita 16K de caracteres não assinados. A fita e as células são quebradas quando avançadas / incrementadas além dos limites. A leitura do EOF coloca um 0 na célula atual. O tempo medido inclui o tempo para analisar o arquivo de origem e o tempo para processar todos os arquivos de entrada. O código mais rápido vence.

O vetor de teste será um conjunto de arquivos Ascii projetados para testar a classificação de casos extremos, incluindo

  • Uma lista já classificada: "ordenada"

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

    ~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#"!
    
  • Um arquivo que consiste em muitas cópias de alguns valores exclusivos: "onlynine"

    ibbkninbkrauickabcufrfckbfikfbbakninfaafafbikuccbariauaibiraacbfkfnbbibknkbfankbbunfruarrnrrrbrniaanfbruiicbuiniakuuiubbknanncbuanbcbcfifuiffbcbckikkfcufkkbbakankffikkkbnfnbncbacbfnaauurfrncuckkrfnufkribnfbcfbkbcrkriukncfrcnuirccbbcuaaifiannarcrnfrbarbiuk
    
  • Um arquivo ascii completamente aleatório: "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
    
  • Um arquivo aleatório no intervalo 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¦Ó 
    

Cada arquivo de entrada possui no máximo 255 bytes.

Aqui está o intérprete. Foi escrito para Windows no modo console, mas deve ser fácil de portar: basta substituir read_time()e sysTime_to_ms()por equivalentes específicos da 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 até agora

Aqui está o tempo médio de 5 execuções do conjunto completo de vetores:

 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)
AShelly
fonte
Qual é o alcance dos elementos de entrada?
Keith Randall
É o intervalo das células, exceto 0: 1-255.
precisa saber é o seguinte
você deveria repetir o meu, eu fiz isso um pouco mais rápido.
Keith Randall
Parece ser duas vezes mais rápido que o meu mais recente - farei o tempo oficial quando voltar à máquina que usei para os outros.
ASHelly

Respostas:

9

Aqui está um tipo que é pelo menos 6x mais rápido que o meu quicksort. É um algoritmo que faria pouco sentido em uma linguagem tradicional, pois é O (N * m) onde m é o valor máximo de entrada. Após coletar a entrada, ela passa pela matriz, contando células> 0 e, em seguida, diminuindo cada uma. Em seguida, adiciona 1 às primeiras countcélulas no vetor de resultado. Repete os passes até a contagem ser 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]);

Aqui está um que é 2x mais rápido. Baseia-se livremente no "tipo de espaguete" : estabelece uma sequência de 1s contanto que cada entrada. O valor em cada célula representa o número de fios pelo menos durante esse período. (Então [3,2,1,2] se torna |4|0|3|0|1|0|0|). Em seguida, começa a "medir" os fios e imprime o comprimento toda vez que encontra o fim de um.

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

Cru:

>,[[-[>>+<<-]>+>]<[<<]>,]+>[>+<-]>[>[>+<<->-]<[<<.>>-]<<[>>+<<-]>>+>>]
AShelly
fonte
Não bata contando tipo! É o meu tipo favorito, devido a uma vitória maciça que obtive uma vez: se m é conhecido por ser pequeno, você pode obter enormes acelerações em algoritmos "rápidos". Da mesma forma, a classificação por bolhas supera a classificação rápida nos dados classificados principalmente. Nenhum algoritmo ___ é o melhor para todos os contextos.
precisa saber é o seguinte
Eu não acho que isso seja exatamente um tipo de contagem. Seu comentário me forçou a fazer mais algumas pesquisas. Eu acho que isso é mais como um tipo de contas . Mas nem tenho certeza se isso está certo.
precisa saber é o seguinte
Não, você está certo. Este é um tipo estranho. Pode ser útil para algum aplicativo que envolva listas de listas vinculadas ... mas eu duvido disso.
usar o seguinte comando
4
A analogia física é que você tem N pilhas de moedas de tamanhos diferentes. Reserve espaço para mais N pilhas. Você tira uma moeda do topo de cada pilha que possui moedas e adiciona 1 a cada pilha no novo conjunto da direita para a esquerda até que sua mão esteja vazia. Repita até que todas as pilhas originais estejam vazias. Agora, o novo conjunto é classificado em ordem crescente da esquerda para a direita.
precisa saber é o seguinte
7
>>+>,[->+>,]<[<[<<]<[.<[<<]<]>>[+>->]<<]

Não me lembro de quem foi esse algoritmo. Talvez Bertram Felgenhauer? Ele veio de discussões sobre o concurso de golfe Brainfuck nº 2, mais de uma década atrás.

Este é o mais rápido ainda nas entradas de amostra.

Também não se limita a entradas de comprimento <256, mas pode lidar com entradas arbitrariamente longas.

Ambas as coisas também se aplicavam às respostas de Albert, abaixo. O bom desse exemplo é que o tempo de execução é O (N) no comprimento de entrada. Sim, isso realmente funciona em tempo linear. Já comia um fator constante de 255 como um lanche.

Daniel Cristofani
fonte
3

Uma implementação simples de classificação de contagem. Cada bloco tem 3 células de largura, contendo a entrada atual, um marcador e a contagem do número de vezes que o contador aparece na 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
>+[>[<-.+>-]<[->>>+<<<]>>>+]

sem comentários:

,[[-[->>>+<<<]>>>>+<]>>+<[-<<<]<,]>+[>[<-.+>-]<[->>>+<<<]>>>+]
Keith Randall
fonte
2
>,[>+>,]+[<[<-<]>>[<[>>]>[<->[>>]<.<[<<]]>>]<<<<<+]
Albert
fonte
2
>>+>,[>+>,]<[[<-<]>+>+[>]>[[-<<[[>>+<<-]<]>>]>-.+[>]>]<<]
Albert
fonte