Javascript를 활용해서 대량의 데이터를 조회해야되는 경우에 일반적인 반복문을 사용하면 시간이 오래걸리는 경우가 존재 한다.
가령, 1부터 1,000,000 까지의 데이터가 존재하는데 특정 데이터를 탐색한다 하면 일반적인 구조는 아래와 같다.
var data = [1,2,3,4,5,...1000000] //데이터가 담긴 배열
var target = 999,999 //찾고자 하는 데이터
//찾는 반복문
for(var i = 0; i < data.length;i++){
if(data[i] == target){ //만약 찾는데이터가 같다면
console.log(data[i], 'end!');
return;
}
}
자..위 구조에 의하면 반복문에 의해서 999,999번 돌다가 데이터를 찾는모습이 나오게된다.
만약 데이터가 많아지면 많아 질 수록 속도가 더욱 느려저..심지어 브라우저가 멈춰버릴 수도 있다.
이럴 경우를 대비해서 이진탐색 알고리즘을 사용하면 조금 더 과부하를 줄일 수 있는 기능을 만들 수 있다.
이진탐색은 절반씩 나누어서 대상이 있는지 확인하는 알고리즘이다.
위 사진처럼 맨 처음에 절반으로 나누어서 비교를 한다.
예를들어 100만개를 50만개로 각각 나누어 크기를 비교 한 경우 포함된 크기만 사용하고 포함되지 않는 크기는 버린다.
단순히 한번만 동작시키더라도 100만번 탐색 대상이 50만반으로 바뀌는 것을 알 수 있다.
100만번 대상을 50만번으로, 50만번을 25만번으로, 25만번을 12만5천번으로..
이런식으로 점차 줄여가며 찾고자 하는 데이터를 검색하도록 하는 것 이다.
이를 응용한 코드이다.
데이터는 json형식으로 만들었으며, 왠만한 탐색이 100번이내에 종료됨을 확인 할 수 있다.
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<title> hello </title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<script src = "https://ajax.googleapis.com/ajax/libs/jquery/2.1.3/jquery.min.js"></script>
</head>
<body>
</body>
</html>
<script type="text/javascript">
var time = getDateRangeData('2019-01-01','2551-01-30'); //날짜배열
var array = [];
time.forEach(function(arg, idx){
array.push({date:arg, value: idx+1});
});
var searcher = '2419-01-25';
//1. 절반으로 나눈뒤 비교한다.
//2. 또 절반으로 나눈뒤 비교하며 계속 절반씩 나누어서 찾는다.
var looper = 0;
function MergeSortTypeSearch(data, target, startLen, endLen){
var half = Math.ceil( (startLen + endLen) / 2);
var compareA = new Date(data[half].date).getTime();
var compareB = new Date(target).getTime();
looper++;
if(compareA == compareB){
console.log('end', looper, target, data[half].date);
} else if(compareA > compareB){
//console.log('배열이 비교값보다 큽니다.');
//반복문은 0 ~ half
MergeSortTypeSearch(data, target, startLen, half);
} else {
//console.log('배열이 비교값보다 작습니다.');
//반복문은 half ~ data.length
MergeSortTypeSearch(data, target, half, data.length -1);
}
}
MergeSortTypeSearch(array, searcher,0, array.length -1);
//날짜 사이값을 만들어주는 함수
function getDateRangeData(param1, param2){ //param1은 시작일, param2는 종료일이다.
var res_day = [];
var ss_day = new Date(param1);
var ee_day = new Date(param2);
while(ss_day.getTime() <= ee_day.getTime()){
var _mon_ = (ss_day.getMonth()+1);
_mon_ = _mon_ < 10 ? '0'+_mon_ : _mon_;
var _day_ = ss_day.getDate();
_day_ = _day_ < 10 ? '0'+_day_ : _day_;
res_day.push(ss_day.getFullYear() + '-' + _mon_ + '-' + _day_);
ss_day.setDate(ss_day.getDate() + 1);
}
return res_day;
}
</script>
반복문을 처음부터 끝까지 사용하여 프로그램이 멈추는 경우에는 이진탐색 알고리즘을 활용하자.
물론 저 코드의 문제점은 해당 배열값에 존재하지 않는 데이터가 대상으로 등장하면 무한loop에 빠진다는 점 이다.
그래서, 데이터를 아에 처음부터 시작, 끝 값에 대해서 존재하는지 판단하는 비교문이 필요하다.
그리고 시작과 끝값 사이에 존재하지만 없는 경우가 발생 할 수 있으므로 이에대한 처리도 추가하면 좋은 코드가 완성 될 것 이다.
댓글