java - 将字符串插入已排序的字符串数组列表的最有效方法是什么？

Question

我有一个包含 17,000 个单词的 ArrayList。仅当单词尚未在列表中时，我才需要将其添加到列表中，并且我需要保留列表的排序顺序。即，我需要将其放入按字母顺序排列的正确位置。

我不知道如何找到正确的插入位置。我正在使用二进制搜索来查找单词是否已经在列表中，如果它在列表中则返回索引，如果不是则返回-1。我打算使用 ArrayList.add(int index, E element) 把它放进去。

score 3 · Accepted Answer

TreeSet将为您处理重复项，并按字母顺序排列单词。

示例：（WordList是ArrayList单词的）

TreeSet<String> WordSet = new TreeSet<String>(WordList);

score 2 · Accepted Answer

使用内置binarySearch方法。如果未找到密钥，则返回的数字为
-(insertionIndex) - 1

score 1 · Accepted Answer

在二分搜索中，您将到达一个点，即您还剩下 2 个项目，一个在上面，一个在下面，其中一个可能 == 到您的项目。对于您的情况，您将没有 == 情况，因此返回较高的索引并插入其位置。不知道java有没有元组类，也可以自己构建一个容器。无论哪种方式，返回类似：

(bool, int) binSearch(IList list)
  returns true, -1 if found
  returns false, higher of 2 bounds otherwise

显然这不是java，但转换并不困难

score 1 · Accepted Answer

如果您编写了二进制搜索，则可以对其进行修改以返回最后搜索的值。该值可以是匹配字符串的位置，也可以是应该插入的位置。

那是在二分搜索中，您细分列表，直到您找到字符串或无法进一步细分它。不能再细分列表的那个位置就是应该插入字符串的位置。

score 0 · Accepted Answer

众所周知，要加快进程，一般的想法是使用更多的内存。在这里，它可以是每个字母的第一个字符串的索引。例如一个额外的 ArrayList，用伪写：

ArrayList indexes;
indexes[0] = {"a", 0};
indexes[1] = {"b", 123};
...

对于以“a”开头的字符串，您可以在索引 0-123 之间进行二进制搜索。

score 0 · Accepted Answer

如您所说，如果没有重复的单词，则可以考虑实施trie。在 trie 上的插入操作比在哈希表中要快一些，因为没有冲突。搜索也是如此。

此外，在ArrayList列表中间插入一个元素，这意味着重新定位一半元素或增加数组大小，这可能有点昂贵。

如果你很好奇，可以在以下页面中看到一个实现：https ://forums.oracle.com/forums/thread.jspa?messageID=8787521

6 回答 6