Satik
Counting sort stringů
c-plus-plus
#include "stdafx.h"
#include <iostream> // konzole
#include <windows.h> // vsechno mozny, mereni casu
#include <string> // stringy pro vypis
#include <fstream> // zapis do souboru
using namespace std;
// dostane pole, index a vrati string - stringy dlouhe 4 znaky totiz nejsou zakoncene nulou
string GetString(unsigned char * pole, int pos)
{
string ret = "1234";
for (int i=pos; i<pos+4; i++)
{
ret[i-pos] = pole[i];
if (!pole[i])
{
ret.resize(i-pos);
break;
}
}
return ret;
}
// vygeneruje nahodny char v rozmezi 'a' az 'z'
unsigned char RandomChar()
{
return rand()%26+97;
}
// vygeneruje nahodne stringy dlouhe 1-4 znaky, obsahujici jen povolene znaky
void Generuj2 (unsigned char * pole, int size)
{
for (int i=0; i<size; i++)
{
int len=1+rand()%4;
for (int j=0; j<4; j++)
{
if (j>=len)
{
pole[(i*4)+j]=0;
}
else
{
pole[(i*4)+j]=RandomChar();
}
}
}
}
// posledni verze radici metody (pouziva se counting sort)
void Serad3 (void * data, int velikost)
{
// pole slov je vlastne pole zaznamu, kde kazdy ma delku 4 znaky a pokud je slovo kratsi nez 4 znaky, tak se na konec dava nula
unsigned int * pole = (unsigned int *) data; // udelame si tedy z dat pole intu, je rychlejsi vzit z pameti jeden int nez postupne 4 chary
const int sizeCounts = 32*32*32*32; // potrebna velikost pole, kdyz velikost jednoho znaku bude mocnina dvou, bude se nam s tim lip delat nez s cislem 27 (26 pro abecedu a 1 pro nulu)
int * counts = new int[sizeCounts]; // pole ukladajici pocty opakovani
ZeroMemory(counts,sizeCounts*4); // vynulujeme ho, C++ nam promenne nenuluje
// tady projedeme cely vstup, kazde slovo prepocitame na jeho odpovidajici hodnotu a pak do pole, ktery uklada pocet vyskytu pricteme jednicku
for (int i=0; i<velikost; i++)
{
unsigned int val = pole[i];
unsigned int tmp = val;
unsigned int hash;
// v tmp mame cele slovo, & 0xff ze slova vytahne jen posledni ascii znak
// pak se odecte 96 (tam nekde zacina znak 'a') a pak se to zase posune o nekolik bitu doleva, podle toho, jakou prioritu ten znak pri razeni ma
tmp = tmp & 0xff;
tmp = tmp - 96;
tmp = tmp << 15; // posun o 3x5 bitu (protoze pro ulozeni 32 hodnot je potreba 5 bitu, 32 = 2^5)
hash = tmp;
// tady to same, akorat si musime posunout val o osm bitu doprava, abysme brali druhy znak z vstupu
tmp = val >> 8;
tmp = tmp & 0xff;
if (tmp!=0) // kdyz narazime na nulu, uz dal jit nemusime, tam uz ty znaky neplatej
{
tmp = tmp - 96;
tmp = tmp << 10;
hash = hash | tmp; // a jen ty mezivysledny tmp (coz je teda ascii znak prevedeny na rozsah 0-32 pro nase ucely) pridame do vysledku, kterej nam urci index do pole counts
tmp = val >> 16;
tmp = tmp & 0xff;
if (tmp!=0)
{
tmp = tmp - 96;
tmp = tmp << 5;
hash = hash | tmp;
tmp = val >> 24;
if (tmp!=0)
{
tmp = tmp - 96;
hash = hash | tmp;
}
}
}
// pricist pocet vyskytu
counts[hash]++;
}
// vypsat to z counts na vystup
int outputindex=0;
char * tmp = new char[4];
for (int countsIndex=0; countsIndex<sizeCounts; countsIndex++)
{
if (counts[countsIndex]==0) continue; // pokud tohle slovo nebylo ani jednou, jedeme dal a ani ho neresime
unsigned int hash=countsIndex;
*(unsigned int*) tmp = 0; // vynulovat cele slovo najednou
// nasledujici radky by se mozna daly optimalizovat, jeste jinak - jit na to z druhy strany a az se narazi na nulu, tak prestat pripovat chary, podobne jako o cca 20-30 radku vys, ale u velkych poctu slov (rekneme nad 2M-5M slov) by to uz asi nebylo skoro znat.
// sestavi ten string
char letter;
// precte zkraceny znak a udela z nej odpovidajici ascii znak
letter = hash & 31;
if (letter!=0)
{
letter += 96;
tmp[3] = letter;
}
// precte dalsi zkraceny znak a udela z nej odpovidajici ascii znak
hash>>=5;
letter = hash & 31;
if (letter!=0)
{
letter += 96;
tmp[2] = letter;
}
hash>>=5;
letter = hash & 31;
if (letter!=0)
{
letter += 96;
tmp[1] = letter;
}
hash>>=5;
letter = hash & 31;
if (letter!=0)
{
letter += 96;
tmp[0] = letter;
}
// ted podle toho, kolikrat se to slovo opakovalo, ho prida na vystup. Vypocet toho slova probehne jen jednou, pak uz se jen lepi vysledek (lepit jeden int je rychlejsi nez 4xchar)
for (int c=0; c<counts[countsIndex]; c++)
{
pole[outputindex] = *(unsigned int *)tmp;
outputindex++;
}
}
delete[] tmp;
delete[] counts;
}
// main
int _tmain(int argc, _TCHAR* argv[])
{
int size = 100000000;
cout << "Word count" << endl;
cin >> size;
// pole slov
unsigned char * pole2 = new unsigned char[size*4];
// vygenerovani nahodnych slov
Generuj2(pole2, size);
LARGE_INTEGER clock, clock2, freq;
double time;
// vypocet doby a samotne razeni
QueryPerformanceCounter(&clock);
Serad3((void *)pole2, size);
QueryPerformanceCounter(&clock2);
QueryPerformanceFrequency(&freq);
time=((double)clock2.QuadPart-(double)clock.QuadPart)/(double)freq.QuadPart;
cout << endl << endl << "Time: " << time*1000.0 << "ms." << endl;
cout << endl << "Save results to file? (yes/no)";
string answer="no";
cin >> answer;
// ulozeni vysledku do souboru
if (answer=="yes")
{
// save results
ofstream os;
os.open("results.txt");
for (int i=0; i<size; i++)
{
os << GetString(pole2, i*4) << endl;
}
os.close();
}
system("pause"); // tohle se mi libi vic nez cekani udelat treba pres cin
delete[] pole2; // uklizime po sobe
return 0;
}
Neformátovaný
Přidáno: 27.1.2013
Expirace: Neuvedeno
Autor: Luboš Běhounek Satik