0

我在 C++03 中有一组整数，其中整数表示相对于参考点的猜测。该算法运行一长串项目，并且对于每个项目，它尝试相对于该项目的参考点的每个整数猜测（一个昂贵的操作），直到找到匹配项或所有猜测都用尽。一个项目最多匹配一个猜测，但可能不匹配。我想计算每个相对整数猜测成功找到匹配项的次数，以便在迭代的每个下一个项目上，对该项目的猜测集进行排序，使得那些最成功的猜测排在那些不太成功的猜测之前基于已处理的项目。

我可以想象使用 std::map 将每个相对猜测映射到该相对猜测成功找到匹配的次数。这样，在每个项目的迭代中，我可以反转映射并将映射的所有值反向映射到它们的键。反向迭代第二个多图，我可以处理对每个项目的猜测，从最成功的猜测开始向下直到找到匹配项。此时，第一张地图将被更新以指示现在哪个猜测更成功了。类似地，第二个多重映射将被更新以从其旧的成功计数中删除匹配的猜测，并将其重新插入其现在增加的成功计数中。

然而，这似乎很复杂，我想有一个更优雅的答案。虽然，通过每次迭代从头开始重建多映射而不是尝试增量维护它，也许值得浪费精力使代码更易于理解？

是否有适合此问题的已知设计模式数据结构？我怎样才能最好地排列我的猜测，以便更成功的猜测冒泡到顶部？在这里应用优先队列有意义吗？

4

2 回答 2

3

我会选择一个struct包含成功计数和猜测的选项。从std::vector所有初始猜测中的 a 开始，每个猜测的成功计数为 0。每次通过时，从 开始my_vec.begin()并迭代到my_vec.end()。如果猜测成功，则停止迭代，增加成功计数，并根据成功计数将其冒泡到正确的位置。

for (auto it = my_vec.begin(); it != my_vec.end(); ++it) {
    if (try_it(it->guess)) {
        ++it->successes;
        while (it != my_vec.begin() && it->successes > (it - 1)->successes) {
            swap(*it, *(it - 1));
            --it;
        }
        break;
    }
}
于 2013-04-25T20:16:01.520 回答
1

std::vector( , )的pairs (或structs) 个。guesscorrect

增量correct，（二进制？）搜索正确的点，在正确猜测和新点之间滑动元素超过 1。可能在“团块”中滑动比一次滑动一个要快，但也许不是。

std::vector< std::pair< int, std::size_t > > guess_buffer;
template<typename TryGuess>
bool Try( guess_buffer& guesses, TryGuess const& try_guess ) {
  for (guess_buffer::iterator it = guesses.begin(); it != guesses.end(); ++it) {
    if (try_guess( it->first)) {
      it->second++;
      while (it != guesses.begin()) {
        --it;
        if (it->second < (it+1)->second) {
          std::swap( *it, *(it+1) );
        } else {
          return true;
        }
      }
      return true;
    }
  }
  return false;
}

鉴于您已经从头迭代到此处，搜索和滑动将足够快。迭代的局部性和速度将弥补两个整数的滑动成本。

如果你想要更少的代码，从计数到猜测的多映射，迭代记住迭代器，如果成功通过迭代器删除，增加计数，然后重新插入。应该会慢一些。

template<typename X>
struct reverse_order {
  template<typename T, typename U>
  bool operator()( T const& t, U const& u ) const {
    return std::less<X>()( u, t );
  }
};
typedef std::multi_map< std::size_t, int, reverse_order<std::size_t> > guess_map;
template<typename TryGuess>
bool Try( guess_map& guesses, TryGuess const& try_guess ) {
  for( guess_map::iterator it = guesses.begin(); it != guesses.end(); ++it ) {
    if( try_guess( it->second ) )
    {
      std::pair<std::size_t, int> modify = *it;
      guesses.erase(it);
      modify.first++;
      guesses.insert(modify);
      return true;
    }
  }
  return false;
}
于 2013-04-25T20:12:55.253 回答