Řazení slov

Naučíme tě pracovat na home-office.

Zjistit více...

Dvouvláknová verze

c-plus-plus

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
using namespace std;

inline int value(char* str)
{
    char ch1 = str[0] - 96;
    char ch2;
    char ch3;
    char ch4;
    if(str[1] == 0)
    {
      ch2 = 0;
      return ch1*19683;
    }
    ch2 = str[1] - 96;
    if(str[2] == 0)
    {
      ch3 = 0;
      return ch1*19683 + ch2*729;
    }
    ch3 = str[2] - 96;
    if(str[3] == 0)
    {
      ch4 = 0;
      return ch1*19683 + ch2*729 + ch3*27;
    }
    ch4 = str[3] - 96;
    return ch1*19683 + ch2*729 + ch3*27 + ch4;
}

inline void ValueToStr(int value, char* str)
{
    str[0] = value / (19683) + 96;
    value %= (19683);
    if(value == 0)
    {
      str[1] = 0;
      return;
    }
    str[1] = value / (729) + 96;
    value %= (729);
    if(value == 0)
    {
      str[2] = 0;
      return;
    }
    str[2] = value / 27 + 96;
    value %= 27;
    if(value == 0)
    {
      str[3] = 0;
      return;
    }
    str[3] = value + 96;
    str[4] = 0;
}

struct Data
{
  char** array;
  int & size;
  int* countArray;
  int* threadCountArray;
  volatile bool* done;
  volatile int* index;
};

void CountThread(void* d)
{
  Data & data = *((Data*)d);
  const int diff = 19683;
  int half = data.size / 2;
  int size = data.size;
  int* countArray = data.countArray;
  int* threadCountArray = data.threadCountArray;
  char** array = data.array;
  
  for(int i=size-1;i>half-1;i--)
    threadCountArray[value(array[i])-diff]++;
  
  *data.done = true;
}

void SortThread(void* d)
{
  Data & data = *((Data*)d);
  const int diff = 19683;
  int half = data.size / 2;
  int size = data.size;
  int* countArray = data.countArray;
  int* threadCountArray = data.threadCountArray;
  char** array = data.array;
  
  for(int i=511757,j=size-1;i>255878;i--)
  {
    for(int k=0;k<countArray[i]+threadCountArray[i];k++,j--)
      if(k == 0)
        ValueToStr(i+diff,array[j]);
      else
      {
        char* ptr = array[j + k];
        *((int*)array[j]) = *((int*)ptr);
      }
  }
  
  *data.done = true;
}

void CountingSort(char** array, int size)
{
    const int diff = 19683;
    int countArray[511758];
    int* threadCountArray = new int[511758];
    int half = size / 2;
    for(int i=0;i<511758;i++)
    {
      countArray[i] = 0;
      threadCountArray[i] = 0;
    }
    volatile bool done = false;
    Data data = {array,size,countArray,threadCountArray,&done};
    CreateThread(0,0,(LPTHREAD_START_ROUTINE)&CountThread,(void*)&data,0,0);
    
    for(int i=0;i<half;i++)
      countArray[value(array[i])-diff]++;
    
    while(!done);
    done = false;
    
    CreateThread(0,0,(LPTHREAD_START_ROUTINE)&SortThread,(void*)&data,0,0);
    
    for(int i=0,j=0;i<255879;i++)
    {
      for(int k=0;k<countArray[i]+threadCountArray[i];k++,j++)
        if(k == 0)
          ValueToStr(i+diff,array[j]);
        else
        {
          char* ptr = array[j - k];
          *((int*)array[j]) = *((int*)ptr);
        }
    }
    
    while(!done);
    delete [] threadCountArray;
}


int main()
{
    LONGLONG frequency;
    LONGLONG counter;
    LONGLONG begin;
    QueryPerformanceFrequency((LARGE_INTEGER*)&frequency);
    
    srand(time(0));
    int count;
    cin>>count;
    char** array = new char*[count];

    QueryPerformanceCounter((LARGE_INTEGER*)&begin);

    for(int i=0;i<count;i++)
    {
        int chars = rand() % 4 + 1;
        array[i] = new char[5];
        array[i][chars] = '\0';
        array[i][4] = '\0';
        for(short int j=0;j<chars;j++)
          array[i][j] = rand() % 26 + 97;
    }
    
    QueryPerformanceCounter((LARGE_INTEGER*)&counter);
    cout<<(counter - begin) / (frequency / 1000)<<endl;
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    CountingSort(array,count);
    QueryPerformanceCounter((LARGE_INTEGER*)&counter);
    cout<<(counter - begin) / (frequency / 1000)<<endl;
    
    /*for(int i=0;i<count;i++)
        cout<<array[i]<<endl;*/
    
    getchar();
    getchar();
    
    for(int i=0;i<count;i++)
        delete [] array[i];
    delete [] array;
}

Neformátovaný

Přidáno: 27.1.2013
Expirace: Neuvedeno

Autor: Lukáš Hruda