11

我在竞争性编程竞赛的解决方案中多次遇到这个特定的代码片段。我了解此代码的基本用法来超越时间限制，但我想更深入地了解它。我知道 unistd.h 可以访问系统调用包装函数，例如 fork、pipe 和 I/O 原语（读、写……）。

如果有人可以解释或指导我找到可以帮助我进一步理解它的资源，那也很棒。

#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
class FastInput {
public:
    FastInput() {
        m_dataOffset = 0;
        m_dataSize = 0;
        m_v = 0x80000000;
    }
    uint32_t ReadNext() {
        if (m_dataOffset == m_dataSize) {
            int r = read(0, m_buffer, sizeof(m_buffer));
            if (r <= 0) return m_v;
            m_dataOffset = 0;
            m_dataSize = 0;
            int i = 0;
            if (m_buffer[0] < '0') {
                if (m_v != 0x80000000) {
                    m_data[m_dataSize++] = m_v;
                    m_v = 0x80000000;
                }
                for (; (i < r) && (m_buffer[i] < '0'); ++i);
            }
            for (; i < r;) {
                if (m_buffer[i] >= '0') {
                    m_v = m_v * 10 + m_buffer[i] - 48;
                    ++i;
                } else {
                    m_data[m_dataSize++] = m_v;
                    m_v = 0x80000000;
                    for (i = i + 1; (i < r) && (m_buffer[i] < '0'); ++i);
                }
            }
        }
        return m_data[m_dataOffset++];
    }
public:
    uint8_t m_buffer[32768];
    uint32_t m_data[16384];
    size_t m_dataOffset, m_dataSize;
    uint32_t m_v;
};
class FastOutput {
public:
    FastOutput() {
        m_dataOffset = 0;
    }
    ~FastOutput() {
    }
    void Flush() {
        if (m_dataOffset) {
            if (write(1, m_data, m_dataOffset));
            m_dataOffset = 0;
        }
    }
    void PrintUint(uint32_t v, char d) {
        if (m_dataOffset + 11 > sizeof(m_data)) Flush();
        if (v < 100000) {
            if (v < 1000) {
                if (v < 10) {
                    m_data[m_dataOffset + 0] = v + 48;
                    m_dataOffset += 1;
                } else if (v < 100) {
                    m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 0] = v + 48;
                    m_dataOffset += 2;
                } else {
                    m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 0] = v + 48;
                    m_dataOffset += 3;
                }
            } else {
                if (v < 10000) {
                    m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 0] = v + 48;
                    m_dataOffset += 4;
                } else {
                    m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 0] = v + 48;
                    m_dataOffset += 5;
                }
            }
        } else {
            if (v < 100000000) {
                if (v < 1000000) {
                    m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 0] = v + 48;
                    m_dataOffset += 6;
                } else if (v < 10000000) {
                    m_data[m_dataOffset + 6] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 0] = v + 48;
                    m_dataOffset += 7;
                } else {
                    m_data[m_dataOffset + 7] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 6] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 0] = v + 48;
                    m_dataOffset += 8;
                }
            } else {
                if (v < 1000000000) {
                    m_data[m_dataOffset + 8] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 7] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 6] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 0] = v + 48;
                    m_dataOffset += 9;
                } else {
                    m_data[m_dataOffset + 9] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 8] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 7] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 6] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
                    v /= 10;
                    m_data[m_dataOffset + 0] = v + 48;
                    m_dataOffset += 10;
                }
            }
        }
        m_data[m_dataOffset++] = d;
    }
    void PrintChar(char d) {
        if (m_dataOffset + 1 > sizeof(m_data)) Flush();
        m_data[m_dataOffset++] = d;
    }
    void ReplaceChar(int offset, char d) {
        m_data[m_dataOffset + offset] = d;
    }
public:
    uint8_t m_data[32768];
    size_t m_dataOffset;
};

还有一件事：在生产级代码中使用类似技术是一种好习惯吗？

4

3 回答 3

14

在生产级代码中采用类似技术是一种好习惯吗？

不，重新实现轮子会导致错误。错误需要额外的开发时间和成本。

可以帮助我进一步理解它。

如果您不理解代码，则代码编写得不好。代码是由人类编写的，也是为人类编写的。如果另一个程序员不能很快地理解代码，可能会有很大的问题。这种想法（“为人类编写”）背后的基本原理很简单：开发时间成本很高，而不可读的代码会增加开发时间。

有问题的代码片段利用了几种糟糕的编码实践：

  1. 匈牙利表示法（在区分大小写的表示法中，尤其是在 C++ 中，不需要它），
  2. m_v短变量成员（例如，您能在不阅读程序其余部分的情况下说出什么意思吗？）
  3. 硬编码值 ( + 48, + 11)
  4. （主观）混合有符号/无符号整数/字符（mingw/gcc 在编译时会惹恼你）。
  5. 代码复制粘贴（v /= 10和类似的 - C++ 有宏/模板，该死的，所以如果你想手动展开循环，请使用它们！）。
  6. 不必要的多级 if/else。

除非您想在编程方面变得更糟，否则我建议您避免尝试“理解”此代码片段。这是坏的。

我严重怀疑这种特殊设计是分析的结果。最有可能的情况是一些“天才”假设他的代码片段将胜过内置函数。

当您想要性能时，请遵循以下模式：

  1. 编写初始版本。
  2. 重复直到性能提升不再值得或直到没有解决方案：
    1. 不要对什么会提高性能做出太多假设。你是人，人的工作就是犯错。根据墨菲定律，您的假设将是不正确的。
    2. 首先考虑算法优化。
    3. 通过探查器运行代码。
    4. 定位瓶颈。
    5. 如果在此特定例程中花费的总时间将减少到零，请调查总性能增益。
    6. 如果收益合理（时间/成本），则优化程序。否则忽略。
于 2012-03-17T13:08:05.810 回答
3

试试这个以获得更快的 I/O

ios_base::sync_with_stdio(false); cin.tie(NULL);

它设置标准 C++ 流是否在每次输入/输出操作后与标准 C 流同步。默认情况下，iostream 对象和 cstdio 流是同步的。

于 2015-08-24T17:50:07.503 回答
2

在PrintUint函数中，他基本上只是手动展开一个循环。展开循环有时是一件好事——但是编译器已经这样做了，而且大多数时候会比你做得更好。

要插入我最喜欢的语言功能，最好使用模板来实现：一个简单的实现（可能存在更聪明的实现）如下所示：

// I'm sure the compiler can figure out the inline part, but I'll add it anyways
template<unsigned int N> 
inline void print_uint_inner(uint32_t v) {
    m_data[m_dataOffset + N] = v - v / 10 * 10 + 48;
    print_uint_inner<N-1>(v / 10);
}

// For situations just like this, there's a trick to avoid having to define the base case separately.
inline void print_uint_inner<0>(uint32_t v) {
    m_data[m_dataOffset] = v - v / 10 * 10 + 48;
}

template<unsigned int N>
inline void print_uint_helper(uint32_t v) {
    print_uint_inner<N-1>(v);
    m_dataOffset += N;
}

// We could generate the compile-time binary search with templates too, rather than by hand.
void PrintUint(uint32_t v, char d) {
    if (m_dataOffset + 11 > sizeof(m_data)) Flush();
    if (v < 100000) {
        if (v < 1000) {
            if (v < 10) {
                print_uint_helper<1>(v);
            } else if (v < 100) {
                print_uint_helper<2>(v);
            } else {
                print_uint_helper<3>(v);
            }
        } else {
            if (v < 10000) {
                print_uint_helper<4>(v);
            } else {
                print_uint_helper<5>(v);
            }
        }
    } else {
        if (v < 100000000) {
            if (v < 1000000) {
                print_uint_helper<6>(v);
            } else if (v < 10000000) {
                print_uint_helper<7>(v);
            } else {
                print_uint_helper<8>(v);
            }
        } else {
            if (v < 1000000000) {
                print_uint_helper<9>(v);
            } else {
                print_uint_helper<10>(v);
            }
        }
    }
    m_data[m_dataOffset++] = d;
}

一般来说，做这种好的编码实践吗？可以，但前提是满足以下所有条件：

  • 您已经编写了明显的、易于理解的、简单的版本。
  • 您已经分析了您的程序，因此您知道这段代码花费了足够的时间来值得付出努力
  • 您愿意完成额外的工作以确保更复杂的版本实际上是正确的
  • 您已经对修改后的程序进行了概要分析，因此您知道重写实际上改善了您的运行时间。

此外，您可能应该保留切换回简单版本的能力，无论是使用编译时常量还是预处理器指令。这很重要，原因有两个：

  • 在调试时，切换回简单版本的能力将有助于缩小可能出现问题的地方
  • 当你尝试在不同的计算机上运行时（甚至是不同条件下的同一台计算机），你可能会发现复杂版本不再比简单版本快。
于 2012-03-17T12:44:09.573 回答