java - 将列表与自身交错

Question

给定一个 List 实例，将 List 的大小增加 f 的最有效方法是什么，这样新元素是原始元素的副本，与原始数组交错？

例如

f        = 2
Original = [a,b,c,...,x,y,z]
New      = [a,a,b,b,c,c,...,x,x,y,y,z,z]

我目前的实现是这样的:

List< Foo > interleave( List< Foo > original, int f ) {
    int newSize = original.size() * f;
    List< Foo > interleaved = new ArrayList< Foo >( newSize );

    for( Foo foo : original ) {
        for( int j = 0; j < factor; j++ ) {
            interleaved.add( new Foo( foo ) );
        }
    }
}

问题是我的原始列表可能非常大，因此性能不是很好。我有一种预感，有一种更有效的方法可以做到这一点；有人有什么建议吗？

Answer 1

您提供的代码优化得很好，但还有一些可以改进的地方；重要的取决于您的具体需求。

---

首先，如果您的克隆元素将保持与原始元素相同的值，或者只有少数元素(与总数相比)将更改它们的值，您可能需要考虑引用 -基于克隆而不是当前的“真正克隆所有”代码，如果不是完全不同的方法甚至不创建新列表的话。

    /**
     * PROS:
     * -Very low memory-footprint, as no new objects are created in memory, just references to a single (original) object.
     * -Can be done with generalization; A single method will function for most classes and data-types, as is below.
     * 
     * CONS:
     * -If you need each clone element to be changed independently from eachother and/or the orininal, this will not work directly,
     * because any change to an reference-element will apply to all other reference-elements that point to that same Object.
     * 
     * @param <E> Sub-class generalizator. Used so that the returned list has the same sub-class as the source.
     * @param list Source list. The list containing the elements to be interleaved.
     * @param f The factor to interleave for. In effect, the number of resulting elements for each original.
     * @return A list containing the interleaved elements, with each element being a REFERENCE to the original object.
     */
    public static <E> List<E> interleaveByReference(List<E> list, int f) {
        List<E> interleaved = new ArrayList<E>(list.size() * f);
        for (E obj : list) {
            for (int i = 0; i < f; i++) {
                interleaved.add(obj);
            }
        }
        return interleaved;
    }

如果您只需要几个克隆来更改值，您的交错列表最好基于引用，并且需要更改的元素稍后单独替换。

但是请注意，这种方法的有效性在很大程度上取决于需要更改原始列表元素的数量；如果需要更改太多，这种方法虽然在内存占用方面仍然更好，但在速度性能方面会更差(这似乎是您主要关心的问题)。

“稍后的个体克隆”可以通过类似的方式实现:

public static void replaceWithTrueClone(List<String> list, int objIndex) {
    list.add(objIndex, new String(list.get(objIndex)));
    list.remove(objIndex + 1);
}

//OR

public static void replaceWithNewObject (List<String> list, int objIndex, String newObject) {
    list.add(objIndex, newObject);
    list.remove(objIndex + 1);
}

---

如果每个元素中的大部分在程序执行过程中都将具有独立的值，那么您当前的方法已经非常准确了。

可以进行两项改进。直接在代码中显示会更容易，所以这就是我要做的:

    /**
     * PROS:
     * -Each element is an independent object, and can be set to independent values without much of an effort.
     * 
     * CONS:
     * -Each element has it's own allocated memory for it's values, thus having a much heavier memory footprint.
     * -Is constructor-dependent, and thus cannot be generalized as easily;
     * Each different expected class will probably need it's own method.
     * 
     * @param list Source list. The list containing the elements to be interleaved.
     * @param f The factor to interleave for. In effect, the number of resulting elements for each original.
     * @return A list containing the interleaved elements.
     * For each of the original elements, the first is a REFERENCE, and the other are CLONES.
     */
    public static List<String> interleaveByClone(List<String> list, int f) {
        List<String> interleaved = new ArrayList<String>(list.size() * f);
        for (String obj : list) {
            interleaved.add(obj); //The first element doesn't have to be cloned, I assume.
            //If it has to be cloned, delete the line above, and change 'i=1' to 'i=0' on the line below.
            for (int i = 1; i < f; i++) {
                interleaved.add(new String(obj));
            }
        }
        return interleaved;
    }

    /*
     * What was changed from the original is commented below.
     */

    public static List<String> original(List<String> original, int factor) {
        /*
         * It is unnessessary to have this 'newSize' variable. It gets needlessly maintained until the end of the method.
         * Although the impact is unworthy of measurement (negligible), it still exists.
         */
        int newSize = original.size() * factor;
        List<String> interleaved = new ArrayList<String>(newSize); //Just do the '*factor' operarion directly, instead of 'newSize'.

        for (String foo : original) {
            /*
             * If you can use the original here, that's one less cloning operation (memory-allocation, etc...) per original element.
             * A low-impact optimization, but still a good one.
             */
            for (int j = 0; j < factor; j++) {
                interleaved.add(new String(foo));
            }
        }
        return interleaved;
    }

---

使用包含 200 万个元素的原始列表和 2 的因子，我在 10 次运行中得到以下平均速度:

• 创建和填充原始列表需要 6030 (~) 毫秒2000000 个不同的元素。
• 用 75 (~) 毫秒将列表与interleaveByReference() 方法。
• 用 185 (~) 毫秒将列表与interleaveByClone() 方法。
• 用 210 (~) 毫秒将列表与原始()方法。