Javascript 이진탐색을 활용한 탐색 기능 향상(Javascript Binary search, javascript 반복문 속도 향상)
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에 빠진다는 점 이다.
그래서, 데이터를 아에 처음부터 시작, 끝 값에 대해서 존재하는지 판단하는 비교문이 필요하다.
그리고 시작과 끝값 사이에 존재하지만 없는 경우가 발생 할 수 있으므로 이에대한 처리도 추가하면 좋은 코드가 완성 될 것 이다.