ARA

우리는 프로그래밍을 하다보면, 한번쯤은 반복문을 사용하게 되는 경우가 있다.

이 때 반복문에서 사용할 변수를 선언하게 되는데, 이 경우 구체적으로 어디에 변수를 선언하면 좋을지 고민하게 된다.

//  1. 반복문 안에 선언하는 경우
public void foo() {
    while () {
        int i = 10;
    }
}

//  2. 반복문 밖에 선언하는 경우
public void foo() {
    int i = 10;
    while () {
    }
}

위의 두 경우를 가지고, 자바에서 각 상황에서 어떤 것이 구조에 있어서 장점을 가지고, 성능에 어떤 영향을 주는지 살펴보고자 한다.

1️⃣ 구조적 장점

우선 구조적 장점으로는 반복문 안에 선언하는 것이 가장 바람직하다.

이유로는 지역변수는 자동 변수이기 때문이다.

지역변수는 stack이라는 메모리 공간에 저장되기 때문에, 스코프 종료와 함께 자동으로 회수된다.

이 때문에 지역변수는 자동변수라는 이름으로 함께 불리기도 한다.

지역변수의 스코프를 제한하면, 메모리를 효율적으로 사용할 수 있으며 다른 스코프에서 참조하여 값이 변하는 걱정도 덜 수 있다.

예를 들어 반복문 밖에 선언한 i 변수는 반복문이 한 사이클을 돌더라도 해당 값이 남아있기 때문에, 이를 참조하는 다른 코드에서 문제가 발생할 여지가 있다.

반대로 반복문 안에 선언한 i 변수는 반복문이 돌 때마다 해당 값을 새로 선언하고, 초기화하기 때문에 잘못된 값이 들어갈 염려가 없다.

2️⃣ 성능

이 부분은 감히 어떤 방식이 더 좋은 지 말하기 어려운데, 그래도 상황별로 나눠서 생각해볼 수는 있겠다.

Stack에 저장되는 변수

stack에 저장될 지역변수라면, 크게 성능 차이가 날만한 부분은 딱히 없을 것으로 생각된다.

굳이 꼽자면, 지역변수가 반복문마다 선언되고 초기화 되는 부분이 반복된다는 부분 일 것이다.

이건 컴파일러 단에서 최적화를 해줘서 성능에 그렇게 큰 영향을 주지 못할 것 같다는 생각이 든다.

(구체적으로 바이트 코드를 까보고, 어셈블리를 봐야 알겠지만은…)

그렇기에 stack에 저장되는 형식의 변수라면 두 방식 역시 성능적인 차이가 크게 의미있을 것 같진 않다.

Heap에 저장되는 변수

다만 heap에 저장될 변수라면 이야기는 다르다.

이 때 위의 코드를 다음과 같이 수정하고 정수형 캐쉬는 없다고 가정한다.

//  1. 반복문 안에 선언하는 경우
public void foo() {
    while () {
        Integer i = 10;
    }
}

//  2. 반복문 밖에 선언하는 경우
public void foo() {
    Integer i = 10;
    while () {
        Integer i2 = i;
    }
}

우선 첫 번째 경우는 매번 반복문에서 새로운 정수형 객체를 생성하는 방식이다 (new Integer())

두 번째 경우는 이미 생성된 정수형 객체를 가르키는 새로운 정수형 변수를 선언하고, 초기화한 것이다.

따라서 엄밀히 말하면 첫 번째 경우와는 다르게 new Integer()를 사용하지 않았기에, heap에 새로운 메모리가 생성되지 않는다.

이 말은 GC의 대상이 되지 않기에, 크게 봤을 때 GC로 인한 성능 저하가 첫 번째에 비해 적다는 뜻이다.

자바에서는 문자열을 생성하는 과정에서도 new 키워드로 생성하냐, 아니면 리터럴로 생성하냐에 따라서 GC 퍼포먼스가 달라질 정도로 주의를 요한다.

과연 적지 않은 수의 반복문으로 객체를 생성하면 GC 성능에 영향이 적다고 말 할 수 있을까?

결론

반복문 내부에 생성되는 변수의 타입과 변수가 레퍼런스 하는 메모리 공간에 따라 권장하는 방법이 달라질 수 있다.

일반적인 원시형 변수를 사용하는 경우에는 코드 가독성 및 코드 구조를 위해 반복문 내부에 선언하는 것을 권장하고,
객체형 변수를 사용하는 경우에는 GC 성능에 영향을 줄 수 있기 때문에, 반복문 밖에서 선언하는 것을 권장할 수 있겠다.

참고자료

• https://okky.kr/questions/322734

PS. 자동 변수가 선언되는 것이 성능에 주는 영향이 적은 지 알려주는 글이 있어서 가져온다.

우선 C언어 같은 경우에는, 일반적인 타입은 이미 해당 크기가 정해져있기 때문에 컴파일 때 얼마만큼 스택에 저장해야할 지 알 수 있다.

따라서 미리 해당 크기만큼 stack에 저장하는 것으로 컴파일러가 최적화 한다면, 그만큼 선언에 필요한 cpu 사이클이 줄어드는 셈이다.

https://stackoverflow.com/questions/7959573/declaring-variables-inside-loops-good-practice-or-bad-practice

자료구조를 공부하다 보니 문뜩 드는 생각이 있다.

stack을 공부하다 보면 수식 표기법인 전위(Prefix), 중위(Infix), 후위(Postfix)의 개념을 배우고, 이를 응용해서 계산기를 만든다.

근데 막상 계산기를 만드는 대부분의 예제는 후위 표기법으로 되어있는 걸 알 수 있다.

전위나 후위 둘 다 괄호도 없고, 연산자 우선순위를 따로 신경 쓸 필요가 없는데 왜 후위표기법만 사용해서 쓰는 건지 궁금해서 찾아봤다. (추가로 이유는 자세히 안 적혀 있어서, 나름대로 생각을 해봤다.)

우선 첫 번째 이유로는 후위 표기법이 다른 표기법에 비해 연산 과정이 쉽기 때문이란다.

내 생각으로 간단한 예제를 만들어봤다.

# 1 + (2 * 3)
# Prefix
+1*23

전위 표기법의 경우 위와 같은 상황에서 우선 stack으로 계산하려면 변수에 +와 1을 올려둔 상태 일 것이다.

하지만 뒤에 2 \* 3을 계산 해야지, 결과를 얻을 수 있는 상황이다.
그렇기에 전위 표기법은 추가적인 연산이 필요한 상황을 고려해야 할 필요가 있다.

# 1 + (2 * 3)
# Postfix
123*+

반면에 후위 표기법은 간단하게 왼쪽에서 오른쪽으로 쭉 읽으면서 stack에 저장하고, 연산자를 만나면 꺼내서 연산하면 된다.
그렇기에 전위 표기법에 비해 훨씬 간단하게 구현할 수 있기 때문에, 이런 차이점이 생긴게 아닐까 싶다.

두 번째 이유는 후위 표기법이 전위 표기법에 비해 적은 괄호를 사용하기 때문이란다.
근데 이건 후위나 전위 둘다 괄호를 사용하지 않는 게 특징인데, 왜 있는 건진 잘 모르겠다..
(혹시 아시는 분은 댓글 달아주시면 감사하겠습니다.)

이러한 이유로 계산기를 만들 때, 전위 표기법보다는 후위 표기법이 조금 더 우위를 가진다는 것 같다.
그럼에도 전위 표기법과 후위 표기법 역시 각각 사용되는 분야가 조금씩 다르고, 그 분야에서 장점이 있다고 한다.

전위 표기법

• 주로 단일 연산자 (Unary Operator)에서 사용되며, 다른 표기법에 의해 연산이 빠름
• LISP이나 Clojure 등의 프로그래밍 언어에서 사용됨

후위 표기법

• 주로 컴파일러에 의한 코드 생성에서 사용됨
• 다른 표기법에 비해 수식 평가(Evaluate)에 수월함

더 깊게 찾아보진 않아서, 구체적인 사항이 더 있을거 같다는 생각이 든다.
나중에라도 다시 궁금해지면, 글 내용에 더 추가해봐야겠다.

출처

• https://www.geeksforgeeks.org/why-do-we-need-prefix-and-postfix-notations/
• https://www.quora.com/What-are-the-advantages-of-the-postfix-form-of-an-expression-over-the-infix-and-the-prefix
• https://www.baeldung.com/cs/infix-prefix-postfix

컴퓨터 공학에서는 가장 필수로 가르치는 몇몇 과목이 있는데, 대표적으로 자료구조와 알고리즘이 있다.

특히 정렬 알고리즘은 자료구조를 배우면서도 종종 언급되곤 하는데, 그만큼 기초적이면서 활용도가 많다는 뜻이다.

분명 학교 과목으로 배웠지만, 산업기사 자격증을 따고 나서 다 잊어버렸다...

코딩 테스트를 위해 공부할 겸, 스스로 복기하기 위해 글을 정리하게 되었다.

(앞으로 꾸준히 포스팅 있길)

정렬되지 않은 주어진 데이터가 있다고 하자.

이럴 때 가장 단순하게 이를 정렬하는 방법에는 어떤 것이 있을까?

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

맨 처음에 프로그램을 배울 때 당시의 내 생각으로는 모든 수를 비교하여, 가장 작은 순서대로 정렬하는 것을 떠올릴거 같다.

이미 첫 번째 원소로 7이 있으므로, 이 원소를 기준으로 더 작은 값만을 선택해 나가면 된다.

두 번째 원소인 5는 7보다 작으므로, 최소값의 기준을 5로 변경한다.

세 번째 원소인 9는 최소값인 5보다 크므로, 넘어간다.

네 번째 원소인 0은 최소값인 5보다 작으므로, 최소값의 기준을 0으로 변경한다.

이후 이와 같은 식으로 반복하다가, 마지막 원소까지 비교가 끝나면 첫 번째 원소와 최소 값을 가진 원소를 서로 바꾼다.

위 이미지를 코드로 옮겨보면 다음과 같다.

# 가장 첫번째 자리의 수로는 가장 작은 수가 와야하므로
# arr[min]과 arr[i]를 비교하여 arr[i]가 arr[min]보다 작을 경우
# min = i로 값을 변경

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)-1):
    if array[min] > array[i]:
        min = i

if min != 0:
    array[0], array[min] = array[min], array[0]
    
print(array)

# [0, 5, 9, 7, 3, 1, 6, 2, 4, 8]

이제 이걸 배열 마지막까지 반복하면, 모든 수가 정렬될 것이다.

위와 같은 형식의 정렬 방법을 선택 정렬이라고 한다.

전체를 정렬하는 코드는 아래와 같다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min = i
    for j in range(i + 1, len(array)):
        if array[min] > array[j]:
            min = j
    array[i], array[min] = array[min], array[i]

print(array)

# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

떠올리기 쉬운만큼 단순한 면이 있고, 그만큼 비효율적인 부분이 크다.

우선 시간복잡도로는 for 반복문이 2중으로 중첩되어 있으므로 O(n^2)가 될 것이다.

이는 주어진 입력의 크기가 커질수록 연산횟수가 커진다는 뜻이다.

단순히 10 크기의 입력이 주어졌을 때는 100회의 연산을 해야하지만,

100 크기의 입력이 주어졌을 때는 10,000회의 연산을 해야한다.

다른 정렬 알고리즘에 비해 비효율적인 부분이 크지만,

그래도 작은 수의 입력과 빠르게 코드를 작성해야할 때는 유용하게 사용 될 수 있다고 하니

몸에 익혀두는 것이 좋을거 같다.

참고 : 이것이 취업을 위한 코딩테스트다 with python