.NET の ConcurrentBag<T> のようなクラスはどのように実装できるでしょうか?

StackOverflow https://stackoverflow.com/questions/1688870

質問

の存在にとても興味をそそられます。 ConcurrentBag<T> 次期 .NET 4.0 フレームワークのクラス:

バッグは、順序が重要ではない場合にオブジェクトを保管するのに便利で、セットとは異なり、バッグは重複をサポートします。

私の質問は次のとおりです。このアイデアはどのように実現できるでしょうか?私がよく知っているほとんどのコレクションは、本質的に (内部では) 何らかの形式の配列に相当し、その順序は「重要」ではないかもしれませんが、 は 順序 (その必要がないにもかかわらず、列挙はほとんど常に変更されていないコレクションを通過するのです。 List, Queue, Stack, 、など。同じ順序で）。

推測しなければならないとしたら、内部的には次のようなことが考えられると思います。 Dictionary<T, LinkedList<T>>;しかし、単に使用するのが意味がないことを考えると、実際にはかなり疑わしいように思えます どれでも タイプ T キーとして。

私が期待/希望しているのは、これは実際にはどこかですでに「解明」されている確立されたオブジェクト タイプであり、この確立されたタイプを知っている誰かがそれについて教えてくれるということです。これは私にとって非常に珍しいものであり、実生活では理解しやすい概念の 1 つですが、開発者として使用可能なクラスに変換するのは困難です。だからこそ、私は可能性について興味を持っています。

編集:

一部の回答者は、 Bag 内部的にはハッシュテーブルの形式である可能性があります。これは私の最初の考えでもありましたが、この考えには 2 つの問題があると予想していました。

  1. 問題の型に適したハッシュコード関数がない場合、ハッシュテーブルはあまり役に立ちません。
  2. コレクション内のオブジェクトの「数」を単に追跡することは、オブジェクトを保存することと同じではありません。

Meta-Knight が示唆したように、おそらく次のような例がこれをより明確にするでしょう。

public class ExpensiveObject() {
    private ExpensiveObject() {
        // very intense operations happening in here
    }

    public ExpensiveObject CreateExpensiveObject() {
        return new ExpensiveObject();
    }
}

static void Main() {
    var expensiveObjects = new ConcurrentBag<ExpensiveObject>();

    for (int i = 0; i < 5; i++) {
        expensiveObjects.Add(ExpensiveObject.CreateExpensiveObject());
    }

    // after this point in the code, I want to believe I have 5 new
    // expensive objects in my collection

    while (expensiveObjects.Count > 0) {
        ExpensiveObject expObj = null;
        bool objectTaken = expensiveObjects.TryTake(out expObj);
        if (objectTaken) {
            // here I THINK I am queueing a particular operation to be
            // executed on 5 separate threads for 5 separate objects,
            // but if ConcurrentBag is a hashtable then I've just received
            // the object 5 times and so I am working on the same object
            // from 5 threads at the same time!
            ThreadPool.QueueUserWorkItem(DoWorkOnExpensiveObject, expObj);
        } else {
            break;
        }
    }
}

static void DoWorkOnExpensiveObject(object obj) {
    ExpensiveObject expObj = obj as ExpensiveObject;
    if (expObj != null) {
        // some work to be done
    }
}
役に立ちましたか？

解決

あなたはConcurrentBag<T>の詳細を見れば、あなたはそれが基本的には、内部的に、カスタマイズされたリンクリストだことがわかります。

バッグは、重複を含み、インデックスによってアクセスできないことから、

、二重にリンクされたリストは、実装のための非常に良いオプションです。これは、挿入および除去のため、かなりきめ細かいことをロックできます（あなたがコレクション全体をロックする必要はありません、あなたは取り付け/取り外している場所の周りだけのノード）。あなたが重複心配じゃないので、何のハッシュが関与していません。これは、二重リンクリスト完璧になります。

他のヒント

ConcurrentBag上でいくつかの良い情報がここにあります：<のhref = "http://geekswithblogs.net/BlackRabbitCoder/archive/2011/03/03/c.net-little-wonders-concurrentbag-and-blockingcollection.aspx" rel = "nofollowを"> http://geekswithblogs.net/BlackRabbitCoder/archive/2011/03/03/c.net-little-wonders-concurrentbag-and-blockingcollection.aspx の

  ConcurrentBagが動作することを

道   新しいの利点を取ることです   ThreadLocalのタイプ（新しい中   そのように.NET 4.0）のためにSystem.Threading   袋を使用して、各スレッドがリストを持っています   ちょうどそのスレッドにローカルな。

     

この追加または削除することを意味します   スレッドローカルリストは非常に低いが必要です   同期。問題がでてきます   スレッドには、アイテムを消費に進み、   それは地元のリストが空であるのです。この中   ケースバッグは、「ワークスチール」を行います   どこで奪うが、他の項目意志   そのリスト内のアイテムを持っているスレッド。   これは、より高いレベルを必要とします   のビットを付加同期   テイク操作にオーバーヘッドます。

発注のでConcurrentBagは、データの高速検索を可能にするために舞台裏でハッシュテーブルを使用している可能性は重要ではありません。しかし、 HashSetののバッグは、重複を受け入れます。多分各アイテムは、アイテムが追加されたときに1にセットされ、Countプロパティと対にすることができます。あなたが二度目に同じ項目を追加した場合、あなただけのこのアイテムのCountプロパティをインクリメントすることができます。

すると、1より大きい数を持っているアイテムを削除するには、あなただけのこのアイテムのカウントを減少させることができました。カウントが1だった場合は、ハッシュテーブルから項目-カウントペアを削除します。

さて、（バッグの概念はどこから来たのか）のSmalltalkで、コレクションは重複を可能にするものであるものの、基本的にはハッシュと同じです。代わりにかかわらず、複製オブジェクトを格納するには、「発生回数」、例えば、各オブジェクトの参照カウントを維持します。 ConcurrentBagは忠実な実装である場合、これはあなたの出発点を与える必要があります。

「バッグ」という概念は「マルチセット」と同義だと思います。

実装方法に興味がある場合は、オープン ソースの「Bag」/「Multiset」実装 (これらは Java です) が多数あります。

これらの実装は、ニーズに応じてさまざまな方法で「バッグ」を実装できることを示しています。TreeMultiset、HashMultiset、LinkedHashMultiset、ConcurrentHashMultiset の例があります。

Google コレクション
Googleには数多くの 「MultiSet」の実装, 1 つは ConcurrentHashMultiset です。

Apache Commons
Apache には多数の「Bag」実装があります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top