- 主题:请教一个算法。
struct Range
{
int32_t lower_bound;
int32_T upper_bound;
}
现在有很多个这样的 range, std::vector<Range>，每个 Range 都是独特的，不会重复。
bool isNumberInRange(int32_t number)
{
// 判断给定的 NUMBER 是否在其中某个 range 内，然后返回这个 RANGE，
}
我现在就是循环遍历，，有更高效的算法吗？数量在5万个 RANGE 内。
--
FROM 218.76.62.*
排序过的话就有高效算法。
随机排列就没有。
【 在 speedboy2998 的大作中提到: 】
: struct Range
: {
: int32_t lower_bound;
: ...................
--
FROM 123.103.9.*
没有排序过。
【 在 lipp 的大作中提到: 】
: 排序过的话就有高效算法。
: 随机排列就没有。
:
--
FROM 218.76.62.*
那还有啥可说的。。。
【 在 speedboy2998 的大作中提到: 】
: 没有排序过。
--
FROM 123.103.9.*
反正每个Range都是独立的
就试试Par for each
【 在 speedboy2998 的大作中提到: 】
: struct Range
: {
: int32_t lower_bound;
: ...................
--
FROM 107.77.208.*
std::find_if(std::execution::par_unseq, range_vec, [n](const auto& r)->bool noexcept
{
return std::find_if(std::execution::par_unseq, r, xxxx) != std::end(r);
});
寄希望与多核cpu的系统调度吧
【 在 speedboy2998 的大作中提到: 】
: struct Range
: {
: int32_t lower_bound;
: ...................
--
FROM 115.193.184.*
那先排个序呗，如果这个函数要调用很多次。
【 在 speedboy2998 的大作中提到: 】
: 没有排序过。
--
FROM 183.192.17.*
排个序，这是典型的弱偏序，stl容器和算法可以直接用。
【 在 speedboy2998 的大作中提到: 】
: struct Range
: {
: int32_t lower_bound;
: ...................
--
修改:allegro FROM 158.140.1.*
FROM 158.140.1.*
把range放到std::map 里面 提供自己的 operator <
好处是与新的range进来的话直接扔到map就好了，省事。 查找也能用map上那一套。
--
FROM 1.91.33.*
是的，直接用equal_range还能查找intersection。
【 在 hongdiao 的大作中提到: 】
: 把range放到std::map 里面 提供自己的 operator <
: 好处是与新的range进来的话直接扔到map就好了，省事。 查找也能用map上那一套。
--
FROM 73.162.73.*