Olivkovo řešení

//
// Demo program pro vyuku predmetu APPS (09/2011)
// Petr Olivka, katedra informatiky, FEI, VSB-TU Ostrava
// email:[email protected]
//
// Priklad pouzit vlaken v OS Windows
// Pro overeni paralelismu je nutno mit alespon dvoujadrovy procesor
//
// ***********************************************************************
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#include <tchar.h>

using namespace std;

#define TYP int

//------------ KONSTANTY ----------------
 const int NAHODA = 200;
 const int ARRAY_SIZE = 10;
 int MAX1, MAX2;
 int *POLE;
 int *FIRST;
 int *SECOND;
//--------------------------------------
// funkce rand() je pouze 16 bitova
// rand32 vraci 32 bitove nahodne cislo
int rand32()
{
    return rand() * RAND_MAX + rand();
}

void PrintArray(int arr[], int size)
{
for(int i = 0; i<size; i++)
   {
      cout<<arr[i]<<endl;
   }

}

//----------------FUNKCE START-----------------------
void SelectionSort(int arr[], int size)
{
        int i, j, mi, tmp;
        for (i = 0; i < size - 1; i++) {
                /* najdeme minimum */
                mi = i;
                for (j = i+1; j < size; j++) {
                    if (arr[j] < arr[mi]) {
                        mi = j;
                    }
                }
                /* vyměníme arr[i] a arr[mi] */
                tmp = arr[i];
                arr[i] = arr[mi];
                arr[mi] = tmp;
      //Pomocny vypis
   //cout<<"Pruchod: "<<size-i<<endl;
      //      PrintArray(arr,size);

      }
}


void InsertionSort(int arr[], int size) {

      int i, j, tmp;

      for (i = 1; i < size; i++) {

            tmp = arr[i];

            j = i;

            while (j > 0 && arr[j - 1] > tmp) {

                  arr[j] = arr[j - 1];

                  j--;

            }

            arr[j] = tmp;
//Pomocny vypis
   //cout<<"Pruchod: "<<size-i<<endl;
      //      PrintArray(arr,size);
     }

}

void BubbleSort(int arr[], int size)
{
  int i, j, temp;

  for (i = (size - 1); i > 0; i--)
  {
    for (j = 1; j <= i; j++)
    {
      if (arr[j-1] > arr[j])
      {
        temp = arr[j-1];
        arr[j-1] = arr[j];
        arr[j] = temp;
      }
    }
   //Pomocny vypis
   //cout<<"Pruchod: "<<size-i<<endl;
      //      PrintArray(arr,size);
 //Sleep(20);
  }
}



void CoppyArray(int arr1[], int arr2[], int size)
{
for(int i = 0; i<size; i++)
   {
      arr2[i]=arr1[i];
   }

}

void SplitArray(int arr[],int arr1[], int arr2[], int size)
{
   int secondhalf = size-size/2;
for(int i = 0; i<size; i++)
   {

      if(i<(size/2))
      {
         arr1[i]=arr[i];
      }
      else
      {
         arr2[i-secondhalf]=arr[i];
      }
   }

}

void CombineArray(int arr[],int arr1[], int arr2[], int size)
{
   int secondhalf = size-size/2;
   int j=0;
   int k=0;
for(int i = 0; i<size; i++)
   {

      if((arr1[j]<arr2[k] && j<size/2) || k==secondhalf)
      {
         if(j<size/2)
         {
         arr[i]=arr1[j];
         }
         j++;
      }
      else
      //if((arr2[k]<arr1[j] && k<secondhalf) || j==size)
      {
         if(j<secondhalf)
         {
         arr[i]=arr2[k];
         }
         k++;
      }

}
}

//TADY KONCI MOJE FUNKCE
int hledej_max( int levy, int pravy, int *pole )
{
   int nejvetsi = pole[ levy ];
   for ( int i = levy + 1; i < pravy; i++ )
      if ( nejvetsi < pole[ i ] )
         nejvetsi = pole[ i ];
   Sleep( 5000 ); // Zpožďovač
   return nejvetsi;
}
// vypocet casoveho intervalu v milisekundach
int kolik_ms( LPFILETIME pred, LPFILETIME po )
{
   hyper pred64b = pred->dwHighDateTime;
   pred64b = ( pred64b << 32 ) | pred->dwLowDateTime;
   hyper po64b = po->dwHighDateTime;
   po64b = ( po64b << 32 ) | po->dwLowDateTime;
   // konverze 100ns -> 1ms
   return ( int ) ( ( po64b - pred64b ) / 10000 );
}

void HyperSelectionSort(int levy, int pravy, int *pole)
{
        int i, j, mi, tmp;
      for ( int i = levy; i < pravy-1; i++ )
       {
                /* najdeme minimum */
                mi = i;
                for (j = i+1; j < pravy; j++) {
                    if (pole[j] < pole[mi]) {
                        mi = j;
                    }
                }
                /* vyměníme arr[i] a arr[mi] */
                tmp = pole[i];
                pole[i] = pole[mi];
                pole[mi] = tmp;
      //Pomocny vypis
   //cout<<"Pruchod: "<<size-i<<endl;
      //      PrintArray(arr,size);
   }
}


// vlakno A bude hledat maximalni prvek pole mezi prvkem 0 a DELKA/2
// vysledek ulozi do globalni promenne MAX1
DWORD WINAPI vlaknoA( LPVOID )
{
   printf( "Startuje vlakno A\n" );
    // Tady přinde funkce
   BubbleSort(FIRST, ARRAY_SIZE/2);
   return 0;
}

// vlakno B bude hledat maximalni prvek pole mezi prvkem DELKA/2 a DELKA
// vysledek ulozi do globalni promenne MAX2
DWORD WINAPI vlaknoB( LPVOID )
{
   printf( "Startuje vlakno B\n" );
    // Tady přinde funkce
   BubbleSort(SECOND, ARRAY_SIZE-ARRAY_SIZE/2);
   return 0;
}


//---------------FUNKCE END -------------------------

int _tmain(int argc, _TCHAR* argv[])
{
   srand( ( int ) time( NULL ) );

//   int arr[ARRAY_SIZE];

   POLE = new int[ARRAY_SIZE];
   FIRST = new int[ARRAY_SIZE/2];
   SECOND = new int[ARRAY_SIZE-ARRAY_SIZE/2];
   int BubbleArr[ARRAY_SIZE];
   int InsertArr[ARRAY_SIZE];
   int SelectArr[ARRAY_SIZE];
   int FirstArr[ARRAY_SIZE/2];
   int SecondArr[ARRAY_SIZE-ARRAY_SIZE/2];

cout<<"Puvodni pole\n";
   for(int i = 0; i<ARRAY_SIZE; i++)
   {
      POLE[i]=rand32()%NAHODA;
   }

//PrintArray(POLE, ARRAY_SIZE);

SplitArray(POLE, FIRST,SECOND, ARRAY_SIZE);

//Rozkopirovani puvodního pole pro sorty
CoppyArray(POLE, BubbleArr, ARRAY_SIZE);
CoppyArray(POLE, InsertArr, ARRAY_SIZE);
CoppyArray(POLE, SelectArr, ARRAY_SIZE);
/*
cout<<"Bubble sort\n";
BubbleSort(BubbleArr, ARRAY_SIZE);
PrintArray(BubbleArr, ARRAY_SIZE);


cout<<"Select sort\n";
SelectionSort(SelectArr, ARRAY_SIZE);
PrintArray(SelectArr, ARRAY_SIZE);

cout<<"Insert sort\n";
InsertionSort(InsertArr, ARRAY_SIZE);
PrintArray(InsertArr, ARRAY_SIZE);


SplitArray(arr, FirstArr,SecondArr, ARRAY_SIZE);
cout<<"Prvni pulka sort\n";
PrintArray(FirstArr, ARRAY_SIZE/2);
cout<<"Druha pulka sort\n";
PrintArray(SecondArr, ARRAY_SIZE-ARRAY_SIZE/2);
*/

//TADY KONCI MUJ RUKOPIS

HANDLE p1, p2;
FILETIME cas_pred, cas_po;

   // zaznamenani casu pred zapocetim hledani
   GetSystemTimeAsFileTime ( &cas_pred );

   // vytvoreni dvou vlaken
   p1 = CreateThread( 0, 0, vlaknoA, 0, 0, 0 );
//   WaitForSingleObject( p1, INFINITE );
   p2 = CreateThread( 0, 0, vlaknoB, 0, 0, 0 );

   // cekani na ukonceni vlaken
   WaitForSingleObject( p1, INFINITE );
   WaitForSingleObject( p2, INFINITE );

   // zaznam casu po ukonceni prace obou vlaken
   GetSystemTimeAsFileTime( &cas_po );

   //printf( "Nalezene maximum je %d\n", max( MAX1, MAX2));
   cout<<"FIRST SORT\n";
   //PrintArray(FIRST, ARRAY_SIZE/2);
   cout<<"SECOND SORT\n";
   //PrintArray(SECOND,ARRAY_SIZE-ARRAY_SIZE/2);
   printf( "Cas hledani byl %d [ms]\n", kolik_ms( &cas_pred, &cas_po ) );

   //JEDNO VLAKNO
   printf( "Trideni pomoci 1 vlakna...\n" );
   GetSystemTimeAsFileTime( &cas_pred );

   SplitArray(POLE, FirstArr,SecondArr, ARRAY_SIZE);

   BubbleSort(FirstArr,ARRAY_SIZE/2);

   BubbleSort(SecondArr,ARRAY_SIZE-ARRAY_SIZE/2);

   GetSystemTimeAsFileTime( &cas_po );
   cout<<"\nPrvni pulka\n";
   //PrintArray(FirstArr,ARRAY_SIZE/2);
   cout<<"\nDruha pulka\n";
//   PrintArray(SecondArr,ARRAY_SIZE-ARRAY_SIZE/2);
   printf( "\nCas razeni byl %d [ms]\n", kolik_ms( &cas_pred, &cas_po ) );

   cout<<"Spojovani pole\n";
   GetSystemTimeAsFileTime( &cas_pred );
   CombineArray(POLE,FirstArr, SecondArr, ARRAY_SIZE);
   GetSystemTimeAsFileTime( &cas_po );
   printf( "\nCas razeni byl %d [ms]\n", kolik_ms( &cas_pred, &cas_po ) );
   cout<<"Tisk spojeneho pole\n";

   PrintArray(POLE, ARRAY_SIZE);

system("PAUSE");
return 0;
}