首页 > 代码库 > 针对范围对的高效查找算法设计(不准用数组)

针对范围对的高效查找算法设计(不准用数组)

题目链接在:针对一群范围对的最快查找算法设计(不要用数组),是我目前遇到的一个较棘手的问题。

描述如下:

假如有一群范围对,格式为:<范围表示,该范围对应的结果值>,设计一个最快查找算法,使得给定一个值,输出该值所在范围对的结果值。
注意:范围对之间没有交集,即不可能存在<1, 10>和<2, 11>这样的两个范围对。

例如有以下几个范围对:
<<1, 2>, 20>
<<3, 37>, 27>
<<48, 57>, 28>
<<58, 63>, 27>
<<97, 128>, 122>
<<129, 149>, 12>
<<150, 189>, 13>
<<200, 245>, 14>
<<246, 256>, 129>
<<479, 560>, 12>

假如给定一个数100,则根据题意应输出122,因为100属于范围对<97, 128>

要求:不要用范围对作为下标用数组来存储,因为范围对可能非常大。

对于这个问题,思考许久,有了下面几个思路


1. 用STL map来存储这些范围对(key)及对应的结果集(value),用map进行查找

范围对定义如下:

复制代码
class range {
public:
    int from;                                                                  
    int to; 

public:
    range(): from(-1), to(-1) {}
    range(int f, int t): from(f), to(t) {}
};
复制代码

map定义为:

typedef map<range*, int> range_map;

但这里有个问题,map的key是自定义类型,一般需要自定义比较函数才能进行查找,一般的自定义比较函数如下:

struct cmp_func {
    bool operator()(const range* lc,const range* rc) const {
        return (lc->from < rc->from) || (lc->from == rc->from && lc->to < rc->to);
    }
};

但这样的比较函数并不适用于我们的需求,因为我们要求查询的并不是一个范围对,即并不是查询map中有没有<3, 37>这样的范围对,而是要求给定一个值,查询这个值属于哪个范围对,那么能不能自定义一个这样的比较函数呢?以上面那个例子为例,如果我们查找35这个数,我们将35包装成一个范围对<35, 35>,然后查找它包含在map中的哪个范围对,上面的例子是包含在<3, 37>这样的范围对,这样就找到了,也就是两个key相等,只要它们包含在同一个范围对即可。这似乎有点奇怪,违背了通常意义上的比较含义(也就是两个key相等,两个key的组成部分都应该相同才是)。不管如何,这样的比较函数还是比较简单的,如下:

struct cmp_func {
    bool operator()(const range* lc,const range* rc) const {
        return lc->to < rc->from;
    }
};

这样就实现了我们用map的find函数来查找给定的一个数属于哪个范围对了。当然,这时我们的map定义就变成了:

typedef map<range*, int, cmp_func> range_map;

用map查找表面上看上去应该挺高效的,至少比一个个顺序查找要快吧,但事实却并非如此。我用未自定义比较函数的map顺序查找和自定义上面比较函数的map find查找,结果却发现用自定义比较函数后的效果并不好,竟然比顺序查找还要慢,下面的粗糙的测试程序:

复制代码
#include<iostream>
#include<stdio.h>
#include<map>
#include<sys/time.h>
using namespace std;

class range {
public:
    int from;                                                                  
    int to; 

public:
    range(): from(-1), to(-1) {}
    range(int f, int t): from(f), to(t) {}
};

struct cmp_func {
    bool operator()(const range* lc,const range* rc) const {
        return lc->to < rc->from;
    }
};

typedef map<range*, int, cmp_func> range_map;

int get_next1(range_map *rm, int c) {
    for(range_map::iterator it = rm->begin(); it != rm->end(); ++it) {
        if(c >= it->first->from && c <= it->first->to) return it->second;
    }

    return -1; // not found.
}

int get_next2(range_map *rm, int c) {
    range_map::iterator iter = rm->find(new range(c, c));
    if(iter != rm->end())  return iter->second;

    return -1;  // not found.
}

int main()
{
    struct timeval t_begin, t_end;

    range_map *rm = new range_map();
   
    rm->insert(pair<range*, int>(new range(1, 2), 20));
    rm->insert(pair<range*, int>(new range(3, 37), 27));
    rm->insert(pair<range*, int>(new range(48, 57), 28));
    rm->insert(pair<range*, int>(new range(58, 63), 27));
    rm->insert(pair<range*, int>(new range(97, 128), 122));
    rm->insert(pair<range*, int>(new range(129, 149), 12));
    rm->insert(pair<range*, int>(new range(150, 189), 12));
    rm->insert(pair<range*, int>(new range(200, 245), 14));
    rm->insert(pair<range*, int>(new range(246, 256), 129));
    rm->insert(pair<range*, int>(new range(479, 560), 12));

    gettimeofday(&t_begin,NULL);
    int result[256];
    for(int c = 0; c < 256; c++)
        result[c] = get_next1(rm, c);
    gettimeofday(&t_end,NULL);
    double timeuse=1000000*(t_end.tv_sec-t_begin.tv_sec)+(t_end.tv_usec-t_begin.tv_usec);
    timeuse/=1000000;
    printf("\nget_next1 time use: %.12f\n", timeuse);
    for(int c = 0; c < 256; c++)
        cout << result[c] << " ";
    cout << endl;

    gettimeofday(&t_begin,NULL);
    for(int c = 0; c < 256; c++)
        result[c] = get_next2(rm, c);
    gettimeofday(&t_end,NULL);
    timeuse=1000000*(t_end.tv_sec-t_begin.tv_sec)+(t_end.tv_usec-t_begin.tv_usec);
    timeuse/=1000000;
    printf("\nget_next2 time use: %.12f\n", timeuse);
    for(int c = 0; c < 256; c++)
        cout << result[c] << " ";
    cout << endl;

    return 0;
}
复制代码

运行结果为:

get_next1 time use: 0.000124000000
get_next2 time use: 0.000144000000

当然这个例子并不能代表所有情况,且每次运行结果也不一样,但从每次的运行结果来看,几乎没有一次是用自定义比较函数比顺序查找情况好的。这至少说明了一点:我们的自定义比较函数让map在查找时做了一些额外的工作,减慢了速度。比如我们为了使用map的find函数,不得不封装我们的一个数为一个range对象,在查找的时候还得调用我们自定义的比较函数进行处理。

难道就只能顺序查找吗?在这个不靠谱的思路过后又萌生了另一个不靠谱的思路。

 

2. 使用二分查找的思想来查找范围对

我们使用ranges和results这两个数组来保存范围对及对应的结果,按序保存,每两个ranges数对应一个results里的数。

例如上面的例子保存为:

int ranges[] = {1, 2, 3, 37, 48, 57, 58, 63, 97, 128, 129, 149, 150, 189, 200, 245, 246, 256, 479, 560};
int results[] = {20, 27, 28, 27, 122, 12, 13, 14, 129, 12};

使用二分查找来查找某个数属于哪个范围对。那么如何查找呢?比如查找35属于哪个范围对,首先与最中间的128进行比较,35<128,这时候有两种可能:

(1)100在128前半部分的数组里,即1, 2, 3, 37, 48, 57, 58, 63, 97;

(2)由于128是范围对<97, 128>的第二部分,那么也有可能这个数属于这个范围对。

由于35不属于这个范围对,那么只有在97之前的部分找(不包括97),继续二分即与37进行比较,35 < 37,与上类似,此时35属于范围对<3, 37>,也就是找到了。

再举个例子,找130属于哪个范围对,同样的先与128比较,130 > 128,这时候130只可能在128的后半部分而不需要判断是否属于范围对<128, 129>,因为<128, 129>不是范围对。怎么判断是不是范围对呢?很简单,根据当前位置的奇偶性判断即可。

下面是我写的二分查找算法,及与map顺序查找、数组顺序查找的简单对比试验:

复制代码
#include<iostream>
#include<stdio.h>
#include<map>
#include<sys/time.h>
using namespace std;

class range {
public:
    int from;                                                                  
    int to; 

public:
    range(): from(-1), to(-1) {}
    range(int f, int t): from(f), to(t) {}
};

typedef map<range*, int> range_map;

int get_next1(range_map *rm, int c) {
    for(range_map::iterator it = rm->begin(); it != rm->end(); ++it) {
        if(c >= it->first->from && c <= it->first->to) return it->second;
    }

    return -1; // not found.
}

// binary search
int get_next2(int *ranges, int *results, int size, int c) { if(size <= 1) return -1; int start, end, mid; start = 0; end = size - 1; while(start <= end) { if(c < ranges[start] || c > ranges[end]) return -1; mid = start + (end - start) / 2; if(c == ranges[mid]) return results[mid / 2]; if(c < ranges[mid]) { if(mid % 2 == 1) { if(c >= ranges[mid - 1]) return results[mid / 2]; else end = mid - 2; } else end = mid - 1; } else { if(mid % 2 == 0) { if(c <= ranges[mid + 1]) return results[mid / 2]; else start = mid + 2; } else start = mid + 1; } } return -1; // not found. } int get_next3(int *ranges, int *results, int size, int c) { for(int i = 0; i < size;) { if(i % 2 == 0) { if(c >= ranges[i] && c <= ranges[i + 1]) return results[i / 2]; else if(c < ranges[i]) return -1; else i += 2; } } } int main() { struct timeval t_begin, t_end; range_map *rm = new range_map(); rm->insert(pair<range*, int>(new range(1, 2), 20)); rm->insert(pair<range*, int>(new range(3, 37), 27)); rm->insert(pair<range*, int>(new range(48, 57), 28)); rm->insert(pair<range*, int>(new range(58, 63), 27)); rm->insert(pair<range*, int>(new range(97, 128), 122)); rm->insert(pair<range*, int>(new range(129, 149), 12)); rm->insert(pair<range*, int>(new range(150, 189), 13)); rm->insert(pair<range*, int>(new range(200, 245), 14)); rm->insert(pair<range*, int>(new range(246, 256), 129)); rm->insert(pair<range*, int>(new range(479, 560), 12)); int ranges[] = {1, 2, 3, 37, 48, 57, 58, 63, 97, 128, 129, 149, 150, 189, 200, 245, 246, 256, 479, 560}; int results[] = {20, 27, 28, 27, 122, 12, 13, 14, 129, 12}; // int r = get_next2(ranges, results, 20, 65); // cout << r << endl; gettimeofday(&t_begin,NULL); int result[256]; for(int c = 0; c < 256; c++) result[c] = get_next1(rm, c); gettimeofday(&t_end,NULL); double timeuse=1000000*(t_end.tv_sec-t_begin.tv_sec)+(t_end.tv_usec-t_begin.tv_usec); timeuse/=1000000; printf("\nget_next1 time use: %.12f\n", timeuse); // for(int c = 0; c < 256; c++) // cout << result[c] << " "; // cout << endl; gettimeofday(&t_begin,NULL); for(int c = 0; c < 256; c++) result[c] = get_next2(ranges, results, 20, c); gettimeofday(&t_end,NULL); timeuse=1000000*(t_end.tv_sec-t_begin.tv_sec)+(t_end.tv_usec-t_begin.tv_usec); timeuse/=1000000; printf("\nget_next2 time use: %.12f\n", timeuse); // for(int c = 0; c < 256; c++) // cout << result[c] << " "; // cout << endl; gettimeofday(&t_begin,NULL); for(int c = 0; c < 256; c++) result[c] = get_next3(ranges, results, 20, c); gettimeofday(&t_end,NULL); timeuse=1000000*(t_end.tv_sec-t_begin.tv_sec)+(t_end.tv_usec-t_begin.tv_usec); timeuse/=1000000; printf("\nget_next3 time use: %.12f\n", timeuse); // for(int c = 0; c < 256; c++) // cout << result[c] << " "; // cout << endl; return 0; }
复制代码

运行结果为:

get_next1 time use: 0.000302000000
get_next2 time use: 0.000043000000
get_next3 time use: 0.000165000000

说明二分查找算法还是挺高效的,顺序查找也不错,有时候表现的与二分查找差不多,这里的数据比较少,体现不出准确的对比,但至少可能说明二分查找算法比简单的顺序查找(map顺序和数组顺序查找)要快不少。

 

上面是自己的一点拙见,相信二分查找算法肯定不是最高效的算法,但目前实在想不出更好的办法了。大家有想法的尽管提,不试试不知道算法好不好!