将列表的列表转换为树结构的形式，以提高搜索效率

作为项目需求的一部分，我需要在列表列表中搜索节点(字符串)。集合由N个链表组成，每个链表是由L个节点组成的链表。这里N的值较大，一般为>= 5000, L =<100 .

哪种数据结构最适合转换每个列表的L节点，从而使搜索更快更容易?

我不确定是否以某种树结构的形式转换列表，因为列表的节点是字符串(我可以手动分配一些no。把每个节点转换成合适的树结构，这样搜索会更快吗?如果是，哪个树结构是理想的)

提前感谢您的帮助。

我建议有两种结构:

1)排序字符串的列表，以便您可以进行二进制搜索(复杂度:O(n*log(n))插入和搜索)

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

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

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

我建议使用散列映射或排序树，将字符串(城市名称)映射到形式为(index_in_main_list, index_in_subblist)的元组。

在哈希映射的情况下，这允许常量时间查找String，同时仍然允许在原始列表上迭代。

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

例如，在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));
    }
}

编辑:请注意，如果您不需要遍历原始列表，则可以在构建哈希映射或树后将其删除。当索引被记住时，您仍然可以找到该城市所属的序列。为了迭代而重建列表将会是一种混乱。

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

你可以使用索引像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所说，另一种选择是使用hashmap，但是其余的代码(如果您希望操作列表)将会有点困难，所以请保持简单。:)

相关内容

最新更新

热门标签：