没有足够的背景信息来真正进行推测。我能做的最好的事情就是提到，在 AKS 环境中出现此行为的最常见原因是 pod 的 CPU 切片并发过多。我建议在 Azure SDK 存储库中打开一个问题，因为我们想要收集 Azure SDK 日志进行分析，从而深入了解您的应用程序和主机环境。

我正在练习黑客等级，题目如下：杰西喜欢饼干，他希望一些饼干的甜度大于价值。为此，需要两块甜度最低的饼干

我正在就以下问题进行黑客排名练习：

Jesse 喜欢吃饼干，他希望一些饼干的甜度大于价值。为此，将两块甜度最低的饼干反复混合。这样就形成了一种特殊的组合饼干，其特点是：

甜度（最不甜的饼干，第二不甜的饼干）。

如此循环，直到所有饼干都变甜为止。

给定一定数量的饼干的甜度，确定所需的最少操作次数。如果不可能，则返回。

例子

最小的值为 。移除它们然后返回到数组。现在 。移除并返回到数组。现在 。移除 ，返回 和 。最后，移除并返回 。现在 。所有值都是 因此过程在迭代后停止。返回 。

功能描述 在下面的编辑器中完成cookies功能。

cookies有以下参数：

int k：阈值 int A[n]：甜度值数组返回

int：所需迭代次数或 -1

我用 Python 编写了这个非常简单的解决方案：

def cookies(k, A):
    i = 0
    while True:
        A.sort()
        print(A)
        if A[0] >= k:
            break
        elif len(A)< 2:
            i = -1
            break
        n1 = A.pop(0)
        n2 = A.pop(0)
        new_cookie = (n1 + 2*n2)
        A.insert(0, new_cookie)
        i += 1
    return i

它失败了几个测试用例。我没有看到任何边缘情况的错误。速度之类的东西是通过黑客等级来评估的吗？这是否不是性能/最佳的？是否存在我的排序导致溢出的边缘情况？

编程挑战网站经常会遇到一些问题，即简单的实现方式时间复杂度很差。他们会向其抛出非常大的输入，如果超过时间限制，就会失败。你需要想出巧妙的解决方案来避免指数级的复杂度。

在学习按顺序执行的基本 5 级流水线处理器时，当处理器刷新时，每个分支预测错误所浪费的周期数是一个常数。但是

当了解按顺序执行的基本 5 级流水线处理器时，当处理器被刷新时，每个分支错误预测浪费的周期数是一个常数。

但是，对于具有深管道的多发射无序现代处理器来说，情况又如何呢？在课堂上，我们正在处理器上运行不同程序的模拟，并且每次预测失误所浪费的周期数因同一处理器的程序而异，在某些情况下，每次预测失误只浪费 10 个周期，但在某些情况下，预测失误前浪费的周期超过 100 个。这比管道深度大得多。我期望这个数字接近管道深度，并且与程序运行无关。

我一直在试图对此做出解释。我知道在现代处理器中，分支评估可能发生在不同的阶段，因此浪费的周期数不是恒定的。但我无法解释为什么对于不同的程序，这种差异可能大一个数量级。处理器是否“知道”哪些指令需要刷新？

现代处理器浪费的周期数会有很大差异，并且取决于程序吗？如果是这样，这怎么可能呢？不同的程序之间的差异怎么会这么大？

您的 HR 问题副本中似乎缺少一些单词。例如“如果不可能，则返回 。”——它应该返回什么？

您如何衡量分支预测失误的成本。我并不了解我的最新架构，但我很好奇，如果预测失误导致内存加载缓存未命中，然后是（正确路径）内存加载缓存未命中，是否会因占用主内存总线而导致极长的延迟。

您可以使用二分查找将新 cookie 插入到适当的位置，而不是每次循环时都对列表进行排序。排序是 n*logn，二分查找是 logn。

这是个好问题。模拟器对我来说有点像黑匣子，我一直在尝试找出它如何测量错误预测成本。我们正在使用 SESC 模拟处理器，但很难找到文档...

您可以使用 heapq 来解决这个问题。您当前的方法效率低下，并且会失败，正如评论所述。

import heapq

def cookies(k, A):
    heapq.heapify(A)
    i = 0

    while len(A) > 1 and A[0] < k:
        n1 = heapq.heappop(A)
        n2 = heapq.heappop(A)
        new_cookie = n1 + 2 * n2
        heapq.heappush(A, new_cookie)
        i += 1

    if A[0] < k:
        return -1
    return i

print(cookies(7, [1, 2, 3, 9, 10, 12]))

印刷

2

笔记

• pop(0) 从列表中选取具有 O(N) 时间复杂度。
• insert(0, value) 放入列表中也是 O(N) 时间复杂度。

您必须意识到，现代处理器可以在一个周期内完成（或试图完成）许多指令。因此，浪费的周期数可能很少，但周期数并不一定反映错误预测的真正浪费。

我会尝试一下这个。

多核架构中乱序执行所浪费的周期数将超过管道的深度，因为重新排序需要额外的努力。

现代推测核心中的分支可以在不同阶段（例如，ID vs. EXE vs. MEM）发现错误预测，这会导致错误预测后浪费的周期数不同。顺序处理器在解决错误预测时通常有一个固定的阶段，因此浪费的周期数是恒定的。

对于无序处理器，分支解析的点可能会有所不同，因此浪费的周期数也可能会有所不同。另外，请记住，无序处理器会根据发现错误预测时的推测深度推测性地执行指令，这可能会导致更多的浪费周期。一个推测的分支可能会导致其他推测的分支。对于每个程序来说，情况并不相同，并且无序的惩罚也会有所不同。

此外，预测器准确性、代码密度、并行性和访问模式也发挥着作用。考虑顺序访问，其中内存顺序将遵循程序顺序。每个程序是否具有相同的访问模式？程序之间使用了多少个线程？缓存局部性（空间、时间）？某些数据结构比其他数据结构更适合缓存；由于解决错误预测时的命中次数与未命中次数不同，错误预测周期惩罚可能会有所不同。（例如，链接列表的局部性较差，而数组的局部性很好）。

重新排序是什么意思？我认为我们在课堂上还没有讲过这个。我认为到目前为止最合理的解释是，这涉及到一些缓存/内存延迟，这就是为什么浪费的周期会有很大差异。在某些程序中，由于局部性较差，周期损失会更大。

我需要找到内存级并行性 (MLP) 或在处理过程中由每个缓存级别的未命中状态处理寄存器 (MSHR) / 填充缓冲区同时持有的内存请求数......

我需要找到在 C/C++ 程序执行期间每个缓存级别的内存级并行性 (MLP) 或由未命中状态处理寄存器 (MSHR) / 填充缓冲区同时持有的内存请求数。

我找到了一个 链接 ，它解释了使用不同的性能计数器事件来测量 L1 和 L2 MSHR。

我正在寻找 C/C++ 代码。

我编写了一些代码来解决在线问题，这里.mustConstraint = set()notConstraint = set()violated = 0satisfied = 0 for i in range(0, int(input(''))): constrain = input('')

我已经编写了一些代码来解决在线问题， 这里 .

mustConstraint = set()
notConstraint = set()
violated = 0
satisfied = 0 

for i in range(0, int(input(''))):
    constraint = input('')
    mustConstraint.add(frozenset(constraint.split()))

for i in range(0, int(input(''))):
    constraint = input('')
    notConstraint.add(frozenset(constraint.split()))

for i in range(0, int(input(''))):
    group = input('')
    group = set(group.split())

    for x in mustConstraint:
        if x & group == x:
            satisfied +=1
        
    for y in notConstraint:
        if y & group == y:
            violated += 1

violated += len(mustConstraint) - satisfied

print(violated)

总结一下这个问题，输入的第一行包含一个正整数 X，X => 0。接下来的 X 行输入将包含两个单词，以空格分隔。这两个单词 必须 属于同一组。输入的下一行将包含另一个正整数 Y，Y => 0。接下来的 Y 行输入将包含两个单词，以空格分隔。这两个单词 不能 属于同一组。输入的下一行将包含一个正整数 G，G >= 1。接下来的 G 行输入将分别包含三个不同的单词，以单个空格分隔。这三个单词被放在同一组中。

输出 0 到 X+Y 之间的一个整数，表示违反的约束的数量。

此处的 问题站点 ，因为通过提供的示例案例及其解释，可以更容易地理解问题。

不幸的是，由于最后一批有大约 300,000 个输入，我的嵌套 for 循环太慢了，无法满足 4 秒的时间限制——有人可以帮我优化代码吗？

大部分延迟来自于这个块：

for i in range(0, int(input(''))):
    group = input('')
    group = set(group.split())

    for x in mustConstraint:
        if x & group == x:
            satisfied +=1
        
    for y in notConstraint:
        if y & group == y:
            violated += 1

嵌套的 for 循环每次执行 100,000^2 次迭代，总计该代码块进行 200 亿次迭代（2*100,000^2）

如果有人能找到减少迭代次数的方法，那么将会产生很大的不同。

请在此处描述代码的作用，而不是仅提供外部站点的链接。结果应以文本形式发布，而不是屏幕截图。

我看到你接受了这里和你之前问题的答案。请不要忘记按照评论中的要求修复这两个问题（在本例中是@Barmar 的第一条评论）。请记住，这里的问题和答案应该对每个人都有用，包括未来有相同/类似问题的访问者。（真的，在你修复之前我不应该在这里回答，我只是太累了，没有注意到，之后才阅读评论。）

两种解决方案均轻松通过所有测试。

解决方案 1：最小改变

用组中三对上的小环替换较大的内环，即更改

    for x in mustConstraint:
        if x & group == x:
            satisfied +=1
        
    for y in notConstraint:
        if y & group == y:
            violated += 1

更改为：

    a, b, c = group
    for pair in {a, b}, {a, c}, {b, c}:
        if pair in mustConstraint:
            satisfied += 1
        if pair in notConstraint:
            violated += 1

解决方案 2：仅需两个集合运算

所有三个部分都指定了一组对。有助于将其放入函数中。然后查找/计算违规情况：

• 应该是但实际上不是的配对。
• 本来不应该存在但却存在着的配对。

from itertools import combinations

def pairs():
    return {
        frozenset(pair)
        for _ in range(int(input()))
        for pair in combinations(input().split(), 2)
    }

must = pairs()
must_not = pairs()
are = pairs()

print(len(must - are) + len(must_not & are))

您可以更有效地利用集合运算：

为了提高效率，一次读取所有输入。

使用字典来存储约束，使用集合来表示组。

通过迭代每个组并更新违规计数来有效地检查约束。

像这样：

import sys

input = sys.stdin.read
data = input().splitlines()

index = 0

# Read must constraints
must_constraint_count = int(data[index])
index += 1
must_constraints = []
for _ in range(must_constraint_count):
    must_constraints.append(set(data[index].split()))
    index += 1

# Read not constraints
not_constraint_count = int(data[index])
index += 1
not_constraints = []
for _ in range(not_constraint_count):
    not_constraints.append(set(data[index].split()))
    index += 1

# Read groups
group_count = int(data[index])
index += 1
groups = []
for _ in range(group_count):
    groups.append(set(data[index].split()))
    index += 1

# Check constraints
satisfied = 0
violated = 0

# Check must constraints
for must in must_constraints:
    in_same_group = False
    for group in groups:
        if must.issubset(group):
            satisfied += 1
            in_same_group = True
            break
    if not in_same_group:
        violated += 1

# Check not constraints
for not_c in not_constraints:
    for group in groups:
        if not_c.issubset(group):
            violated += 1
            break

print(violated)

输入处理： 为了提高效率，使用 sys.stdin.read 一次读取整个输入。

存储约束： 约束存储在集合列表中，以便于检查。

处理组： 将组存储为集合以利用快速子集检查。

检查约束：

对于每个必须约束，检查约束集是否是任何组的子集。如果是，则满足该约束。如果不是，则违反该约束。

对于每个非约束，检查约束集是否是任何组的子集。如果是，则违反了约束。

表现：

集合和 issubset() 方法的使用使得约束检查更加高效。

一次读取所有输入并在内存中处理可避免多次 I/O 操作，从而加快执行速度。

找到有关复杂常见操作的更多帮助 Big-O Cheat Sheet .

此外， Python 的时间复杂度 很好地解释了 Python 内置数据类型的性能特征。

\'这减少了迭代次数\' - 是吗？为什么？ - \'并且显著提高了性能\' - 是吗？有多少？