java - 无空 "maps": Is a callback solution slower than tryGet()?

Question

在对 "How to implement List, Set, and Map in null free design?" 的评论中, Steven Sudit我开始讨论使用回调，处理“找到”和“未找到”情况，与 tryGet()方法，采用 out参数并返回一个 boolean 值，指示是否已填充 out 参数。 Steven 坚持认为回调方法更复杂，而且几乎肯定会更慢。我坚持认为复杂性并没有更大，最坏的表现也是一样的。

但是代码胜于 Eloquent ，所以我想我会同时实现两者，看看我得到了什么。最初的问题是关于语言的相当理论性的(“为了论证起见，假设这种语言甚至没有 null”)——我在这里使用了 Java，因为那是我得心应手的。 Java 没有 out 参数，但它也没有一流的函数，所以从风格上讲，这两种方法应该同样糟糕。

(题外话:就复杂性而言:我喜欢回调设计，因为它固有地强制 API 的用户处理这两种情况，而 tryGet() 设计要求调用者执行他们自己的样板条件检查，他们可能会忘记或得到错了。但是现在两者都实现了，我明白为什么 tryGet() 设计看起来更简单，至少在短期内是这样。)

一、回调示例:

class CallbackMap<K, V> {
    private final Map<K, V> backingMap;

    public CallbackMap(Map<K, V> backingMap) {
        this.backingMap = backingMap;
    }

    void lookup(K key, Callback<K, V> handler) {
        V val = backingMap.get(key);
        if (val == null) {
            handler.handleMissing(key);
        } else {
            handler.handleFound(key, val);
        }
    }
}

interface Callback<K, V> {
    void handleFound(K key, V value);
    void handleMissing(K key);
}

class CallbackExample {
    private final Map<String, String> map;
    private final List<String> found;
    private final List<String> missing;
    private Callback<String, String> handler;

    public CallbackExample(Map<String, String> map) {
        this.map = map;
        found = new ArrayList<String>(map.size());
        missing = new ArrayList<String>(map.size());
        handler = new Callback<String, String>() {
            public void handleFound(String key, String value) {
                found.add(key + ": " + value);
            }

            public void handleMissing(String key) {
                missing.add(key);
            }
        };
    }

    void test() {
        CallbackMap<String, String> cbMap = new CallbackMap<String, String>(map);
        for (int i = 0, count = map.size(); i < count; i++) {
            String key = "key" + i;
            cbMap.lookup(key, handler);
        }
        System.out.println(found.size() + " found");
        System.out.println(missing.size() + " missing");
    }
}

现在， tryGet()示例——据我所知，这种模式(我很可能是错的):

class TryGetMap<K, V> {
    private final Map<K, V> backingMap;

    public TryGetMap(Map<K, V> backingMap) {
        this.backingMap = backingMap;
    }

    boolean tryGet(K key, OutParameter<V> valueParam) {
        V val = backingMap.get(key);
        if (val == null) {
            return false;
        }
        valueParam.value = val;
        return true;
    }
}

class OutParameter<V> {
    V value;
}

class TryGetExample {
    private final Map<String, String> map;
    private final List<String> found;
    private final List<String> missing;

    private final OutParameter<String> out = new OutParameter<String>();

    public TryGetExample(Map<String, String> map) {
        this.map = map;
        found = new ArrayList<String>(map.size());
        missing = new ArrayList<String>(map.size());
    }

    void test() {
        TryGetMap<String, String> tgMap = new TryGetMap<String, String>(map);

        for (int i = 0, count = map.size(); i < count; i++) {
            String key = "key" + i;
            if (tgMap.tryGet(key, out)) {
                found.add(key + ": " + out.value);
            } else {
                missing.add(key);
            }
        }
        System.out.println(found.size() + " found");
        System.out.println(missing.size() + " missing");
    }
}

最后，性能测试代码:

public static void main(String[] args) {
    int size = 200000;
    Map<String, String> map = new HashMap<String, String>();
    for (int i = 0; i < size; i++) {
        String val = (i % 5 == 0) ? null : "value" + i;
        map.put("key" + i, val);
    }

    long totalCallback = 0;
    long totalTryGet = 0;

    int iterations = 20;
    for (int i = 0; i < iterations; i++) {
        {
            TryGetExample tryGet = new TryGetExample(map);
            long tryGetStart = System.currentTimeMillis();
            tryGet.test();
            totalTryGet += (System.currentTimeMillis() - tryGetStart);
        }
        System.gc();

        {
            CallbackExample callback = new CallbackExample(map);
            long callbackStart = System.currentTimeMillis();
            callback.test();
            totalCallback += (System.currentTimeMillis() - callbackStart);
        }
        System.gc();
    }

    System.out.println("Avg. callback: " + (totalCallback / iterations));
    System.out.println("Avg. tryGet(): " + (totalTryGet / iterations));
}

在我的第一次尝试中，回调的性能比 tryGet() 低 50%。 ，这真的让我很惊讶。但是，凭直觉，我添加了一些垃圾收集，性能损失消失了。

这符合我的直觉，即我们基本上是在谈论采用相同数量的方法调用、条件检查等并重新排列它们。但是后来，我写了代码，所以我很可能写了一个次优或次优的惩罚 tryGet()执行。想法？

更新:根据 Michael Aaron Safyan 的评论, 固定 TryGetExample重复使用 OutParameter .

Answer 1

我想说，无论性能如何，这两种设计在实践中都没有意义。我认为这两种机制都过于复杂，更重要的是，没有考虑到实际使用情况。

实际使用情况
如果用户在 map 中查找某个值但该值不存在，则该用户很可能需要以下内容之一:

使用该键将一些值插入映射

取回一些默认值

被告知该值不存在

因此，我认为更好的、无 null 的 API 应该是:

has(key)这表明 key 是否存在(如果只想检查 key 是否存在)。

get(key)如果存在键，则报告值；否则，抛出 NoSuchElementException。

get(key,defaultval)它报告键的值，如果键不存在，则返回 defaultval。

setdefault(key,defaultval)如果 key 不存在，则插入 (key,defaultval)，并返回与 key 关联的值(如果没有先前的映射，则为 defaultval，否则为 prev 映射)。

返回 null 的唯一方法是，如果您像在 get(key,null) 中那样明确要求它。这个 API 非常简单，但能够处理最常见的 map 相关任务(在我遇到的大多数用例中)。

我还应该补充一点，在 Java 中，has() 将被称为 containsKey()，而 setdefault() 将被称为 putIfAbsent()。因为 get() 通过 NoSuchElementException 表示对象不存在，所以可以将键与 null 关联并将其视为合法关联......如果 get() 返回 null，则表示该键已与该值关联null，而不是键不存在(尽管如果您愿意，您可以定义您的 API 以禁止 null 值，在这种情况下，如果给定的值为 null，您将从用于添加关联的函数中抛出 IllegalArgumentException) .此 API 的另一个优点是 setdefault() 只需执行一次查找过程而不是两次，如果您使用 if( ! dict.has(key) ){ dict.set(key,val) ; }。另一个优点是，您不会让编写 dict.get(key).doSomething() 之类的东西的开发人员感到惊讶，他们假设 get() 将始终返回一个非空对象(因为他们从未在字典中插入空值) ...相反，如果该键没有值，它们会得到 NoSuchElementException，这与 Java 中的其余错误检查更加一致，并且比 NullPointerException 更容易理解和调试。

回答问题
要回答原始问题，是的，您不公平地惩罚 tryGet 版本....在基于回调的机制中，您仅构造回调对象一次并在所有后续调用中使用它；而在您的 tryGet 示例中，您在每次迭代中都构造了 out 参数对象。尝试走线:

OutParameter out = new OutParameter();

将上面的行从 for 循环中取出，看看这是否会提高 tryGet 示例的性能。换句话说，将这一行放在 for 循环之上，并在每次迭代中重复使用 out 参数。