1

考虑一下，如果我必须在表中搜索特定行，根据 ORM，每一行都是我相信的对象。我没有在 JDBC 上投入大量精力，所以通常作为一种更好的做法，这些 POJO 对象在哪里收集或保存？在集合或列表中？

我试图找到在 List Vs 中搜索元素的复杂性。放

我做了什么？

private void searchSet() {
        Set<String> names = new HashSet<>();
        names.add("srk");
        names.add("lastminute");
        names.add("monkey");
        for(String x:names){
            if(x.equals("monkey")){
                System.out.println("caught the name "+x);
            }
        }

}



private void searchList() {
    List<String> names = new ArrayList<>();
    names.add("srk");
    names.add("lastminute");
    names.add("monkey");
    for(String x:names){
        if(x.equals("monkey")){
            System.out.println("caught the name "+x);
        }
    }

}

我正在使用以下方法计算在集合和列表中搜索元素所花费的时间。

    long startTime,endTime,totalTime;
    startTime = System.nanoTime();
    endTime = System.nanoTime();
    totalTime = endTime - startTime;

现在，我有下面的统计数据

System.out.println("Time taken to search an element in list : "+totalTime);//for list - 614324 
System.out.println("Time taken to search an element in set : "+totalTime);//for set - 757359

基于这些统计数据可以得出结论，在 List 中搜索元素比在集合中搜索更快？哪个是存储数据库记录对象的更好集合，用于搜索。在 List Vs Set 中搜索元素的复杂性是多少。在一般意义上？

4

3 回答 3

4

数据结构没有复杂性，算法有。（请注意，数据结构通常具有其基本操作的复杂性，它们本身就是微小的算法。）在您的情况下，您自己为两个容器实现了查找算法，并且您将其作为线性搜索进行，即 O(n ）。您观察到的速度差异是 ArrayList 比 HashSet 遍历更简单和更快的结果，即算法具有相同的复杂性，但常数因子更小。

其次，您在要计时的函数中有 I/O。这通常会完全支配您执行的任何实际操作，并使您的基准测试无用。

第三，您正在寻找复杂性并编写了基准。那是错误的。您可以通过基准测试并在图表中绘制不同输入大小的结果来获得复杂性的提示，但要真正了解复杂性，您必须分析算法，而不是运行它。

第四，Java 中的 List 和 Set 不是数据结构，它们是接口。您选择的数据结构是 ArrayList（实现 List 接口的连续数组数据结构的一个版本）和 HashSet（实现 Set 接口的哈希表数据结构的一个版本）。所以你需要看看那些。

对于数组，除非它已排序，否则查找算法需要线性时间，因为除了遍历整个事物之外别无选择。

对于针对查找进行了优化的哈希表，查找算法在技术上在最坏情况下仍为 O(n)，但在常见情况下为 O(1)。但是，您必须实际使用优化的查找算法（由 Set.contains 提供）才能利用这一点 - 对 HashSet 的线性搜索并不比对 ArrayList 的线性搜索更好（实际上更糟）。

于 2013-05-23T14:06:45.260 回答
2

两个集合中都已经contain()给出了方法，那你为什么还要遍历呢？O(n)list is和 set 的复杂性O(1)是恒定的。

于 2013-05-23T13:47:42.877 回答
0

列表实现代码： https ://referencesource.microsoft.com/#PresentationFramework/src/Framework/System/Windows/Documents/List.cs,eabc7101897ec6e6

设置实现代码： https ://referencesource.microsoft.com/#System.Core/System/Collections/Generic/HashSet.cs,50c894a3f7ad7bd0

数据结构时间复杂度： https ://www.bigocheatsheet.com/

有用的书：Anany Levitin 的算法设计和分析简介

前两个链接演示了 Set 类和 List 的内部实现，基本上它们都是使用 Array 数据结构类型实现的。第三个链接演示了不同操作的每个数据结构的复杂性。如果您希望测量两个不同代码（Set、List）的复杂度，我们可以

  1. 使用时间复杂度进行算法分析，通过查看最多的操作来补偿算法解决问题所花费的大部分时间。2.设置表示算法基本操作执行次数的总和
  2. 使用标准公式和求和运算规则，要么找到计数的封闭式公式，要么至少确定其增长顺序。
于 2020-01-23T14:36:15.457 回答