Gå til innhold

Rot13 algoritme

KodeHans

Anbefalte innlegg

KodeHans

KodeHans

Skrevet
Skrevet

Hei. Jeg er ganske fersk og behøver hjelp til å lage en rutine for å konvertere tekst til rot13. Grunnen til at jeg spør er fordi jeg ikke er god på optimalisering og er ute etter den raskeste løsningen for å konvertere store mengder tekst. Tusen takk for all hjelp.

 

KodeHans

Lenke til kommentar

Videoannonse

Videoannonse
Annonse
KodeHans

KodeHans

Skrevet
  • Forfatter
Skrevet

Takk, algoritmen er ganske greit forklart, kan du eller noen andre vise meg hvordan man implementerer dette på best mulig måte mtp. hastighet og optimalisering? Det er mest tiden det tar som er viktig for meg, og ikke så veldig mye hvordan den implementeres. Den bør være ganske rask for å takle store mengder data på kortest mulig tid. :)

Lenke til kommentar
KodeHans

KodeHans

Skrevet
  • Forfatter
Skrevet (endret)

laurell: Tar du utfordringen? :)

 

Det er ikke så viktig hvordan du implementerer det, bare timingen er god. Det er mer snakk om millisekunder enn det er snakk om selve implementasjonen. Det er så mange kodere her på forumet og mange har sikkert innspill, hvis vi bare får opp noen eksempler.

 

Det er ikke det som kommer ut av funksjonen som er så viktig (selv om det også må være riktig), men det er hvor mye rå data man kan skvise gjennom funksjonen per tidsintervall som er viktig for meg. Hvis vi ser for oss at rot13 funksjonen er et sort rør, og vannet som strømmer gjennom røret er rå data som ikke er rotert. Det er hvor mye vann som strømmer gjennom røret per tidsintervall som er viktig for meg.

 

Jeg er ute etter den beste implementasjonen.

Endret av KodeHans
Lenke til kommentar
Sokkalf™

Sokkalf™

Skrevet
Skrevet (endret)

Evigheter siden jeg har programmert i C, men tenkte jeg fikk prøve meg.. (nå er kanskje ikke programmeringsspråket så viktig, siden det er algoritmen du lurer på, men så var de nå i C/C++-kategorien spørsmålet lå..)

 

Mitt forsøk, leser bare tekst fra stdin og outputter rot13 til stdout.

 

#include <stdio.h>
char translation_map[] = "NOPQRSTUVWXYZABCDEFGHIJKLM	  nopqrstuvwxyzabcdefghijklm";
unsigned char read_byte(FILE *f)
{
    char c;
    c = fgetc(f);
    if (c == EOF) return '\0';
    return c;
}
int main(int argc, char *argv[])
{
       while(!feof(stdin)) {
		    char c;
		    c = read_byte(stdin);
		    if(((c >= 0x41) && (c <= 0x5A)) || ((c >= 0x61) && (c <= 0x7A)))
				    printf("%c", translation_map[c-0x41]);
		    else printf("%c", c);
    }
    return 0;
}

 

Å bruke et statisk array til "translation" er vel sannsynligvis bortkastet, da utregning sannsynligvis går like kjapt etter kompilatoroptimisering, men var det første som falt meg inn for å få ting til å gå kjapt, så jeg begynte i den enden. :p

Endret av Sokkalf™
  • Liker 1
Lenke til kommentar
LonelyMan

LonelyMan

Skrevet
Skrevet

Vil vel forøvrig være enda kjappere sånn sett å bare putte inn en hel ASCII-tabell ferdig rotert og oversette rått uten noen form for conditionals etc..

 

256 bytes ferdig kalkulert vil fort havne i topp prioritert cache i prosessoren, og den cachen er omtrent like rask som prosessorens registre, nesten. Så det vil gå fortere med en ferdig rotert buffer ja, det er garantert.

  • Liker 1
Lenke til kommentar
Sokkalf™

Sokkalf™

Skrevet
Skrevet (endret)

Kan den optimaliseres, hvor mye data takler den per millisekund, om du tar bort stdout for å se hvor mye den takler ved å konvertere bare i minnet, uten å skrive ut?

 

Siden det er første forsøk, så kan den nok garantert optimaliseres, ja.

 

Har en rot13-implementasjon i bash også:

while read linje
 do
   echo "$linje" | tr 'A-Za-z' 'N-ZA-Mn-za-m'
 done

 

Testet dem opp mot hverandre. Bash-implementasjonen konverterte på 20kB/sek, mens C-implementasjonen min var rundt 1000 ganger raskere, med omlag 20MB/sek.

Endret av Sokkalf™
  • Liker 1
Lenke til kommentar
KodeHans

KodeHans

Skrevet
  • Forfatter
Skrevet

Takk for det :)

 

Jeg ser du testet ved å lese fra harddisken, det kan gjøre at selve algoritmen ikke får kjørt seg fullt da harddisken ofte er den som holder ting tilbake litt. Hvis du konverterer en statisk streng i minnet, frem og tilbake så får du kanskje sett potensialet til algoritmen, hvor raskt den takler data.

Lenke til kommentar
Sokkalf™

Sokkalf™

Skrevet
Skrevet

Harddisken er ikke flaskehalsen her, siden den greier mye større hastigheter.

 

Uten rot13 går det på 90MB/sek. (Piping av tekst til /dev/null).

 

Jeg har testet med en 100MB stor loggfil, noe større mengder av random tekst som lar seg "kryptere" med rot13 har jeg ikke, så det er begrenset hvor nøyaktige tallene blir med så lite data. Men de gir en pekepinn, om ikke annet.

 

Noe mer innsats gidder ikke jeg å legge i dette her, men du må gjerne bygge videre på det selv. :)

  • Liker 1
Lenke til kommentar
KodeHans

KodeHans

Skrevet
  • Forfatter
Skrevet

Ok, leser du 100 MB inn til minnet først og så konverterer du, eller streamer du og konverterer i samme kjør? Om du likevel senere får tid eller lyst, så kan du godt lese inn 100 MB til minnet først, og så konvertere dataene i minnet og forkaste resultatene, bare for å se hvor rask den er uten å streame, og uten å sende til dev/null, men bare å forkaste resultatet (ikke gjøre noe med det) :)

 

Igjen, takk for koden, det var snilt.

Lenke til kommentar
LonelyMan

LonelyMan

Skrevet
Skrevet (endret)

Jeg har laget en assembler funksjon for å konvertere, jeg har optimalisert den litt, men ikke så altfor mye. Denne funksjonen roterer strenger med en hastighet på:

 

1,708,945,260 bytes per sekund (1,7 milliarder bytes per sekund) i minnet. Dette på en gammel core 2 duo 3.0 GHz maskin med DDR3 Ram.

 

Dvs du kan rotere en streng på 1,7 MB på 1 millisekund. Eller du kan rotere en streng på 1709 bytes på 1 mikrosekund. Eller konvertere 1,7 bytes på 1 nanosekund.

 

 

OPTION PROLOGUE:NONE
OPTION EPILOGUE:NONE
;esi = ansi string pointer
;ebp = Sett til lengden av streng og del på 8 (multipler av 8)
ALIGN 16
Rot13L8 PROC
push ebx
push edi
xor ecx, ecx
xor edx, edx
mov edi, OFFSET Rot13Buf4
ALIGN 16
@@: mov eax, [esi]
mov ebx, [esi+4]
mov cl, al
mov dl, ah
mov cl, [edi+ecx]
mov dl, [edi+edx]
shr eax, 16
mov [esi], cl
mov [esi+1], dl
mov cl, al
mov dl, ah
mov [esi+2], cl
mov [esi+3], dl
mov cl, bl
mov dl, bh
mov cl, [edi+ecx]
mov eax, esi
mov dl, [edi+edx]
shr ebx, 16
add esi, 8
sub ebp, 1
mov [eax+4], cl
mov [eax+5], dl
mov cl, bl
mov dl, bh
mov [eax+6], cl
mov [eax+7], dl
jnz @B
pop edi
pop ebx
ret
Rot13L8 ENDP
OPTION PROLOGUE:PROLOGUEDEF
OPTION EPILOGUE:EPILOGUEDEF

 

Jeg har vedlagt test programmet hvis noen vil teste hastigheten på en annen type maskin.

Rot13Assembler.rar

Endret av LonelyMan
  • Liker 2
Lenke til kommentar
Valkyrex

Valkyrex

Skrevet
Skrevet

Denne formen bruker ikke noen lookup eller noe, og trenger heller ikke allokere noen ny array. Den tar et og et tegn løpende: les -> behandle -> skriv. Har ikke sett på effektiviteten, men tenkte å bare presentere en annen måte å gjøre det på (just for the fun of it, og det er nok mye som kan fikses på / optimaliseres her ja).

 

#include <iostream>
#include <fstream>
using namespace std;
void rot13(fstream* file) {
int size, begin, end, i;
unsigned char buffer;
char temp;

file->seekg(0, ios::beg);
begin = (int)file->tellg();
file->seekg(0, ios::end);
end = (int)file->tellg();
size = end - begin;
i = 0;
while (i < size && !file->eof()) {
 file->seekg(i, ios::beg);
 file->read(&temp, 1);
 buffer = (unsigned char)temp;

 if (buffer >= int('A') && buffer <= int('Z')) {
  buffer += 13;
  if (buffer > int('Z')) {
   buffer = (buffer % int('Z')) + int('A') - 1;
  }
 }
 else if (buffer >= int('a') && buffer <= int('z')) {
  buffer += 13;
  if (buffer > int('z')) {
   buffer = (buffer % int('z')) + int('a') - 1;
  }
 }
 temp = (char)buffer;
 file->seekp(i, ios::beg);
 file->write(&temp, 1);
 i++;
}
}
int main() {
fstream f("routes.dta", ios::in | ios::out | ios::binary);
if (f) rot13(&f);
f.close();
return 0;
}

  • Liker 1
Lenke til kommentar
Valkyrex

Valkyrex

Skrevet
Skrevet

Hehe, code-golf anyone? xD

 

#include <fstream>
using namespace std;
#define r(w,x,y)if(w>=x&&w<=y){w+=13;if(w>y){w=(w%y)+x-1;}}
int main(){
int s,t,a=97,A=65,z=122,Z=90;
unsigned char b;
char c;
fstream f("routes.dta",ios::in|ios::out|ios::binary);
f.seekg(0,ios::beg);
t=f.tellg();
f.seekg(0, ios::end);
s=f.tellg();
s=s-t;
t=0;
while(t<s){
f.seekg(t,ios::beg);
f.read(&c,1);
b=(unsigned char)c;
r(b,A,Z)
r(b,a,z)
c=(char)b;
f.seekp(t++,ios::beg);
f.write(&c,1);
}}

Lenke til kommentar

Opprett en konto eller logg inn for å kommentere

Du må være et medlem for å kunne skrive en kommentar

Opprett konto

Det er enkelt å melde seg inn for å starte en ny konto!

Start en konto

Logg inn

Har du allerede en konto? Logg inn her.

Logg inn nå
Gå til emneliste
×
×
  • Opprett ny...