요약
LeetCode 문제를 풀면서 자료의 표현 방식이 성능에 큰 영향을 준다는 점을 다시 확인했다. 또한 Express의 req, res, next()가 어떻게 협력하여 요청을 처리하는지 파이프라인 관점에서 정리했다.
배운 것
LeetCode 3043 최적화
LeetCode 3043번 문제를 풀었다. 두 정수형 배열에 있는 원소들 중 임의의 두 수를 선택했을 때, 공통의 일치하는 prefix의 최대 길이를 구하는 문제였다.
우선, 각 배열의 길이가 최대 50000이기 때문에, 가능한 모든 쌍을 만들어서 크기를 구하는 방식으로 하면 시간복잡도가 O(n²)이 되어서 문제를 제 시간 안에 해결하기 힘들다. (n은 둘 중 긴 배열의 원소의 개수)
대신, 한 배열의 모든 prefix를 미리 저장해두고 다른 배열의 prefix와 비교하는 방식을 사용하면, 같은 prefix를 반복해서 계산하지 않아도 되므로 훨씬 효율적으로 처리할 수 있다.
또한 원소는 최대 10⁸ 이하의 정수이므로, 각 숫자의 자릿수는 최대 8자리이다. 따라서 각 원소마다 prefix를 생성하는 비용은 사실상 상수 시간에 가깝고, 전체 시간 복잡도는 O((n + m) × 8), 즉 실질적으로 O(n)에 가깝게 동작한다.
이때 prefix를 저장하는 자료구조로는 Set을 사용했다. 순서는 중요하지 않고 포함 여부만 빠르게 판단하면 되기 때문이다.
처음에는 다음과 같이 문자열과 배열 기반으로 prefix를 생성했다:
class Solution {
func longestCommonPrefix(_ arr1: [Int], _ arr2: [Int]) -> Int {
var answer = 0
var preSet = Set<[Int]>()
arr1.map {
Array(String($0)).compactMap { Int(String($0)) }
}.forEach { element in
var current = [Int]()
element.forEach { num in
current.append(num)
preSet.insert(current)
}
}
arr2.map {
Array(String($0)).compactMap { Int(String($0)) }
}.forEach { element in
var current = [Int]()
element.forEach { num in
current.append(num)
if preSet.contains(current) && answer < current.count {
answer = current.count
}
}
}
return answer
}
}이 코드도 문제를 시간 내에 통과하지만, String <-> Int 타입 컨버전이 반복되고 정수형 배열 자체를 해싱하는 작업이 들어가야 하며, prefix 생성 과정에서도 불필요한 메모리 사용이 발생한다.
조금 더 생각해보니, prefix를 굳이 앞에서부터 만들 필요가 없었다. 정수를 10으로 계속 나누면 마지막 자릿수가 제거되므로 prefix가 역순으로 만들어진다.
최종적인 제출 코드는 다음과 같다:
class Solution {
func longestCommonPrefix(_ arr1: [Int], _ arr2: [Int]) -> Int {
var answer = 0
var preSet = Set<Int>()
arr1.forEach { element in
var current = element
while current > 0 {
preSet.insert(current)
current /= 10
}
}
arr2.forEach { element in
var current = element
while current > 0 {
if preSet.contains(current) && answer < String(current).count {
answer = String(current).count
break
}
current /= 10
}
}
return answer
}
}첫 번째 코드의 656ms에서 87ms로 상당히 연산 시간이 짧아진 것을 알 수 있다.
Express의 Request와 Response
저번에 정리했듯이 Express의 미들웨어 체인은 함수형 체인이 아니라 res, req를 공유하는 체인이다.
input
.parsing()
.routing()
.response()
// 이런 구조가 아니다Express는 하나의 req, res 객체를 여러 Middleware가 공유한다. 각 Middleware는 필요에 따라 객체를 수정하고, next()를 호출하여 다음 단계로 실행 흐름을 넘긴다.
Request
↓
Middleware
↓
Middleware
↓
Router
↓
Route Handler
↓
Response따라서 Express는 함수형 체인보다는 공유 객체 기반의 파이프라인에 가깝다.
next()의 역할
처음에는 next()가 다음 Middleware에게 req, res를 전달하는 함수라고 생각했다. 하지만 실제로는 Express에게 “다음 Middleware를 실행해"라고 알려주는 콜백 함수이다. 개념적으로는 다음과 비슷하게 동작한다.
const stack = [
middlewareA,
middlewareB,
middlewareC
];
function run(index) {
stack[index](
req,
res, // req, res는 Express가 생성해준다
() => run(index + 1)
);
}즉 next()는 데이터를 전달하는 함수가 아니라, 다음 Middleware를 실행하는 함수라고 이해할 수 있다.
처음에는 함수의 시그니처에 req, res가 있는데 왜 next()에서 전달하지 않는지 의문이었다.
하지만 Express는 함수형 체인이 아니라 공유 객체 기반의 파이프라인 구조이다. req, res는 Express가 이미 들고 있으며, 다음 Middleware를 실행할 때 동일한 객체 참조를 다시 전달한다.
따라서 next()는 데이터를 넘기는 역할이 아니라, 단순히 다음 단계로 실행 흐름을 넘기는 역할만 담당한다.
Swift식으로 생각해보면 다음과 같다.
let stack: [(Request, Response, () -> Void) -> Void] = [
middlewareA,
middlewareB,
middlewareC
]
func run(_ index: Int) {
stack[index](
req,
res,
{
run(index + 1)
}
)
}남은 의문
- Express는 Middleware 스택을 내부적으로 어떤 자료구조로 관리할까?
- 비동기 Middleware에서
next()호출과 Promise 처리는 내부적으로 어떻게 연결될까?