UVA 100：“3n +1问题”取2

Question

这是我第二次尝试解决这个问题，我的第一次尝试是在这里：UVA 100：“3n+1问题”

这一次我试着从你在第一次尝试中指出的失败和错误中吸取教训。

• 我辞职了，不把多份陈述写成一行。(这导致了代码长度的平衡，不过:( )
• 我删除了我为“优化”代码而放置的构造，但这些构造被证明是减慢了代码的速度，即std::pow、std::log2和最重要的是std::unordered_map。
• 我做了一些实际的基准测试，我认为代码现在相当快。
• 每当我认为我的意图不明显时，我就添加评论。
• 但是我不明白为什么，但是好吧，我已经把using namespace std放在一边了
• 我仍然试图做代码错误的证明，例如，检查输入的正确性。
• 我已经放置了assert宏。

对这段代码有什么评论吗？

// This program solves UVA Online Judge Problem 100: "The 3n + 1 Problem"
// Problem specification:
// https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36

#ifdef ONLINE_JUDGE
  #define NDEBUG
#endif

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <cmath>
#include <limits>
#include <cassert>

// aoo = At Or Operator[]
template<class Container>
typename Container::reference
aoo(Container &cont, typename Container::size_type index) {
  #ifndef NDEBUG
    return cont.operator[](index);
  #else
    return cont.at(index);
  #endif
}

template<class Container>
typename Container::value_type::reference
aoo(Container &cont, typename Container::size_type i1,
    typename Container::value_type::size_type i2) {
  #ifndef NDEBUG
    return cont.operator[](i1).operator[](i2);
  #else
    return cont.at(i1).at(i2);
  #endif
}

using seqlen = std::uint_fast16_t;
using seqval = std::uint_fast32_t;

// As of now, the problem specification incorrectly states that all integers
// in the input will be less than 10.000. The correct boundaries, stating that
// integers will be less than 1.000.000, can be found in the archived version:
// web.archive.org/web/20161225044321/https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36
constexpr seqval input_max = 999999;

using cache_t = std::vector<std::vector<seqlen>>;
static_assert(std::numeric_limits<cache_t::size_type>::max() >= input_max,
    "This implementation cannot hold the cache.");

// cache[0] stores lengths of all values from 1 to input_max
// cache[1] stores maximums of lengths of 2-3, 4-5, etc
// cache[2] stores maximums of lengths of 4-7, 8-12, etc
// etc
cache_t cache = []()
{
  //Log2 and pow are slow, but hopefully it doesn't matter in the initialization
  cache_t ret(std::log2(input_max), cache_t::value_type{});

  // 0 means unknown
  for(cache_t::size_type i = 0; i < ret.size(); i++)
    aoo(ret, i) = cache_t::value_type(input_max / std::pow(2,i), 0);
  aoo(ret, 0, 0) = 1;

  return ret;
}();

seqlen calculate_collatz_length(seqval n)
{
  auto collatz_next = [](seqval n) 
  {
    assert(n >= 1);

    if(n%2 == 0)
      return n/2;
    else {
      // Problem specification guarantees us that
      // no operation overflows a 32bit integer.
      assert(n <= (UINT32_MAX-1)/3);
      return 3*n+1;
    }
  };

  seqlen excessive_length = 0;
  while(n > input_max)
  {
    n = collatz_next(n);
    ++excessive_length;
  }

  if(aoo(cache, 0, n-1)==0)
    aoo(cache, 0, n-1) = calculate_collatz_length(collatz_next(n)) + 1;

  return aoo(cache, 0, n-1) + excessive_length;
}

seqlen get_length_from_cache(seqval i, seqval j)
{
  assert(1 <= i && i <= j && j <= input_max+1);

  if(i == j)
    return 0;

  cache_t::size_type exponent;
  seqval adji, adjj, interval;

  auto adjust_bounds_to_multiplications_of_a_power_of_two = [&, i, j]()
  {
    assert(1 <= i && i < j && j <= input_max+1);

    exponent = 0;
    interval = 1;
    auto adjusted_j = [j](seqval interval)
      {return interval*(j/interval);};
    auto adjusted_i = [i,j,adjusted_j](seqval interval)
      {return adjusted_j(interval) - interval;};
    auto broadened_i = [i](seqval interval)
      {return i+interval;};

    while(j >= broadened_i(4*interval) ||
        adjusted_j(2*interval) >= broadened_i(2*interval))
    {
      interval *= 2;
      exponent++;
    }
    assert(interval <= j-i);
    assert(std::pow(2,exponent) == interval);

    adjj = adjusted_j(interval);
    adji = adjusted_i(interval);
    assert(
      adjj <= j &&
      adji >= i &&
      adjj % interval == 0 &&
      adji % interval == 0 &&
      adji + interval == adjj &&
      adjusted_j(interval*2) < broadened_i(interval*2));
  };

  adjust_bounds_to_multiplications_of_a_power_of_two();

  cache_t::value_type::size_type ind = adji/interval - 1;
  if(aoo(cache, exponent, ind) == 0) {
    if(exponent == 0)
      aoo(cache, exponent, ind) = calculate_collatz_length(adji);
    else {
      seqval mid = adji + interval/2;
      assert(mid+interval/2 == adjj);
      aoo(cache, exponent, ind) =
        std::max(get_length_from_cache(adji, mid),
            get_length_from_cache(mid, adjj));
    }
  }

  assert(
    aoo(cache, exponent, ind) ==
    *std::max_element(
      aoo(cache, 0).begin()+adji-1,
      aoo(cache, 0).begin()+adjj-1));

  return std::max({
    get_length_from_cache(i, adji),
    aoo(cache, exponent, ind),
    get_length_from_cache(adjj, j)
  });
}

struct test_case
{
  // long unsigned not seqval to avoid this:
  // https://codereview.stackexchange.com/questions/146669/enforcing-correct-input-output-of-integers
  long unsigned int i, j;

  // Sole purpose of this operator: Check input correctness
  friend std::istream &operator >> (std::istream &is, test_case &tc) try
  {
    std::string inpstr;
    std::getline(is, inpstr);
    if(!is.good()) {
      if(is.eof()) {
        // Either no characteres were read, in which case
        // failbit is set already, or the input didn't end with '\n',
        // which is invalid and we need to set failbit
        is.setstate(std::ios_base::failbit);
      }
      return is;
    }

    std::stringstream inp(inpstr+'\n');
    inp.exceptions(std::ios_base::badbit);

    inp >> tc.i >> tc.j;
    if(!inp.good()) {
      is.setstate(inp.rdstate());
      return is;
    }

    if(tc.i < 1 || tc.i > input_max || tc.j < 1 || tc.j > input_max) {
      is.setstate(std::ios_base::failbit);
      return is;
    }

    // No errors were detected, input is correct
    return is;
  } catch(...) {
    is.setstate(std::ios_base::badbit);
    return is;
  }
};

int main()
{
  #ifdef NDEBUG
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
  #endif
  std::cin.exceptions(std::ios_base::failbit | std::ios_base::badbit);
  std::cout.exceptions
    (std::ios_base::eofbit | std::ios_base::failbit | std::ios_base::badbit);

  while(std::cin.peek() != decltype(std::cin)::traits_type::eof())
  {
    test_case tc;
    std::cin >> tc;

    // Unary + to avoid this:
    // https://codereview.stackexchange.com/questions/146669/enforcing-correct-input-output-of-integers
    std::cout << tc.i << ' ' << tc.j << ' ' <<
        +get_length_from_cache(std::min(tc.i, tc.j),
            std::max(tc.i, tc.j)+1) << '\n';
  }

  // On any error an exception should've been thrown somewhere above, so here
  // we can announce SUCCESS
  return EXIT_SUCCESS;
}

编辑:用于基准测试的文件：http://www.filedropper.com/100_3.

Answer 1

1. 许多变量都有非常奇怪的名称(比如aoo )。这到底是什么意思？"at或operator()"，真的吗？)
2. 您将cache_t定义为向量向量，然后创建大量不可读的函数来处理它(包括初始化)。get_length_from_cache真的很大。我不知道里面发生了什么(在里面创建很多lambda函数有什么意义？在我看来，这只会增加混乱。在我看来，与cache_t相关的一切看起来都是一团糟。我强烈建议创建一个具有有意义的名称的适当文档化的类，该类使用简短、可读的、命名正确的方法实现缓存。另一个让它成为单独类的理由是，它实际上不是向量的向量:它是一种内部使用向量向量的数据结构(我不知道您的代码中到底发生了什么)。
3. 添加注释并不能神奇地提高代码的可读性。理想情况下，代码应该是自文档化的。这里绝对不是这样的。正如我之前说过的，我不知道缓存会做什么。
4. 我不认为拥有test_case结构和执行所有复杂的IO操作有什么意义。问题语句保证输入是正确的。它可以是: cin >> I >> j；cout << get_length_from_cache(.) <<‘n’；
5. 如果您想使代码可读性，您应该：
   • 正确地构造它(如果某物是一个单独的实体，就像您的缓存一样，它应该作为一个单独的类实现)
   • 尽可能避免使代码变得复杂。做同样事情的更简单的方法通常是更好的方法。