哪个更贵?实例化高级数据结构或执行几个循环(一个接一个O(n))并使用数组

Question

我的任务是创建一个算法来解决给定的问题，但也被指示在时间和内存方面给出最优的解决方案。我将得到一个字符串数组。最后，我想把数组中所有字符串的所有字符都放到char[]中。

我对你的问题(特别是那些处理过代码和性能优化的人)是我应该使用List<char>然后手动销毁对象并将内容复制到char[]中，或者我是否手动执行并且仅使用数组(我也不确定如何做。)。实例化List<>对象的成本是否大于循环遍历String[]，将每个字符串转换为char[]，然后将所有char[]数组合并在一起?

编辑:

好吧，我再精确一点。将String[]的所有字符串转换为List<>或任何其他抽象数据结构并使用该结构，还是执行以下操作更好:循环遍历String[]，将每个字符串转换为char[]，然后将所有char[]数组合并在一起?

Answer 1

如果您需要重复，那么实际上您只需将所有字符串附加在一起。在这种情况下，为什么不使用字符串缓冲区呢?

StringBuilder sb = new StringBuilder();
for (String s : myStringArray){
    sb.append(s);
}
char chars[] = sb.toString().toCharArray();

StringBuilder也可以创建一个初始容量，以避免动态调整大小的成本。这不会像分配char[]和直接插入字符那样快，但对于大多数用途来说应该足够快。作为另一种选择，请检查CharBuffer，它由char[].

Answer 2

我假设你真正想做的是连接字符串(即连接它们端到端)以形成字符数组。

这可能是最节省内存的方法:

int size = 0;
for (String s : strings) { size += s.length(); }
char[] result = new char[size];
int i = 0;
for (String s : strings) {
    for (int j = 0; j < s.length(); j++) {
        result[i++] = s.charAt(j);
    }
}

如果您试图最小化内存分配和/或复制，我不建议使用String.toCharArray()或StringBuffer/StringBuilder。

Answer 3

伪代码:

ArrayList<Character> charList = new ArrayList<Character>();
for ( String s : strings ) {
    charList.addAll(s.toCharArray());
}
return charList.toArray(Character.class);

之类的