3

インスタンスを考えると、新しい要素が元の要素の複製であり、元の配列とインターリーブされるように、のサイズを1倍にList増やす最も効率的な方法は何ですか?Listf

例えば

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

問題は、元のリストが非常に大きくなる可能性があるため、パフォーマンスがあまり良くないことです。これを行うにはもっと効率的な方法があるという予感があります。誰か提案がありますか?

4

3 に答える 3

1

これは、完全な複製を犠牲にすることなく、非常にうまく機能します。

List< String > interleave(final List< String > original, final int f ) {
    final int size = f * original.size();
    final List<String> originalCopy = new ArrayList<String>();
    for (String each : original) {
        originalCopy.add(new String(each)); // <=== duplicate here.
    }
    return new AbstractList<String>() {
        @Override
        public String get(int index) {
            return originalCopy.get(index / f);
        }

        @Override
        public int size() {
            return size;
        }            
    };
}

テスト

System.out.println(interleave(Arrays.asList("a", "b", "c"), 2));
System.out.println(interleave(Arrays.asList("x", "y"), 3));

出力

[a, a, b, b, c, c]
[x, x, x, y, y, y]
于 2012-08-28T16:18:38.080 に答える
1

提供するコードは十分に最適化されていますが、いくつかの改善が可能です。あなたの正確なニーズに応じて重要なもの。


まず、複製された要素が元の要素と同じ値のままになる場合、またはそれらの一部(合計と比較して)の値が変更される場合は、代わりに参照ベースの複製を検討することをお勧めします新しいリストを作成することさえしない完全に異なるアプローチではないにしても、現在の「true-cloneitall」コードの。

    /**
     * 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);
}

プログラムの実行中にすべての要素のほとんどが独立した値を持つ場合、現在のメソッドはすでにかなり正確です。

行うことができる2つの改善があります。コードで直接表示する方が簡単なので、次のようにします。

    /**
     * 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回の実行で次の平均速度が得られます。

  • 元のリストを作成して2000000の異なる要素で埋めるには、6030(〜)ミリ秒かかります。
  • リストをメソッドでインターリーブするには、75(〜)ミリ秒かかり interleaveByReference()ます。
  • リストをメソッドでインターリーブするには、185(〜)ミリ秒かかり interleaveByClone()ます。
  • リストをメソッドでインターリーブするには、210(〜)ミリ秒かかり original()ます。
于 2012-08-29T19:49:29.800 に答える
0

元の要素を再挿入し、複製を作成するだけで、わずかなスピードアップを実現できます。

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

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

  return interleaved;
}
于 2012-08-29T07:24:01.640 に答える