c++ - 多态过滤器迭代器范围

Question

我有一个元素序列(通常是 std::vector<T> )和一个方法 overlap_range(Iterator, Iterator, T)用于获取这些元素的子集 overlap用 T 编辑.

如果元素序列满足特定条件，则overlap_range的结果将是连续的，并且可以在对数时间内确定。否则可能存在多个不连续的此类子范围，只能在线性时间内确定。确定是否满足标准需要线性时间。

我想要以下内容:

1. overlap_range是多态的，从某种意义上说，如果已知满足标准，算法将以对数时间运行。
2. 返回的子范围是多态的，以便能够在满足条件的情况下利用子范围的已知属性。

我提出的解决方案是在 overlap_range 中使用默认值标志参数，这会处理 (1)。然后我想通过使用 boost::filter_iterator<std::function<bool(T)>, Iterator> 来解决 (2) std::function<bool(T)>在哪里简单地返回 true如果已知满足标准。然而，事实证明这是大约。比简单地使用仿函数来测试 overlap 慢 50 倍在这两种情况下编辑。 overlap 的逻辑不是特别复杂，但范围内的元素数量足够大，如果可能的话，不必对其进行不必要的评估具有显着优势。

还有其他方法可以帮助我解决这个问题吗？

更多详情

虽然我认为以上内容足以理解问题，但这里还有一些可能有用的背景信息。

• T是任何可以简化为 GenomicRegion 的对象，它只是在单个连续序列(即两个坐标)上定义一组坐标。任何这样的 T实际上是一个 Mappable<T>这基本上需要一个方法 get_region .

• overlaps然后定义为

  inline GenomicRegion::DifferenceType overlap_size(const GenomicRegion& lhs, const GenomicRegion& rhs) noexcept
  {
      return static_cast< GenomicRegion::DifferenceType>(std::min(lhs.get_end(), rhs.get_end())) -
              static_cast< GenomicRegion::DifferenceType>(std::max(lhs.get_begin(), rhs.get_begin()));
  }
  
  inline bool overlaps(const GenomicRegion& lhs, const GenomicRegion& rhs) noexcept
  {
      auto num_bases_overlaped = overlap_size(lhs, rhs);
      return (num_bases_overlaped == 0) ? !are_adjacent(lhs, rhs) || empty(std::min(lhs, rhs)) : num_bases_overlaped > 0;
  }
  

• 任何Mappable类可以按开始坐标排序，然后是结束坐标(如果开始坐标相等)。
• 对数重叠搜索(和连续结果区域)的“标准”是:如果 a <= b然后end(a) <= end(b) , 例如所有 T 都是如此尺寸相同。

• 朴素的过滤器迭代器定义为

  template <typename MappableType>
  class IsOverlapped
  {
  public:
      IsOverlapped() = delete;
      template <typename MappableType_>
      IsOverlapped(const MappableType_& mappable) : region_ {get_region(mappable)} {}
      bool operator()(const MappableType& mappable) { return overlaps(mappable, region_); }
  private:
      GenomicRegion region_;
  };
  
  template <typename Iterator>
  using OverlapIterator = boost::filter_iterator<IsOverlapped<typename Iterator::value_type>, Iterator>;
  
  template <typename Iterator>
  using OverlapRange = boost::iterator_range<OverlapIterator<Iterator>>;
  

• overlap_range然后可以声明为

  template <typename ForwardIterator, typename MappableType>
  OverlapRange<ForwardIterator>
  overlap_range(ForwardIterator first, ForwardIterator last, const MappableType& mappable, bool is_bidirectional=false)
  

当然，这可以简单地返回范围 OverlapRange<ForwardIterator>(first, last) ，但我们可以通过有效地找到右边界和左边界(如果范围为 is_bidirectional)来做得比这更好。 .

Answer 1

最大的减速可能是因为 std::function<> 中的动态调度.您可以尝试将其替换为自定义的、非类型删除的谓词类型(函数对象？)。

---

我可能应该问 "be overlapped with T " 范围内的元素意味着什么。将被称为量词的数字映射但是，让我直接下结论，因为这是炫耀 Boost Interval Container 库的好借口。

请注意，该演示取决于 Boost ICL 内置 Combining Styles 的事实和许多事情的比较器。来自 Map concept 的文档:

• Maps of Sets that will be called Collectors and
• Maps of Numbers which will be called Quantifiers

为了更好地了解它开箱即用的实现方式，我选择使用 Collector 进行演示。 s，即 T在你的术语中恰好是 std::set<int> .

Live On Coliru

#include <boost/icl/interval_map.hpp>
#include <set>

namespace icl = boost::icl;

using Container = icl::interval_map<
    size_t,          // mirrors the vector index
    std::set<int> >; // set intersection models our "overlap"

Container generate_random_data();

#include <iostream>

int main() {
    auto haystack = generate_random_data();

    // let's find all ranges where the T overlaps with -2:

    using Seive = Container::value_type;

    std::cout << "Haystack: " << haystack << "\n";
    std::cout << "Overlaps -2: \n\t-> " << (haystack & Seive {{ 0, 1024 }, { -2 }}) << "\n";
    std::cout << "Overlaps +7: \n\t-> " << (haystack & Seive {{ 0, 1024 }, { +7 }}) << "\n";

    // you can even do a "multi-sieve" in one pass:
    std::cout << "Overlaps any of +7 or -2: \n\t-> " << (haystack & Seive {{ 0, 1024 }, { -2, +7 }}) << "\n";

    // and more interesting, you can narrow any of the "overlap" targets to a certain input range:
    Container combined;
    combined += Seive {{ 128, 512 }, { -2 }};
    combined += Seive {{ 512, 768 }, { +7 }};
    std::cout << "Complex query " << combined << ": \n\t-> " << (haystack & combined) << "\n";
}

#include <random>
#include <functional>

Container generate_random_data() {
    using namespace std;

    mt19937 prng {random_device{}()};
    // mt19937 prng {3236629322};
    auto card     = bind(uniform_int_distribution<>(1,       5),    ref(prng));
    auto domain   = bind(uniform_int_distribution<size_t>(0, 1024), ref(prng));
    auto codomain = bind(uniform_int_distribution<>(-10,     10),   ref(prng));
    auto gen_val  = [&] { 
        Container::value_type::second_type v;
        generate_n(inserter(v, end(v)), card(), codomain);
        return v;
    };

    auto gen_range = [&]() -> Container::value_type { 
        auto left = domain(), right = domain();
        if (left>right) swap(left, right);

        return { 
            Container::interval_type::right_open ( left, right ),
            gen_val()
        };
    };

    {
        Container data;
        generate_n(icl::inserter(data, end(data)), prng() % 1024, gen_range);
        return data;
    }
}

哪个打印(针对特定种子)

Haystack: {([0,1)->{-10 3 })([1,5)->{-10 })([5,13)->{-9 -1 3 7 10 })([13,17)->{-4 1 6 10 })([17,69)->{0 2 4 8 })([69,81)->{-7 -4 9 })([81,97)->{1 8 10 })([97,102)->{6 })([102,701)->{-10 -2 1 3 7 })([701,987)->{3 })([987,1002)->{-9 6 7 8 10 })([1002,1003)->{2 3 4 5 9 })([1003,1004)->{-9 -7 3 9 })([1004,1024)->{-10 -2 2 5 })}
Overlaps -2: 
    -> {([102,701)->{-2 })([1004,1024)->{-2 })}
Overlaps +7: 
    -> {([5,13)->{7 })([102,701)->{7 })([987,1002)->{7 })}
Overlaps any of +7 or -2: 
    -> {([5,13)->{7 })([102,701)->{-2 7 })([987,1002)->{7 })([1004,1024)->{-2 })}
Complex query {([128,512)->{-2 })([512,768)->{7 })}: 
    -> {([128,512)->{-2 })([512,701)->{7 })}

您可以多次运行示例以查看其他随机生成的数据集的结果。