python - 我的 Codekata 解决方案提供了正确的解决方案，但在最终测试用例期间遇到了性能问题

Question

我在 python3 中完成了我的算法以解决 codewars.com 上的“codekata”。(https://www.codewars.com/kata/odder-than-the-rest-1/train/python)我的代码正确地解决了初始测试用例并且速度足够快。然而，当提交它进行最终测试时，代码会因为花费太长时间来解决给定任务而超时。

最初，我将 for 循环的内容实现为一个名为“calculate_oddness_level”的单独函数。我发现这可能比在 for 循环内执行要慢一些，所以我就这样做了。

我知道在 for 循环中执行 while 循环并不是最佳性能。我想过几次如何避免这种情况。但是，我需要确定列表中每个奇数的“奇数”级别。为了确定“级别”，需要一个循环并且似乎比递归更快。因此，除了在 for 循环中运行 while 循环之外，似乎别无选择。然而，我通过立即为它们分配“奇数级别”0 来消除所有偶数运行循环。

因此我不知道如何才能显着提高性能。

def oddest(a):
        if len(a) == 0: return None
        list_of_oddness_levels = []
        for n in a:
                if n % 2 == 0:
                     list_of_oddness_levels.append(0)
                else :
                    level = 1
                    while True:
                        n = (n-1)/2
                        if n % 2 == 0 or n % 1 != 0:
                                break
                        else:
                                level += 1
                    list_of_oddness_levels.append(level)
                print("adding Level!")
        maximum = max(list_of_oddness_levels)
        index_of_maximum = list_of_oddness_levels.index(maximum)

        if list_of_oddness_levels.count(maximum) > 1:
                return None
        else:
                return a[index_of_maximum]

根据最初的测试用例，我的代码应该能正确解决任务。然而，它似乎运行速度很慢，因为它在最终提交期间遇到了超时错误。

我知道，可能有一些简单的数学解决方案或大约 5 行高级代码利用了一些我不知道的 python3 库或特殊函数。然而，一个详细的、一步一步的、尽可能具有描述性的“干净代码”解决方案将是首选。

Answer 1

• 你不需要一个列表，你可以用 O(1) 的额外空间来完成。

• 问题很可能不是您的实现，而是 -1。为什么？它是无限奇数，因为 (-1 - 1)/2 = -1。有趣的是，这是唯一一个这样的数字，所有其他负数的奇数级别都是 1。

• 对于正数，您基本上是在计算从右边设置为 1 的连续位的数量，因此您可以使用掩码来提高速度。

假设 32 位整数(对不起 Java)，这就是这样一个实现的样子:

public Integer oddest(int[] a) {
    if (a == null || a.length == 0)
        return null;
    // create the 31 masks needed, the left-most bit is only set for negative numbers
    int[] masks = new int[31];
    masks[0] = 1;
    for (int i = 1; i < 31; i++)
        masks[i] = (masks[i - 1] << 1) | 1; // masks[i - 1] * 2 + 1
    int bestNumber = 0;
    int bestLevel = 0;
    boolean conflict = true;
    for (int n : a) {
        int level = 0;
        if (n == -1) {
            return -1;
        } else if (n & 1 == 1) { // number is odd
            if (n < 0) {
                level = 1;
            } else {
                // now use the masks and bisection to find the oddity of positive numbers
                int left = 0; // finally at the index of best matching mask
                int right = 31; // never reached, finally left + 1
                while (left + 1 < right) {
                    int mid = (left + right) >> 1;
                    if (n & masks[mid] == masks[mid])
                        left = mid;
                    else
                        right = mid;
                }
                level = right;
            }
        }
        if (level > bestLevel) {
            bestNumber = n;
            bestLevel = level;
            conflict = false;
        } else if (level == bestLevel && n != bestNumber) {
            conflict = true;
        }
    }
    if (conflict)
        return null;
    return bestNumber;
}