多态过滤器迭代器范围

Question

我有一个元素序列(通常是std::vector<T>)，以及一个方法overlap_range(Iterator, Iterator, T)，用于获得这些元素的子集，这些元素是overlap与T ed的。

如果元素的序列满足一定的条件，则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<>中的动态调度。您可以尝试用自定义的、非类型擦除的谓词类型(函数对象?)来替换它。

---

我可能应该问它是什么意思的元素在一个范围" overlapped与T "。称为量词的数字映射但是，让我跳到一点结论，因为这是一个很好的借口来展示Boost Interval Container库。

请注意，演示依赖于Boost ICL为许多事情内置了组合样式和比较器这一事实。Map概念的文档:

• 将被称为收集器和
的集合的映射
• 数字映射将被称为量词

为了更好地理解它的开箱即用，我选择用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: nt-> " << (haystack & Seive {{ 0, 1024 }, { -2 }}) << "n";
    std::cout << "Overlaps +7: nt-> " << (haystack & Seive {{ 0, 1024 }, { +7 }}) << "n";
    // you can even do a "multi-sieve" in one pass:
    std::cout << "Overlaps any of +7 or -2: nt-> " << (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 << ": nt-> " << (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 })}

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