최근 leetcode 문제를 풀면서 느낀 점이 있다. leetcode에서는 알고리즘을 submit하면 메모리 사용량과 런타임 시간을 알려주기 때문에, 이에 대해서 한 번 더 생각하게 된다.(물론 들쭉날쭉하게 표시되기 때문에 헷갈리고 실제로 의미없다는 이야기도 있지만, 나에게 적어도 퍼포먼스에 대해서 생각하는 계기를 주었다.)
1. Add Digits
https://leetcode.com/problems/add-digits/submissions/
문제 자체는 아주 간단한 것이었다.
Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.
Example 1:
Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
Since 2 has only one digit, return it.
Example 2:
Input: num = 0
Output: 0받은 Int를 자릿수로 쪼개서 더하고, 1의 자리수가 될때까지 더하는 것이었는데
따라서
- 숫자를 스트링화한다
- split으로 array로 만든다.
- reduce로 arr 값을 더한다.
3-1. 2. split array 길이가 1이라면, 그냥 그 값을 리턴한다.
3-2. 2. aplit array 길이가 1 이상이라면 아직 더할 것이 남아있으니 한번 더 1.부터 iterate한다.
// first solution
var addDigits = function (num) {
function numSplit(num) {
return num.toString().split("");
}
function strReduce(arr) {
return arr.reduce((acc, n) => acc + Number(n), 0);
}
function plusStr(num1) {
const split = numSplit(num1);
const sum = strReduce(split);
if (split.length == 1) return sum;
return plusStr(sum);
}
return plusStr(num);
};
첫번째 해결책은 이랬다.
2. 더 나은 방법은 뭘까?
아마, 내가 작성한 위 솔루션은 O(n)일 것이다.
toString O(n)
split O(n)
reduce O(n)
즉 3번의 for 문이 도는 형태가 되는 것이라고 생각하는데.
https://leetcode.com/problems/add-digits/discuss/579918/javascript-solutions-with-explanation
ps)위 url의 해설에 따르면 맞는 듯 하다.
몇 가지 생각해볼 만한 것은,
- String을 Array화 하지 않고 reduce하면 어떻지?
사실 이것은 Python에서는 그냥 되는것인데, JS에서는 call해서 사용할 수 있을 것 같다. 거의 사용해본적은 없지만...
/**
* @param {number} num
* @return {number}
*/
var addDigits = function (num) {
function numSplit(num) {
return (num+'');
}
function strReduce(arr) {
return arr.reduce((acc, n) => acc + Number(n), 0);
}
function plusStr(num1) {
const split = numSplit(num1);
const sum = Array.prototype.reduce.call( // call
split,
(acc, curr) => acc + Number(curr),
0
)
if (split.length == 1) return sum;
return plusStr(sum);
}
return plusStr(num);
};- reduce를 그냥 for loop으로 대체하면 어떨까?
JS의 각종 native 메소드들은 코드를 덜 적게 하는데 도움을 주지만, 실제로 퍼포먼스는 조금 느리다는 이야기를 들은 적이 있다.
/**
* @param {number} num
* @return {number}
*/
var addDigits = function (num) {
function numSplit(num) {
return (num+'');
}
function strReduce(arr) {
return arr.reduce((acc, n) => acc + Number(n), 0);
}
function plusStr(num1) {
const split = numSplit(num1);
let sum = 0;
for(let i = 0; i<split.length; i++){
sum += parseInt(split[i])
}
if (split.length == 1) return sum;
return plusStr(sum);
}
return plusStr(num);
};jsperf사이트가 접속이 되지 않는데,
https://jsben.ch/
에서 실제 체크를 해볼 수 있었다.
3. 실제 속도를 체킹해보니
위 사이트에서 나오는 값은 jsperf와 동일하게, ops/second 값으로 초당 몇번 실행되는지 확인하는 수치이다.
- Array.prototype.reduce.call을 사용했을 경우
call 메소드를 적용한 블록 2가 그냥 느리다. 사실 그럴거라고 생각은 하고 있었다.
- reduce를 for loop으로 변환했을 때,
reduce보다 for loop가 훨씬 좋은 것을 확인할 수 있었다.
사실 이 그래프의 내용을 알고 있었기 때문에, 어떻게든 예상된 결과라고 할 수 있을 것 같다.
다만 이렇다고 결코 reduce의 가치가 떨어진다고는 생각하지 않는데,
실제 코드를 작성하다 보면 for loop을 두세번씩 중첩하는 일도 있고,(물론 이것도 심사숙고하다보면 더 줄여나갈 수 있겠지만..) 그럴때마다 for loop을 여는 것은 가독성에 너무 큰 문제를 줄 수 있기 때문이다. 결국
reduce와 for loop을 놓고 생각했을 때, 결국 중요한 것은 속도 차이가 너무 크지 않다면 결국 가독성이 최고라는 것이라고 생각한다.
4. number 형을 효율적으로 string으로 바꾸는 법?
위 내용들을 찾으면서 검색하던 중,
다른 답안에서는 toString(str) 대신 '' + str을 사용해서 string화 한다는 것을 알게 되었다.
알고는 있는 내용이었지만, 이것이 속도가 더 빠를까?
(생각해보니, toString()보다 에러가 덜 나는 것은 기억이 나는데, 완전히 까먹고 있었다. 앞으로 이걸로 써야겠다.)
예를 들어,
(1928385).toString()
// 잘됨
null.toString()
// Uncaught TypeError: Number.prototype.toString requires that 'this' be a Number
null + '' = 'null'
undefined + '' = 'undefined'
// 이므로, 일단 빨간화면을 드러내지 않기 위해선 + ''를 쓰는 것이 나아 보인다.
https://stackoverflow.com/questions/14918778/why-concat-empty-character-is-faster-than-tostring
의 내용에서 테스트 결과를 찾을 수 있었다.
var number = 27387329;
var str;
str = "" + number + ""; //1위
str = String(number); // 4위
str = number.toString(); //3위
str = "" + number; //2위
의 순서대로 빠른데, 1위인 "" + number + "" 가 가장 빠르고, 위처럼 빨간화면을 띄우는 일도 없으니 앞으로는 저렇게 사용하는 것이 나을 것 같다.
ps) 사파리에서는 측정 결과가 다르다.
반대로 toString()이 가장 빠르다는 것을 알 수 있었다.
그렇지만, toString()에서 역시 null object, undefined에서 에러가 나는 것은 똑같으니깐, 위의 string concat "" + nuber + ""을 사용하는 것이 가장 좋지 않은가 한다.
그런데 왜 이런 일이 일어나는 것일까?
https://stackoverflow.com/questions/14918778/why-concat-empty-character-is-faster-than-tostring
위 크롬 V8의 c function stacktrace에 따르면,
실제 toString()을 사용하는 경우 코드가 추가로 더 붙어있다고 하는데..
이 부분은 시간날 때 더욱 확인해보아야 할 것 같다.
