0

Javaでは、int[] a = new int[10000000];任意の数で完全に埋められた配列があります。コードでは、任意のサブシーケンスを削除する必要があることがよくあります。これは、連続していない可能性のある要素のセットです。

int[]オーバーを使用する理由LinkedListは、要素を通過する際の速度の向上です。現在、要素の削除は行われていないため、アプリケーションの実行時に大量のゴミが保管されます。要素を削除するとスピードアップする可能性があるので、非常に興味深い質問です。

可能な限り最速の方法で配列からサブシーケンスを削除するにはどうすればよいですか？

4

2 に答える 2

2

配列を短くするか、配列の最後に未使用の要素を許可できるかによって異なります。このためのツールはですSystem.arraycopy。配列を短くするには、新しい配列を割り当てる必要があります。

public int[] remove(int[] original, removeStart, removeEnd) {
    int originalLen = original.length;
    int[] a = new int[originalLen - removeEnd - removeStart];
    System.arraycopy(original, 0, // from original[0]
        a, 0,                     // to a[0]
        removeStart);             // this many elements
    System.arraycopy(original, removeEnd, // from original[removeEnd]
        a, removeStart,                   // to a[removeStart]
        originalLen - removeEnd);         // this many elements
    return a;
}

配列をコンパクトにするには：

System.arraycopy(array, removeEnd, // from array[removeEnd]
    array, removeStart,            // to array[removeStart]
    array.length - removeEnd);     // this number of elements

範囲の重複について心配する必要はありません。arraycopyそれらを正しく処理します。

削除する要素の範囲が不連続である場合は、これらのソリューションの1つを一般化するか（移動は少なくなりますが、コードはより複雑になります）、連続する各ブロックを個別に削除できます（プログラミングは簡単ですが、データを移動します。破棄します）。

削除するインデックスが散在している場合は、手動で行います。設計は、それが個々のインデックスに散在しているかどうか、または範囲のコレクションであるかどうかによって異なります。後者の場合（これはテストされていませんが、アイデアが得られるはずです）：

/**
 * Simple class to hold the start and end of a range.
 */
public static class Range implements Comparable<Range> {
    int start;
    int end;
    public int compareTo(Range other) {
        if (start < other.start) return -1;
        if (start > other.start) return 1;
        if (end < other.end) return -1;
        if (end > other.end) return 1;
        return 0;
    }
}
/**
 * Remove a list of ranges from an array.
 * @param original the array from which to remove the values.
 * @param toRemove the list of ranges to remove. This must be
 *    sorted in ascending order of range start before calling this method.
 * @param compact flag indicating whether to simply compact the original
 *    array or to copy the values into a new array. If false, will allocate
 *    a new array of the exact size needed to contain the elements not removed.
 */
public int[] remove(int[] original, List<Range> toRemove, boolean compact) {
    int[] a;
    if (compact) {
        a = original;
    } else {
        int len = 0;
        for (Range range : toRemove) len += range.end - range.start;
        a = new int[original.length - len];
    }
    int nextSource = 0;
    int nextDest = 0;
    for (Range range : toRemove) {
        if (nextSource < range.start) {
            System.arraycopy(original, nextSource, a, nextDest,
                range.start - nextSource);
            nextDest += range.start - nextSource;
            nextSource = range.start;
        }
        nextSource = range.end;
    }
    if (nextSource < original.length) {
        System.arraycopy(original, nextSource, a, nextDest,
            original.length - nextSource);
    }
    return a;
}
于 2012-11-11T20:38:22.070 に答える
0

[ System＃arraycopy ]（http://docs.oracle.com/javase/1.4.2/docs/api/java/lang/System.html#arraycopy(java.lang.Object、int、java.lang.Object）を使用します、int、int））以下のように：

      System.arraycopy(orginalArray, startIndex, newArray, 
                     newArrayStartIndex, numOfElementsToCopy);
      orginalArray = newArray;

注意：これは連続した場所で機能します。連続したセクションがさらにある場合でも、これは役立ち、同様の方法で複数回呼び出すことができます。ただし、削除する位置が完全にランダムである場合は、配列をトラバースする必要があると思います。

于 2012-11-11T20:32:17.113 に答える