Po wdrożeniu QuickSort w BrainF *** , zdałem sobie sprawę, że prawdopodobnie nie było tak szybko. Operacje, które są O (1) w normalnych językach (takie jak indeksowanie tablic) są znacznie dłuższe w BF. Większość zasad skutecznego sortowania można wyrzucić przez okno, gdy kodujesz w tarczy Turinga.
Oto wyzwanie, aby wdrożyć „Najszybszą procedurę sortowania BrainF *** w historii”. Poświęcę czas na wszystkie wpisy, używając tłumacza poniżej. Intepreter używa taśmy 16K znaków bez znaku. Zarówno taśma, jak i komórki są zawijane, gdy są zwiększane / zwiększane poza granice. Odczyt EOF umieszcza 0 w bieżącej komórce. Mierzony czas obejmuje zarówno czas analizy pliku źródłowego, jak i czas przetwarzania wszystkich plików wejściowych. Najszybszy kod wygrywa.
Wektor testowy będzie zestawem plików Ascii zaprojektowanych do testowania sortowania przypadków brzegowych, w tym
Lista już posortowana: „zamówiona”
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
Odwrócona lista posortowana: „wstecz”
~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#"!
Plik składający się z wielu kopii kilku unikalnych wartości: „onlynine”
ibbkninbkrauickabcufrfckbfikfbbakninfaafafbikuccbariauaibiraacbfkfnbbibknkbfankbbunfruarrnrrrbrniaanfbruiicbuiniakuuiubbknanncbuanbcbcfifuiffbcbckikkfcufkkbbakankffikkkbnfnbncbacbfnaauurfrncuckkrfnufkribnfbcfbkbcrkriukncfrcnuirccbbcuaaifiannarcrnfrbarbiuk
Całkowicie losowy plik ascii: „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
Losowy plik z zakresu 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¦Ó
Każdy plik wejściowy ma maksymalnie 255 bajtów.
Oto tłumacz. Jest napisany dla trybu konsoli Windows, ale powinny być łatwe do portu: wystarczy wymienić read_time()
i sysTime_to_ms()
z platformy konkretnych odpowiedników.
Stosowanie: 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));
}
Dotychczasowe wyniki
Oto średni czas 5 przebiegów pełnego zestawu wektorów:
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)
źródło
Odpowiedzi:
Oto rodzaj, który jest co najmniej 6 razy szybszy niż mój szybki asortyment. Jest to algorytm, który nie miałby większego sensu w tradycyjnym języku, ponieważ jest to O (N * m), gdzie m jest maksymalną wartością wejściową. Po zebraniu danych wejściowych przechodzi przez tablicę, zliczając komórki> 0, a następnie zmniejszając każdą z nich. Następnie dodaje 1 do pierwszych
count
komórek w wektorze wynikowym. Powtarza podania, aż liczbawyniesie 0. BF:
Algorytm równoważny C:
Oto taki, który jest 2x szybszy. Opiera się luźno na „sortowaniu spaghetti” : określa ciąg 1s tak długo, jak każde wejście. Wartość w każdej komórce odpowiada liczbie pasm co najmniej tak długiej. (Tak więc staje się [3,2,1,2]
|4|0|3|0|1|0|0|
). Następnie zaczyna „mierzyć” pasma i drukuje długość za każdym razem, gdy znajdzie koniec jednego.Surowy:
źródło
Nie pamiętam, kto wpadł na ten algorytm. Może Bertram Felgenhauer? Wynikało to z dyskusji na temat zawodów nr 2 w Brainfuck Golf ponad dziesięć lat temu.
Jest to najszybszy jak dotąd na przykładowych danych wejściowych.
Nie ogranicza się również do danych wejściowych o długości <256, ale może obsługiwać dowolnie długie dane wejściowe.
Obie te rzeczy były również prawdziwe w odpowiedziach Alberta poniżej. Zaletą tego jest to, że czas działania wynosi O (N) na długości wejściowej. Tak, to faktycznie działa w czasie liniowym. Zjadł już stały współczynnik 255 jako przekąskę.
źródło
Prosta implementacja sortowania liczącego. Każde wiadro ma 3 komórki szerokości, zawierające bieżące dane wejściowe, znacznik i liczbę wyświetleń licznika na wejściu.
bez komentarza:
źródło
źródło
źródło