6

我正在编写一个严格读取文本文件（.txt）的java应用程序。这些文件可以包含超过 120,000 个单词。

该应用程序需要存储所有 +120,000 个单词。它需要将它们命名为 word_1、word_2 等。它还需要访问这些词以对它们执行各种方法。

这些方法都与字符串有关。例如，将调用一个方法来说明 word_80 中有多少个字母。将调用另一种方法来说出 word_2200 中的特定字母。

此外，有些方法会比较两个单词。例如，将调用一个方法来比较 word_80 和 word_2200 并需要返回哪个有更多的字母。将调用另一种方法来比较 word_80 和 word_2200，并且需要返回两个词共享的特定字母。

我的问题是：由于我几乎只使用字符串，最好将这些单词存储在一个大的 ArrayList 中吗？几个小的 ArrayList？或者我应该使用许多其他存储可能性之一，如向量、哈希集、链接列表？

我的两个主要问题是 1.) 访问速度，以及 2.) 拥有尽可能多的预建方法供我使用。

提前谢谢你的帮助！！

哇！感谢大家对我的问题提供如此快速的答复。你所有的建议都对我帮助很大。我正在考虑并考虑您反馈中提供的所有选项。

请原谅我的任何模糊；让我解决你的问题：

  1. 问）英语？
    A）文本文件实际上是用英文写的书。在第二语言中出现的单词是罕见的——但并非不可能。我将文本文件中非英语单词的百分比设置为 .0001%

  2. 问）家庭作业？
    A）我现在微笑着看着我的问题的措辞。是的，它确实类似于学校作业。但不，这不是家庭作业。

  3. 问）重复？
    一）是的。可能每五个左右的词，考虑连词，文章等。

  4. 问）访问？
    A）随机和顺序。一种方法当然有可能随机定位一个单词。一种方法同样可能希望在 word_1 和 word_120000 之间按顺序查找匹配的单词。这就引出了最后一个问题……</p>

  5. Q) 遍历整个列表？
    一）是的。

另外，我计划发展这个程序来对单词执行许多其他方法。我再次为我的模糊性道歉。（细节确实使世界变得不同，不是吗？）

干杯!

4

11 回答 11

16

我会将它们存储在一个大的 ArrayList 中，然后担心（可能不必要的）优化。

天生懒惰，我认为优化不是一个好主意，除非有明显的需要。否则，您只是在浪费本可以更好地花在其他地方的精力。

事实上，如果您可以为您的字数设置一个上限，并且您不需要任何花哨的 List 操作，我会选择一个普通的（本机）字符串对象数组，其中包含一个包含实际数字的整数。这可能比基于类的方法更快。

这为您提供了访问各个元素的最快速度，同时仍然保留了执行所有精彩字符串操作的能力。

注意我没有针对 ArrayLists 对原生数组进行基准测试。它们可能和原生数组一样快，所以如果你对我的能力没有我那么盲目相信的话，你应该自己检查一下:-)。

如果它们确实同样快（甚至接近），那么额外的好处（例如可扩展性）可能足以证明它们的使用是合理的。

于 2009-02-06T03:07:00.917 回答
3

只是用一个非常幼稚的基准来确认 pax 假设

public static void main(String[] args)
{
    int size = 120000;
    String[] arr = new String[size];
    ArrayList al = new ArrayList(size);
    for (int i = 0; i < size; i++)
    {
        String put = Integer.toHexString(i).toString();
        // System.out.print(put + " ");
        al.add(put);
        arr[i] = put;
    }

    Random rand = new Random();
    Date start = new Date();
    for (int i = 0; i < 10000000; i++)
    {
        int get = rand.nextInt(size);
        String fetch = arr[get];

    }
    Date end = new Date();
    long diff = end.getTime() - start.getTime();
    System.out.println("array access took " + diff + " ms");

    start = new Date();
    for (int i = 0; i < 10000000; i++)
    {
        int get = rand.nextInt(size);
        String fetch = (String) al.get(get);

    }
    end = new Date();
    diff = end.getTime() - start.getTime();
    System.out.println("array list access took " + diff + " ms");
}

和输出：
数组访问花了 578 毫秒
数组列表访问花了 907 毫秒

运行它几次，实际时间似乎有所不同，但通常数组访问快 200 到 400 毫秒，超过 10,000,000 次迭代。

于 2009-02-06T04:14:59.530 回答
2

如果您将按顺序访问这些字符串，则 LinkedList 将是最佳选择。

对于随机访问，ArrayLists 具有很好的内存使用/访问速度折衷。

于 2009-02-06T03:15:45.390 回答
1

我的看法：

对于非线程程序，Arraylist 总是最快和最简单的。

对于线程程序，java.util.concurrent.ConcurrentHashMap<Integer,String> 或 java.util.concurrent.ConcurrentSkipListMap<Integer,String> 非常棒。也许您稍后希望允许线程以便同时对这个巨大的事物进行多个查询。

于 2009-02-06T06:59:38.840 回答
1

如果您想要快速遍历和紧凑的大小，请使用 DAWG（有向无环字图）。这种数据结构采用了 trie 的概念，并通过查找和分解常见的后缀和常见的前缀对其进行了改进。

http://en.wikipedia.org/wiki/Directed_acyclic_word_graph

于 2011-02-14T21:46:23.303 回答
0

使用哈希表？这将为您提供最佳的查找速度。

于 2009-02-06T03:05:44.243 回答
0

ArrayList/Vector 如果顺序很重要（它看起来很重要，因为你正在调用单词“word_xxx”），或者 HashTable/HashMap 如果它不重要。

我将把弄清楚为什么要使用 ArrayList 与 Vector 或 HashTable 与 HashMap 的练习留给您，因为我偷偷怀疑这是您的作业。检查 Javadocs。

您不会从 Collections Framework 类中获得任何可以帮助您的方法，因为它们都没有执行字符串比较操作。除非您只想按字母顺序或其他方式对它们进行排序，否则在这种情况下，您将使用 Collections 框架中的 Tree 实现之一。

于 2009-02-06T04:39:01.947 回答
0

基数树或帕特里夏树怎么样？

http://en.wikipedia.org/wiki/Radix_tree

于 2009-02-06T06:40:55.087 回答
0

与数组或数组列表相比，链表的唯一优势在于是否在任意位置进行插入和删除。我认为这里不是这种情况：您阅读文档并按顺序构建列表。

我认为当原始发布者谈到找到“word_2200”时，他的意思只是文档中的第 2200 个单词，而不是每个单词都有任意标签。如果是这样，那么他所需要的就是对所有单词的索引访问。因此，一个数组或数组列表。如果真的有更复杂的东西，如果一个词可能被标记为“word_2200”而下一个词被标记为“foobar_42”或类似的，那么是的，他需要一个更复杂的结构。

嘿，你想告诉我们你为什么要这样做吗？我很难记得上次我对自己说：“嘿，我想知道我正在阅读的这份文件中的第 1,237 个单词是比第 842 个单词长还是短？”

于 2009-08-11T17:31:33.960 回答
-1

取决于问题是什么 - 速度或内存。

如果是内存，最小的解决方案是编写一个函数 getWord(n)，它每次运行时都会扫描整个文件，并提取单词 n。

现在 - 这不是一个很好的解决方案。一个更好的解决方案是决定你想使用多少内存：假设 1000 个项目。应用程序启动时扫描文件中的单词一次，并存储一系列书签，其中包含单词编号和文件中它所在的位置 - 这样做的方式是使书签或多或少均匀分布文件。

然后，打开文件进行随机访问。函数 getWord(n) 现在查看书签以找到最大的单词 # <= n（请使用二进制搜索），搜索到指定的位置，然后扫描文件，计算单词，找到请求的词。

一个更快的解决方案，使用更多的内存，是为块构建某种缓存 - 基于 getWord() 请求通常在集群中通过。您可以进行调整，以便如果有人要单词#X，但它不在书签中，那么您可以寻找它并将其放入书签中，通过合并最近最少使用的书签来节省内存。

等等。实际上，这取决于问题所在——取决于可能的检索模式。

于 2009-02-06T05:13:14.063 回答
-2

我不明白为什么这么多人建议使用 Arraylist 等，因为您没有提到必须遍历整个列表。此外，您似乎希望将它们作为键/值对（“word_348”="pedantic"）进行访问。

为了获得最快的访问速度，我会使用 TreeMap，它会进行二进制搜索以找到您的密钥。它唯一的缺点是它是不同步的，但这对您的应用程序来说不是问题。

http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html

于 2009-02-06T05:05:37.730 回答