为什么嵌套循环在代码中被认为是低效和糟糕的设计？嵌套循环的更好选择是什么？

Question

这个问题涉及到另一个问题（link 在评论中给出），它建议使用 switch 语句，但在我的情况下，我认为使用 switch 语句是不适用的。

我写了一些 Java 代码，可以将 phone 数字 (123456789) 转换为相应的英文单词（一二三四五六七八九）。

此 Java 程序还识别连续两次和三次出现的数字。在这种情况下，第一个出现的地方将被读作一个单独的数字，然后是 "double" 或 "triple" 个数字.例如，数字 "1 2 222" 将被读取为 "one two triple two".

public class DigitToWord {

    public static Map<String, String> map;

    static {
        Map<String, String> result = new HashMap<>();
        result.put("0", "zero");
        result.put("1", "one");
        result.put("2", "two");
        result.put("3", "three");
        result.put("4", "four");
        result.put("5", "five");
        result.put("6", "six");
        result.put("7", "seven");
        result.put("8", "eight");
        result.put("9", "nine");
        map = result;
    }

    public static String convertNumberToWords(String n) {
        String result = "";
        for(int i=0; i<n.length(); i++) {
            String w = Character.toString(n.charAt(i));
            String d = map.get(w) + " ";
            if( (i < n.length()-2)  &&  ((Character.toString(n.charAt(i+1)).equals(w))  &&  (Character.toString(n.charAt(i+2)).equals(w))) ) {
                result = result + d + "double " + d;
                i += 2;
            } else if( (i < n.length()-1)  &&  (Character.toString(n.charAt(i+1)).equals(w)) ) {
                result = result + " double " + d;
                i += 1;
            } else {
                result = result + d;
            }
        }
        return result;
    }
}

以下是我认为值得讨论的问题：

问题 1。由于这些嵌套循环（特别是对于生产代码），为什么这被认为是一个糟糕的设计？嵌套循环的更好替代方案是什么？

问题 2。如果我们向该程序添加更多功能，我们如何使该代码具有可扩展性？

Q2的解释：比如有四个连续的数字，打印'quadruple'。如果五个连续的数字，打印'quintuple'。如果连续六个数，打印'sextuplet'.

我天真的方法，解决Q2是写另一个函数打印'quadruple'，一个单独的函数打印'quintuple'，另一个函数打印'sextuplet'，等等。

虽然我愿意听取您的反馈和建议，但我认为这可能有助于我改进，这种方法听起来很老套且无效。

Answer 1

Why is this considered a bad design, due to these nested loops (especially for production code)?

嵌套循环本身并不是“糟糕的设计”。

嵌套循环可能是一个低效的解决方案，可能是一个更好的解决方案。另一方面，它们 可能不是 更好的解决方案。（旁白：低效的解决方案不一定是糟糕的设计。这取决于低效对其他事物以及您的优先级的影响。）

考虑以下因素：

String[][] lotsOfStrings = new String[N][N];

// Populate the above from a file

// Find "fred"
boolean found = false;
for (int i = 0; i < N && !found; i++) {
    for (int j = 0; j < N && !found; j++) {
        found = "fred".equals(lotsOfStrings[i][j]);
    }
}

这是一个嵌套循环。但这并不是低效的。事实上，在这里尝试避免嵌套循环会导致 non-idiomatic 代码的效率很可能低于上面的代码，尤其是在它被 Java JIT 编译器优化之后。

What is the better alternative to nested loops?

对此没有统一的答案。这取决于您要解决的问题。

IMO，前面的示例没有“更好”的解决方案。无论如何，您必须先测试 N^2 个字符串，然后才能确定缺少 "fred" 个字符串。（如果你使用嵌套循环或其他一些方式来迭代它们，这并没有什么不同。）

您可以对其进行调整，使其略微更快。但是花费大量精力编写适当的性能测试、调整、测试、调整、测试……可能不值得付出努力。

但在其他情况下...

假设我们需要查找 巨大的 字符串数组是否包含任何重复项。简单的解决方案是：

String[] lotsOfStrings = new String[N];

// Populate the above from a file

// Test for duplicates
boolean duplicates = false;
for (int i = 0; i < N && !duplicates; i++) {
    for (int j = i + 1; j < N && !duplicates; j++) {
        duplicates = lotsOfStrings[i].equals(lotsOfStrings[j]);
    }
}

即要进行N * (N + 1) / 2比较，其中N是字符串的个数。（它有复杂性O(N^2)）

一个更复杂的解决方案是：

String[] lotsOfStrings = new String[N];
// Populate the above from a file

// Test for duplicates
Set<String> seen = new HashSet<>();
boolean duplicates = false;
for (int i = 0; i < N && !duplicates; i++) {
    duplicates = !seen.add(lotsOfStrings[i]);
}

那只会执行 N 添加操作，而 HashSet 上的 add 是 O(1)（摊销）。所以上面会快很多......当 N 很大时。（但是对于 N 的非常小的值，它会变慢，因为创建 HashSet 并向其添加对象的开销。）

How do we make this code scalable; e.g. to support "triple", "quadruple", "quintuple" etcetera.

嗯，这实际上是一个示例，其中嵌套循环提供了一个简单而有效的解决方案。像这样：

public static Map<Integer, String> map2;

static {
    Map<Integer, String> result = new HashMap<>();
    result.put(2, "double");
    result.put(3, "triple");
    result.put(4, "quadruple");
    // ...
    map = result;
}


public static String convertNumberToWords(String n) {
    String result = "";
    for(int i=0; i<n.length(); i++) {
        String w = Character.toString(n.charAt(i));
        String d = map.get(w) + " ";
        int count = 1;
        while (count + i < n.length) {
            if (n.charAt(i) == n.charAt(i + count)) {
                count++;
            } else {
                break;
            }
        }
        if (count > 1) {
            result = result + " " + map2.get(count) + " " + d;
            i = i + count - 1;
        } else {
            result = result + " " + d;
        }
    }
    return result;
}

请注意，您的原始版本中存在一些问题（我认为还有错误），但为了（我的！）时间，我不会指出它们。

最后，我要指出，除非您翻译的 phone 数字有数百位，或者数百万 phone 数字，否则这段代码的效率很可能无关紧要。

并且使用 switch 与使用 Map 之间的性能差异将太小而不相关，除非您正在处理大量 phone 数字翻译。

低效的解决方案不一定是坏的解决方案。

Secondly, when you're given with such a problem by your employer/recruiter, they do not want Just solution, but how efficient your code is and how many possible ways you come up with for solving the problem.

嗯，是的。但他们真正想知道的是，您是否有能力识别何时可以更有效地解决问题。（假设他们并非毫无头绪。毫无头绪的招聘人员是个问题。）为此，您需要比“嵌套循环不好”做得更好。这就是为什么一个好的 CS 学位在数据结构和算法上有 1 或 2 个单元......教学生（除其他外）如何进行复杂性分析，以及如何科学地优化代码 .

为什么嵌套循环在代码中被认为是低效和糟糕的设计？嵌套循环的更好选择是什么？

Why are nested loops considered as inefficient and bad design in code? What is the better alternative of nested loops?

java

scalability

hashmap

nested-loops