Diskuze: Paralelní třídění

švrčajs

Člen

švrčajs:18.1.2016 21:51

Zdravím, potřeboval bych pomoct, mám program, který pomocí vláken načte čísla ze souborů, setřídí je a uloží je do dalšího souboru. Ale mám problém s ukládáním dat do souboru. Nejdříve mi vypíše pár čísel správně, ale pak mi začne házen nesmyslné záporné čísla a nevím proč. Nekoukl by na to někdo ?
Pracuje se s binárními soubory a čísla jsou 24 bitová, bez znaménka, proto mě zaráží, že to ve výsledném souboru hází záporná čísla...

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#include <assert.h>


void quicksort(unsigned int * array, int left_begin, int right_begin)
{
        int pivot = array[(left_begin + right_begin) / 2];
        int left_index, right_index, pom;
        left_index = left_begin;
        right_index = right_begin;
        do {
                while (array[left_index] < pivot && left_index < right_begin)
                        left_index++;
                while (array[right_index] > pivot && right_index > left_begin)
                        right_index--;

                if (left_index <= right_index) {
                        pom = array[left_index];
                        array[left_index++] = array[right_index];
                        array[right_index--] = pom;
                }
        } while (left_index < right_index);

        if (right_index > left_begin) quicksort(array, left_begin, right_index);
        if (left_index < right_begin) quicksort(array, left_index, right_begin);
}

unsigned int ** array;
unsigned int * len;

struct params
{
        FILE * file;
        int counter;
};


void OpenAndSort(params * p)
{
        if (p->file == NULL)
        {
                printf("Nelze cist soubor\n");
                return;
        }

        char buffer[3];
        unsigned int num = 0;
        bool exist = false;
        int size = 0;
        int k = 0;

        while (true)
        {


                fread(buffer, sizeof(buffer), 1, p->file);
                num = (buffer[0] & 0xFF) | ((buffer[1] & 0xFF) << 8) | ((buffer[2] & 0xFF) << 16);
                if (feof(p->file))
                        break;
                if (!exist)
                {
                        exist = true;
                        size = num;
                        array[p->counter] = (unsigned int *)malloc(sizeof(unsigned int) * size);
                }
                else
                {
                        array[p->counter][k++] = num;
                }
        }


        quicksort(array[p->counter], 0, size - 1);

        len[p->counter] = size;

        fclose(p->file);
}
//algoritmus převzat z https://phoenix.inf.upol.cz/esf/ucebni/zakladni_alg.pdf

void rank(unsigned int a[], int l1, unsigned int b[], int l2, unsigned int res[])
{
        unsigned int c1;
        unsigned int c2;
        unsigned int min;
        int m = 0;
        int n = 0;


        c1 = a[m];
        c2 = b[n];

        for (int i = 0; i < l1 + l2; i++)
        {
                if (c1 < c2)
                {
                        res[i] = c1;
                        m++;
                        c1 = a[m];
                }
                else
                {
                        res[i] = c2;
                        n++;
                        c2 = b[n];
                }
        }

}

void ranking(char * filename, int m)
{

        FILE * f = fopen(filename, "wb");
        if (f == NULL)
        {
                printf("nelze zapsat do souboru\n");
                return;
        }
        int sum = 0;
        for (int i = 0; i < m; i++)
                sum += len[i];
        unsigned int * c = (unsigned int *)malloc(sizeof(unsigned int) * sum);
        char buf[9];
        if (m == 2)
        {
                rank(array[0], len[0], array[1], len[1], c);
                for (int i = 0; i < len[0] + len[1]; i++)
                {
                        fwrite(&c[i], 3, 1, f);
                }
        }

        if (m == 3)
        {
                unsigned int * a = (unsigned int *)malloc(sizeof(unsigned int) * (len[0] + len[1]));
                rank(array[0], len[0], array[1], len[1], a);
                rank(a, len[0] + len[1], array[2], len[2], c);
                for (int i = 0; i < len[0] + len[1] + len[2]; i++)
                {
                        fwrite(&c[i], 3, 1, f);
                }
        }
        if (m == 4)
        {
                unsigned int * a = (unsigned int *)malloc(sizeof(unsigned int) * (len[0] + len[1]));
                unsigned int * b = (unsigned int *)malloc(sizeof(unsigned int) * (len[2] + len[3]));
                rank(array[0], len[0], array[1], len[1], a);
                rank(array[2], len[2], array[3], len[3], b);
                rank(a, len[0] + len[1], b, len[2] + len[3], c);
                for (int i = 0; i < len[0] + len[1] + len[2] + len[3]; i++)
                {
                        fwrite(&c[i], 3, 1, f);
                }
        }

        fclose(f);

}

int main(int argc, char * argv[])
{
        if (argc != 4)
        {
                printf("zadejte spravne argumenty: pocet-souboru nazev-vstupu nazev-vystupu\n");
                system("pause");
                return -1;
        }

        int m = atoi(argv[1]);
        if (m < 2 || m > 4)
        {
                printf("pocet souboru muze byt v intervalu <2;4>\n");
                return -1;
        }

        char * input = argv[2];
        char * output = argv[3];

        char ** inputs = (char**)malloc(sizeof(char) * m);
        for (int i = 0; i < m; i++)
        {
                inputs[i] = (char *)malloc(sizeof(char) * (strlen(input) + 2));
                int k = 0;
                bool suffix = false;

                for (int j = 0; j < strlen(input); j++, k++)
                {
                        if (input[j] != '.')
                        {
                                inputs[i][k] = input[j];
                        }
                        else
                        {
                                char buf[2];
                                itoa(i + 1, buf, 10);
                                inputs[i][k++] = buf[0];
                                inputs[i][k] = input[j];
                                suffix = true;
                        }
                }
                if (!suffix)
                {
                        char buf[2];
                        itoa(i + 1, buf, 10);
                        inputs[i][strlen(input)] = buf[0];
                }
                inputs[i][strlen(input) + 1] = '\0';
        }



        array = (unsigned int **)malloc(sizeof(unsigned int *) * m);
        len = (unsigned int *)malloc(sizeof(unsigned int) * m);
        HANDLE * threads = (HANDLE *)malloc(sizeof(HANDLE) * m);

        for (int i = 0; i < m; i++)
        {
                params * p = (params*)malloc(sizeof(params));
                p->file = fopen(inputs[i], "r");
                p->counter = i;

                threads[i] = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)OpenAndSort, (LPVOID)p, CREATE_SUSPENDED, NULL);

                if (threads[i] == INVALID_HANDLE_VALUE)
                {
                        printf("Nelze vytvorit vlákno\n", i);
                        return -1;
                }
                assert(threads[i]);
                ResumeThread(threads[i]);
        }

        WaitForMultipleObjects(m, threads, true, INFINITE);
        ranking(output, m);
        system("pause");
        return 0;
}

Odpovědět

18.1.2016 21:51

švrčajs

Člen

švrčajs:19.1.2016 21:58

Už jsem našel chybnou část kodu, ale vůbec nevím proč se tam hodí záporné hodnoty.. testuju to na if m =3.. naalokuju pole c, první pár čísel to vypíše, přesněji 251 a následně to vypisuje jen -842150451... Hledal jsem na netu čím by to mohlo být, ale nic jsem nenašel a už mi z toho kapánek hrabe

void ranking(char * filename, int m)
{
FILE * f = fopen(filename, "w");
        if (f == NULL)
        {
        printf("Can't open file for writing\n");
        return;
        }
        int sum = 0;
        for (int i = 0; i < m; i++)
        sum += len[i];
        unsigned int * c = (unsigned int *) malloc (sizeof(unsigned int) * sum);
        printf(" suma %i\n", sum);
        char *buf = (char *)malloc(sizeof(char) * 9);
        if (m == 2)
        {
        rank(array[0], len[0], array[1], len[1], c);



        for (int i = 0; i < len[0] + len[1]; i++)
        {
        itoa(c[i], buf, 10);

        fputs(buf, f);


        fputs("\n", f);
        }
        }

        if (m == 3)
        {
        unsigned int * a = (unsigned int *) malloc (sizeof(unsigned int) * (len[0] + len[1]));
        rank(array[0], len[0], array[1], len[1], a);
        rank(a, len[0] + len[1], array[2], len[2], c);
        for (int i = 0; i < sum; i++)
        {
                printf("c: %i", c[i]);
                itoa(c[i], buf, 10);
                fputs(buf, f);

                fputs("\n", f);
                buf = (char *)realloc(buf, 9);
        }
        }
        if (m == 4)
        {
        unsigned int * a = (unsigned int *) malloc (sizeof(unsigned int) * (len[0] + len[1]));
        unsigned int * b = (unsigned int *) malloc (sizeof(unsigned int) * (len[2] + len[3]));
        rank(array[0], len[0], array[1], len[1], a);
        rank(array[2], len[2], array[3], len[3], b);
        rank(a, len[0] + len[1], b, len[2] + len[3], c);
        for(int i = 0; i < len[0] + len[1] + len[2] + len[3]; i++)
        {
        itoa(c[i], buf, 10);
        fputs(buf, f);
        fputs("\n", f);
        }
        }

        fclose(f);



}

Nahoru Odpovědět

19.1.2016 21:58

švrčajs

Člen

švrčajs:19.1.2016 22:03

Tady jsou soubory, se kterýma pracuju http://leteckaposta.cz/448930640

Nahoru Odpovědět

19.1.2016 22:03

švrčajs

Člen

švrčajs:27.1.2016 18:12

Nevím, jestli to někoho zajímalo... Ale chyba byla úplně primitivní při otvírání souborů, jsem je četl jako textové, stačilo to upravit na čtení bin. souboru...

Akceptované řešení
+20 Zkušeností
+2,50 Kč

Nahoru Odpovědět

27.1.2016 18:12