팀장 님 께서 EC2 서버 하나 구축해 보라고 하셨다. 기존에 있던 테스트 서버를 기준 삼아서 만들던 와중 RedHat으로 되어 있던 기존 꺼에서 aws linux 바꾸기로 해서 다시 만들려고 하던 와중 실수로 기존 테스트 서버를 터미네이트 시켜 버렸다...

이렇게 터미네이트 되어버린 인스턴스 는 기존에 가지고 있던 root ebs까지 모두 날려버리기 때문에 기존에 스냅샷 이 없다면.. 복구할 방법이 존재하지 않는다.... ㅠㅠ 

설정이 완벽하게 끝난 서버라면 ebs 를 인스턴스 와 분리하던가 아니면 스냅샷 을 찍어 태그네임 박아서 기록해 두고, AMI까지 생성해서 관리한다면 보다 완벽하다. 꼭꼭 꼭 해두자.

어쨌든 구축하면서 했던 삽질 모든 걸 기록해보고자 한다. 

EC2의 기본 세팅은 기존 ami를 사용하지 않고 aws에서 제공해 주는 이미지 템플릿을 사용했다. 

ssh 키 같은거는 기존 pem 파일을 사용하기로 하였으며 docker를 이용해서 기존 디비들을 구축하려고 했다.

1. sudo yum update -y
2. sudo yum install -y docker
3. sudo service docker start

위 스탭 으로 기존 데이터를 업데이트해주고 도커 설치 후 서비스 시작해 주면 된다.

docker pull [mysql,redis,kafka]

docker run --name mysql -e MYSQL_ROOT_PASSWORD=plea2018 -p 3306:3306 -d mysql

docker run -d --name redis -p 6379:6379 redis
docker run --name some-kafka -d -p 9092:9092 confluentinc/cp-kafka:latest

하다 보니 거지 같은 sudo 커맨드를 계속 써야 한다. sudo 코드를 없애기 위해 아래 명령어를 실행해 그룹에 추가해 주자.

sudo usermod -aG docker $USER

mysql부터 외부에서 접속 테스트를 실행하던 중 자꾸 kafka 도커가 상태가 계속 떨어진다... 로그를 확인해 보자.

KAFKA_ZOOKEEPER_CONNECT is required.
Command [/usr/local/bin/dub ensure KAFKA_ZOOKEEPER_CONNECT] FAILED!

위와 같은 에러가 나오고 알아보니 zookeeper의 추가적인 설치와 설정이 필요하다. 왜?

Apache ZooKeeper는 Kafka가 클러스터 환경에서 효율적으로 작동하는 데 필요한 분산 조정 및 관리를 제공하므로 Apache Kafka의 중요한 구성 요소이다. 

그래서 추가적인 zookeper 설치가 필요하다.

그전에 먼저 docker network create kafka-net을 이용해 카프카 용 별도의 네트워크를 설정해 준다.

이렇게 생성된 네트워크를 이용해 주키퍼 컨테이너 와 통신이 가능해진다. 그렇기에 네트워크 를 생성해서 주키퍼와 연결해 준다.

docker run -d --name zookeeper --network kafka-net -p 2181:2181 confluentinc/cp-zookeeper

실행해 주키퍼를 실행해 주면 역시나 바로 죽어버린다. 로그를 확인해 보면 
Command [/usr/local/bin/dub ensure-atleast-one ZOOKEEPER_CLIENT_PORT ZOOKEEPER_SECURE_CLIENT_PORT] FAILED!
주키퍼 클라이언트 포트를 설정해 달라고 한다. 그냥 넣어주자. 한 번에 실행이 되는 적이 없다 아주

docker run -d --name zookeeper -p 2181:2181 -e ZOOKEEPER_CLIENT_PORT=2181 zookeeper:latest

주키퍼 실행 이 되었다면 이제 카프카를 켜주자.

docker run -d --name kafka --network kafka-net -p 9092:9092 e KAFKA_ZOOKEEPER_CONNECT=zookeeper:2181 confluentinc/cp-kafka
음 또 죽는다.

Command [/usr/local/bin/dub ensure KAFKA_ADVERTISED_LISTENERS] FAILED!

카프카 리스너 설정이 안 되어 있어 에러가 발생했다.

docker run -d --name kafka --network kafka-net -p 9092:9092 -e KAFKA_ZOOKEEPER_CONNECT=zookeeper:2181 -e KAFKA_ADVERTISED_LISTENERS=PLAINTEXT://localhost:9092 confluentinc/cp-kafka

이렇게 로컬호스트로 추가 해주었지만 실질적인 연결을 위해서는 hostname or IP address를 저기 로컬호스트에 대신 넣어주어야 하지만 일단 실행이 목표이기 때문에 로컬호스트로 박아주었다.

PLAINTEXT://ec2-xx-xx-xxx-xxx.compute-1.amazonaws.com:9092 이런 식의 주소를 써주어야 한다고 하는데 나중에 테스트가 필요한 부분 같다.

이렇게 실행이 되는가 싶었는데 또 죽는다. ㅋㅋㅋㅋ

이번에 로그를 까보면 가관이다. 용량이 부족하단다 ㅎㅎ

OpenJDK 64-Bit Server VM warning: INFO: os::commit_memory(0x00000000 c0000000, 1073741824, 0) failed; error='Not enough

이걸 해결하기 위해 처음 컨테이너 가 실행될 때 메모리를 제한하는 방법이 있다. "KAFKA_HEAP_OPTS="-Xms100 M"" 100M 만 힙메모리로 지정하겠다는 의미이다. 

docker run -d --name kafka --network kafka-net -p 9092:9092 -e KAFKA_ZOOKEEPER_CONNECT=zookeeper:2181 -e KAFKA_ADVERTISED_LISTENERS=PLAINTEXT://localhost:9092 -e KAFKA_HEAP_OPTS="-Xms100M" confluentinc/cp-kafka

메모리가 아슬아슬하게 도달하고 

이렇게 실행이 되는 걸 볼 수 있다.

팀장님 이 말하시기를 주키퍼 내장된 컴포즈가 있을 텐데 왜 이렇게 어렵게 하냐라고 하신다.... ㅠㅠ 컴포즈 버전으로 다시 해보자.

저위에 주키퍼 다운로드하는 저 명령어 다필요 없이

docker run -d --name kafka johnnypark/kafka-zookeeper

이거만 실행 하면 그냥 돌아간다 ... ㅠㅠ 

카프카 로그를 보면 이렇게 성공적으로 실행이 된다.

자 이제 팀장님의 추가적인 지시사항으로 이 서버는 오전 09 시에 켜지고 18시에 내려가는 서버이다 즉 이 서비스 들을 데몬에 등록해서 실행시켜주어 한다. 이런 팀장님의 의도를 모르고 aws lambda와 aws event bus , cloud formation이나 알아보고 있으니 그냥 하루를 아무것도 하지 않고 날렸다. 

먼저 데몬에 대해 알아보자.

리눅스 시스템이 처음 가동될 때 실행되는 백그라운드 프로세스 일종으로 메모리에 상주하면서 특정 요청이 오면 즉시 대응할 수 있도록 대기 중인 프로세스이다. 바로 가보자.

서비스 작성

cd /etc/systemd/system , 으로 이동해서  원하는이름.service 로 작성해준다.

 

touch docker-init.service 

 

vi docker-init.service

이렇게 적어주고 
서비스 등록 을 해주자. 도커도 다운로드한 거기 때문에 이렇게 서비스 등록이 필요하다.
systemctl start docker.service

systemctl start docker-init.service

위와 같이 작성하면 서버를 끄고 킬떄 마다 매번 명령어 실행 필요 없이 백그라운드에서 자동화 실행이 된다.

명령어를 실행해 등록이 되었는지 다시 한번 확인해 준다.

자 이제 시간에 맞춰 켜지고 꺼지는 자동화를 설정해 주자.

먼저 구조 가 어떻게 되는지 알아야 한다. 

aws_event_bridge에서 특정시간에 이벤트를 발행시키는데 그 이벤트의 대상이 aws_lambda 함수가 된다. 그래서 우리는

람다 함수에 원하는 기능을 작성하고

이벤트 브리지 에는 이벤트 발행 규칙을 정해주면 된다.

aws_lambda를 생성해서 키고 끄는 것을 설정해 보자.

aws_lambda를 가서 생성한다. 노드 파이썬을 권장한다. 웹에서 수정이 가능하기 때문에 편하다.

이렇게 생성하면 자동으로 역할 이 생기게 되는데 iam 으로 가서 json 으로 역할 수정을 해준다.

{
    "Version": "2012-10-17",
    "Statement": [
        {
            "Effect": "Allow",
            "Action": [
                "logs:CreateLogGroup",
                "logs:CreateLogStream",
                "logs:PutLogEvents"
            ],
            "Resource": "arn:aws:logs:*:*:*"
        },
        {
            "Effect": "Allow",
            "Action": [
                "ec2:Start*",
                "ec2:Stop*"
            ],
            "Resource": "*"
        }
    ]
}

태그도 ec2_instance_run_close로 달아주자.

// Ec2 start
import boto3
region = 'ap-northeast-2'
instances = ['당신의 ec2 인스턴스 아이디']
ec2 = boto3.client('ec2', region_name=region)

def lambda_handler(event, context):
    ec2.start_instances(InstanceIds=instances)
    print('started your instances: ' + str(instances))
    
// EC2 stop
import boto3

region = 'ap-northeast-2'
instances = ['당신의 ec2 인스턴스 아이디']
ec2 = boto3.client('ec2', region_name=region)

def lambda_handler(event, context):
    ec2.stop_instances(InstanceIds=instances)
    print('stopped your instances: ' + str(instances))

이렇게 시작과 중지 함수를 각각 생성해서 테스트까지 모두 마무리해야 한다. 실제로 테스트해서 인스턴스 가 켜고 꺼지는지 확인하자.

모두 제대로 동작한다면 이제 aws_eventbridge로 가자

규칙생성에 rule type을 일정으로 정하고 크론으로 지정해주자.

instance _close = 0 18 ?  * MON-FRI * 

instance_open = 0 0 ? * MON-FRI *

UTC로 표기되기 때문에 현지 시간에 맞게 잘 조정하자 ㅠㅠ 
이후 대상 선정을 aws_lambda로 선정하고, 검토 및 생성으로 건너뛰어서 생성해 주자.

각가의 시작과 종료가 각각 설정되어 있는 모습이다.

슬랙에 알림 메시지  보내주는 것도 설정해 주자. 

슬랙에 가서 incoming webhook을 추가한다. (https://api.slack.com/apps/A04T3RM5WNT/incoming-webhooks?success=1)
커스텀하게 앱 만들어서 추가해도 된다.

import boto3
import json
import urllib.request


region = 'ap-northeast-2'
instances = ['당신의 인스턴스 주소']
ec2 = boto3.client('ec2', region_name=region)

webhook_url = '웹훅 url'

def post_slack(argStr):
    message = argStr
    send_data = {
        "text": message,
    }
    send_text = json.dumps(send_data)
    request = urllib.request.Request(
        webhook_url, 
        data=send_text.encode('utf-8'), 
    )

    with urllib.request.urlopen(request) as response:
        slack_message = response.read()

def lambda_handler(event, context):
    ec2.start_instances(InstanceIds=instances)
    post_slack('started your instances: ' + str(instances))

이렇게 작성하고 배포하고 테스트를 눌러보면?

요렇게 서버 다운 하고 올라올 때 이렇게 메시지 가 전송 되는 모습이다.

긴글 읽어주셔서 감사합니다.

나는 언제 LinkedList를 사용했는가? 데이터를 주로 앞에서 삽입하는 경우 즉 queue의 자료구조가 필요했다면 사용한 것 같다. 

linked 연결되 있다는 소리이다. 여기에 는 그렇다면 그래프, 트리 도 포함되어야 마땅하지 않겠는가? 이 두 개의 자료구조 또한 연결된 구조다. 다만 이번 챕터에서 분석하고 성능측정 해볼 것은 다음의 하나의 노드만 포인팅 하는 자료구조를 공부해볼 것이다.

연결 자료 구조는 데이터 하나를 크게 노드라는 단위로 부르고 있으며 노드 안에는 하나의 데이터가 들어있고 다음 노드를 포인팅 하는 주소값이 들어가 있다. 

바로 구현해 보자.

생성자 몇 개 와 toString을 만들어 나의 편의성을 위해 위와 같이 작성했다. 이번에도 역시 숫자의 데이터 값만 받아서 노드를 구상할 생각이다.

지난번에 사용한 인터페이스 그냥 그대로 가져다 사용해도 될 것 같다고 생각한다. 사실 명확하게 떠오르는 생각 이 없다..... LinkedList 본연의 기능보다 오히려 Queue 형태의 자료구조로 더 많이 사용했던 것 같다.

생각보다 사용한 함수들 이 많이 있어서 일단 작성했다. (API DOC을 참고해서 작성)

public interface LinkedListInterface {
    void add(int index,int number);
    boolean add(int number);
    void addFirst(int number);
    void addLast(int number);
    
    boolean contains(int number);
    
    int get(int index);
    int getFirst();
    int getLast();
    
    int indexOf(int number);
    
    boolean offer(int number);
    boolean offerFirst(int number);
    boolean offerLast(int number);
    
    int peek();
    int peekFirst();
    int peekLast();
    
    int poll();
    int pollFirst();
    int pollLast();
    
    int pop();
    void push(int number);
    
    int remove();
    int remove(int index,int number);
    int removeFirst();
    int removeLast();
    
    int set(int index,int number);
    int size();
}

구현

package datastructure.myLinkedList;

import java.util.LinkedList;

public class GuiwooLinkedList implements LinkedListInterface {

    private int total;
    private GuiwooNode first;
    private GuiwooNode last;

    public GuiwooLinkedList() {
        this.total = 0;
        this.first = null;
        this.last = null;
    }

    @Override
    public void add(int index, int number) {
        if(index >= this.size()) throw new IndexOutOfBoundsException();
        if(this.size() == 0 || this.size() == index+1){
            this.add(number);
            return;
        }

        if(index == 0){
            first = new GuiwooNode(number,first);
        }else{
            int count = 0;
            GuiwooNode current = this.first;
            GuiwooNode previous = this.first;
            while(count < index){
                previous = current;
                current = current.next;
                count++;
            }
            previous.next = new GuiwooNode(number,current);
        }
        total++;
    }

    @Override
    public boolean add(int number) {
        if(first == null){
            first = new GuiwooNode(number);
            first.next = first;
            last = first;
        }else{
            GuiwooNode next = new GuiwooNode(number);
            last.next = next;
            last = next;
        }
        total++;
        return true;
    }

    @Override
    public void addFirst(int number) {
        if(this.size() == 0){
            this.add(number);
        }else{
            first = new GuiwooNode(number,first);
        }
    }

    @Override
    public void addLast(int number) {
        this.add(number);
    }

    @Override
    public boolean contains(int number) {
        return this.indexOf(number) >= 0;
    }

    @Override
    public int get(int index) {
        if(index >= this.size()) throw new IndexOutOfBoundsException();
        GuiwooNode current = this.first;
        int cnt = 0;
        while(cnt < index){
            current = current.next;
            cnt++;
        }
        return current.data;
    }

    @Override
    public int getFirst() {
        if(first == null) throw new NullPointerException();
        return first.data;
    }

    @Override
    public int getLast() {
        if(first == null) throw new NullPointerException();
        return last.data;
    }

    @Override
    public int indexOf(int number) {
        GuiwooNode current = this.first;
        int cnt = 0;
        while(current != null){
            if(current.data == number) return cnt;
            cnt++;
            current = current.next;
        }
        return -1;
    }

    @Override
    public boolean offer(int number) {
        try{
            return this.add(number);
        }catch (Exception e){
            return false;
        }
    }

    @Override
    public boolean offerFirst(int number) {
        try{
            this.addFirst(number);
            return true;
        }catch (Exception e){
            return false;
        }
    }

    @Override
    public boolean offerLast(int number) {
        try{
            this.addLast(number);
            return true;
        }catch (Exception e){
            return false;
        }
    }

    @Override
    public int peek() {
        return this.getFirst();
    }

    @Override
    public int peekFirst() {
        return this.getFirst();
    }

    @Override
    public int peekLast() {
        return this.getLast();
    }

    @Override
    public int poll() {
        if(first == null) throw new NullPointerException();
        int value = first.data;
        first = first.next;
        return value;
    }

    @Override
    public int pollFirst() {
        return this.poll();
    }

    @Override
    public int pollLast() {
        GuiwooNode current = first;
        GuiwooNode previous = first;
        while(true){
            if(current.next == null) break;
            previous = current;
            current = current.next;
        }
        previous.next = null;
        return current.data;
    }

    @Override
    public int pop() {
        return this.pollLast();
    }

    @Override
    public void push(int number) {
        this.add(number);
    }

    @Override
    public int remove() {
        return this.pollLast();
    }

    @Override
    public int remove(int index) {
        if(index >= this.size()) throw new IndexOutOfBoundsException();
        if(index == 0) return this.poll();
        else if(index+1 == this.size()){
            return this.pollLast();
        }else{
            int cnt = 0;
            GuiwooNode current = first;
            GuiwooNode previous = first;
            while(cnt < index){
                cnt++;
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
            return current.data;
        }
    }

    @Override
    public int removeFirst() {
        return this.pollFirst();
    }

    @Override
    public int removeLast() {
        return this.pollLast();
    }

    @Override
    public int set(int index, int number) {
        if(index >= this.size()) throw new IndexOutOfBoundsException();
        GuiwooNode current = first;
        int count = 0;
        while(count <index){
            if(current != null) current = current.next;
            count++;
        }
        current.data = number;
        return number;
    }

    @Override
    public int size() {
        return this.total;
    }
}

테스트 코드

package datastructure.myLinkedList;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.BeforeAll;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

public class GuiwooLinkedListTest {
    private GuiwooLinkedList gll;
    private int listSize = 10;
    @BeforeEach
    void init(){
        gll = new GuiwooLinkedList();
        for(int i=1;i<=listSize;i++){
            gll.add(i);
        }
    }

    @Test
    void addBasic(){
        int i = gll.indexOf(10);
        assertEquals(9,i);
    }

    @Test
    void contains(){
        boolean contains = gll.contains(100);
        assertFalse(contains);
    }

    @Test
    void sizeCheck() throws Exception{
        int size = gll.size();
        assertEquals(listSize,size );
    }

    @Test
    void addNumberByIndex() throws Exception{
        gll.add(0,100);
        int i = gll.indexOf(100);
        // 맨 앞에 추가할때
        assertEquals(0,i);
        // 가운데 추가할때
        gll.add(5,500);
        int i1 = gll.indexOf(500);
        assertEquals(5,i1);

        assertEquals(listSize+2,gll.size());
    }

    @Test
    void addFirst(){
        gll.addFirst(10000);
        int i = gll.indexOf(10000);
        assertEquals(i,0);
    }

    @Test
    void addLast() throws Exception{
        gll.add(20000);
        int i = gll.indexOf(20000);
        assertTrue(gll.contains(20000));
        assertEquals(listSize,i);
        assertEquals(listSize+1,gll.size());
    }

    @Test
    void getByIndex() throws Exception{
        int i = gll.get(0);
        assertEquals(1,i);
        int i1 = gll.get(9);
        assertEquals(10,i1);
    }

    @Test
    void getFirst() throws Exception{
        int first = gll.getFirst();
        assertEquals(1,first);
    }

    @Test
    void getLast() throws Exception{
        int last = gll.getLast();
        assertEquals(10,last);
    }

    @Test
    void peek() throws Exception{
        int peek = gll.peek();
        assertEquals(1,peek);
        int i = gll.peekFirst();
        assertEquals(1,peek);
        int i1 = gll.peekLast();
        assertEquals(10,i1);
    }

    @Test
    void poll() throws Exception{
        for(int i=1;i<=listSize;i++){
            int poll = gll.poll();
            assertEquals(poll,i);
        }
    }

    @Test
    void pollLast () throws Exception{
        int i = gll.pollLast();
        assertEquals(10,i);
    }

    @Test
    void removeByIndex () throws Exception{
        gll.remove(5);
        int i = gll.indexOf(6);
        int i1 = gll.get(5);
        assertEquals(i,-1);
        assertEquals(i1,7);
    }

    @Test
    void set() throws Exception{
        gll.set(9,1000);
        int i = gll.indexOf(1000);
        assertEquals(9,i);
    }

}

어제 와는 다르게 apiDoc을 보고 작성했으니 실질적인 비교를 해보자.

먼저 클래스 작성자의 설명을 읽어보자.

doubly-linked list라는 표현을 쓴다. 이중연결 리스트?라고 해석이 되는데 음 그러면 노드의 선언이 잘못되었다. 

노드 내부적으로 필드가 하나 더 추가되어 앞뒤로 탐색이 가능해야 한다. 단방향 리스트 가 되어버린 내 구현체는 반쪽 짜리였다.

어쩐지 함수를 작성할 때마다 매번 역방향 탐색 이 있다면 적어도 50% 이상의 성능향상 이 있다고 생각되던 참이던데 참... 

마저 읽다 보면 arrayList와 동일하게 이 클래스도 동기화 예약어를 사용하지 않는다.

다중 스레드 환경에서 비동기적 수행이 필요하다면 아래와 같은 방식을 권장한다.

Collections.synchronizedList(new LinkedList(...));

읽다 보면 재미있는 설명과 예외가 있다. ConcurrentModificationException 전 회사 다닐 때 마주했던 에러였다.

언제 발생하는가? 리스트를 순회하면서 데이터 수정 을 하게 되면 마주하게 되는 에러이다.

modCount를 비교하면서 순회하게 되는데 이때 modCount 순회와 modCount의 값을 비교하면서 돌게 되는데 이때 숫자가 맞지 않다면 위와 같은 에러를 뱉어낸다. 한 번씩 고의로 에러를 내보면 어떤 의미인지 이해하기 쉽다.

listIterator 의해 수행되는 반복자는 빠르게 위 예외를 터트린다고 한다. 최대한 빠르게 위 에러를 터트리는데, 클래스 작성자는 이 예외에 의존해 프로그램을 작성하지 말라고 말한다. 오직 버그를 확인하기 위해 확인하라고 한다.

즉 동기화되지 않은 동시 수정이 있는 겨우 위와 같은 에러를 빠르게 터트려 주어 사전에 방지해주는 함수 설계가 되어 있지 않을까라고 생각한다. modCount 가 여기서 말하는 빠르게 터트리는 트리거 일 것 같은데 차근차근 함수를 살펴보자.

add(int index, E element)

- 특정 인덱스에 원하는 값을 넣어주는 함수이다

- 나의 구현 : 인덱스 가 현재 사이즈 보다 크거나 같은 경우 예외를 던지고, 제일 앞에 추가할 때 뒤에 추가할 때의 분기를 나누어 주었고 , 사이즈에 따른 분기도 나누어 주었다.

-  총 3개의 함수를 호출한다. (checkPositionIndex, linkLast, linkBefore)

- checkPositionIndex => 말 그대로 들어온 인덱스의 범위를 확인하는 함수이다.

- linkLast => index와 사이즈가 같은 경우 분기를 나눈다. 함수 내부적으로 총 개수에 따라 다시 분기를 나누고 first last 그리고 size를 업데이트해준다.

- linkBefore => 말 그대로 가운데 끼여 주는 함수이다. 확실히 previous 포인터 가 있으니깐 함수가 훨씬 간단한다.

o(n) 만큼 의 시간이 걸릴 것으로 보인다. for loop에 의해 분기를 돌아 index까지 current와 previous 업데이트가 필요하기 때문이다.

node(index)의 함수가 따로 있는데 이건 인덱스에 따른 노드를 반환해주는 함수이다. 
1000줄 이 넘어가는 클래스이다 보니 클래스 작성자도 귀찮았는지 x라는 변수를 선언해서 리턴해준다. ㅋㅋ
클린코드 읽다 보면 변수명에 대해 한 챕터를 사용할 정도로 중요하게 생각하는 거 같은데 작자 가 중간중간 자바 의 몇몇 클래스에 대해 혹평을 내리고는 하는데 이런 것 들도 그의 마음에 들지 않았을 것으로 생각된다.ㅎㅎ

다만 이 이렇게 previous와 next를 동시에 가지고 있다면 total 기준으로 반으로 나눠 가까운 쪽에서 시작한다면 최소 내가 작성한 코드보다 빠를 것으로 예상된다.

add(E e)

- 가장 끝 쪽에 e를 추가해주는 함수이다.

-  나의 구현 : 총 total의 숫자를 증가시켜 주고, 현재 노드가 없는 경우만 판별해 분기를 나눠 주었다. null이라면 first와 tail 모두 동일한 노드이기 때문에 이렇게 분기를 나눠주었다.

- 위에서 사용한 linkLast(e)에 그냥 return true이다.

- 사실 인터페이스 작성하고 클래스 구현을 하면서 이 함수에서 boolean을 리턴하면서 얻게 되는 이득이 뭔지 고민을 많이 해봤다. 도대체 어떤 경우에 false 리턴하는지 몰랐는데... 그냥 여기  클래스 작성자도 true로 박아놨다. ㅎㅎ.. 고민 한 시간이 아깝다...

o(1)의 시간이 걸릴 것으로 예상된다. 왜? tail을 직접적으로 필드 내에 가지고 있기 때문에 바로바로 접근이 가능하다. 고민의 여지없이 상수 시간이다.

addFirst(E e)

- 이번에는 가장 앞쪽에 e를 추가해주는 함수이다.

-  0인 사이즈에 따라 분기를 나눠 위에서 작성한 add(E e)를 이용해 추가해주거나 head를 교체해주거나 단순하다.

- modCount와 size를 증가시켜 주고, linkFirst라는 새로운 함수가 있는데 내가 작성한 것 과 다를 바 없다.

- o(1)의 시간이 소요된다 이유는 위와 동일하다.

addLast(E e)

- 나의 구현 : 끝에 추가하나 add를 이용해서 마지막에 추가하나 별차이를 모르겠다 실제로도 그냥 add 함수를 내부적으로 구현했다.

- add와 동일하게 구현되어 있다 단 차이점이라면 반환값의 유무 정도?

- o(1) add 함수 자체를 들고 와서 사용하기 때문에 이렇게 정했다.

contains(E e)

- e 가 list 안에 존재하는 여부를 반환해주는 함수이다.

- 나의 구현 : 지난번 ArrayList에서 했듯이 indexOf를 이용해 -1을 리턴하면 false를 리턴하는 함수를 작성했다.

- 나의 구현과 동일하게 작성되어 있다. indexOf를 이용해 반환한다.

- indexOf는 loop를 이용해 리스트를 순회하기 때문에 o(n) 시간 복잡도를 소요한다.

get(int index)

- 연결 리스트 이더라도 리스트 본연의 get 이 있어야 한다. index에 따른 값을 반환한다.

- 나의 구현 : index 범위를 확인 후 하나의 currentNode와 count를 지정해 count 가 index에 도달할 때까지 루프를 돈다.

- 확실히 pervious 가 있으니깐 위에서 내가 언급했듯이 index와 전체 크기를 비교해 반 이하라면 front에서 이상이라면 rear로부터 시작한다.

- o(n)이라고 해야 할지 o(lonN) 이라고 해야할지 잘 모르겠다. 어쨌든 o(n) 보다는 빠르다는 생각이 든다. o(1) 보다는 느리지만 o(n) 보다는 빠르기 때문에 o(logN)이라고 생각한다. 

getFirst()

- 함수명 그대로 당연히 첫 번째 Element를 반환한다.

- 나의 구현 : Frist에 해당하는 포인터는 객체 내부에 존재하기 때문에 바로 조회 가능하다.

- null 체크 이후 바로 나와 유사하게 리턴을 때려주는 모습이다.

- 의심 여지없이 o(1) 시간복잡도를 가진다.

getLast()

- 함수명 그대로 마지막 Element를 반환한다.

- 나의 구현 : First와 동일하게 Last 즉 tail 노드 도 가지고 있기 때문에 바로 조회 가능하다.

- 위와 동일하다.

- o(1) 시간 복잡도

indexOf(E e)

- 주어진 오브젝트의 인덱스를 반환하는 함수이다 없다면 -1을 반환하기 때문에 contains에서 활용된다.

- 나의 구현 : 사실 이 함수를 제일 먼저 구현했다. testCode에서 확인을 위해서는 add와 확인 이 필요하기 때문에 먼저 작성했다,

단순하게 while을 이용해 동일한 오브젝트를 만날 때까지 돌린다.

- 나와 동일하게 반복문 한 번의 순회를 통해 동일한 값을 찾아낸다. 다만 null 인 경우 의 분기를 나눠준다. 

- for 문 자체를 정말 깔끔하게 사용했다. 아래와 같은 방식으로 사용했다. 중간 x!= null 이 인상적이다. 

for(Node<E> x = first; x != null; x = x.next){

- 한 번의 순회를 모두 거쳐야 하기 때문에 o(n) 시간복잡도를 의미한다.

// 여기부터 Queue Opertaion이라고 명시되어 있다.

offer(E e)

- 마지막에 요소를 추가한다. 사실 add와 이것의 차이를 둬서 구분하는 이유를 모르겠다 둘 다 동일한 반환값에 동일한 기능을 하는데

- 찾아보니 인터페이스(Queue)의 기능 구현을 위해 작성이 된 코드이다. ㅋㅋ.... 

- 자바 구현 자체도 return add(E e)이다.

- offerFirst, offerLast 전부 동일한 사유이다.

peek()

- 가장 앞에 있는 값을 보여준다. null 체크 후 first의 값을 반환한다.

- peekFirst(), peekLast() 동일하다.

poll()

- 앞에서부터 이번에는 뽑아간다. 즉 인덱스 및 총사이즈가 변경되는 함수이다.

- 나의 구현 : null check 이후 first를 다음 first 로 바꿔주고 바꾸는 과정 중 잠시 데이터를 가지고 있다 리턴한다.

- first 를 받아서 unlinkFirst 함수를 실행한다. 이 함수는 first 자체를 null로 바꿔주는 코드가 있다. 왜? 가비지컬렉션에 도움이 되기 위해 이 코드를 작성했다고 되어있다. 와... 이런 부분까지 신경 쓰는지 몰랐다. 

- 이 함수에서는  놓친 부분이 많다. null을 이용해 gc에 도움을 주고, total의 수도 줄여주지 않았다. 이런 실수를 줄여야 하는데 후...

- o(1) 시간복잡도라고 믿어 의심치 않는다.

- pollFirst(), pollLast() 도 동일하게 구현되어 있다. pollLast()는 unlinkLast 함수이고 first와 동일한 로직이다.

pop(), push()

- stack을 표현하기 위해서 작성된 함수이다. 각각 addFirst , removeFirst 등의 함수를 각각호출한다.

remove(int index)

- 나의 구현 : index 가 0 인경우 혹은 size와 같은 경우는 바로 리턴을 해주는 최적화를 적용했다.

함수 내부적으로 count와 previous, current 3개 의 변수를 두어 index까지 조회하고 previous.next = current.next를 이용해 지워 주었다. 이렇게 보니 이렇게 되면 gc에서 삭제된 current를 즉각 회수하지 않는다. 계속 힙메모리를 차지하고 있는 반쪽 자리이다.

- 위에서 한번 언급한 node(index)를 이용해 해당 노드를 가져온다. 이렇게 해도 되는 이유는? 필드 내부적으로 전 그리고 다음 노드가 있기에 가능한 방법이다. unlink에서 역시나 삭제된 노드는 바로 null 처리를 통해 메모리 최적화가 진행되어 있다.

removeFirst(), removeLast() 모두 위에 언급한 unlinkFirst, unlinkLast를 이용해 사용된다.

사실 LinkedList 클래스 내부적으로 이 위의 함수들의 구현된 사항은 몇 줄 되지 않는다.

list-iterator, 직렬화, clone을 위한 코드가 400줄 이 넘는다. 그중 list-iterator에 대해 말하고 싶다.

위에서 언급한 ConcurrentModificationException 은 이 친구가 뱉어준다.

Iterator 가 만들어진 이후 remove 혹은 add를 이용해 수정을 한다면? 저 위의 에러가 뱉어진다.

checkForComodification을 이용해 modCount와 expectedModCOunt를 비교해 빠르게 에러를 뱉어준다. 위에서 add, remove 함수에서 전체 개수 외에 modCount 도 같이 체크해준 이유가 된다. 

LinkedList , ArrayList 내가 전에 사용하던 느낌이 맞다. 두 클래스 모두 다중 스레드에서는 안전하지 않는다.

무언가 를 추가하고, get()의 사용빈도가 적다? 여지없이 LinkedList를

그게 아닌 get(), set()의 빈도가 높다면 ArrayList의 선택이 타당하다.

CS 적으로 생각해 보자.

ArrayList는 하나의 긴 띠 안에 자료들이 오와 열을 맞춰 정렬되어 있다. 그러나 LinkedList는? 여기저기 흩뿌려져 있다. 하드웨어 적으로 이는 낭비를 의미할 수도 있다. 

다시 말해 속도의 측면 만 이 아닌 공간적 측면을 보더라도 어느 정도의 cost 가 각각 있다. 

Think Data Structures 책에서는 다음과 같이 언급한다.

 

1. 응용프로그램 의 실행 시간이 중요하다.

2. 응용 프로그램의 실행시간이 선택한 자료구조에 의존한다.

3. 증가 차수에 따라 어느 자료구조가 나은지 실제로 예측할 수 있을 만큼 문제크기가 충분히 크다. 

 

즉 작업하는 리스트 가 어마무시하게 크지 않다면 기대하는 성능을 얻기 어려울지도 모른다. 작은 문제에서는 이차 알고리즘 이 선형 알고리즘 보다 빠르기도 하고 선형 알고리즘이 상수시간 보다 빠르기도 하다.

LinkedList를 공부하면서 예전에 잠깐 읽은 블록체인 이 생각난다. 블록체인 또한 현재의 해쉬값 에는 전 해쉬 값이 포함되기 때문에 생각이 났다. 이런 기술에서도 이런 자료구조 가 접목 되어 있는 부분이 있어 자료구조 의 명확한 이해가 보다 중요해지는 거 같다.

그리고 최근 읽은 블로그 글이 생각난다.  C++, C 등의 언어가 다시 떠오르고 있다고 한다 왜? 클라우드 서비스를 이용하는 최신 서비스 들은 메모리의 성능, 하드웨어의 사용 은 즉각적인 비용으로 청구되기 때문에 이에 대한 최적화를 위해 migration 진행하는 곳도 많다는 Medium 블로그 글을 읽은 적이 있다. 

GC의 최적화 보다 메모리 관리를 직접 하는이 언어 들은 어느 정도 의 큰 데이터를 다뤄야 다른 언어에서 넘어갈 만큼 의 효율이 있는지도 궁금하다. 책에서는 어느정도 큰 데이터를 다루지 않는다면 유의미한 성능을 얻기 어렵다고 말한다. 그렇다면 다시 말해 그만큼 jvm 메모리에서 들고 있어줘야 한다는 소리인데. 이런 경험을 해보려면 도대체 얼마나 많은 양의 리스트를 들고 있어야 하는지 느낌도 없다.

이번 공부를 통해서 나름의 ArrayList와 LinkedList의 사용의 내 나름의 기준이 세워졌다. 전에 생각하던 이유에 몇 개 더 추가되진 않은 것 같지만 이렇게 java의 코드를 이렇게나마 볼 수 있어 좋은 시간을 보냈다.

코드 전문

특정 자료구조가 필요할 때 배열의 길이가 명확하지 않다면 주로 arrayList를 사용했다.
데이터를 앞에서부터 넣는다고 한다면 linkedList를 사용했다. (최신순으로 Queue의 느낌이 필요하다면)

깊이 있게 공부해 보고 싶어서 내가 제일 사용을 많이 하는 이 2개부터 파보려고 한다. 저 2가지 이유 이외에 보다 명확한 이유와 나 자신을 설득시키기 위해 오늘 공부해본 걸 작성해보고자 한다.

ArrayList를 그냥 내가 생각하는 느낌대로 Class를 작성해 구현해 보자.

(E 타입을 받아 제네릭 하지 않게 그냥 단순 숫자 배열로 만 작성해 보자.)

package datastructure;

public interface ArrayListInterface {
    // 뒤에부터 추가
    boolean add(int num);
    // 인덱스 에 의한 추가
    boolean add(int num,int idx);
    // 처음 발견한 숫자 삭제
    boolean removeByNum(int num);
    // 인덱스 에 의한 삭제
    boolean removeByIdx(int idx);
    // 인덱스 로 값 가져오기
    int get(int idx);
    boolean isEmpty();
    boolean contains(int num);
    int size();
}

ArrayList라고 하면 이 정도로 내가 제일 많이 사용하는 것 같다.

구현

package datastructure;

import java.util.Arrays;

public class GuiwooArrayList implements ArrayListInterface{
    private int[] guiwoo;
    private int total;

    public GuiwooArrayList() {
        this.guiwoo = new int[10];
        this.total = 0;
    }
    @Override
    public boolean add(int a){
        expendArray();
        guiwoo[total++] = a;
        return true;
    }

    @Override
    public boolean add(int num, int idx) {
        if(idx >= this.size()) throw new ArrayIndexOutOfBoundsException();
        expendArray();
        int[] temp = new int[this.size()-idx-1];
        System.arraycopy(guiwoo,idx,temp,0,temp.length);
        System.arraycopy(temp,0,guiwoo,idx+1,temp.length);
        guiwoo[idx] = num;
        total++;
        return true;
    }
    private void expendArray(){
        if(this.size() == guiwoo.length){
            int[] next = new int[this.size()*2];
            System.arraycopy(this.guiwoo,0,next,0,guiwoo.length);
            guiwoo = next;
        }
    }

    @Override
    public boolean removeByNum(int num){
        int idx = -1;
        for(int i=0;i<this.size();i++){
            if(num == guiwoo[i]){
                idx = i;
                break;
            }
        }
        return this.removeByIdx(idx);
    }
    @Override
    public boolean removeByIdx(int idx){
        if(idx == -1) throw new IllegalArgumentException("없어요");
        int[] temp = new int[this.size()-idx-1];
        System.arraycopy(guiwoo,idx+1,temp,0,temp.length);
        System.arraycopy(temp,0, guiwoo,idx,temp.length);
        total--;
        return true;
    }
    @Override
    public int get(int idx){
        if(idx >= this.size()){
            throw new ArrayIndexOutOfBoundsException("허용 인덱스 범위  초과");
        }
        return this.guiwoo[idx];
    }
    @Override
    public boolean isEmpty(){
        return this.size() == 0 ;
    }

    @Override
    public boolean contains(int num) {
        for(int target : guiwoo){
            if(target == num) return true;
        }
        return false;
    }

    @Override
    public int size(){
        return this.total;
    }
    public String toString(){
        return Arrays.toString(this.guiwoo);
    }

}

테스트

package datastructure;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

class GuiwooArrayListTest {
    @Test
    void addTest(){
        int target = 11;
        GuiwooArrayList guiwoo = new GuiwooArrayList();
        for (int i = 0; i < target; i++) {
            guiwoo.add(i);
        }
        Assertions.assertSame(target,guiwoo.size());
    }

    @Test
    void addNumByIdx(){
        int targetNum = 100;
        int targetIdx = 5;
        GuiwooArrayList guiwoo = new GuiwooArrayList();
        for (int i = 0; i < 5; i++) {
            guiwoo.add(i);
        }
        Assertions.assertThrows(ArrayIndexOutOfBoundsException.class,
                ()->guiwoo.add(targetNum,targetIdx));
    }

    @Test
    void addNumByidx(){
        int targetNum = 100;
        int targetIdx = 2;
        GuiwooArrayList guiwoo = new GuiwooArrayList();
        for (int i = 0; i < 5; i++) {
            guiwoo.add(i);
        }
        guiwoo.add(targetNum,targetIdx);
        Assertions.assertEquals(guiwoo.get(targetIdx),targetNum);
        Assertions.assertEquals(guiwoo.size(),6);
    }

    @Test
    void removeTestByNumber() throws Exception{
        int target = 11;
        GuiwooArrayList guiwoo = new GuiwooArrayList();
        for (int i = 0; i < target; i++) {
            guiwoo.add(i);
        }
        guiwoo.removeByNum(6);
        Assertions.assertSame(guiwoo.size(),target-1);
        guiwoo.add(15);
        Assertions.assertSame(15,guiwoo.get(guiwoo.size()-1));
    }

    @Test
    void removeByIdx(){
        int target = 11;
        GuiwooArrayList guiwoo = new GuiwooArrayList();
        for (int i = 0; i < target; i++) {
            guiwoo.add(i);
        }
        guiwoo.removeByIdx(6);
        Assertions.assertSame(7,guiwoo.get(6));
    }
}

스프링 부트가 아닌 그냥 자바 프로젝트라서 라이브러리에 junit을 추가해줘서 테스트 코드를 돌렸다.

나름 예쁘게 작성해보고 싶어서 30분 정도 투자해서 코드를 작성한 것 같다.

특별할 것 없이 최초 생성 시 10 개의 배열 사이즈를 고정해서 사용하는 로직이다. 배열의 범위가 가득 찾을 때 확장을 시켜주는 로직이다.

이중 System.arrayCopy를 정말 많이 사용했는데 한번 살펴보자.

먼저 설명을 읽어보자.

length의 숫자만큼 src에서 가져와 dst로 복사한다.라는 첫 번째 문단이 있고 두 번째 문단을 보면 내 코드의 문제점 이 보인다.

동일한 src와 dst를 참조할 경우 자체적으로 copy를 실시해 내부적으로 수행이 된다는 의미이다. 

즉 제거할 때 capacity의 변화가 없는 경우 라면 나의 코드처럼 temp 변수를 사용할 이유가 없어지는 것이다.

removeByIdx의 함수만 수정 후 테스트를 돌려보자.

이렇게 테스트 가 잘 통과되니 기분이 좋다.

계속해서 arrayCopy를 읽어보자. 어느 경우에 안되는지 에 대한 예시를 들어주고 있다. 배열이 아닌 경우, 인덱스 의 숫자가 - 인 경우 등등 (ArrayStroeException, IndexOutOfBounds,...) 

@IntrinsicCandidate

함수를 보면 IntrinsicCandidate 어노테이션과, native라는 생전 처음 보는 친구들이 달려있다. 살펴보자.

instrinsic 내장함수 란 각 언어마다 컴파일러, 혹은 인터프리터 등이 있는데 이 두 친구들이 특별하게 핸들링하는 함수들을 지칭한다.

즉 최적화된 내장함수들을 의미한다는 소리이다.

다시 말해 low 한 레벨 어셈블리 어 같은 언어로 jvm에서 호출하는 것을 의미하는 것 같다. 

다양한 글들을 읽어보면 significant performance benefits이라고 한다. 하나의 테스트를 예로 보여주는데 sqrt를 100k 번 하는 클래스 호출 함수와 내장 함수 의 속도 비교를 보여주는 데 무려 35%가량의 속도 차이가 발생한다.

심지어 JVM 마다 호출하는 경우가 있고 아닌 경우도 있다고 한다. 즉 저 어노테이션 이 있으면 low level 코드를 불러 최적화된 성능을 보여준다는 소리임과 동시에, 다른 JVM, OS 등에서 실행했을 경우 다른 성능을 보여줄 수 있다는 의미이기도 하다. 

조심해서 사용해야 할 이유가 있다는 소리이다. 이런 low level 문제가 발생된다면 버그 찾기가 정말 어려워질 것으로 보인다. 

한 블로그 포스팅에서는 우리가 종속성 및 런타임을 최신 상태로 유지해야 할 이유라고 말한다.

native

java native interface에서 구현된 함수를 지칭할 때 이 예약어를 사용한다.

C로 작성한 main에서 호출해보려고 이것저것 시도하다가 실패했다. 추후 go 언어로 함수하나 작성해서 컴파일해서 해볼 예정이다.

dll 파일 혹은 so 확장자의 파일이 필요하고 이걸 lib에 추가해야 System.load 가 가능한 것으로 보이는데 추후 도전해보자 오늘 목표로부터 너무 멀어졌다.

위와 같은 방식으로 arrayList를 구현해 보았다. 실제 구현된 코드를 보면서 차이점을 한번 살펴보자.

ArrayList를 가서 읽어보자.

가장 첫 줄에 List 인터페이스 의 크기조절 이 가능한 자료구조라고 설명 되어 있다. null을 포함한 모든 object를 받을 수 있으며 size manipulating 한다고 작성되어 있다. vector 자료구조 와 다른 점이라고 한다면 단순 동기화를 지원하지 않는다는 점이다.

저 단순한 동기화 지원하지 않는 것 때문에 arrayList의 자료구조 가 더 생긴 건가 라는 의문이 생긴다.

찾다가 흥미로운 글이 있어 작성한다. arrayList와 vector의 차이점 중 뚜렷한 부분 중 하나는 바로 최적화 부분인데 확장을 함에 있어

arraylist는 >>1 이 연산자를 이용해 50% 를 확장, vector는 100% 를 확장한다.

Synchronized 동기화는 좋은 작업인가 에 대한 의문점을 가질 필요가 있다. 물론 동기화 가 보장된다면 좋다고 생각할 수 있다. 그러나 동기화를 하는 데 있어 비용이 든다. 시간 혹은 메모리가 이 말은 즉 느리다는 소리다. 지난번 스트링 버퍼와 스트링 빌더 의 차이에서 볼 수 있듯이 동기화에 드는 비용은 커지면 커질수록 확연한 속도차이가 발생한다.

단일 스레드 의 경우 이런 동기화 비용을 지불할 필요도 없을뿐더러 위와 같은 확장성에 있어서도 불필요한 소요가 생긴다.

이런 부분에서 본다면 내가 작성한 커스텀 arrayList 매번 *2 만큼 확장하는데 말할 것도 없이 최적화가 필요한 부분이다.

이런 부분 때문에 새로운 프로젝트 라면 항상 arrayList를 사용할 것을 권장한다.

동기화 부분 은 컬렉션 함수로 아래와 같이 제공되어 arrayList 또한 동기화 작업을 진행할 수 있다.

Collections.SynchronizedList(arrayList);

add(int n) vs add(E e)

동일한 방법으로 뒤에 추가하면서 total size를 이용해가면서 추가한다. 사이즈 가 같다면 grow()라는 함수를 이용해 capacity를 증가시켜 준다. 이렇게 뒤로 항상 추가를 하게 된다면 평균 constant 시간 즉 o(1)의 시간 값을 소모한다고 판단해도 좋을 것 같다. 

왜? 이미 증가한 배열에 [total++] 이런 식으로 디렉트로 넣어주면 된다. 

*2 만큼의 사이즈 증가로 인한 속도의 차이가 궁금하니 100k 기준으로 테스트 코드를 돌려보자.

몇 번을 돌려도 그렇게 유 의미한 차이는 나지 않는다. 동일한 로직을 이용했기 때문인가 최적화 부분 에서 의 차이를 검증하기 위해

BenchMarkTest를 이용해 보자.

이렇게 벤치마크 추가해 주고(jmh.core, jmh.generator.annprocess) 

간단한 클래스 만들어서 돌려주자. (추후 benchmark 블로그 포스팅도 하겠다.)

package datastructure;

import org.openjdk.jmh.annotations.*;

import java.util.ArrayList;
import java.util.concurrent.TimeUnit;

@BenchmarkMode(Mode.AverageTime)
@State(Scope.Thread)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 10)
@Fork(1)
@Measurement(iterations = 100)
public class GuiwooBenchMark {

    @Param({"10","1000000"})
    public int size;

    @Benchmark
    public void arrayList(){
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
    }
    @Benchmark
    public void arrayListCustom(){
        GuiwooArrayList list = new GuiwooArrayList();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
    }
}

mili 초에서 차이가 별로 없기에 나노 초 재확인했다. 여전히 나의 custom list 가 더 빠른 것이 확인된다. 

grow()와 expend() 함수 의 최적화 차이 여부로 판별된다. 즉 최적화 간에 호출되는 함수 들에 따라 arrayList의 함수가 더 느리다는 결론이 나왔지만 아직 찝찝하다.

add(E el, int idx)

다만 이렇게 인덱스에 의해 추가가 되는 경우는 생각을 해보아야 한다. 중간 인덱스에 끼이면 arrayCopyOf를 사용해 중간에 추가해서 밀어 넣어주는 방식이다. 중간검증을 통해 grow 여부를 판별하고, 밀어 넣어주기 때문에 copy 될 배열의 for loop 한번 돌 시간이 필요하기 에 o(n) 시간이 소요된다.

get(int idx)

그렇다면 다시 말해 이렇게 get으로 뽑아온다면? 배열에서 디렉트로 뽑아오는데 당연히 o(1)의 속도를 보여준다. 

isEmpty(), size()

이 두 친구 들은 클래스 내부적으로 필드를 가지고 있어 바로 호출하면 되기 때문에 o(1)의 속도를 보여준다.

remove(E el)

내가 작성한 것과 동일하게 최초발견된 오브젝트를 삭제한다. object 찾는 for loop 한번, 지우는 로직을 위해 arrayCopy 한번 

통상 o(n) 시간복잡도를 가질 것으로 보인다.

remove(E el, int idx)

o(n) 시간복잡도를 가질 것이다. for loop을 이용해 탐색, arrayCopy를 통해 밀어줄 것들 복사해서 밀어준다면 동일한 시간복잡도가 나와야 한다. 

contains(E el)

o(n) 시간복잡도를 가질 것이다. for loop을 이용해 탐색을 한다 다만 흥미로운 점은 arrayList 상에서는 indexOf(E el)을 이용해 > 0을 이용해 반환 값을 결정한다.

위에 구현한 함수 상에서 비슷한 로직을 이용해 arrayList 함수 또한 구현되어 있다. 이외에 궁금한 게 있으니 api documentation을 보자 가독성이 20000배 좋다.

놓친 부분으로는 addAll, forEach(), iterator(), etc... (https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/ArrayList.html)

list의 capacity 즉 size 최적화를 위한 trimToSize 도 존재한다. 신기한 함수다. 얼마큼 유동적인 listSize를 운용해야 메모리 낭비를 줄이기 위해 이 함수를 사용할지 느낌조차 없다.
(추가적으로 검색해보니 늘어난 배열에 대해서 가바지 컬렉터 에서 수거하거나, 줄이는 신비한 묘책이 없기때문에 이러한 함수가 제공된다.)

다만 웃긴 점이 하나 있는데 retainAll이라는 함수에서는 파라미터로  받는 컬렉션을 제외한 나머지를 삭제한다. 이때 batchRemove()라는 함수이름을 사용하지만, addAll 은 이런 게 없어서 아쉬웠다. removeAll, retailAll 이 2 경우 모두 사용하기 위해서 이렇게 함수로 뺀 것처럼 보이지만. 아쉬운 부분이긴 하다.

ArrayList 하나 알아보기 위해서 이렇게 시간을 오래 들여서 보니 부족한 게 너무 많아서  어디부터 손봐야 할지 모르겠다.. 

어렴풋이 나마 느꼈던 것이 맞았다는 기분이 들어 좋았고, vector 같은 쓰면 안 되는 이유, synchronized 하지 않는 이유 등 모른 부분을 보다 명확히 알게 돼서 나름 보람찬 공부였다.

상수시간 을 가지는 add, size 등 을 자주 사용하게 된다면 비교할것도 없이 ArrayList 를 사용하면 된다. 

그게 이 ArrayList 자료구조 가 의 존재 이유라고 생각된다.

치고 있을 사람들 을 위해

-- use guiwoo;
create table Accounts (
	account_id serial primary key,
    account_name varchar(20),
    first_name varchar(20),
    last_name varchar(20),
    email varchar(100),
    password_hash char(64),
    portrait_image blob,
    hourly_rate numeric(9,2)
);

create table BugStatus(
	status varchar(20) primary key
);

create table Bugs(
	bug_id serial primary key,
    date_reported date not null,
    summary varchar(80),
    descriiption varchar(1000),
    resolution varchar(1000),
    reported_by bigint unsigned not null,
    assigned_to bigint unsigned,
    verified_by bigint unsigned,
    status varchar(20) not null default 'NEW',
    priority varchar(20),
    hours numeric(9,2),
    foreign key (reported_by) references Accounts(account_id),
    foreign key (assigned_to) references Accounts(account_id),
    foreign key (verified_by) references Accounts(account_id),
    foreign key (status) references BugStatus(status)
);

create table Comments(
	comment_id serial primary key,
    bug_id bigint unsigned not null,
    author bigint unsigned not null,
    commet_date datetime not null,
    comment text not null,
    foreign key (bug_id) references Bugs(bug_id),
    foreign key (author) references Accounts(account_id)
);

create table Screenshots(
	bug_id bigint unsigned not null,
    image_id bigint unsigned not null,
    screenshot_image blob,
    caption varchar(100),
    Primary key (bug_id,image_id),
    foreign key (bug_id) references Bugs(bug_id)
);

create table Tags(
	bug_id bigint unsigned not null,
    tag varchar(20) not null,
    primary key (bug_id,tag),
    foreign key (bug_id) references Bugs(bug_id)
);

create table Products(
	product_id serial primary key,
    product_name varchar(50)
);

create table BugsProducts(
	bug_id bigint unsigned not null,
    product_id bigint unsigned not null,
    primary key (bug_id,product_id),
    foreign key (bug_id) references Bugs(bug_id),
    foreign key (product_id) references Products(product_id)
);

싱글턴 패턴 이란 ?

Singleton is a creational design pattern that lets you ensure that a class has only one instance, while providing a global access point to this instance.

참조

코드 전체적으로 인스턴스 의 접근을 제공할때, 항상 하나의 인스턴스 만을 반환 해주는 것을 싱글턴 으로 정의한다.

왜 필요할까?

- 사실 코드를 작성해 오면서 문제가 되었던 부분이 없었다 이러한 디자인 패턴이 없어도, 그러나 나 자신도 모르게 썻던 기억이 있을 것이다. 예를 들어보자 피자를 좋아하니 피자를 구워보자.

우리 코드에는 오븐이 하나밖에 없다고 가정을 해보자. 그렇다면 우리 오븐에 쿠킹 을 하기 전 분명 전역변수를 이용하던 정적 필드 를 이용하던 어떻게든 현재 오븐상태 를 알아오고 그에 대한 검증이후에 도우 를 넣을것 아닌가 ? 비슷하다 이런 느낌을 좀더 우아하게 정의 내린것이 싱글턴 패턴이다. 필요한 이유에 대한 정의를 보자.

Ensure that a class has just a single instance. Why would anyone want to control how many instances a class has? The most common reason for this is to control access to some shared resource—for example, a database or a file.

1. 가장 일반적인 이유가 공유된 자원 의 접근을 제어하기 위해 사용된다고 한다  예 를든다면 데이터베이스 혹은 파일 에서

Provide a global access point to that instance. Remember those global variables that you (all right, me) used to store some essential objects? While they’re very handy, they’re also very unsafe since any code can potentially overwrite the contents of those variables and crash the app.

2. 매우 편리하게 전역 변수를 사용해서 공유자원 에 접근을 한다면, 어느 코드(어플리케이션 이 실행되는 데 필요한 모든 코드 들) 나 잠재적으로 이 전역변수를 덮어 사용할수 있어 앱에 문제를 야기한다고 한다.

오븐에 예로 들었던 사실중 하나가 사실은 앱에 문제를 야기할수 있다. 왜? 오븐 사용 전 에 검증 뿐만 아니라, 도우 를 만들때도, 토핑 을 얹을때도 무언가 잡다한 어떤한것을 할때도 모든 함수에 저 전역변수 에 접근하고 덮어서 사용할수 있다 라고 이해가 된다.

이런 잠재적인 이유를 알았으니 한번 적용해보자 도대체 어떻게 하면 될까 ? 제공 되는 예시를 내가좋아하는 피자 오븐으로 덮어서작성해보자.

코드보기

public class Testing {
    public static void main(String[] args) throws InterruptedException {
        System.out.println("피자도우 를 만들고 오븐에 넣어보자.");
        Oven singleton = Oven.getInstance(true);
        Oven anotherSingleton = Oven.getInstance(false);
        System.out.println(singleton.isUse);
        System.out.println(anotherSingleton.isUse);
    }
}

public class Oven {
    private static Oven instance;
    public boolean isUse;

    private Oven(boolean isUse) throws InterruptedException {
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        this.isUse = isUse;
    }
    public static Oven getInstance(boolean isUse) throws InterruptedException {
        if(instance == null){
            instance = new Oven(isUse);
        }
        return instance;
    }
}

보이는가? 오븐을 두번 생성해서 넣어도 우리는 현재 오븐 의 상태 값을 받는다. 

자 그러면 문제가 될 상황인 서로다른 방에서 피자를 여러개 만들어서 오븐을 가져온다면 ?  어떻게 해야할까 ?  싱글턴에서는 그러면 어떻게 핸들링을 할까 ?

코드보기

package Singleton;

public class Testing {
    public static void main(String[] args) throws InterruptedException {
        Thread threadFoo = new Thread(new Hawaiian());
        Thread threadBar = new Thread(new Margherita());
        threadFoo.start();
        threadBar.start();
    }

    static class Hawaiian implements Runnable {
        @Override
        public void run() {
            Oven singleton = null;
            try {
                singleton = Oven.getInstance(true);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            System.out.println(singleton.isUse);
        }
    }

    static class Margherita implements Runnable {
        @Override
        public void run() {
            Oven singleton = null;
            try {
                singleton = Oven.getInstance(false);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            System.out.println(singleton.isUse);
        }
    }
}

홀리몰리 ? 원하던 결과 값이 아니다 공유된 오븐이 아닌 각자 새로운 오븐을 생성한다. 이렇게 된다면 어떻게해야 동일한 오븐을 타켓할수 있을까 ? volatile 과, 싱크로나이즈 하나 띡  인스턴스 생성하는 부분에 묶어주면 된다. 

Java volatile이란?

• volatile keyword는 Java 변수를 Main Memory에 저장하겠다라는 것을 명시하는 것입니다.
• 매번 변수의 값을 Read할 때마다 CPU cache에 저장된 값이 아닌 Main Memory에서 읽는 것입니다.
• 또한 변수의 값을 Write할 때마다 Main Memory에 까지 작성하는 것입니다.

코드보기

package Singleton;

public class Oven {
    private static volatile Oven instance;
    public boolean isUse;

    private Oven(boolean isUse) throws InterruptedException {
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        this.isUse = isUse;
    }
    public static Oven getInstance(boolean isUse) throws InterruptedException {
        synchronized(Oven.class) {
            if (instance == null) {
                instance = new Oven(isUse);
            }
            return instance;
        }
    }
}

똑같은 결과값을 반환하고 똑같은 오븐을 참조하기 시작했다. 그런데 굳이 이렇게 까지 해서 동기화를 시켜야하나 싶은 생각이 들기 시작한다. 이때 쉽게 작성하기 위해서 Jvm 을 이용하는 방법이 있다. 오븐 클래스 안에 이너클래스 로 스테틱을 생성하게 되면 Jvm 실행 시점에 클래스 로더에 올라가 jvm 이 나쁜 쓰레드로 부터 보호해준다. 바로 가보자.

코드보기

package Singleton;

public class Oven {
    public boolean isUse;
    private Oven(){}
    private static class OvenKeeper{
        private static final Oven instance = new Oven();;
    }
    public static Oven getInstance(boolean isUse){
        Oven o = OvenKeeper.instance;
        o.isUse = isUse;
        return o;
    }
}

스레드 가순서가 불안정해서 동일한 값을 매 실행마다 주진 않지만 각자 동일한 객체를 가르킨다. 오우 홀리 static 을 활용한 jvm 에 올리는 방법도 좋은거 같다. 

이 외에 눈에 띄는 방법중 하나인 enum 을 이용하는 방법이다. 

To overcome this situation with Reflection, Joshua Bloch suggests the use of Enum to implement Singleton design pattern as Java ensures that any enum value is instantiated only once in a Java program. Since Java Enum values are globally accessible, so is the singleton. The drawback is that the enum type is somewhat inflexible; for example, it does not allow lazy initialization.

이넘 또한 전역적으로 접근이 가능하고 한번만 인스턴스화 되기에 조슈아 씨는 이 방법을 추천한다고 합니다. 플랙시블 하지않아 지연 로딩을 허가하지 않는다는데 바로 가보자

코드보기

package Singleton;

public enum Oven {
    INSTANCE;
    public static boolean isUse;

    public static Oven getInstance(boolean change){
        isUse = change;
        return Oven.INSTANCE;
    }
}

와우 ... 제일 간단하면서도 위에 멀티스레드 케이스를 전부 통과한다 왜 ?

Enum은 private 생성자로 인스턴스 생성을 제어하며, 상수만 갖는 특별한 클래스이기 때문이다.

시각적으로 봐도 매우 간단하게 구현이 가능한 부분에서 보면 환상적 이다. 다만 왜 이러한 이넘 타입을 권하는지 알아보자.

일반적인 위에 구현된 싱글톤 패턴 에서는 직렬화 과정에서 싱글톤이 싱글톤이 아닌 매우 이상한 값들을 생성하고 부여한다.

따라서 일반적인 싱글톤에는 implements Serializable 추가해주고 모든 필드에 transient 를 추가해 직렬화 과정에 그대로 넘어가게 설정해 주어야 한다. readResolve() 메서드를 구현하여 현재 싱글톤의 인스턴스를 리턴해주는 이런 불필요한 과정을 거쳐야 한다.

Enum 에는 그런것이 전혀 필요하지 않다. 그냥 다 해준다. 또한 싱글톤 관련하여 검색하다 보면

Using Reflection to destroy Singleton Pattern 이라는 결과를 볼수 있는데 이는 싱글턴 패턴 을 파괴할수 있는 방법을 보여준다.

package com.journaldev.singleton;

import java.lang.reflect.Constructor;

public class ReflectionSingletonTest {

    public static void main(String[] args) {
        EagerInitializedSingleton instanceOne = EagerInitializedSingleton.getInstance();
        EagerInitializedSingleton instanceTwo = null;
        try {
            Constructor[] constructors = EagerInitializedSingleton.class.getDeclaredConstructors();
            for (Constructor constructor : constructors) {
                //Below code will destroy the singleton pattern
                constructor.setAccessible(true);
                instanceTwo = (EagerInitializedSingleton) constructor.newInstance();
                break;
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        System.out.println(instanceOne.hashCode());
        System.out.println(instanceTwo.hashCode());
    }

}

이 코드를 보면 해쉬코드 의 값이 각각 다르게 나온다. 어떻게 ? 리플렉션, setAccesible 이라는 함수를 이용하면 private 생성자 호출이 가능해진다. (반면 이 리플렉션은 하이버네이트 , 스플링에서 정말 많이 사용된다.어노테이션 에서 사용되어진다.)

그러나 enum 싱글턴에서는 이 모든 반례들을 보장해준다. 

만들기 제일 쉬운 Enum 이 최고의 방법이라니..

Enum 싱글턴 은 멀티쓰레드 상황, 직렬화, 리플렉션 을 이용한  싱글턴 부수기 모든 곳에서 방어가 되기 때문에 최고라고 생각한다. 무엇보다 사용하기 정말 쉽지 않은가 쉽고 직관적인게 최고다.

긴글 읽어주셔서 감사합니다.

참조 사이트

디자인 패턴

싱글턴 패턴 파괴

Enum 구현

long beforeTime = System.currentTimeMillis(); //코드 실행 전에 시간 받아오기
        
//실험할 코드 추가
// ex) 
/***/
        
long afterTime = System.currentTimeMillis(); // 코드 실행 후에 시간 받아오기
long secDiffTime = (afterTime - beforeTime)/1000; //두 시간에 차 계산
System.out.println("시간차이(m) : "+secDiffTime);