알고리즘 최적화: 실제 사례

This post originally appeared on steadbytes.com

인터뷰에서 복잡성(따라서 상대적 성능)을 분석하라는 요청을 받았습니다.
작동하는 프로덕션 소프트웨어에서 추출한 C 코드 조각. 후속 조치로 성능 문제를 식별하고 이에 대한 솔루션을 구현하는 프로세스를 시연합니다.

이 코드는 원래 코드와 관련된 일반적인 문제를 논의하는 사전 인터뷰 시험의 일부로 제공되었습니다. 사전 인터뷰 시험 질문에 대한 솔루션을 게시하지 않을 것이며(코드에 잠재적인 문제가 있을 수 있음) 향후 응시자가 검색할 수 없도록 코드 구조를 변경했습니다. 그러나 핵심 알고리즘은 이 게시물에서 집중할 흥미로운 '실제' 최적화 문제를 나타냅니다.

원래 read_file 알고리즘

이름에서 알 수 있듯이 read_file는 디스크에서 메모리로 파일을 읽습니다. 데이터를 저장
배열과 읽은 총 바이트 수를 반환합니다.

#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <stdlib.h>

#define BUFSIZE 4096

size_t read_file(int fd, char **data)
{
    char buf[BUFSIZE];
    size_t len = 0;
    ssize_t read_len;
    char *tmp;

    /* chunked read from fd into data */
    while ((read_len = read(fd, buf, BUFSIZE)) > 0)
    {
        tmp = malloc(len + read_len);
        memcpy(tmp, *data, len);
        memcpy(tmp + len, buf, read_len);
        free(*data);
        *data = tmp;
        len += read_len;
    }
    return len;
}

알고리즘 복잡성

read_file는 memcpy로 인한 O(n2) 공간 및 시간 복잡성을 가집니다.while 루프 내의 작업:

while ((read_len = read(fd, buf, BUFSIZE)) > 0)
{
    /* allocate space for both existing and new data */
    tmp = malloc(len + read_len);
    /* copy existing data */
    memcpy(tmp, *data, len);
    /* copy new data */
    memcpy(tmp + len, buf, read_len);
    free(*data);
    *data = tmp;
}

이전에 읽은 모든 데이터는 각 반복에서 새 배열로 복사됩니다.

+-+
| |
+-+
 | copy existing data
 v
+-+   +-+
| |   | |
+-+   +-+
 |     |
 v     | read new data
+--+   |
|  | <-+
+--+
 |
 v
+--+   +-+
|  |   | |
+--+   +-+
  |     |
  v     |
+---+   |
|   | <-+
+---+
 |
 v
+---+    +-+
|   |    | |
+---+    +-+
  |       |
  v       |
+----+    |
|    | <--+
+----+

...

성능 문제 식별

알고리즘의 복잡성을 찾는 것은 알고리즘의 성능이 입력 크기에 따라 확장된다는 상대적인 아이디어를 얻는 데 좋습니다. 그러나 이것은 실제 실행 시간과 같지 않습니다. 예를 들어 작은 입력만 수신하는 경우 O(n2) 알고리즘은 문제가 되지 않을 수 있습니다. 최적화를 시작하기 전에 해당 코드는 항상 벤치마킹 및/또는 프로파일링되어야 합니다. 이렇게 하면 문제가 실제로 존재하는지, 제안된 솔루션이 효과적인지 여부를 식별하는 데 도움이 됩니다.

"The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming"

-- Donald Knuth, The Art of Computer Programming

프로그램에 대한 main 진입점은 단순히 read_file를 사용하여 표준 입력에서 읽고 읽은 총 바이트 수를 인쇄합니다.

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <stdlib.h>

#define BUFSIZE 4096

size_t read_file(int fd, char **data);

int main(int argc, char *argv[])
{
    char *data = NULL;

    size_t len = read_file_improved(STDIN_FILENO, &data);

    printf("%ld\n", len);

    return 0;
}

크기가 증가하는 임의로 생성된 텍스트 파일로 프로그램을 실행하면 O(n2) 복잡성이 명확하게 나타납니다.



0.5Gb의 입력 크기는 완료하는 데 1시간 이상 걸립니다!

향상된 알고리즘

read_file의 문제는 반복되는 데이터 복사(각 바이트만 복사)입니다.
한 번 O(n) 복잡성을 줄 것입니다. linked list 을 사용하면 파일에서 읽은 각 청크에 대한 포인터를 순서대로 저장할 수 있습니다. 루프의 각 반복에서 새 노드를 생성합니다. 루프가 종료된 후 연결된 목록을 한 번 순회할 수 있으며 모든 청크가 최종data 배열에 복사됩니다. 의사 코드에서:

typedef struct node_t
{
    char *data; /* chunk of data read from file */
    int len; /* number of bytes in chunk */
    struct node_t *next; /* pointer to next node */
} node_t;

size_t read_file_improved(int fd, char **data)
{
    char buf[BUFSIZE];
    ssize_t read_len;
    size_t len = 0;

    /* build linked list containing chunks of data read from fd */
    node_t *head = NULL;
    node_t *prev = NULL;
    while ((read_len = read(fd, buf, BUFSIZE)) > 0)
    {
        node_t *node = malloc(sizeof(node_t));
        node->data = malloc(read_len);
        memcpy(node->data, buf, read_len);
        node->len = read_len;
        node->next = NULL;

        /* first chunk */
        if (head == NULL)
        {
            head = node;
        }
        /* second chunk onwards */
        if (prev != NULL)
        {
            prev->next = node;
        }
        prev = node;
        len += read_len;
    }

    /* copy each chunk into data once only */
    *data = malloc(len);
    char *p = *data;
    node_t *cur = head;
    while (cur != NULL)
    {
        memcpy(p, cur->data, cur->len);
        p += cur->len;
        cur = cur->next;
    }

    return len;
}

알고리즘 복잡성

연결 목록 작성(node_t 구조체에 대한 오버헤드가 일정하다고 가정)은 O(n)입니다. 파일의 각 바이트는 파일에서 배열로 읽혀지고 다시는 건드리지 않습니다.

    file reads
 +------+------+
 |      |      |
 V      V      V
+-+    +-+    +-+
| | -> | | -> | | ...
+-+    +-+    +-+

상자 사이의 화살표는 연결된 목록 노드 포인터를 나타냅니다

.

연결된 목록에서 data로 청크를 복사하는 마지막 단계도 O(n)입니다. 연결된 목록의 순회 포인터는 O(1)이며 각 청크의 각 바이트는 한 번만 복사됩니다.

함께, 그것은 O(2n) ~= O(n)

성능 비교

각 구현을 벤치마킹하기 위해 main 진입점은 기본적으로 개선된 알고리즘 사용과 원래 알고리즘 사용 간에 전환하기 위해 선택적 --slow 인수를 취하도록 조정됩니다.

int main(int argc, char *argv[])
{
    size_t len;
    char *data = NULL;
    /* default to improved implementation*/
    if (argc == 1)
    {
        len = read_file_improved(STDIN_FILENO, &data);
    }
    /* optionally specify original implementation for comparison purposes */
    else if (argc == 2 && !strcmp(argv[1], "--slow"))
    {
        len = read_file(STDIN_FILENO, &data);
    }
    else
    {
        fprintf(stderr, "usage: read_file [--slow]\nReads from standard input.");
        return 1;
    }
    /* do some work with data */
    printf("%ld\n", len);

    return 0;
}

무작위로 생성된 동일한 텍스트 파일benchmark을 실행하면
매우 명확한 결과:

결론

알고리즘의 복잡성을 이해하는 것은 잘 수행되는 프로그램을 구현하는 데 중요합니다. 그러나 조기 최적화를 방지하기 위해 성능 벤치마크와 결합해야 합니다. 이 게시물에서는 다음을 수행하는 방법을 시연했습니다.

성능 문제 식별

알고리즘의 복잡성 결정

성능이 더 좋도록 알고리즘 재설계

최적화의 유효성 증명

벤치마크 스크립트 및 분석을 포함한 전체 코드는 GitHubhere에서 찾을 수 있습니다.