list - 以树结构的形式转换列表列表以进行高效搜索

Question

作为项目要求的一部分，我需要在列表列表中搜索节点（字符串）。该集合由 N 个列表组成，每个列表都是由 L 个节点组成的列表。这里 N 的值很大，通常 >= 5000，L =< 100。

什么数据结构最适合转换每个列表的 L 个节点，以便搜索更快更容易？

我不确定是否将列表转换为某种树结构的形式，因为列表的节点是字符串（我可以手动为每个节点分配一些编号并将其转换为合适的树结构，以便搜索更快？如果是，哪种树结构是理想的）

提前感谢您对此提供的任何帮助。

score 1 · Accepted Answer

我建议两种结构：

1）对字符串列表进行排序，以便您可以进行二进制搜索（复杂性：O(n*log(n)) 用于插入和搜索）

2) 更好：将字符串放在一个hashmap中，这样插入和搜索是O(1)。

您也可以使用 B-tree (http://en.wikipedia.org/wiki/B-tree)，但它类似于保持列表有序，我认为这会导致更多开销。

如果性能是一个问题，我肯定会选择（2）。

score 1 · Accepted Answer

我建议使用散列图或排序树，将字符串（城市名称）映射到形式的元组（index_in_main_list，index_in_sublist）。

在散列映射的情况下，这允许对字符串进行恒定时间查找，同时仍允许对原始列表进行迭代。

你提到了城市的字符串，子列表是旅行路线。由于城市可能位于多条旅行路线上，因此您应该为每个散列保留几个元组。

例如，在 Java 中，类型声明将是：

public class IndexTuple {
    public final int fst;
    public final int snc;
    public IndexTuple(int fst, int snd) {
        this.fst = fst;
        this.snd = snd;
    }
}

HashMap<String, ArrayList<IndexTuple>> lookupMap;

// The sublists of cities. I've used an ArrayList as example, but
// that's language and context dependent. Use arrays if the size
// won't change.
ArrayList<ArrayList<String>> cities;

填充数据结构变得非常容易，只需遍历列表并添加：

for(int i = 0; i < cities.size(); i++) {
    for(int j = 0; j < cities.get(i).size(); j++) {
        String city = cities.get(i).get(j));
        if(!lookupMap.containsKey(city) {
            lookupMap.put(city, new ArrayList<IndexTuple>());
        }
        lookupMap.get(city).add(new IndexTuple(i, j));
    }
}

编辑：请注意，如果您不必遍历原始列表，则可以在构建散列图或树后将其删除。记住索引后，您仍然可以找出城市所属的序列。重建列表以进行迭代将是一种混乱。

score 0 · Accepted Answer

我实际上不会更改数据结构。列表列表是一个非常好的数据结构，原因有两个：

您可以使用 Mainlist(5)(7) 之类的索引，基本上将您的列表视为一个大的二维数组（具有不同的列大小）。
很容易在你的脑海中“想象”，这样进一步的编码会更容易

因此，根据您的编程语言，可以执行双重 for 循环：

for all elements in mainlist:
   for all elements in sublist:
       if element == target:
           break;
       endif
    endfor
endfor

或者更好的是，您可以使用 foreach 循环：

在任何情况下，foreach 都非常有效，它会遍历所有列表并停止（一旦你说 break;）。所有其他转换可能会花费您大量的计算。

另一种选择是 izaera 所说的使用哈希图，但是您的其余代码（如果您希望操作列表）会有点困难，所以请保持简单。:)

list - 以树结构的形式转换列表列表以进行高效搜索

3 回答 3

Related

Reference