LinkedHashMap的复杂度

Question

LinkedHashMap的复杂度

javatime-complexitybig-onested-loopslinkedhashmap

3

我有一个简单的问题，需要找到数组A中第一个唯一的元素。但是，困扰我的是使用不同方法的时间复杂度。到目前为止，我已经尝试了这两种方法。

第一种方法：

LinkedHashMap<Integer, List<Integer>> map = new LinkedHashMap<Integer, List<Integer>>();
for (int i = 0; i < A.length; i++)
{
    if (!map.containsKey(A[i]))
        map.put(A[i], new ArrayList<>());
    map.get(A[i]).add(i);
}

for (Map.Entry<Integer, List<Integer>> m : map.entrySet())
    if (m.getValue().size() == 1)
        return m.getKey();
return -1;

第二种方法：

    for(int i=0; i< A.length; i++){
        boolean unique = true;
        nestedFor:for(int j=0; j< A.length; j++){
            if(i != j && A[i] == A[j]){
                unique = false;
                break nestedFor;
            }
        }
        if(unique)
            return A[i];
    }
    return -1;

使用一个1000000个元素的数组进行测试，第一种方法执行时间约为2000毫秒，而第二种方法执行时间约为10毫秒。我的问题是：第一种方法的复杂度为O(nLogn)，比第二种方法的复杂度O(n^2)更快，应该执行得更快，我错在哪里了？以下是测试代码：

    int[] n = new int[1000000];
    for (int i = 0; i < n.length; i++)
        n[i] = new Random().nextInt(2000000);

    long start = System.currentTimeMillis();
    firstUnique(n);
    System.err.println("Finished at: " + (System.currentTimeMillis() - start ) + "ms");

编辑：

for (int i = 0; i < A.length; i++)
{
    if (!map.containsKey(A[i]))
        map.put(A[i], new ArrayList<>());
    map.get(A[i]).add(i);
}

消耗了99%的执行时间，而

for (Map.Entry<Integer, List<Integer>> m : map.entrySet())
    if (m.getValue().size() == 1)
        return m.getKey();

始终为1-3毫秒。所以，是的，填充地图是最昂贵的操作。

您会建议哪种方法对于这种问题最有效？

- user3215799

使用第一种方法，您还要测量至少创建的200万个对象，在函数调用结束时超出范围 - 但是您的GC正在处理它。如果第二个版本中的A是int []，则您在那里没有这个开销... - BeyelerStudios

2

使用System.currentTimeMillis()不是进行基准测试的好方法，请参考https://dev59.com/hHRB5IYBdhLWcg3wz6UK了解有关进行Java基准测试的更多信息。 - CConard96

你可以通过迭代 for (int j = i + 1; ...) 来使第二种方法的速度大约快两倍（在最坏情况下）。不仅可以遍历一半的元素，还可以跳过 i != j 检查。 - Andy Turner

6个回答

1

时间复杂度忽略系数，因为通常了解函数随着输入大小的增加如何增长更有用。尽管您的第一个函数具有较低的时间复杂度，在小输入大小时，它将运行得更慢，因为您正在创建许多计算代价昂贵的ArrayList对象。然而，您的第二个方法仅使用数组访问，这比实例化对象要便宜得多。

- Natecat

你是指“在大输入尺寸下”吗？除非你认为他们的输入很小... - 4castle

他没有写错，他写的就是他想表达的意思，而且是正确的。 - Erwin Smout

1

时间复杂度是指在渐进意义下理解的（即随着输入规模增长到googolplex），没有其他含义。如果一个算法具有线性时间复杂度，那只意味着存在一些a、b使得执行时间（大致上!!!）= a * 输入大小 + b。它并不说明a和b的实际大小，而且两个线性算法仍然可能具有巨大的性能差异，因为它们的a/b的大小相差很大。

（另外，你的例子不太恰当，因为算法的时间复杂度应该考虑所有底层操作的复杂性，例如对象创建等。其他人在他们的答案中也暗示了这一点。）

- Erwin Smout

谢谢您的回复，如果您需要解决相同的问题（数组中的第一个唯一元素），您会使用什么？ - user3215799

1

首先，为什么基准测试不相关：

即使我们忽略由使用的方法、GC等引起的不准确性，发现方法2在一百万个条目上更快，并不能告诉您它在十亿个条目上的表现如何。

大O是一个理论概念，必须在理论上证明。在这里，大多数基准测试可以为您做的是让您估计复杂度，而这不是通过比较两种方法在一个输入上完成的，而是通过比较一个方法在多个输入上完成的，每个输入的规模都比前一个大一个数量级（即使这样也很难得出任何有用的结论）。

大O是最坏情况下的复杂度，但是你的随机输入可能在第一种方法（map）中处于“中间”，而对于数组来说则远非最坏情况——实际上，在第一次迭代中成功的概率为50%，而map必须完全处理，并且平均将有约500,000个条目。

“map”方法的最坏情况可能是所有元素都不同，但哈希码相等（因此您需要在每个n迭代中读取添加的整个元素列表）。

“array”方法的最坏情况是所有元素都相等（需要完成整个嵌套迭代）。

关于寻找好的算法 - 你可以使用 Map<Integer, Boolean> 替代 Map<Integer, List<Integer>，因为你只需要存储唯一标识而不是值的列表 - 当你第一次看到元素时，添加 True，当你遇到重复时切换到 False LinkedHashMap 的操作 put，containsKey/get 的大O复杂度为 O(n)（最坏情况），使整个算法的复杂度为 O(n^2)

然而，put 的摊销复杂度为 O(1)（使所有插入的摊销复杂度为 O(n)），get 的平均复杂度是常数（这取决于所使用的哈希函数对给定输入的效果如何）；唯一值查找然后是 O(n)

- Jiri Tousek

那么你的意思是第一种方法也是O(n^2)复杂度吗？ - user3215799

此外，对数组进行排序然后查找第一个唯一元素并不是解决方案，因为我需要找到第一个唯一元素（具有最小索引）。 - user3215799

我更新了地图最坏情况的想法 - 请参阅帖子。是的，在最坏的情况下，所有元素都不同，但落入HashMap的同一个桶中，因此对于每个元素，您必须读取所有过去的元素。这几乎与第二个算法完全相同，对于每个元素，它必须读取（在其他帖子中建议的优化之后）所有未来的元素。 - Jiri Tousek

关于对数组进行排序的想法，你是正确的。我认为稳定的排序算法会帮助你，但显然是错误的。 - Jiri Tousek

1

请考虑使用两个集合：

public int returnFirstUnqiue(int[] a)
{
  final LinkedHashSet<Integer> uniqueValues = new LinkedHashSet<Integer>(a.length);
  final HashSet<Integer> dupValues = new HashSet<Integer>(a.length);

  for (int i : a)
  {
    final Integer obj = i;
    if (!dupValues.contains(obj))
    {
      if (!uniqueValues.add(obj))
      {
        uniqueValues.remove(obj);
        dupValues.add(obj);
      }
    }
  }

  if (!uniqueValues.isEmpty())
  {
    return uniqueValues.iterator().next();
  }
  return -1;
}

- Brett Okken

0

我的观察：第二种方法更快，因为它使用了具有声明宽度的 Array。在第一个示例中，大小发生变化。

请尝试定义更精确的LinkedHashMap大小，以将初始容量设置为1000000。

另一件事是，数组是一种更简单的结构，GC不会尝试做任何事情。但是，当涉及到LinkedHashMap时，它更加复杂，并且在某些情况下，创建和操作的成本远比从Array获取特定索引处的元素要复杂得多。

- RMachnik

我不是在比较ArryList和LinkedHashMap，而是在比较简单的数组和LinkedHashMap。同意，在LinkedHashMap内部有ArrayLists的分配。 - RMachnik

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andy Turner · Accepted Answer

我怀疑您没有选择能够创建第二种情况下的“最坏情况”输入。

比如，如果您构建的数组中所有数百万个元素都有一个重复项（例如：A [i] = 2 * i / A.length），那么第二种方法比第一种方法慢得多，因为它必须检查10^12个元素的组合。

您可以使其稍微快一点（大致快两倍），方法是将内部循环的条件更改为仅从j = i + 1进行检查，但10^12 / 2仍然是一个非常大的数字。

如果您只是随机选择数字来填充数组，则第一个元素是唯一的可能性相当高，而前两个元素中有一个是唯一的可能性更大等等。几个元素之后，您几乎可以确定该元素是唯一的，因此它将在几次迭代后停止。

第一种方法花费的2秒时间太长了。我只能想到您在基准测试之前没有正确地预热JIT。但即使不尝试这样做，对于我来说，您的第一种方法只需要40-50ms的时间（在几次迭代后降至10-15ms）。

大部分时间都是由于对象的创建 - 在键和值的自动装箱以及ArrayList实例的创建中。