5

これは、私が C# で何度も遭遇した問題ですが、一般的な解決策は見つかりませんでした。C++/STL では、キーを使用して各要素にアクセスすることなく、イテレータを使用してマップ内のすべての値を O(n) 時間で更新できます。SortedList、SortedDictionary などの C# コレクションで同様の動作を取得する方法はありますか?

私は次のようなことができます

foreach (int key in list.Keys)
{
    list[key] *= 3;
}

ただし、キーを使用して各要素を検索するとlog(n)がかかるため、O(n * log(n))がかかります。

アイデアを与えるために、私は次のようなものを探しています：

SortedList<int, double> list = new SortedList<int,double>();

// Add few values fist

// E.g. first try ...
IList<double> values = list.Values;
for (int i = 0; i < values.Count; i++)
{
    values[i] *= 3;
}

// E.g. second try
foreach (KeyValuePair<int, double> kv in list)
{
    kv.Value *= 3;
}

List は既にソートされているため、値 (キーではなく) を同時に更新しながらトラバースできるはずです。実装上は問題ないように見えますが、何らかの理由で機能が利用できないようです。

また、同じ方法を使用して、既知の位置からその範囲内の別の変更値まで反復できるため、これは簡単なケースではありません。

サードパーティのライブラリを使用せずに、.NET のキー付きコレクションを使用して C# でこれを行う方法はありますか?

ありがとうございました

ジーブス

4

3 に答える 3

3

最も簡単な解決策は、値を参照型でラップすることです。

class WrappedInt { public int Value; }
Dictionary<TKey, WrappedInt> dictionary = ...;
foreach (var wrappedVal in dictionary.Values)
{
    wrappedVal.Value *= 3;
}
// or 
foreach (var wrappedVal in dictionary)
{
    wrappedVal.Value.Value *= 3;
}

このアプローチは、任意のコレクション (リストまたはディクショナリ) で機能します。ラッパーなしで設計によりこれを行う数少ないコレクションの 1 つがLinkedList.

もちろん、非常に特殊なコレクション (何らかの外部コンポーネントによって作成されたもの) がある場合は、いつでもリフレクションの使用にフォールバックし、基になるストレージで値を直接変更できます。

于 2012-10-30T17:06:25.210 に答える
1 
SortedList<int, double> list = new SortedList<int,double>
{
    { 1, 3.14 },
    { 2, 1.618 },
};

var newList = new SortedList<int, double>(list.ToDictionary(kv => kv.Key, kv => kv.Value * 3)).Dump();

docsによると、SortedList コンストラクターは O(n)です。
.ToDictionary は、内部で Dictionary.Add をループします。容量が十分なソースの場合、Dictionary.Add は O(1) です

O(n) * O(1) はまだ O(n) なので、大丈夫です :-)

もちろん、このアプローチを使用すると、必要なスペースは 2 倍になります。

于 2012-10-30T17:30:47.643 に答える
0

C# では、ディクショナリ要素へのアクセスは O(1) の定数時間に近くなります。

Dictionary.Values を呼び出して値を更新すると、値のリストを取得できます。

foreach(var value in valuesDict.Values)
{
    // update value;
}

このプロパティ ( Dictionary.Values)の値を取得することも O(1) 操作です。.

于 2012-10-30T17:06:41.663 に答える