在这段代码中，给定一个由一百万个数字组成的字符串，要求返回所有重复的三位数。代码使用了Python标准库的collections.Counter类来实现。

这段代码中的问题是要找出字符串中重复的三位数。解决方法是使用collections.Counter类对字符串进行计数，并打印出重复次数大于1的三位数。

这段代码还提供了一个并行执行版本的解决方法。作者在一篇博客文章中详细解释了这个方法。该方法将字符串分割为多个部分，每个部分独立地扫描并计算重复的三位数，然后将每个部分的结果相加，并从最后一个部分中减去重复计数的三位数，最后得到最终结果。这个方法适用于在计算农场/云上的多个进程上并行执行。

然而，并行化会带来很大的开销，在字符串长度为100万字符的情况下，可能过于复杂。我们需要在进行优化之前进行性能分析，以确定是否值得承担维护代码的额外负担。

当然，在进行任何优化之前，我们需要先进行测量，以确保不会偏离Pythonic代码的原则。作者决定编写这段代码，以了解多核解决方案的实现工作量。

总结起来，这段代码的问题是要找出字符串中重复的三位数，解决方法是使用collections.Counter类进行计数，并提供了一个并行执行的版本。在选择是否使用并行化方案时，需要进行性能分析，并权衡维护代码的开销。

【文章】"Given a string of a million numbers, return all repeating 3 digit numbers"这个问题的出现的原因以及解决方法

在这段对话中，提到了一个问题：给定一个由一百万个数字组成的字符串，返回所有重复的三位数。讨论的开始，某些情况下了时间复杂度的问题，指出要查看这一百万个数字至少需要O(n)的时间复杂度，其中n是这里的一百万。接着，有人给出了一个O(n)的解决方案：创建一个大小为1000的数组，代表每个可能的三位数的出现次数。一次前进一位，第一个索引为0，最后一个索引为999997，然后递增数组[三位数]以创建直方图（每个可能的三位数的出现次数）。然后输出数组中计数>1的内容。

接下来，有人提出了一个问题，是否可以使用字典。这个字典的键是重复的三位数，值是它重复的次数。通过遍历字符串，可以向字典添加新的键值对（尽管这个字典可能会很长）。有人回答说，字典是可以使用的，但并不需要。所有可能的"键"在预先已知，限定在0到999的范围内。两者之间的区别是使用三个字符的字符串作为键进行基于键的访问所需的时间，与使用三位数字符串转换为索引然后使用索引访问数组所需的时间。

之后某些情况下了另一种方法，即使用BCD（二进制编码十进制）来存储三个数字，将它们存储在12位中。并通过屏蔽低4位来解码ASCII数字。但是这种x-'0'的模式在Python中是无效的，它是C语言的一个特点（其中字符是整数）。

然后有人说，相比简单的数组，字典要慢得多。Python中的字典查找非常快。当然，数组访问更快，所以如果我们一开始就处理整数，你是对的。然而，在这种情况下，我们有三位数的字符串，如果我们想要将它们与数组一起使用，首先必须将它们转换为整数。事实证明，与首先进行整数转换然后访问数组相比，字典查找实际上更快。在这种情况下，数组解决方案实际上比字典解决方案慢50%。

接下来有人表示，将字符串转换为数字的开销不应该比计算哈希值更大，而字典查找确实要计算哈希值。然后有人提出了一些优化的方法，将数组初始化为1000个零，这样就不需要检查空元素。一次取出4个索引：| num = int(str[i:i+6]) | arr[num // 1000] += 1 | arr[num % 1000] += 1 | num = (num % 100000) // 10 | arr[num // 10] += 1 | arr[num % 1000] += 1 | i += 4 | ...

在这个的问题中，还涉及到了时间复杂度的概念。有人指出，如果输入数字始终恰好有一百万位，则该算法的时间复杂度是O(1)，常数因子为一百万。

最后还某些情况下了关于时间复杂度的问题。有人表示，如果问题空间只有一个元素，那么从技术上讲，所有算法都与输入大小无关。

，这段讨论主要是围绕如何在给定一个由一百万个数字组成的字符串中找出所有重复的三位数展开的。讨论中提到了使用数组和字典两种方法，分别讨论了它们的优缺点和适用性。同时还涉及到了时间复杂度的问题，讨论了常数时间和线性时间的概念。通过这些讨论，我们可以得出一个解决这个问题的最佳方法，即使用一个大小为1000的数组，统计每个三位数的出现次数，并输出出现次数大于1的三位数。

文章标题：寻找重复的三位数-问题的原因和解决方法

你刚刚得到了轻松的任务，也许你不想为对冲基金工作，那里的量化分析师不了解基本算法 🙂

如果像在这个问题中那样，你需要至少访问每个元素，那么就没有办法以O(1)的复杂度处理任意大小的数据结构。在这种情况下，你所能期望的最好的复杂度是O(n)，其中n是字符串的长度。

尽管如此，一个名义上的O(n)算法对于固定的输入大小来说确实是O(1)，所以从技术上讲，他们在这里可能是正确的。然而，这通常不是人们使用复杂度分析的方式。

在我看来，你可以通过多种方式给他们留下深刻的印象。

首先，通过告诉他们，除非你使用上面提到的“可疑”的推理，否则不可能以O(1)的复杂度来解决这个问题。

其次，通过展示你高超的技能，提供像下面这样的Python代码：

inpStr = '123412345123456'
# O(1) array creation.
freq = [0] * 1000
# O(n) string processing.
for val in [int(inpStr[pos:pos+3]) for pos in range(len(inpStr) - 2)]:
    freq[val] += 1
# O(1) output of relevant array values.
print ([(num, freq[num]) for num in range(1000) if freq[num] > 1])

这将输出：

[(123, 3), (234, 3), (345, 2)]

当然，你可以根据需要修改输出格式。

最后，告诉他们，对于一个百万位数的字符串，上面的代码在不到半秒的时间内就可以得到结果。而且它似乎呈线性缩放，因为一个1000万字符的字符串需要3.5秒，一个1亿字符的字符串需要36秒。

如果他们需要更好的性能，还有一些可以大大加快处理速度的并行化方法。

当然，这不能在一个单独的Python解释器中完成，因为GIL的原因，但是你可以将字符串分割成像下面这样的部分（重叠由vv表示，以允许对边界区域进行正确处理）：

    vv
123412  vv
    123451
        5123456

你可以将这些部分分配给不同的工作线程，然后在结束后合并结果。

输入的拆分和输出的合并可能会淹没对小字符串（可能甚至是百万位数的字符串）的节省效果，但是对于更大的数据集来说，这可能会有所不同。当然，我的经典口头禅“测量，不要猜测”在这里也适用。

这个口头禅也适用于其他可能性，比如绕过Python，使用其他可能更快的语言。

例如，下面的C代码在与前面的Python代码相同的硬件上运行，处理一亿位数字只需要0.6秒的时间，大致与Python代码处理一百万位数字的时间相同。换句话说，速度要快得多：

#include 
#include 
int main(void) {
    static char inpStr[100000000+1];
    static int freq[1000];
    // Set up test data.
    memset(inpStr, '1', sizeof(inpStr));
    inpStr[sizeof(inpStr)-1] = '\0';
    // Need at least three digits to do anything useful.
    if (strlen(inpStr) <= 2) return 0;
    // Get initial feed from first two digits, process others.
    int val = (inpStr[0] - '0') * 10 + inpStr[1] - '0';
    char *inpPtr = &(inpStr[2]);
    while (*inpPtr != '\0') {
        // Remove hundreds, add next digit as units, adjust table.
        val = (val % 100) * 10 + *inpPtr++ - '0';
        freq[val]++;
    }
    // Output (relevant part of) table.
    for (int i = 0; i < 1000; ++i)
        if (freq[i] > 1)
            printf("%3d -> %d\n", i, freq[i]);
    return 0;
}

这个“固定输入大小”的说法听起来像一个笑话，不管是面试官还是应聘者都没有理解。只要n是固定的或有界的，任何算法都会变为O(1)。

如果他们需要更好的性能，也许他们不应该使用Python，至少对于具体的算法来说是这样。

非常感谢你详细的回答。你不仅解决了问题并回答了我的问题，还描述了面试过程和如何做得好的下一次面试。我会记住你的建议，为下一次面试做好准备。还有为什么是`len(inpStr) - 2`（为什么要减2）？

因为在尝试并行方法时，字符串被“分割”时可能会出现重叠的情况。由于你要寻找三位数的分组，-2允许在两个并行分组之间进行检查，以免错过潜在的有效匹配。

我还是不明白这个想法。我觉得我在并行编程知识上有所欠缺。有没有什么资源可以让我理解为什么是-2？

这不是缺乏并行编程知识的问题。考虑一个长度为N的字符串。如果你在位置N/2处将其分成两部分，你仍然需要考虑到在“边界”处可能会错过一个有效的三位数匹配。因此，你需要检查`string1[N/2-2]`和`string2[2]`之间的匹配（使用从零开始的索引），依此类推。这就是这个想法。

好吧，我明白了。天呐，这么简单，我怎么没明白呢。谢谢你花时间向我解释 🙂

对于更长的数字序列，使用滑动窗口来优化转换为整数的过程可能会有所帮助。例如使用`val -= 100 * (d[i]-'0')`来去掉最高位数字，使用`val = 10*val + d[i+2]-'0'`来累积一个新的最低位数字（正常的字符串转整数解析）。`val % 100`可能不会太糟糕，但前提是`100`是一个编译时常数，所以它不会使用真正的硬件除法。

或者也可以使用SIMD来优化字符串转整数：stackoverflow.com/questions/35127060/…。或者在字符串转整数过程中保存临时值，这样就不需要撤销最高位数字。（当然，对于更长的子字符串，直方图的大小会呈指数级增长，所以可能需要对数组进行多次遍历，只使用一个前缀来保持一些内存局部性。但是，肯定有办法在多次遍历中进行优化...）

在我的回答中的一个评论中，我提到了一次获取4个索引的选项，例如`num = int(str[i:i+6]) ... i += 4`（一次获取6个数字，每次推进4个数字以处理重叠），然后使用除法和模运算来选择四个三位数的集合。正如你提到的，这假设除以常数的操作已经被优化为乘法+移位。考虑到Python的速度可能比C / C++慢100倍以上，我不确定在Python中的除法开销是否那么显著。

这似乎不如保存临时值（例如，使用`10*d4 + d5`来计算`100*d3 + 10*d4 + d5`和`(10*d4 + d5) * 10 + d6`的一部分）好。也许在Python中，粘合操作的开销远高于操作本身的开销。很容易说“如果你关心性能，就不要以这种方式使用Python”，但有时候在Python中找到一个高效的方法已经足够，不需要再费心编写C或汇编实现。但请注意，实际的硬件除法在x86上的吞吐量成本是整数乘法的30倍（32位）或90倍（64位整数）。

`freq = [inpStr.count(str(n) for n in range(1000) if inpStr.count(str(n)) > 1]`这种写法如何？或者使用Counter对象？

当然，你应该自己测试一下这种写法。我假设你不是一个刚开始学习Python的初学者，所以我猜你有一个可以使用的环境 🙂