群图- LeetCode

Question

今天我遇到了一个解决这个问题的方法：https://leetcode.com/problems/group-anagrams/submissions/

作者利用AbstractList解决了这一问题。这个解决方案看起来有点像这样

import java.util.AbstractList;

class Solution {
    private List<List<String>> result;
    private HashMap<String, List<String>> map = new HashMap<>();
    
    public List<List<String>> groupAnagrams(String[] strs) {
        
        return new AbstractList<>() {
            public List<String> get(int key) {
                if (result == null)
                    init(strs);
                return result.get(key);
            }
            
            public int size() {
                if (result == null)
                    init(strs);
                return result.size();
            }      
        };
    }
    
    private void init(String[] strs) {
        for (String str : strs) {
            char[] ch_map = str.toCharArray();
            Arrays.sort(ch_map);
            String key = String.valueOf(ch_map);

            if (!map.containsKey(key))
                map.put(key, new ArrayList<>());
            map.get(key).add(str);
        }

        result = new ArrayList<>(map.values());
    }
}

测试结果为0ms ~ 1ms.。

如果我把

if (result == null)
    init(strs);

从get(int键)和int size()。然后，我将init(strs)放在函数的开头，如下所示：

...
    public List<List<String>> groupAnagrams(String[] strs) {
        init(strs);
        return new AbstractList<>() {
            public List<String> get(int key) {
                return result.get(key);
            }
            
            public int size() {
                return result.size();
            }      
        };
    }
...

测试结果为10 is ~15 is。

我试图打印调用init(strs)的时间数，但这两种情况都返回了1次。

我的问题是，当您将init(Str)放入AbstractClass ?中时，它为什么要快得多呢？

Answer 1

理论

您所提供的解决方案只是一个LeetCode验证执行时间的方法。在给定的练习中，整个运行可能如下所示：

1. 准备一个将传递给测试的数组。
2. 开始数时间。
3. 执行用户提供的解决方案。
4. 别再数时间了。
5. 验证解决方案返回的结果。

"hacky“代码在groupAnagrams方法执行过程中所做的唯一事情就是创建一个匿名类实例，然后返回该实例。完成任务所需的逻辑的实际评估只有在调用了get()或size()方法之后才能完成，这是验证阶段的一部分，并且如上面所假设的-- LeetCode没有对时间进行验证。

Practice

我准备了带有简单项目的GitHub存储库来验证这两种解决方案之间的差异。如前所述，只有一小部分工作是在“结果列表”计算期间完成的(从一开始到现在的时间，以纳秒为单位)：

Result calculated:      4833
> Verification done:    47666

虽然这是它寻找“标准”解决方案的方式：

Result calculated:      42916
> Verification done:    44875

Note

通常，应该使用JMH进行基准测试，但我希望验证尽可能明确，所以我使用了简单的时间差打印(以纳秒为单位)来控制。JVM预热是在我编写的代码中执行的，结果似乎是合理的。