空不含QUOT;地图＆QUOT;：是一个回调的解决方案比tryGet慢（）？ [英] Null-free "maps": Is a callback solution slower than tryGet()?

查看：178
本文介绍了空不含QUOT;地图＆QUOT;：是一个回调的解决方案比tryGet慢（）？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

在评论<一个href=\"http://stackoverflow.com/questions/1072383/how-to-implement-list-set-and-map-in-null-free-design/1080115#1080115\">\"How要实现List，Set和Map在零免费设计？，史蒂芬Sudit 和我成左右使用回调，与处理程序发现和未找到的讨论的情况下，主场迎战 tryGet（）方法，服用 。出参数，并返回一个布尔值，指示出参数是否已经填充史蒂芬认为，回调的做法是更复杂，几乎可以肯定要慢一些，我认为复杂性并没有更大的性能在最坏的情况的相同。

In comments to "How to implement List, Set, and Map in null free design?", Steven Sudit and I got into a discussion about using a callback, with handlers for "found" and "not found" situations, vs. a tryGet() method, taking an out parameter and returning a boolean indicating whether the out parameter had been populated. Steven maintained that the callback approach was more complex and almost certain to be slower; I maintained that the complexity was no greater and the performance at worst the same.

不过，code事实胜于雄辩，所以我想我会同时实现，看看我得到了什么。原来的问题是关于语言相当的理论（，并为论证的缘故，让我们说这种语言甚至没有空） - 我用这里的Java因为这是我得得心应手。 Java没有输出参数，但是它不具备一流的功能，要么，所以风格明智的，它应该为这两种方法同样闹心。

But code speaks louder than words, so I thought I'd implement both and see what I got. The original question was fairly theoretical with regard to language ("And for argument sake, let's say this language don't even have null") -- I've used Java here because that's what I've got handy. Java doesn't have out parameters, but it doesn't have first-class functions either, so style-wise, it should suck equally for both approaches.

（题外话：至于复杂云：我喜欢的回调设计，因为它本质上迫使API的用户来处理这两种情况，而 tryGet（）设计要求调用执行自己的样板条件检查，他们可以忘记或得到错误的。但是现在既然已经落实，我可以看到为什么 tryGet（）设计的的外观的简单，至少在短期内如此。）

(Digression: As far as complexity goes: I like the callback design because it inherently forces the user of the API to handle both cases, whereas the tryGet() design requires callers to perform their own boilerplate conditional check, which they could forget or get wrong. But having now implemented both, I can see why the tryGet() design looks simpler, at least in the short term.)

首先，回调例如：

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（）例子 - 尽我理解的格局（我可能是错的）：

Now, the tryGet() example -- as best I understand the pattern (and I might well be wrong):

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");
    }
}

最后，性能测试code：

And finally, the performance test code:

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％的性能（），这着实让我吃惊。但是，在一个预感，我加了一些垃圾收集和性能损失消失了。

On my first attempt, I got 50% worse performance for callback than for tryGet(), which really surprised me. But, on a hunch, I added some garbage collection, and the performance penalty vanished.

这符合我的直觉，这是我们基本上谈论服用相同数量的方法调用，条件检查等，并重新安排他们。但后来，我写了code，所以我很可能已经写了一个次优或subconsicously处罚 tryGet（）的实施。思考？

This fits with my instinct, which is that we're basically talking about taking the same number of method calls, conditional checks, etc. and rearranging them. But then, I wrote the code, so I might well have written a suboptimal or subconsicously penalized tryGet() implementation. Thoughts?

更新：每href=\"http://stackoverflow.com/users/136540/michael-aaron-safyan\">迈克尔·亚伦Safyan ，固定从 TryGetExample 重用 OutParameter 。

Updated: Per comment from Michael Aaron Safyan, fixed TryGetExample to reuse OutParameter.

推荐答案

大卫，感谢您抽出时间来写这个了。我是一个C＃程序员，所以我的Java技能是有点模糊，这些天。正因为如此，我在决定端口code和测试它自己。我发现了一些有趣的异同，这是pretty太多值得的门票价格就我而言。其中主要的区别是：

David, thanks for taking the time to write this up. I'm a C# programmer, so my Java skills are a bit vague these days. Because of this, I decided to port your code over and test it myself. I found some interesting differences and similarities, which are pretty much worth the price of admission as far as I'm concerned. Among the major differences are:


  1. 我没有实现TryGet因为它的内置词典。

  2. 在要使用本机TryGet，而不是插入空值，以模拟缺失，我干脆省略这些值。这仍然意味着 V =图[K] 都会设定 v 到空，所以我认为这是一个正确的移植。现在回想起来，我可以插入空白和改变（_ map.TryGetValue（键，超时值））到（_ map.TryGetValue（键，出值）及和放大器;！值= NULL）），但我很高兴我没有

  3. 我想是非常公平的。因此，要保持code紧凑性和可维护性越好，我用演算的符号，这让我怕疼定义回调。这隐藏了建立匿名委托的复杂性，并允许我无缝地使用闭包。讽刺的是，查找的实现使用TryGet内部。

  4. 而不是声明的新型词典的，我用了一个扩展方法嫁接查找到标准字典，更简化了code。

  1. I didn't have to implement TryGet because it's built into Dictionary.
  2. In order to use the native TryGet, instead of inserting nulls to simulate misses, I simply omitted those values. This still means that v = map[k] would have set v to null, so I think it's a proper porting. In hindsight, I could have inserted the nulls and changed (_map.TryGetValue(key, out value)) to (_map.TryGetValue(key, out value) && value != null)), but I'm glad I didn't.
  3. I want to be exceedingly fair. So, to keep the code as compact and maintainable as possible, I used lambda calculus notation, which let me define the callbacks painlessly. This hides much of the complexity of setting up anonymous delegates, and allows me to use closures seamlessly. Ironically, the implementation of Lookup uses TryGet internally.
  4. Instead of declaring a new type of Dictionary, I used an extension method to graft Lookup onto the standard dictionary, much simplifying the code.

通过道歉为code的低于专业的品质，那就是：

With apologies for the less-than-professional quality of the code, here it is:

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    static class CallbackDictionary
    {
        public static void Lookup<K, V>(this Dictionary<K, V> map, K key, Action<K, V> found, Action<K> missed)
        {
            V v;
            if (map.TryGetValue(key, out v))
                found(key, v);
            else
                missed(key);
        }
    }

    class TryGetExample
    {
        private Dictionary<string, string> _map;
        private List<string> _found;
        private List<string> _missing;

        public TryGetExample(Dictionary<string, string> map)
        {
            _map = map;
            _found = new List<string>(_map.Count);
            _missing = new List<string>(_map.Count);
        }

        public void TestTryGet()
        {
            for (int i = 0; i < _map.Count; i++)
            {
                string key = "key" + i;
                string value;
                if (_map.TryGetValue(key, out value))
                    _found.Add(key + ": " + value);
                else
                    _missing.Add(key);
            }

            Console.WriteLine(_found.Count() + " found");
            Console.WriteLine(_missing.Count() + " missing");
        }

        public void TestCallback()
        {
            for (int i = 0; i < _map.Count; i++)
                _map.Lookup("key" + i, (k, v) => _found.Add(k + ": " + v), k => _missing.Add(k));

            Console.WriteLine(_found.Count() + " found");
            Console.WriteLine(_missing.Count() + " missing");
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            int size = 2000000;
            var map = new Dictionary<string, string>(size);
            for (int i = 0; i < size; i++)
                if (i % 5 != 0)
                    map.Add("key" + i, "value" + i);

            long totalCallback = 0;
            long totalTryGet = 0;

            int iterations = 20;
            TryGetExample tryGet;
            for (int i = 0; i < iterations; i++)
            {
                tryGet = new TryGetExample(map);
                long tryGetStart = DateTime.UtcNow.Ticks;
                tryGet.TestTryGet();
                totalTryGet += (DateTime.UtcNow.Ticks - tryGetStart);
                GC.Collect();

                tryGet = new TryGetExample(map);
                long callbackStart = DateTime.UtcNow.Ticks;
                tryGet.TestCallback();
                totalCallback += (DateTime.UtcNow.Ticks - callbackStart);
                GC.Collect();
            }

            Console.WriteLine("Avg. callback: " + (totalCallback / iterations));
            Console.WriteLine("Avg. tryGet(): " + (totalTryGet / iterations));
        }
    }
}

我的业绩预期，因为我启发这一个在文章中说，将是两者都不是远远超过其他的更快或更慢。毕竟，大部分的工作是在搜索和添加，而不是简单的逻辑结构它。事实上，它运行变化中的位，但我无法检测到任何一贯的优势。

My performance expectations, as I said in the article that inspired this one, would be that neither one is much faster or slower than the other. After all, most of the work is in the searching and adding, not in the simple logic that structures it. In fact, it varied a bit among runs, but I was unable to detect any consistent advantage.

问题的部分原因是，我用了一个低precision定时器和测试很短，所以我10倍增加数200万和帮助。现在回调是慢3％左右，这是我不考虑显著。在我的速度比较慢的机器，回调了17773437，同时tryget了17234375。

Part of the problem is that I used a low-precision timer and the test was short, so I increased the count by 10x to 2000000 and that helped. Now callbacks are about 3% slower, which I do not consider significant. On my fairly slow machine, callbacks took 17773437 while tryget took 17234375.

现在，为code的复杂性，这是一个有点不公平，因为TryGet是本地人，所以我们就忽略了一个事实，我不得不添加一个回调接口。在调用点，拉姆达符号确实隐藏了复杂性非常出色。如果有的话，它实际上比的if / then /在TryGet其他版本使用，但我想我可以用一个三元运算符，使其同样紧凑。

Now, as for code complexity, it's a bit unfair because TryGet is native, so let's just ignore the fact that I had to add a callback interface. At the calling spot, lambda notation did a great job of hiding the complexity. If anything, it's actually shorter than the if/then/else used in the TryGet version, although I suppose I could have used a ternary operator to make it equally compact.

就整体而言，我发现C＃更优雅，只有一些认为是由于我的偏见作为一个C＃程序员。主要是，我没有定义和实现接口，这减少了管道的开销。我还用pretty标准.NET惯例，这似乎有点比那种风格在Java中的青睐更精简。

On the whole, I found the C# to be more elegant, and only some of that is due to my bias as a C# programmer. Mainly, I didn't have to define and implement interfaces, which cut down on the plumbing overhead. I also used pretty standard .NET conventions, which seem to be a bit more streamlined than the sort of style favored in Java.

这篇关于空不含QUOT;地图＆QUOT;：是一个回调的解决方案比tryGet慢（）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
Java开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆