Setelah menerapkan QuickSort di BrainF *** , saya menyadari mungkin itu tidak secepat itu. Operasi yang O (1) dalam bahasa normal (seperti pengindeksan array) secara signifikan lebih lama di BF. Sebagian besar aturan untuk apa yang membuat pengurutan efisien dapat dibuang ke luar jendela saat Anda melakukan pengkodean dalam turing Turing.
Jadi inilah tantangan untuk mengimplementasikan "BrainF *** Sort Sortine Routine Ever tercepat". Saya akan mengatur waktu semua entri menggunakan juru bahasa di bawah ini. Intepreter menggunakan rekaman 16K karakter yang tidak ditandatangani. Baik pita dan sel membungkus ketika maju / bertambah melewati batas. Membaca EOF menempatkan 0 di sel saat ini. Waktu yang diukur mencakup waktu untuk mengurai file sumber dan waktu untuk memproses semua file input. Kode tercepat menang.
Vektor uji akan berupa kumpulan file Ascii yang dirancang untuk menguji kasus tepi sortir, termasuk
Daftar yang sudah disortir: "dipesan"
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
Daftar yang diurutkan terbalik: "terbalik"
~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#"!
File yang terdiri dari banyak salinan dari beberapa nilai unik: "onlynine"
ibbkninbkrauickabcufrfckbfikfbbakninfaafafbikuccbariauaibiraacbfkfnbbibknkbfankbbunfruarrnrrrbrniaanfbruiicbuiniakuuiubbknanncbuanbcbcfifuiffbcbckikkfcufkkbbakankffikkkbnfnbncbacbfnaauurfrncuckkrfnufkribnfbcfbkbcrkriukncfrcnuirccbbcuaaifiannarcrnfrbarbiuk
File ascii yang benar-benar acak: "acak"
'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
File acak pada rentang 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¦Ó
Setiap file input memiliki paling banyak 255 byte.
Ini penerjemahnya. Ini ditulis untuk mode konsol Windows, tetapi harus mudah port: cukup ganti read_time()
dan sysTime_to_ms()
dengan setara platform-spesifik.
Pemakaian: 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));
}
Hasil Sejauh Ini
Inilah rata-rata waktu 5 kali berjalan dari kumpulan vektor lengkap:
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)
sumber
Jawaban:
Ini adalah jenis yang setidaknya 6x lebih cepat dari quicksort saya. Ini adalah algoritma yang tidak masuk akal dalam bahasa tradisional, karena O (N * m) di mana m adalah nilai input maksimum. Setelah mengumpulkan input, ia melewati array, menghitung sel> 0 dan kemudian mengurangi masing-masing. Kemudian menambahkan 1 ke
count
sel pertama dalam vektor hasil. Mengulangi pass sampai hitungan 0.BF:
Algoritma setara C:
Inilah yang 2x lebih cepat. Ini didasarkan longgar pada "semacam spaghetti" : itu meletakkan string 1s selama setiap input. Nilai dalam setiap sel mewakili jumlah untai setidaknya selama itu. (Jadi [3,2,1,2] menjadi
|4|0|3|0|1|0|0|
). Kemudian mulai 'mengukur' untaian dan mencetak panjang setiap kali menemukan ujungnya.Mentah:
sumber
Saya tidak ingat ide siapa algoritma ini. Mungkin Bertram Felgenhauer? Itu datang dari diskusi sekitar Brainfuck Golf contest # 2, lebih dari satu dekade yang lalu.
Ini adalah yang tercepat pada input sampel.
Ini juga tidak terbatas pada input dengan panjang <256, tetapi dapat menangani input panjang yang sewenang-wenang.
Kedua hal ini juga berlaku untuk jawaban Albert, di bawah. Yang menyenangkan dari yang ini adalah waktu berjalannya adalah O (N) pada panjang input. Ya, hal ini sebenarnya berjalan dalam waktu linier. Itu sudah makan faktor konstan 255 sebagai camilan.
sumber
Implementasi penghitungan yang sederhana. Setiap ember sel 3 sel, berisi input saat ini, spidol, dan jumlah berapa kali penghitung muncul di input.
tanpa komentar:
sumber
sumber
sumber