이번 과제는 Warming-up으로 다음과 같습니다.

integer가 총 천만개가 있는 파일이 있습니다.

이를 불러들여 배열로 만든 후 구간 내 최대값과 그 처음과 끝을 찾는 문제입니다.

구간 내에 음수가 섞여있기에 구간을 크게 잡는다고 하여 좋은 것이 아닙니다.

이를 O(n)의 complexity를 갖는 알고리즘으로 만들어야합니다.

즉, 한 번 수행할 때 1초를 넘기면 안됩니다.

그리고 이를 측정하여 clock수와 수행시간을 내놓아야하며,

상위 5%를 잘라낸 나머지 값들로 평균과 표준편차, boxplot을 구해야합니다.

보고서와 소스 코드를 따로 올리겠습니다.

/*
* Made by Bak JinYeong(2004314081)
* Startday : 2008-09-10
* History
*     2008-09-10
*         I think of the problem.
*         Waiting Input file and example of getting time and clock.
*     2008-09-12
*         I download the file.
*         I See the files and start to make the algorithm.
*    2008-09-14
*        It's holiday. So I'm home in Busan.
*        However I think about this problem,
*        and I can't make the O(n) algorithm.
*        What a sad Story.
*    2008-09-16
*        I make the O(n) algorithm.
*        But I can't write the algorithm to code.
*    2008-09-17
*        I call back the memory of good algorithm.
*        It's similar the my algorithm,
*        but it more simple looking.
*        So I get this algorithm, rewrite the code and test it.
*        I think the result is correct.
*    2008-09-18
*        I don't care space complexity.
*        So I make array variable from file.
*        and I use it.
*        And I add the code to time and clock check.
*    2008-09-18
*        add the code about output.txt file.
*        I can't draw the graph using C.
*        So I write the output in txt file
*        and load from excel.
*    2008-09-19
*        get the means and standard deviation.
*        draw box-plot
*    2008-09-20
*        get the ouput one more.
*    2008-09-21
*        get the output from SKKULUG server.
*        That server did not work getcounter() function.
*        So I modified the code from textbook.
*    2008-09-21(daytime)
*        I don't count the element_index rightly.
*        So I fix it.
*    2008-09-21(night)
*        I change the Max_value variable type int to long double.
*        Thanks to Oseongjun.
*    2008-09-22
*        I change the Max_value variable type lond double to long long int.
*
* blog : http://nosyu.pe.kr
*/
#include <stdio.h> // Standard Input Output header file
#include <stdlib.h> // Standard library header file
#include "clock.h" // clock header file
#include <time.h> // include time library header file

#define INT_NUMBER 10000000 // the number of integer in gen.txt file
#define CHECK_TIMES 3000 // check time

/*
* main function
* argument : void
* return : int
*
* It's main function.
*/
int main(void)
{
    FILE *TxtFileDe; // txt file descriptor
    FILE *OutputFileDe; // Output file descriptor
    int* element_values; // element values in array from txt file
    register int element_index; // element index from array
    int work_times; // work times

    struct  timeval stime, etime; // variable with time check
    double  time_took; // start and stop of times
    double  counter; // count variable

    typedef struct
    {
        int block_head; // start point of block
        int block_tail; // start point of block
        long long int Max_value; // Max value of block
    } Block_struct; // Output struct about block information
    Block_struct Block_Max; // result struct.
    Block_struct Block_Check; // check for the block and next element

    // get the gen.txt file descriptor
    TxtFileDe = fopen("./gen.txt", "r"); // open the gen.txt file
    if(NULL == TxtFileDe) // if open error
    {
        perror("fopen"); // print the message
        exit(2); // end of the program because of error
    }

    // make the output file
    OutputFileDe = fopen("./output.txt", "w");
    if(NULL == TxtFileDe) // if open error
    {
        perror("fopen"); // print the message
        exit(2); // end of the program because of error
    }

    // make array variable.
    element_values = (int *)malloc(sizeof(int) * INT_NUMBER);
    // malloc error check
    if(NULL == element_values) // variable which is returned by malloc
    {
        fprintf(stderr, "Insufficient memory"); // print the error message
        exit(EXIT_FAILURE); // end of the program because of error
    }

    // element from file to array
    for(element_index = 0 ; element_index < INT_NUMBER ; element_index++)
    {
        // load from file to array
        fscanf(TxtFileDe, "%d", &element_values[element_index]);
    }

    // print the subject to output.txt
    fprintf(OutputFileDe,
            "head\ttail\tmax_value\tcounter\ttime(second)\n");

    // Start to iterative work times CHECK_TIMES
    for(work_times = 0 ; work_times < CHECK_TIMES ; work_times++)
    {
        // initialize the variable
        Block_Max.Max_value = 0; // initialize the Max value to 0
        Block_Check.Max_value = 0; // initialize the Max value to 0
        // prepare the count clock
        start_counter(); // counter start
        gettimeofday(&stime, NULL); // Starting Time
        srand48(stime.tv_usec); // set stime to random number

        /*
         * If I have a solution index from 1 to n-1,
         * Then I add the element value at index n and Check block value.
         * Check block is from Max block which
         * I know it or some positive number.
         *
         *
         * If add two things is less than 0,
         * I discard Check block.
         * Because If adding Check block and Max block,
         * it is not larger than Max block.
         * So It will restart.
         *
         *
         * If add two things is more than 0,
         * I update the Check block to add next element.
         * Because it may be larger than Max block. or not.^^
         *
         *
         * Next, I comparison between Check block and Max block.
         * If Check block is larger than Max block,
         * it means Check block is Max block now.
         *
         *
         * I see this algorithm from 'Programming Pearls' page 156.
         * Of course, I've studied it 3 yeasrs ago and rewrite the code.
         */
        for(element_index = 0 ; element_index < INT_NUMBER ; element_index++)
        {
            // If add two things is more than 0
            if((Block_Check.Max_value + element_values[element_index]) > 0)
            {
                // update information Checkbox to add element
                // Check Block's tail update
                Block_Check.block_tail = element_index+1;

                // Check Block's max value update
                Block_Check.Max_value += element_values[element_index];
            }
            else // If add two things is less than 0
            {
                // restart the Check Block.
                // Check Block's head update to next element
                Block_Check.block_head = element_index+2;
                // Max_value is 0.
                Block_Check.Max_value = 0;
            }
            // If Check Block is larger than Max Block
            if(Block_Max.Max_value < Block_Check.Max_value)
            {
                // replace from Check Block to Max Block
                Block_Max.block_head = Block_Check.block_head; // head update
                Block_Max.block_tail = Block_Check.block_tail; // tail update
                Block_Max.Max_value = Block_Check.Max_value;//maxvaule update
            }
        } // end of finding answer for loop
        // get count result
        counter = get_counter(); // get counter
        gettimeofday(&etime, NULL);     // Ending Time
        // I don't know this code.
        // I C&P from gen.c which Developed by Professor Hyoung-Kee Choi.
        time_took = (double)(etime.tv_sec - stime.tv_sec);
        time_took += (double)(etime.tv_usec - stime.tv_usec)/1E6;
        // print the result to output.txt file
        fprintf(OutputFileDe, "%d\t%d\t%lld\t",
                Block_Max.block_head, Block_Max.block_tail,
                Block_Max.Max_value);
        fprintf(OutputFileDe, "%f\t", counter);
        fprintf(OutputFileDe, "%.6f\n", time_took);
    } // end of working for loop

    fclose(TxtFileDe); // close file descripter
    fclose(OutputFileDe); // close file descripter
    free(element_values); // free variable

    // print last value to the display
    printf("head : %d, tail : %d, max_value : %lld\n"
            "counter : %f, time(second) : %f\n",
            Block_Max.block_head, Block_Max.block_tail, Block_Max.Max_value,
            counter, time_took);
    printf("Finish\n"); // print the end of the program message

    return 0; // End of the Program
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.