0

配列、キュー、リンクされたリスト、またはリストデータ構造をサポートするものに格納されている数字のリストがあるとします（つまり、数字のシーケンスが重要です）。ここで、既存のリスト (list.add()) に数値を追加した後、新しいオブジェクトを追加したいとします。しかし、list.add() は元のリストを受け取り、元のリストの番号と新しい番号を含む新しいリストを返します。元のリスト オブジェクトは関数 add() によってまったく変更されません。

したがって、これを実装するには、関数内で元のリストのコピーを作成し、それに新しい番号を追加してから返します。これには O(n) 時間がかかります。

O(n) よりも短い時間でこの作業を行う方法はありますか?

EDIT 1: 要素は最後に追加されます。add() によって返されるオブジェクトには、元のリストのすべての番号と新しい番号が含まれている必要があります。元のリストは変更されません。

編集 2: リストに番号を追加するたびにリスト全体をコピーしないと、可能かもしれないと思います。この点で可能性はありますか？

4

3 に答える 3

0

リンクリストの先頭に追加されるのはO（1）です。

あるいは、ランダム挿入をサポートすることは、最近多くの研究のトピックです。ClojureとScalaは、ハッシュ配列にマップされたtrieに似たものを使用しますが、O（logn）の更新の影響を受けるブランチのみをコピーすることで、より高速な更新を可能にする不変のバリアントを除きます。分岐係数が高い場合（つまり32）、これにより効果的に一定のルックアップも可能になります。

于 2013-01-15T18:38:15.187 に答える
0

なんでコピペしたいの？

O（1）のリストまたは配列の最後に追加するだけです

基本的には、後ろに数字を追加して同じパラメータを使用し、サイズを 1 ずつ増やしてから、リスト オブジェクトを作成します。これが O(1) です。

于 2013-01-15T18:40:19.263 に答える
0

他にどのような機能をサポートする必要があるのか​​ わかりませんaddが、懸念している唯一の方法である場合は、元のリストに追加する部分を表す新しいリストを基本的に維持するラッパー クラスを作成できます。次に、lookupこのラッパー クラスへの a は、元のリストと新しいリストの連結を考慮します。

疑似 C# コードの例を次に示します。

public class ListWrapper
{
    private ArrayList<T> Original;
    private ArrayList<T> ConcatenatedPortion;

    public ImmutableList(ArrayList<T> original)
    {
        Original = original;
        ConcatenatedPortion = new ArrayList<T>();
    }

    public bool Add(<T> element)
    {
        return ConcatenpatedPortion.Add(element);
    }

    public <T> Get(int index)
    {
        if (index < 0) throw new IndexOutOfBoundsException();

        if (index < Original.Length)
            return Original.Get(index);

        int newIndex = index - Original.Length;

        if (newIndex < ConcatenatedPortion.Length)
            return ConcatenatedPortion.Get(newIndex);

        throw new IndexOutOfBoundsException();
    }
}
于 2013-01-18T21:39:18.820 に答える