Sunday, January 31, 2016

Multi-thread Heap Sort

Impossible?
No.
WARNING!!! Some comments in Ukranian!

#define MAX_LOADSTRING 100
using namespace std;
typedef tuple <int,int,int> param_t; // offs,step,n
//array to sort
//const int N = 20000;

int *arr;
int *arr2;
int n;

// Global Variables:
HINSTANCE hInst;                                // current instance
TCHAR szTitle[MAX_LOADSTRING];                    // The title bar text
TCHAR szWindowClass[MAX_LOADSTRING];            // the main window class name

  HWND hWnd;                                    //хендл головного вікна
  HWND hDlgWindow;                                //хендл діалогового вікна

  int threadsCnt;                                    //кількість потоків
  vector<HANDLE>  threads;                //хендли для потоків

   clock_t curtime;                                //змінна для часу


// Forward declarations of functions included in this code module:
ATOM                MyRegisterClass(HINSTANCE hInstance);
BOOL                InitInstance(HINSTANCE, int);
LRESULT CALLBACK    WndProc(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK    About(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK    Sort(HWND, UINT, WPARAM, LPARAM );



void arayOutput()                                    //вивід масиву до файлу
{
    fstream outputfile;                                                        //
    outputfile.open("array.txt", ios::out);                                   
    for (int i=0;i<n;i++)                   
        outputfile<<arr[i]<<endl;                                                   
    outputfile.close();   
}
void heapify(int pos, int n)                    //просіювання елементів масиву
{
    int iLeft = 2 * pos + 1;                    //координати лівого потомка
     if (iLeft < n)
     {
          int iRight = iLeft+1;                //координата правого потомка
          int t = iRight < n && arr[iRight] >= arr[iLeft]   ? iRight : iLeft;    //вибір більшого з потомків, якщо такі є

          if (arr[pos] < arr[t])                   
          {
           swap(arr[pos], arr[t]);            //заміна більшого потомка з батьком, якщо потрібна
           heapify(t, n);                    //просіювання відповідної гілки
          }
     }
}
void heap_make(int n)                        //прохід по дереву для просіювання
{
 for (int i = n / 2; i >= 0; --i )
  heapify(i, n);
}
void heap_sort(int n)                    //звичайне сортування
{
 heap_make(n);                            //побудова сортуючого дерева


 while (n>0)                            //сортування
 {
  swap(arr[0], arr[n - 1]);
  n--;
  heapify(0, n);
 }
}


void heapify_thr(int pos, int n, int thr)        //паралельне просіювання
{
   
    int left = pos*2+1;                            //обчислення координат потомків
    int right = left + 1;
    if (left <n ) heapify_thr(left, n, thr);    //рекурсивний обхід дерева
    if (right <n ) heapify_thr(right, n, thr);
    if (left < n)
   {
       int t = right < n && arr[right] >= arr[left]        //обчислення більшого потомка
       ? right : left;

      if (arr[pos] < arr[t])                    //заміна з батьком, якщо потрібно
      {
       swap(arr[pos], arr[t]);
       heapify_thr(t, n, thr);                    //подальше просіювання
      
      }
     
   }
}
void start_heapify(param_t * params)            //процедура для роботи потоків
{
 int offs = get<0>(*params);                    //зчитування параметрів - номер вершини, кількість елементів, номер потока
 int step = get<1>(*params);
 int n = get<2>(*params);
 heapify_thr(offs,n,offs);                        //початок просіювання

}
void heap_make_mt(int n, int threadsCnt)        //створення сортуючого дерева паралельно у 2-х потоках
{

 for (int i = threadsCnt; i--;) {                //створення потоків
       threads.push_back(CreateThread(0, 0, (LPTHREAD_START_ROUTINE)start_heapify, new param_t(i+1,threadsCnt,n), 0, 0));
 }

 WaitForMultipleObjects(threadsCnt, &threads[0], true, INFINITE);    //очікування завершення роботи потоків
  heapify(0, n);                            //просіювання верхнього елемента
}
void heap_sort_mt(int n, int threads)        //паралельне сортування
{   
 heap_make_mt(n, threads);                    //створення сортуючого дерева

 while (n>0)                                //остаточне сортування
 {
  swap(arr[0], arr[n - 1]);
  n--;
  heapify(0, n);
 }
}




int APIENTRY _tWinMain(HINSTANCE hInstance,
                     HINSTANCE hPrevInstance,
                     LPTSTR    lpCmdLine,
                     int       nCmdShow)
{
    UNREFERENCED_PARAMETER(hPrevInstance);
    UNREFERENCED_PARAMETER(lpCmdLine);

     // TODO: Place code here.
    MSG msg;
    HACCEL hAccelTable;

    srand( 1);

   
     threadsCnt = 2;                //кількість потоків для паралельного сортування
   
    // Initialize global strings
    LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
    LoadString(hInstance, IDC_LAB5_SORT, szWindowClass, MAX_LOADSTRING);
    MyRegisterClass(hInstance);

    // Perform application initialization:
    if (!InitInstance (hInstance, nCmdShow))
    {
        return FALSE;
    }

    hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_LAB5_SORT));

    // Main message loop:
    while (GetMessage(&msg, NULL, 0, 0))
    {
        if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
        {
            TranslateMessage(&msg);
            DispatchMessage(&msg);
        }
    }

    return (int) msg.wParam;
}



//
//  FUNCTION: MyRegisterClass()
//
//  PURPOSE: Registers the window class.
//
//  COMMENTS:
//
//    This function and its usage are only necessary if you want this code
//    to be compatible with Win32 systems prior to the 'RegisterClassEx'
//    function that was added to Windows 95. It is important to call this function
//    so that the application will get 'well formed' small icons associated
//    with it.
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
    WNDCLASSEX wcex;

    wcex.cbSize = sizeof(WNDCLASSEX);

    wcex.style            = CS_HREDRAW | CS_VREDRAW;
    wcex.lpfnWndProc    = WndProc;
    wcex.cbClsExtra        = 0;
    wcex.cbWndExtra        = 0;
    wcex.hInstance        = hInstance;
    wcex.hIcon            = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_LAB5_SORT));
    wcex.hCursor        = LoadCursor(NULL, IDC_ARROW);
    wcex.hbrBackground    = (HBRUSH)(COLOR_WINDOW+1);
    wcex.lpszMenuName    = MAKEINTRESOURCE(IDC_LAB5_SORT);
    wcex.lpszClassName    = szWindowClass;
    wcex.hIconSm        = LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));

    return RegisterClassEx(&wcex);
}

//
//   FUNCTION: InitInstance(HINSTANCE, int)
//
//   PURPOSE: Saves instance handle and creates main window
//
//   COMMENTS:
//
//        In this function, we save the instance handle in a global variable and
//        create and display the main program window.
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{


   hInst = hInstance; // Store instance handle in our global variable

   hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
      CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);

   if (!hWnd)
   {
      return FALSE;
   }

   ShowWindow(hWnd, nCmdShow);
   UpdateWindow(hWnd);

   return TRUE;
}

//
//  FUNCTION: WndProc(HWND, UINT, WPARAM, LPARAM)
//
//  PURPOSE:  Processes messages for the main window.
//
//  WM_COMMAND    - process the application menu
//  WM_PAINT    - Paint the main window
//  WM_DESTROY    - post a quit message and return
//
//
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
    int wmId, wmEvent;
    PAINTSTRUCT ps;
    HDC hdc;

    switch (message)                //обробка повідомлень головного вікна
    {
    case WM_COMMAND:
        wmId    = LOWORD(wParam);
        wmEvent = HIWORD(wParam);
        // Parse the menu selections:
        switch (wmId)
        {
        case ID_FILE_32771:
            hDlgWindow = CreateDialog(hInst, MAKEINTRESOURCE(IDD_DIALOG1), hWnd, Sort);    //створення діалогового вікна при натисненні "Старт"
            break;
        case ID_FILE_32772:        //створення діалогового вікна при натисненні "Про програму"       
            DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);
            break;
       
       
           break;
        case IDM_EXIT:
            DestroyWindow(hWnd);
            break;
        default:
            return DefWindowProc(hWnd, message, wParam, lParam);
        }
        break;
    case WM_PAINT:
        hdc = BeginPaint(hWnd, &ps);
        // TODO: Add any drawing code here...
        EndPaint(hWnd, &ps);
        break;
    case WM_DESTROY:
        PostQuitMessage(0);
        break;
    default:
        return DefWindowProc(hWnd, message, wParam, lParam);
    }
    return 0;
}

//Обробка повідомлень діалогового вікна сортування
INT_PTR CALLBACK Sort(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
    int wmId, wmEvent;
    int inum, length;
    wchar_t buf[20];   

    HWND hedit1;            //текстове поле для кількості елементів
    HWND hedit2;            //текстове поле для часу

    UNREFERENCED_PARAMETER(lParam);
    switch (message)
    {
    case WM_INITDIALOG:
        return (INT_PTR)TRUE;

    case WM_COMMAND:
        {
            wmId    = LOWORD(wParam);
            wmEvent = HIWORD(wParam);
        switch (wmId)
        {       
        case IDC_BUTTON1:                //натиснено "Почати"
            length=10;
           
            hedit1 = GetDlgItem(hDlgWindow,IDC_EDIT1);   
            hedit2 = GetDlgItem(hDlgWindow,IDC_EDIT2);
            SendMessage(hedit1,WM_GETTEXT, length, (LPARAM)buf);        //зчитування кількості елементів масиву
            if (length == 0) MessageBox(hDlgWindow,TEXT("Enter array size"),TEXT("error"),MB_OK);
            else
            {
                inum    = _wtoi(buf);
                if (inum == 0) MessageBox(hDlgWindow,TEXT("Enter array size"),TEXT("error"),MB_OK);
                else
                {
                    n = inum;
                               
                    arr = new int[n];                //створення масив, що буде сортуватися
                    //sort
                    //checkbuttons
                    if(IsDlgButtonChecked(hDlgWindow, IDC_RADIO1))    //вибраний метод звичайного сортування
                    {   
                       for (int i = 0; i < n; i++)                    //заповнення масиву випадковою послідовністю
                         {
 
                             arr[i] = rand() % 1000;
                         }

                         curtime = clock();                            //початковий час
                         heap_sort(n);                                //сортування
                        float diff = ((float)clock()-(float)curtime) /  CLK_TCK;    //кінцевий час
                        const size_t len = 10;
                        wchar_t sBuffer[len];
                       
                        _snwprintf(sBuffer, len-1, L"%f", diff);
                        BOOL b_Ret = SetWindowTextW(hedit2, sBuffer);    //виведення часу, що затрачено на сортування
                       
                        arayOutput();                            //вивід масиву до файлу
                       


                    } 
                    else
                    {
                        if (IsDlgButtonChecked(hDlgWindow, IDC_RADIO2))        //обрано паралельне сортування
                        {
                            for (int i = 0; i < n; i++)                        //заповнення масиву випадковою послідовністю
                            {
 
                             arr[i] = rand() % 1000;
                            }
                            curtime = clock();
                            heap_sort_mt(n, threadsCnt);                    //сортування
                            float diff = ((float)clock()-(float)curtime) /  CLK_TCK;    //облік часу
                            const size_t len = 10;
                            wchar_t sBuffer[len];
                       
                            _snwprintf(sBuffer, len-1, L"%f", diff);
                            BOOL b_Ret = SetWindowTextW(hedit2, sBuffer);        //вивід часу
                            arayOutput();                                    //вивід масиву до файла
                        }
                       
                        else MessageBox(NULL, TEXT("check sorting method"), TEXT("error"),MB_OK);
                    }
                    delete arr;                //висвободження пам'яті масива
                   
                }

            }
           
            //MessageBox(hWnd,TEXT("Start button pushed"),TEXT("ok"),MB_OK);
            break;
        case IDC_BUTTON2:
            MessageBox(hWnd,TEXT("Stop button pushed"),TEXT("ok"),MB_OK);
            break;

        }
           
        if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
        {
           
            EndDialog(hDlg, LOWORD(wParam));
            return (INT_PTR)TRUE;
        }
   
        }
    }
    return (INT_PTR)FALSE;
}

// Message handler for about box.
INT_PTR CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
    UNREFERENCED_PARAMETER(lParam);
    switch (message)
    {
    case WM_INITDIALOG:
        return (INT_PTR)TRUE;

    case WM_COMMAND:
        if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
        {
            EndDialog(hDlg, LOWORD(wParam));
            return (INT_PTR)TRUE;
        }
        break;
    }
    return (INT_PTR)FALSE;
}


No comments:

Post a Comment