시간 복잡도: 알고리즘의 수행시간

입력 N을 기준으로 수행시간을 평가하는 다양한 방법이 존재한다.

• 빅 세타(Average Case): 평균 시간
• 빅 오 (Worst Case): 최악의 시간
• 빅 오메가(Best Case): 최선의 시간

주로, 복잡도를 평가할때, 입력의 값을 특정할 수 없기에 최악의 경우로 알고리즘의 복잡도를 평가하게 된다.

위 세가지의 경우 모두다 최고차항만 제외하고 전부 제외시킨다. 컴퓨터의 연산 속도는 매우 빠르기 때문에, 최고차항을 제외한 나머지는 고려대상에서 제외된다.

Ex)

• f(n): n^2 + n + 1 → T(n): O(n^2)

당연하게도 가장 좋은 복잡도를 가지는 것은 n이 상수시간이 걸리는것이 제일 좋다.

그리고 그래프의 증가되는것을 보면 어떤 방식이 제일 안좋은지 직관적으로 알 수 있는데, 고등학교때 배웠던 함수들을 생각해보자.

상수 → logN → N → NlogN → N^2 → … → 2^N → … → N!

공간 복잡도: 알고리즘 수행에 필요한 메모리 양

보조공간과 입력공간을 합친 개념이고, 보조공간은 알고리즘이 실행되는 동안 사용하는 임시공간이다.

int sum(int a[], int n)
{
  int x = 0;		
  for(int i = 0; i < n; i++) {
    x  = x + a[i];
  }
  return(x);
}

이 알고리즘의 공간 복잡도는 다음과 같이 연산할 수 있다.

int arr[n]; 입력공간, 4*n byte

int n; 입력공간, 4 byte

int x; 보조공간, 4 byte

int i; 보조공간, 4 byte

시간복잡도 표기법과 비슷하게, M(n)은 4n+12가 나온다. 하지만, 계수와 최고차항만 남기고 전부 제거하면 O(n)의 공간복잡도를 가지게 된다.

Redis에 구현

코드를 먼저 보자.

#include <iostream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <unistd.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <netdb.h>

int main(int argc, char **argv) {
  // Flush after every std::cout / std::cerr
  std::cout << std::unitbuf;
  std::cerr << std::unitbuf;
  
  int server_fd = socket(AF_INET, SOCK_STREAM, 0);
  if (server_fd < 0) {
   std::cerr << "Failed to create server socket\n";
   return 1;
  }
  
  // Since the tester restarts your program quite often, setting SO_REUSEADDR
  // ensures that we don't run into 'Address already in use' errors
  int reuse = 1;
  if (setsockopt(server_fd, SOL_SOCKET, SO_REUSEADDR, &reuse, sizeof(reuse)) < 0) {
    std::cerr << "setsockopt failed\n";
    return 1;
  }
  
  struct sockaddr_in server_addr;
  server_addr.sin_family = AF_INET;
  server_addr.sin_addr.s_addr = INADDR_ANY;
  server_addr.sin_port = htons(6379);
  
  if (bind(server_fd, (struct sockaddr *) &server_addr, sizeof(server_addr)) != 0) {
    std::cerr << "Failed to bind to port 6379\n";
    return 1;
  }
  
  int connection_backlog = 5;
  if (listen(server_fd, connection_backlog) != 0) {
    std::cerr << "listen failed\n";
    return 1;
  }
  
  struct sockaddr_in client_addr;
  int client_addr_len = sizeof(client_addr);
  std::cout << "Waiting for a client to connect...\n";
  accept(server_fd, (struct sockaddr *) &client_addr, (socklen_t *) &client_addr_len);
  std::cout << "Client connected\n";
  close(server_fd);
  return 0;
}

std::cout << std::unitbuf;
std::cerr << std::unitbuf;

매번 flush로 배설해내는 동작
std::unitbuf : 조작자(manipulator), 스트림을 항상 Flus, 배설하는 행위로 바꿔줌
반대 동작은, std::cout << std::unitbuf;

int socket(int __domain, int __type, int __protocol) noexcept(true) : 소켓을 만드는 시스템콜, 단지 소켓만 만드는거니까, 통신이랑은 관련 없음

domain: AF_INET → 주소 체계(Address Family)

• IPv4: AF_INET
• IPv6: AF_INET6

type: SOCK_STREAM → 통신 방식 결정, TCP, UDP

• TCP: SOCK_STREAM
• UDP: SOCK_DGRAM

protocol: 0 → OS가 TCP를 쓸건지, UDP를 쓸건지 결정

struct sockaddr_in server_addr;
server_addr.sin_family = AF_INET; // IPv$
server_addr.sin_addr.s_addr = INADDR_ANY; // 0.0.0.0
server_addr.sin_port = htons(6379); // 6379포트로 연결, Redis의 기본 포트번호

sockaddr_in 구조체를 초기화 하는 과정이다.

❔

추가로, 네트워크와 cpu는 데이터를 전송하는 순서가 다르다.

네트워크: 빅 엔디안

cpu: 리틀 엔디안

포트번호가 6379라면, [EB][10] 으로 저장된다. Cpu는 이 순서 그대로 쓰지만, 네트워크에선 다음과 같은 순서로 보낸다.

[10] → [EB]
그렇기 때문에, htons로 host to network short를 통해 바꿔줘야 한다.

if (bind(server_fd, (struct sockaddr *) &server_addr, sizeof(server_addr)) != 0) {
    std::cerr << "Failed to bind to port 6379\n";
    return 1;
  }

int bind(int __fd, const sockaddr *__addr, socklen_t __len) noexcept(true)

• fd: 파일 디스크립터 번호
• addr: sockaddr에서 생성한 구조체
• socklen_t: sockaddr 구조체의 사이즈 크기

서버와 바인딩하는 함수이다. 0.0.0.0:6379 로 연결하는 과정을 나타낸다.

서버입장에서 클라이언트가 요청을 받기 위해 소켓 디스크립터를 만들고, 디스크립터에 6379 포트를 넘겨주는 행위가 bind이다.

이제 추가로, 서버를 활성화 시켜서 클라이언트의 요청에 응해주는 함수는 Listen 함수이다.

추가로, 0.0.0.0:6379는 사실 Ip의 doted_decimal이라도 전부 바꿔줘야 한다. htonl로, 근데 안바꾸는 이유는 어차피 다 0이라서 이 예제에서만 쓰지 않는다. 실제로는 써야한다.

IP 주소 (32비트 = 4바이트)

• 예: 127.0.0.1
  • dotted decimal로 쓰지만 내부에서는 4바이트 정수.
  • 리틀엔디안 host에선 01 00 00 7F
  • 네트워크(big-endian)에선 7F 00 00 01
• → 그래서 사실상 htonl() 필요.

int connection_backlog = 5;
  if (listen(server_fd, connection_backlog) != 0) {
    std::cerr << "listen failed\n";
    return 1;
  }

listen 상태를 돌입하기 위해 3-way handshake를 진행하는데, 연결이 진행되면, 대기열을 만들어 대기열 공간에 몇개를 쌓아둘건지 정하는 것이다.

connect_backlog는 5개의 대기열 공간을 만드는 것이다.

#include <iostream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <unistd.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <netdb.h>

int main(int argc, char **argv) {
  // Flush after every std::cout / std::cerr
  std::cout << std::unitbuf;
  std::cerr << std::unitbuf;
  
  int server_fd = socket(AF_INET, SOCK_STREAM, 0);
  if (server_fd < 0) {
   std::cerr << "Failed to create server socket\n";
   return 1;
  }
  
  // Since the tester restarts your program quite often, setting SO_REUSEADDR
  // ensures that we don't run into 'Address already in use' errors
  int reuse = 1;
  if (setsockopt(server_fd, SOL_SOCKET, SO_REUSEADDR, &reuse, sizeof(reuse)) < 0) {
    std::cerr << "setsockopt failed\n";
    return 1;
  }
  
  struct sockaddr_in server_addr;
  server_addr.sin_family = AF_INET;
  server_addr.sin_addr.s_addr = INADDR_ANY;
  server_addr.sin_port = htons(6379);
  
  if (bind(server_fd, (struct sockaddr *) &server_addr, sizeof(server_addr)) != 0) {
    std::cerr << "Failed to bind to port 6379\n";
    return 1;
  }
  
  int connection_backlog = 5;
  if (listen(server_fd, connection_backlog) != 0) {
    std::cerr << "listen failed\n";
    return 1;
  }
  
  struct sockaddr_in client_addr;
  int client_addr_len = sizeof(client_addr);
  std::cout << "Waiting for a client to connect...\n";
  int client_fd = accept(server_fd, (struct sockaddr *) &client_addr, (socklen_t *) &client_addr_len);

  if(client_fd < 0){
    std::cerr << "accept failed";
    return 1;
  }

  std::cout << "Client connected!\n";
  const char* pong = "+PONG\r\n";
  send(client_fd, pong, strlen(pong), 0);
  close(client_fd);
  
  close(server_fd);
  return 0;
}

미션 1. PING 요청이 Redis에 들어오면 PONG 보내기

서버는 listen 상태에 돌입하게 되면, client의 요청을 받으면 닫힌다.

그 요청은 nc localhost 6379 또는 redis-cli가 설치되어져 있다면, redis-cli PING 요청을 하면 된다.

$ nc localhost 6379

또는

$ redis-cli PING

미션2. Redis 서버에서 이전 명령에 대한 응답이 완료되면, 다음 명령을 수신

redis 실습중에 client가 보낸 데이터를 읽어드릴려면, read 시스템 콜을 쓰면 된다.

ssize_t read(int __fd, void *__buf, size_t __nbytes)

fd는 파일디스크립터, buf는 담을 공간(빈 배열 넣으면 된다), 그다음의 입력한 바이트의 크기만 받으면 되는데, 이걸 어떻게 하냐,

일단 클라이언트는 PING\nPING을 보낼건데,

2번의 PING 요청을 보낸다고 생각하면 된다. 일단 clinet가 한번 보내는거니까, 연결은 계속 유지해야 한다.

연결 유지한 상태에서 PING 요청을 2번 처리하면 되는건데, 로직만 짜면 된다.

처음 짠 로직

const char* pong = "+PONG\r\n";

  char buffer[100];
  while(true){
    int bytes_read = read(client_fd, buffer, sizeof(buffer));
    
    for(int i = 0; i<sizeof(buffer); i++){
      if(buffer[i] == '\n')
        send(client_fd, pong, strlen(pong), 0);
    }

    close(client_fd);
  }

이건 말도 안된다, 그냥 \n만 만나면 출력하게 하는거니, 이상할 뿐이다.

로직도 이상하고 그리고 추가로, buffer에 대해서 이해해야 하는데, buffer는 담을 공간이 어느정도인지 알 수 없다. 그걸 고려해야 한다. 최종 완성 코드는 다음과 같다.

std::string acc;
char buffer[100];
const std::string PONG = "+PONG\r\n";
  
while(true){
  ssize_t n = read(client_fd, buffer, sizeof(buffer));
  if (n < 0) { perror("read"); break; }
  if (n == 0) break; // 연결 종료

  acc.append(buffer, n);

  size_t pos;
  while((pos = acc.find('\n')) != std::string::npos) {
    std::string line = acc.substr(0, pos);
    acc.erase(0, pos+1);

    if(!line.empty() && line.back() == '\r') {
      line.pop_back();
    }

    if(line == "PING") {
      send(client_fd, PONG.c_str(), PONG.size(), 0);
    }
  }
}

자 일단, while문 안에 보면 되는데, 읽어들이는 크기는 버퍼니까 알 수 없다.

“PING\nPING”은 9바이트인데, 이게 한번 읽을때, 크기가 어느정도로 올지 모르니, 일단 계속 받는다. 받는데 대신에 n의 값이 0이거나 0보다 작아서 오류 또는 읽어들이는 내용이 없으면 그떄 종료시키면 된다.

아마 대체로 성공할 것이기 때문에, 0의 값을 읽어들이는 경우에 종료할 것이다.

그상태로, 계속 acc에 담아놀것인데, 예를들어서 이렇게 왔다고 치자

1. PIN → PIN
2. G\n → PING\n // 이때 분기문 돈다.
3. P → PING\nP
4. ING → PING\nPING // 이때 분기문 돈다.

그러면, 받을때마다 append 해서 acc에 담아놓으면 된다.

그렇게, pos위치까지 데이터를 계속 받아가면서 계속 삭제해나가면 된다.