Après avoir implémenté QuickSort dans BrainF *** , j'ai réalisé que ce n'était probablement pas si rapide. Les opérations qui sont O (1) dans les langages normaux (comme l'indexation de tableaux) sont considérablement plus longues dans BF. La plupart des règles pour ce qui fait un tri efficace peuvent être jetées par la fenêtre lorsque vous codez dans un tarpit Turing.
Voici donc un défi pour implémenter le "Fastest BrainF *** Sort Routine Ever". Je chronométrerai toutes les entrées en utilisant l'interpréteur ci-dessous. L'interprète utilise une bande de 16 Ko de caractères non signés. La bande et les cellules s'enroulent lorsqu'elles sont avancées / incrémentées au-delà des limites. La lecture de l'EOF met un 0 dans la cellule actuelle. Le temps mesuré comprend à la fois le temps d'analyse du fichier source et le temps de traitement de tous les fichiers d'entrée. Le code le plus rapide gagne.
Le vecteur de test sera un ensemble de fichiers Ascii conçus pour tester les cas de bord de tri, y compris
Une liste déjà triée: "commandée"
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Une liste triée inversée: "inversée"
~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#"!Un fichier composé de nombreuses copies de quelques valeurs uniques: "onlynine"
ibbkninbkrauickabcufrfckbfikfbbakninfaafafbikuccbariauaibiraacbfkfnbbibknkbfankbbunfruarrnrrrbrniaanfbruiicbuiniakuuiubbknanncbuanbcbcfifuiffbcbckikkfcufkkbbakankffikkkbnfnbncbacbfnaauurfrncuckkrfnufkribnfbcfbkbcrkriukncfrcnuirccbbcuaaifiannarcrnfrbarbiukUn fichier ascii complètement aléatoire: "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?*xUn fichier aléatoire sur la plage 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¦Ó
Chaque fichier d'entrée a au plus 255 octets.
Voici l'interprète. Il est écrit pour Windows en mode console, mais devrait être facile à porter: il suffit de le remplacer read_time()et sysTime_to_ms()avec des équivalents spécifiques à la plate-forme.
Usage: 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));
}
Résultats à ce jour
Voici le temps moyen de 5 exécutions de l'ensemble complet de vecteurs:
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)
la source
Réponses:
Voici un tri qui est au moins 6 fois plus rapide que mon tri rapide. C'est un algorithme qui aurait peu de sens dans un langage traditionnel, car c'est O (N * m) où m est la valeur d'entrée maximale. Après avoir collecté l'entrée, elle passe à travers le tableau, en comptant les cellules> 0 puis en décrémentant chacune. Il ajoute ensuite 1 aux premières
countcellules du vecteur de résultat. Il répète les passes jusqu'à ce que le compte soit 0.BF:
Algorithme équivalent C:
En voici un qui est 2x plus rapide. Il est vaguement basé sur le "tri spaghetti" : il établit une chaîne de 1 aussi longtemps que chaque entrée. La valeur dans chaque cellule représente le nombre de brins au moins aussi longs. (Donc [3,2,1,2] devient
|4|0|3|0|1|0|0|). Ensuite, il commence à «mesurer» les brins et imprime la longueur chaque fois qu'il trouve la fin d'un.Brut:
la source
Je ne me souviens pas de l'idée de cet algorithme. Peut-être celle de Bertram Felgenhauer? Il est venu de discussions autour du concours de golf Brainfuck # 2, il y a plus d'une décennie.
C'est le plus rapide à ce jour sur les entrées d'échantillon.
Il n'est pas non plus limité aux entrées de longueur <256, mais peut gérer des entrées arbitrairement longues.
Ces deux choses étaient également vraies pour les réponses d'Albert, ci-dessous. La bonne chose à propos de celui-ci est que le temps de fonctionnement est O (N) dans la longueur d'entrée. Oui, cette chose fonctionne réellement en temps linéaire. Il a déjà mangé un facteur constant de 255 comme collation.
la source
Une implémentation simple de tri de comptage. Chaque compartiment a une largeur de 3 cellules, contenant l'entrée actuelle, un marqueur et le nombre de fois où le compteur apparaît dans l'entrée.
sans commentaire:
la source
la source
la source