logo标签列表

在Java中，存储未知数量的字符串的最快方法是什么？

javalistcollections
3
我想要存储未知数量的字符串，并在以后按添加顺序读取它们。如我所说，我需要的唯一功能是：
  • 可以添加未知数量的字符串，而不会因为调整大小而变慢
  • 可以按添加顺序读取元素
问题在于，我希望从字典树的一部分输出字符串。因此，在返回字符串之前计算字符串数量将使操作所需的时间加倍。
（另一种解决方案是使用属性跟踪字典树中的字符串数量，但由于我只想返回字典树的一部分，这也不是完美的解决方案）
1
你考虑了哪些选项？ - Andrew Logvinov
3
预计平均有多少个字符串（数量级）？读取前是否已知数量？这是一个硬实时应用程序还是您只是过早地进行优化？针对每个问题的答案（即使是有教养的猜测）可能会大相径庭，而且可能还存在其他因素。此外，“哪种更快？”的唯一通用答案是“试一下并进行分析！”。 - user395760
@delnan 经过一些测试，似乎 ArrayList 更快。如果有不同的可能性，你可以告诉我它们分别在什么情况下更快。 - w1th0utnam3
正如我对Jon Skeet的回答所指出的那样：如果您可以不使用调整大小，基于数组的解决方案在分配和操作方面更快；否则，根据您需要的操作，各种链接列表可能会有用；展开这些列表（将多个项目分组为一个列表节点，避免分配和指针跟踪）如果有大量项目，则也可能有用。如果您需要特定的访问模式，则队列或双端队列可能是一种选择。最后，如果您只是过早地进行优化，则总体上最优选择是任何可用的东西。 - user395760
4个回答
7

LinkedList<string> 对我来说似乎是很好的选择...

  • 保持顺序
  • O(1) 头尾加入元素
  • O(1) 头尾删除元素
  • 遍历成本低廉

访问任意元素开销较大，这通常是不使用它的原因...但在你的情况下似乎不是问题。

3
当然，复杂度并不是一切。假设为了论点而言，OP真正需要的是N-M个字符串中速度最快（以毫秒计）的方法。如果在读取第一个字符串之前已知实际数量，则无需调整数组大小并且可以进行单次分配。同样地，如果M相对较小，可能可以通过采用最坏情况大小来避免重新分配。可能还有更多的例外情况。我并不是针对你的答案或任何其他答案，只是反对这种类型的问题（“我需要做X；我不知道Y和Z，但我真的需要快！”）。 - user395760
1
LinkedList在基本操作中比ArrayList慢得多。LinkedList为每个元素创建新对象，这比ArrayList所做的工作更多。 - Piotr Praszmo
虽然 LinkedList 可能表现出更稳定的添加时间，但插入许多元素时 LinkedList 的整体性能似乎略逊于 ArrayList。（请参见我的答案以获取一些基准测试结果。）使用迭代器迭代 LinkedList 也稍微慢一些（使用显式索引迭代会更慢）；跟随引用不如索引数组快。 - Ted Hopp
3

ArrayList通常比LinkedList快。如果您未指定适当的大小，则每次容量耗尽时，它都将不得不重新分配一个新数组（大小加倍），并将元素复制到新数组中。

您可以使用LinkedList来避免这个成本，但平均时间可能会更长。

无论使用哪种集合，如果内存不足，则GC将触发，这可能还会引入一些延迟。在任何内存中的集合中，"未知数量"而没有任何限制是不可能存储的。如果"未知"可能非常非常大并禁止使用内存中的集合，则必须使用文件或数据库。

2

两个明显的选择是ArrayList和LinkedList。 LinkedList似乎比ArrayList稍微慢一些。这是我的基准测试代码:

import java.util.*;

public class ListTest {
    private static final int N = 50000;
    private static final float NANO_TO_MILLI = 1.0e-6f;

    public static void main(String[] args) {
        String[] strings = new String[N];
        for (int i = 0; i < N; ++i) {
            strings[i] = Integer.toString(i);
        }

        System.out.print("ArrayList: ");
        benchmark(strings, new ArrayList<String>());

        System.out.print("LinkedList: ");
        benchmark(strings, new LinkedList<String>());
    }

    private static void benchmark(String[] strings, List<String> list) {
        // measure how long it takes to add the strings
        long start = System.nanoTime();
        for (String s : strings) {
            list.add(s);
        }
        long addTime = System.nanoTime() - start;

        // measure how long it takes to iterate the list
        start = System.nanoTime();
        int i = 0;
        for (String s : list) {
            ++i;
        }
        long iterateTime = System.nanoTime() - start;

        // report the results
        System.out.println(String.format("add: %.2fms; iterate: %.2fms (%d strings)",
            addTime * NANO_TO_MILLI,
            iterateTime * NANO_TO_MILLI,
            i));
    }
}

下面是一次典型运行的结果：

ArrayList：添加：5.52毫秒；迭代：7.66毫秒（50000个字符串）
LinkedList：添加：7.79毫秒；迭代：8.32毫秒（50000个字符串）

这是在一台装有Intel Core2 Quad Q6600 2.4GHz处理器的Windows机器上进行的。

请注意，这只测量了总时间。它没有测量单个字符串添加时间的变化，我预计ArrayList比LinkedList更高，因为需要重新分配内部数组。

编辑：如果我修改main来重复五次测试，并在每次调用benchmark后调用System.gc()，那么我会得到一些有趣的结果：

ArrayList：添加：5.84毫秒；迭代：7.84毫秒（50000个字符串）
LinkedList：添加：7.24毫秒；迭代：8.27毫秒（50000个字符串）

ArrayList：添加：0.45毫秒；迭代：0.60毫秒（50000个字符串）
LinkedList：添加：0.84毫秒；迭代：5.35毫秒（50000个字符串）

ArrayList：添加：0.52毫秒；迭代：0.72毫秒（50000个字符串）
LinkedList：添加：0.81毫秒；迭代：5.57毫秒（50000个字符串）

ArrayList：添加：3.77毫秒；迭代：0.71毫秒（50000个字符串）
LinkedList：添加：3.35毫秒；迭代：0.93毫秒（50000个字符串）

ArrayList：添加：3.39毫秒；迭代：0.87毫秒（50000个字符串）
LinkedList：添加：3.38毫秒；迭代：0.86毫秒（50000个字符串）

这可能是由于CPU缓存引起的。请注意，对于添加字符串，LinkedList可能会稍微快一些（例如，最后两次迭代），尽管它也可能慢得多。迭代对于LinkedList来说也可能极其缓慢，这也可能是由于局部性不足所致。

感谢您的帖子。目前我正在使用ArrayList，所以我将继续使用它。 - w1th0utnam3
1

使用List接口的实现。通常认为ArrayList是最好的通用集合，因此对于存储字符串，可以做一些简单的事情：

List<String> stringList = new ArrayList<String>();
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接