O（1）を強制的に実行する

Question

私はListのランダム要素を選択して返します。リストは非常に長く（数百万の要素）、この関数は1秒間に数千回呼び出されるため、効率が重要です。

MyClass getRandomElement(List<MyClass> myClasses) { 
    return myClasses.get(getRandomNumber(myClasses.size())); 
} 

は、このソリューションには二つの問題があります。

私の現在の実装は次のようになります。

1. List.getは、O(1)で実行することはできません。例えば、LinkedListは、O(n)にそれを実装します。
2. sizeは、すべてListの実装でO(1)で実行することは保証されていません。

私が気づいているすべての実装がO(1)に実装されているため、2番目の点はあまり説得力がありません。最初の点は問題のある点です。

実装がO(1)であることを保証する（コンパイル/実行時例外ではない）方法はありますか？インターフェイスを次のように変更すると考えました。

MyClass getRandomElement(ArrayList<MyClass> myClasses) 

これは厳しいものです。ユーザーがImmutableListでこの機能を呼び出せるようにします。それはお勧めです。

値がArrayListまたはImmutableListのインスタンスであると主張できます。これにより他のO(1)実装が排除されますが、おそらくそれを使用して暮らすことができます。しかし、これは実行時の強制であり、コンパイル時の強制ではありません。そして、私はこのチェックのランタイムオーバーヘッドが何であるか分かりません。

これはベストプラクティスですか？ RandomAccessのJavadocのから

Answer 1

：

ジェネリックリストアルゴリズムは与えられたリストは、それがシーケンシャルアクセスリストに適用された場合、パフォーマンスの低下を提供するアルゴリズムを適用する前に、このインターフェイスのinstanceofであるかどうかを確認することをお勧めします許容される性能を保証するために必要であればそれらの動作を変更することができる。

ランタイムチェックで暮らすことができれば、探しているものとよく似ています。

---

あなたが交差点の種類を使用して、コンパイル時にこれを行うことができますように実際には、それが見えます：

<T, L extends List<T> & RandomAccess> T getRandomElement(L list) { ... } 

getRandomElement(new ArrayList<String>()); // OK. 
getRandomElement(new LinkedList<String>()); // Compiler error. 

この方法の欠点は、あなたが実際に具体的な（っぽい）のタイプを知っておく必要があるということですそれを呼び出すためにあなたのリストのgetRandomElement(strings)を呼び出す以外のリストのランダム・アクセス・プロパティを、必要としない

void doSomethingWithRandomElements(List<String> strings) { ... } 

：たとえば、次のような方法でgetRandomElement(...)を呼び出すことができませんでした。

次に、ランタイムチェックに戻す必要があります。または、そのメソッドまでジェネリック制約を伝播する必要があります。

コンパイル時と実行時の強制の選択は、どのように使用するかによって大きく異なります。

Answer 2

私はMyClass getRandomElement(List<MyClass> myClasses)をプライベートにし、サポートしているさまざまな種類のリストのメソッドをオーバーロードし、呼び出しをプライベートgetRandomElementにリダイレクトします。

Answer 3

入力の制限や回避しようとしているリスクの種類、取引の対象となるものを慎重に検討する必要があります。明示的に許可するには、パラメータの種類を制限するだけRandomAccessリストを宣言、すなわち

• subListの結果は、ランダム・アクセス・リスト
に適用され、あなたはJREのメソッドによって返されたランダム・アクセス・リストのいずれかに渡す機能を失うことを意味し
• Arrays.asList
• Collections.singletonList(…)によって返されたいずれかCollections.unmodifiableListまたはCollections.synchronizedList
• リストによってラップランダム・アクセス・リスト。 Collections.emptyList()もランダムアクセスリストですが、それはあなたのgetRandomElementメソッドには適していない唯一のリストの例です。またnCopiesはランダムアクセスですが、それをgetRandomElementに渡すのは意味がありません。

これらのリストはすべて、実行時にRandomAccessを実装しますが、コンパイル時には宣言されません。また、Java 7では、実際にランダムアクセスリストであることが分かっている場合には、リストを(List&RandomAccess)に型キャストすることさえできません。

リストのタイプが既知の実際のタイプであっても、RandomAccessを実装しています。 ArrayListの場合、変数やパラメータにはより抽象的な型のListを使用するのではなく、リストの作成からメソッドが呼び出されるポイントまで、コード全体にわたってコンパイル時の型を維持するように開発者に指示しています。メソッドを使用してすべてのメソッドに渡されます。

あなたは多くを犠牲にしています。しかし何のために？

開発者はパフォーマンスがO(n)で、ランダムではないアクセスを持っており、あなたのメソッドを呼び出すリストを使用している場合（size()とget()両方がO(n)であっても、別の後に両方のいずれかを実行するネット複雑さはまだO(n)です）。それは驚くべきことではありません。ランダムアクセスリストについてはO(1)であるが、他のものについてはO(n)であるという現象は、内的操作List.get自体を含め、常に見られる。

したがって、開発者が通過するためにメソッドがO(n)時間の複雑さで実行されているとします。 a LinkedList、問題は開発者decision of using a LinkedList in the first placeです。あなたはあなたの方法でそれを修正しようとすべきではありません。

ところで、非ランダムアクセスの場合のコストを緩和しようとすることができます。：

public static <T> T getRandomElement(List<? extends T> list) { 
    Random r = new Random(); 
    int size; 
    if(list instanceof RandomAccess) { 
     size = list.size(); 
     if(size == 0) throw new NoSuchElementException(); 
     return list.get(r.nextInt(list.size())); 
    } 
    size = 0; 
    T picked = null; 
    for(T element: list) { 
     if(r.nextInt(++size) == 0) { 
      picked = element; 
     } 
    } 
    if(size == 0) throw new NoSuchElementException(); 
    return picked; 
} 

これは、それは不可能だとして、それはそのクラスがO(1)size()メソッドを持っているようLinkedList場合についても、改善はありませんが、非ランダム・アクセス・リストを処理するO(n)本質は変わりません。しかし、並外れたsize()メソッドと弱く一貫性のあるイテレータを持つ並行リストを想像してください。その場合、このメソッドは最終的には失敗する代わりにランダムな要素を返します。それは非Listコレクションでも機能します。また、getまたはsizeのリストがさらに複雑になる場合は、妥当なIteratorと仮定して、複雑さをO(n)に減らします。

多くの複雑な操作は、多くの場合、より簡単な方法で実装されます。単一不可避O(n)操作（もちろん、O(n)空間の複雑さを追加すること）に問題を低減

public static <T> T getRandomElement(List<? extends T> list) { 
    if(!(list instanceof RandomAccess)) { 
     list = new ArrayList<>(list); 
    } 
    Random r = new Random(); 
    int size = list.size(); 
    if(size == 0) throw new NoSuchElementException(); 
    return list.get(r.nextInt(list.size())); 
} 

。その後、特殊なコードを必要とせずに効率的に処理を進めることができます。非ランダムアクセスリストの場合、正味の複雑さがO(n)より悪い場合、これは重要です。具体的な例についてはthe implementation of Collections.shuffleをご覧ください。