1

I need to know the level of a player using the amount of exp he has and the exp chart. I want to do it the most efficient way possible. This is what I got. Note: The real expChart has thousands of levels/index. All the values are in increasing order. 

var expChart = [1,10,23,54,65,78,233,544,7666,22224,64654,456456,1123442];
/*
lvl 0: //0-1[ exp
lvl 1: //[1-10[ exp
lvl 2: //[10-23[ exp
*/
getLvlViaExp = function(exp){
    for(var i = 0 ; i < expChart.length ; i++){
        if(exp < expChart[i]) break;
    }
    return i;
}

This is a more efficient way to do it. Every x steps, (6 i the example, probably every hundreds with real chart), I do a quick comparation and jump to approximative index, skipping many indexes.

getLvlViaExp = function(exp){
    var start = 0;
    if(exp > 233)   start = 6;
    if(exp > 1123442) start = 12;

    for(var i = start ; i < expChart.length ; i++){
        if(exp < expChart[i]) break;
    }
    return i;
}

Is there an even better way to do this?

SOLUTION:

Array.prototype.binarySearch = function(value){
    var startIndex  = 0,
        stopIndex   = this.length - 1,
        middle      = Math.floor((stopIndex + startIndex)/2);
    if(value < this[0]) return 0;
    while(!(value >= this[middle] && value < this[middle+1]) && startIndex < stopIndex){

        if (value < this[middle]){
            stopIndex = middle - 1;
        } else if (value > this[middle]){
            startIndex = middle + 1;
        }

        middle = Math.floor((stopIndex + startIndex)/2);
    }

    return middle+1;
}
4

2 に答える 2

4

検索に最適なアルゴリズムは、O(lg n) のバイナリ検索です (O(c) のハッシュ検索で実行できない場合)。

http://www.nczonline.net/blog/2009/09/01/computer-science-in-javascript-binary-search/

基本的に、チャートの中央にジャンプします ( n / 2)。あなたはその数字から経験値が高いか低いか。高い場合は、真ん中の上半分にジャンプします。下半分の真ん中にジャンプする場合：探しているものが見つかるまで比較して繰り返します。

于 2013-10-18T02:24:15.147 に答える
0 
var expChart = [1,10,23,54,65,78,233,544,7666,22224,64654,456456,1123442];
getLvlViaExp = function(exp){
    var min=0;
    var max=expChart.length-1;
    var i;
    while(min <=max){

    i=Math.round((min+max)/2); 
        //document.write("<br />"+i+":"+min+":"+max+"<br />");
        if(exp>=expChart[i] && exp <=expChart[i+1]) {
        break;
        }
    if(exp>=expChart[i]){
            min=i+1;
        }
    if(exp<=expChart[i]){
            max=i-1;

        }

    }
return i;
}

document.write(getLvlViaExp("10"));

私はそれをテストしましたが、かなりうまくいくようです。答えにたどり着くまでに実際に何ステップ経ったかを確認したい場合は、while ループ内の document.write のコメントを外してください。それを見るのはちょっと魅力的でした。

于 2013-10-18T03:30:04.167 に答える