sort ( 파일 내부 엔트리 )

서버에서 작업을 할때  sort가  필요하면 시스템에서 제공하는 /bin/sort를 주로 사용한다.

빠른지 느린지 성능에 대한 판단없이 그냥 간편해서 사용을 해왔는데

다른 프로그램에서 파일 내부에 있는 엔트리들을 정렬해야 할 필요가 생겨 직접 구현을 해봤다.

간단히 생각나는데로 코딩을 해서 테스트 해봤는데

시스템에 있는 sort와 비교해 3배 정도 시간이 더 걸렸다.

그 동안 별생각 없이 써왔던 sort가 상당히 잘 만들어진 프로그램이라는 생각이 문득 들었고

어떻게 구현됐길래 이런 속도차이가 나오는지 궁금해 소스를 찾아보기로 했다.

http://www.google.com/codesearch#eUA6ue1JOtE/gnu/coreutils/coreutils-4.5.10.tar.gz%7C4rWNV1hf6xo/coreutils-4.5.10/src/sort.c&q=sort%20package:coreutil&type=cs

소스를 깊숙이 파헤치기에는 시간이 많아 소요될것 같아

대략 살펴본 봐로는 파일을 한번만 읽는다는 것이 내가 만든 프로그램과의 속도차이에 주요원인으로 작용했던 것으로 보인다.

내가 처음에 짠 프로그램에서는 라인수를 헤아리기 위해 한번 다시 포인터별로 할당하기 위해 한번

이렇게 두번 파일을 읽는데

이 부분에서 속도 차이가 2배 이상 벌어진것 같다.

그래서 파일을 한번만 읽는 코드로 변경하고 최적화옵션을 주고 컴파일한 바이너리로 테스트 했더니 시스템 sort와 비슷한 속도를 얻었다.

혹시 나중에 또 필요한 일이 생길것 같아 코드도 같아..

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <fcntl.h>

#define DEFAULT_LINE 15

int compare_str( const void *a, const void *b )
{
    return strcmp( *(char**)a, *(char**)b);
}

void print_newline( char *str )
{
    char *r;
    r = str;
    if( *r == '\0' || r == NULL ) return;
    printf("%s\n", str );
}

typedef struct info_line_t
{
    int max;
    int cur;
    char **line;
}info_line_t;


void mark_line( info_line_t* info_line, char *str )
{
    if( *str == '\0' ) return;
    info_line->line[info_line->cur++] = str;
    if( info_line->cur >= info_line->max )
    {
        info_line->max = (info_line->max * 2)+1;
        info_line->line = realloc(  info_line->line, sizeof(char**)*info_line->max );
    }
}

void sort_file( char *filepath )
{
    FILE *fp;
    int i = 0;
    char *p;
    char *buffer;
    struct stat stbuf;
    info_line_t info_line = { DEFAULT_LINE, 0, NULL };

    if(stat( filepath,&stbuf ) == -1)
        return ;

    if((buffer = (char*)malloc(sizeof(char)*((int)stbuf.st_size+1))) == NULL ){
        fprintf( stderr,"cannot allocate memory\n" ); return ;}

    if((fp = fopen( filepath, "r" )) == NULL ){
        fprintf( stderr, "cannot open file(%s)\n", filepath ); return; }

    info_line.line = malloc(sizeof(char**)*info_line.max );

    p = buffer;
    while(( buffer[i] = fgetc( fp )) != EOF )
    {
        if( buffer[i] == '\n' )
        {
            buffer[i] = '\0';
            mark_line( &info_line, p );
            p = &buffer[i+1];
        }
        i++;
    }

    buffer[i] = '\0';
     mark_line( &info_line, p ); 
    fclose(fp);

    qsort( info_line.line, info_line.cur, sizeof(char*), compare_str );

    for( i = 0; i < info_line.cur; i++ )
        print_newline( info_line.line[i] );

    free( buffer );
    free( info_line.line );
}

int main( int argc, char *argv[] )
{
    if( argc != 2 )
    {
        fprintf( stderr,"%s <input> \n", argv[0] );
        return 0;
    }
    sort_file( "input.txt" );
    return 0;
}