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"
!"#$%&'()*+,-./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)
fonte
Respostas:
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
count
células no vetor de resultado. Repete os passes até a contagem ser 0.BF:
Algoritmo equivalente C:
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.Cru:
fonte
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.
fonte
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.
sem comentários:
fonte
fonte
fonte