Sortir Tercepat di BrainF ***

15

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"

    &#33;"#$%&'()*+,-./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)
ASHelly
sumber
Berapa kisaran elemen input?
Keith Randall
Ini adalah rentang sel, kecuali 0: 1-255.
ASHelly
Anda harus retime milik saya, saya membuatnya sedikit lebih cepat.
Keith Randall
Tampaknya lebih dari 2x lebih cepat dari yang terbaru - saya akan melakukan pengaturan waktu resmi ketika saya kembali ke mesin yang saya gunakan untuk yang lain.
AShelly

Jawaban:

9

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 countsel pertama dalam vektor hasil. Mengulangi pass sampai hitungan 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 
<[<<]>>[.>>]

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

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.

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

Mentah:

>,[[-[>>+<<-]>+>]<[<<]>,]+>[>+<-]>[>[>+<<->-]<[<<.>>-]<<[>>+<<-]>>+>>]
ASHelly
sumber
Jangan mengetuk penghitungan! Ini adalah jenis favorit saya, karena kemenangan besar yang saya dapatkan dari itu satu kali: jika m dikenal kecil, Anda bisa mendapatkan speedup besar jika tidak ada algoritma "cepat". Demikian pula, bubble sort mengalahkan quicksort pada sebagian besar data yang diurutkan. Tidak ada satu pun algoritma ___ yang terbaik untuk setiap konteks.
stan
Saya tidak berpikir ini semacam penghitungan. Komentar Anda memaksa saya untuk melakukan penelitian lebih lanjut. Saya pikir ini lebih seperti semacam manik . Tetapi saya bahkan tidak yakin itu benar.
AShelly
Tidak, kamu benar. Ini jenis yang aneh. Bisa bermanfaat untuk beberapa aplikasi yang melibatkan daftar daftar yang ditautkan ... tapi saya ragu akan hal itu.
stan
4
Analogi fisiknya adalah Anda memiliki N tumpukan koin dengan ukuran berbeda. Sisihkan ruang untuk tumpukan N lainnya. Anda mengambil satu koin dari atas setiap tumpukan yang memiliki koin, dan kemudian menambahkan 1 ke setiap tumpukan di set baru dari kanan ke kiri hingga tangan Anda kosong. Ulangi sampai semua tumpukan asli kosong. Sekarang set baru diurutkan naik dari kiri ke kanan.
AShelly
7
>>+>,[->+>,]<[<[<<]<[.<[<<]<]>>[+>->]<<]

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.

Daniel Cristofani
sumber
3

Implementasi penghitungan yang sederhana. Setiap ember sel 3 sel, berisi input saat ini, spidol, dan jumlah berapa kali penghitung muncul di input.

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

tanpa komentar:

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