CODEWITHSUNDEEP
c#.netcollections
Aelian
Aelian

Reputation: 695

Updating all values in a C# keyed collection in O(n) time?

This is a problem I have encountered again and again in C#, but haven't found a general solution. In C++/STL, all values in a map can be updated in O(n) time using an iterator without using keys to access each element. Is there a way to obtain similar behavior with any of the C# collections such as SortedList, SortedDictionary?

I can do something like

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

But that would take O(n * log(n)) as the searching each element using key takes log(n).

Just to give an idea, I am looking for something along the lines of:

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;
}

Since the List is already sorted it should be possible to traverse it updating values (not keys) at the same time. It doesn't look like there is a problem with that from the implementation point of view, but for some reason the functionality is not made available it seems.

Also this is not a trivial case as the same method can be used to iterate from a known position to another modifying values in that range.

Is there a way to do this in C# with any of the keyed collections in .NET without using 3rd party libraries?

Thank you

Jeeves

Upvotes: 6

Views: 974

Answers (3)

Marty Neal
Marty Neal

Reputation: 9533

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();

The SortedList constructor is O(n) according to the docs.
The .ToDictionary loops over Dictionary.Add under the hood. Dictionary.Add is O(1) when the capacity is sufficient source

O(n) * O(1) is still O(n) so you're good :-)

The space requirements are of course doubled using this approach.

Upvotes: 2

Kiril
Kiril

Reputation: 40345

In C# accessing a Dictionary element is close to constant time of O(1).

You can get a list of values by calling Dictionary.Values and updating them:

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

Getting the value of this property (Dictionary.Values) is also an O(1) operation..

Upvotes: 0

Knaģis
Knaģis

Reputation: 21485

Simplest solution would be to wrap the value in a reference type.

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;
}

This approach would work with any collection (list or dictionary). One of the few collections that does this by design without the wrapper is LinkedList.

Of course, if you have a very specific collection (created by some external component), you can always fall back to using reflection and change the values directly in the underlying storage.

Upvotes: 3

Related Questions