java - 多态性(显着)比直接实现慢吗？

Question

所以我有这个类，它基本上是一个实现的 ArrayList，我希望通过使用 java 实现来使使用这个类的代码运行得更快，相反，它运行的速度几乎是原来的两倍。这背后有什么明显的原因让我失踪吗？ 这样是不是意味着要慢一些？

原始手写代码:

public class VertexSet {
    private int[] _set = null;
    private int _sp;
    public final static int INIT_SIZE = 10, INC = 30;

    public VertexSet() {
        _set = new int[INIT_SIZE];
        _sp = 0;
    }

    public VertexSet(VertexSet ot) {
        _set = new int[INIT_SIZE];
        _sp = 0;
        for(int i = 0; i < ot.size(); ++i) this.add(ot.at(i));
    }

    public void add(int a) {
        if(_sp == _set.length) resize();
        _set[_sp] = a;
        ++_sp;
    }
    public int size() {return _sp;}
    public int at(int i) {return _set[i];}

    public String toString() {
        String ans = "Set: |" + size() + "| ";
        for(int i = 0; i < size(); ++i) ans+=this.at(i) + ", ";
        return ans;
    }

    public String toFile() {
        String ans = " ";
        for(int i = 0; i < size(); ++i) ans += this.at(i) + ", ";
        return ans;
    }
    /**
     * this method computes the intersection between this set and ot set.
     * @param ot - the other set
     */
    public VertexSet intersection(VertexSet ot) {
        VertexSet ans = new VertexSet();
        int i1 = 0, i2 = 0, a1, a2;
        while(i1<this.size() & i2 < ot.size()) {
            a1=this.at(i1);
            a2 = ot.at(i2);
            if(a1 == a2) {
                ans.add(a1); ++i1; ++i2;}
            else if(a1 < a2) {++i1;}
            else ++i2;
        }
        return ans;
    }

    private void resize() {
        int[] tmp = new int[_sp + INC];
        for(int i = 0; i < _sp; ++i) tmp[i] = _set[i];
        _set = tmp;
    }

}

扩展java实现后的手写代码:

import java.util.ArrayList;

public class VertexSet extends ArrayList<Integer>{
    public final static int INIT_SIZE = 10;

    public VertexSet() {
        super(INIT_SIZE);
    }

    public VertexSet(VertexSet ot) {
        super(ot);
    }

    public int at(int i) {return get(i);}

    public String toString() {
        String ans = "Set: |" + size() + "| ";
        for(int i = 0; i < size(); ++i) ans+=this.at(i) + ", ";
        return ans;
    }

    public String toFile() {
        String ans = " ";
        for(int i = 0; i < size(); ++i) ans += this.at(i) + ", ";
        return ans;
    }
    /**
     * this method computes the intersection between this set and ot set.
     * @param ot - the other set
     */
    public VertexSet intersection(VertexSet ot) {
        VertexSet ans = new VertexSet();
        int i1 = 0, i2 = 0, a1, a2;
        while(i1<this.size() & i2 < ot.size()) {
            a1=this.at(i1);
            a2 = ot.at(i2);
            if(a1 == a2) {
                ans.add(a1); ++i1; ++i2;}
            else if(a1 < a2) {++i1;}
            else ++i2;
        }
        return ans;
    }
}

Answer 1

您的代码很好地说明了为什么不那样做。您关心性能；但你对背后发生的事情没有真正的了解。因此，与其想出自己的实现方式……不如先了解……是否存在问题。而且我认为在现实世界中很少有场景是集合继承的次要成本需要您使用自定义列表类(请参阅 http://c2.com/cgi/wiki?PrematureOptimization )。

唯一的异常(exception)可能是处理基本类型时；因为 Collection 的东西仅供引用(又名对象类型)。然后账单变得非常昂贵；作为具有 1000 万个 Integer 对象的 ArrayList 比具有 1000 万个整数的数组“成本”高得多。

你想出了一个“正确”的实现；但正如其他人所指出的——一些方法做了一些不必要的事情，这可能解释了这些性能问题。

请记住:整个集合框架是由专家 java 程序员设计和实现的。为什么你认为你的技能会匹配这些人的技能？!

这并不是一种侮辱 - 我只是指出创建这样的库是一项最好留给主题专家的任务。

例如，在“Scala”世界中，语言创建者真正区分了“普通用户”(编写“普通应用程序”)和那些想要设计/实现框架/库的人。人们普遍认为，后面的任务需要对 Scala 编程语言的概念和特性有很多更深入的了解。在 Java 中并没有太大的不同。

此外:您知道 java 即时编译器什么时候工作最好吗？当传入的 java 字节码看起来像“大多数人”编写的代码时，它的效果最好。有很多例子，当人们试图优化他们的 Java 源代码时……后来意识到他们非常特殊的代码导致性能不足；因为 JIT 无法优化那个“不寻常”的字节码。