193

7
Q:

## How to efficiently get highest & lowest values from a List<double?>, and then modify them?

I have to get the sum of a list of doubles. If the sum is > 100, I have to decrement from the highest number until it's = 100. If the sum is < 100, I have to increment the lowest number until it's = 100. I can do this by looping though the list, assigning the values to placeholder variables and testing which is higher or lower but I'm wondering if any gurus out there could suggest a super cool & efficient way to do this? The code below basically outlines what I'm trying to achieve:

``````var splitValues = new List<double?>();

var listSum = splitValues.Sum(split => split.Value);
if (listSum != 100)
{
if (listSum > 100)
{
// how to get highest value and decrement by 1 until listSum == 100
// then reassign back into the splitValues list?
var highest = // ??
}
else
{
// how to get lowest where value is > 0, and increment by 1 until listSum == 100
// then reassign back into the splitValues list?
var lowest = // ??
}
}
``````

update: the list has to remain in the same order as the items are added.

+2  A:

The most efficient way is to write a plain and simple loop that does the work, that will give the least amount of overhead. You have to look at all values in the list to find the largest or smallest, so there is no shortcuts.

I think that the most efficient would be to make an index sort, i.e. create an array of indexes that you sort by the values that they point to. When you start to increment or decrement the values, you may need more than just the smallest or largest number.

+4  A:

I think the most efficient thing is probably to not use the List.Sum() method, and do one loop that calculates the sum, lowest, and highest. It's also easy to write, debug, read, and maintain, which I would say qualifies as super-cool.

+2  A:

Update: Gah, I didn't notice that you seem to only have 4 elements in the list. The answer here is for the general case, and will be overkill for a 4-element problem. Go with looping.

Well, personally I would use a Heap data structure, where each element is the value of each element + its position in the original list.

You need to hunt down a good Heap implementation for C# though. You can use mine, but it is part of a larger class library so it might be a bit of a rubber ball to pull into your project. The code is here: My Mercurial Repository.

I'll be showing examples below on how my implementation would work.

If you don't know how a heap works, it is basically a data structure that looks a bit like an array, but also a bit like a tree, where the nodes of the tree is stored in the array. There's a bit of code involved that "intelligently" moves items around. The beauty of it is that it is super easy to get the highest or lowest item (that is, one of them, not both from the same heap), since it will always be the first element in the array.

So what I would do is this:

1. Create a heap containing value+position for all elements, sorted so that the highest value is the first one
2. Create a heap containing value+position for all elements, sorted so that the lowest value is the first one

Then, if the sum < 0, grab the first element of the heap (value + position), increase the value in the original list by 1, then replace the first element of the heap with (value+1),position. Replacing the first element of the heap has the effect of removing it, and then readding it, potentially moving it to a different position than the first one if it is no longer the highest/lowest value. For instance, let's say you have the following list:

``````list: 1, 2, 3
``````

The heap now looks like this:

``````heap: (1, 0), (2, 1), (3, 2)  <-- second value is position, 0-based
``````

ie. you build it up like this:

``````position:  0, 1, 2
list:      1, 2, 3
|  |  +-------+
|  |          |
+-+  +--+       |
|       |       |
<-+>    <-+>    <-+>
heap: (1, 0), (2, 1), (3, 2)
``````

Now, if the sum is too low, you grab the first element of the lo-heap, which is `(1, 0)`, increase the value at position 0 in the original list by 1, then replace the first element of the heap (which is still `(1, 0)`) with a new element containing the new value, at the same position.

After the replace, the list and heap now looks like this:

``````list: 2, 2, 3
heap: (2, 0), (2, 1), (3, 1)
``````

Let's say the sum is still to low, so you repeat. Now, when re-adding `(3, 0)` instead of `(2, 0)`, it will be pushed a bit back into the heap, so it looks like this:

``````list: 3, 2, 3
heap: (2, 1), (3, 0), (3, 1)
``````

Now, the 2-value is now the lowest one, and thus the first element of the heap. Note that these operations does not reorder the entire heap, only the portions necessary. As such, a heap is ideal for algorithms like this since they are cheap to keep sorted when doing modifications.

So let's see some code. I'm assuming you have an array of values like this:

``````int[] values = new int[] { ... };
``````

Thus, with my heap implementation, the following would do what you want:

``````using System;
using System.Collections.Generic;
using System.Linq;
using LVK.DataStructures.Collections;

namespace SO3045604
{
class LowestComparer : IComparer<Tuple<int, int>>
{
public int Compare(Tuple<int, int> x, Tuple<int, int> y)
{
return x.Item1.CompareTo(y.Item1);
}
}

class HighestComparer : IComparer<Tuple<int, int>>
{
public int Compare(Tuple<int, int> x, Tuple<int, int> y)
{
return -x.Item1.CompareTo(y.Item1);
}
}

class Program
{
static void Main(string[] args)
{
int[] values = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

var valuesWithPositions = values
.Select((value, index) => Tuple.Create(value, index));

var loHeap = new Heap<Tuple<int, int>>(
new LowestComparer(),
valuesWithPositions);
var hiHeap = new Heap<Tuple<int, int>>(
new HighestComparer(),
valuesWithPositions);

int sum = values.Aggregate((a, b) => a + b);

while (sum < 75)
{
var lowest = loHeap;
values[lowest.Item2]++;
loHeap.ReplaceAt(0,
Tuple.Create(lowest.Item1 + 1, lowest.Item2));
sum++;
}
while (sum > 55)
{
var highest = hiHeap;
values[highest.Item2]--;
hiHeap.ReplaceAt(0,
Tuple.Create(highest.Item1 - 1, highest.Item2));
sum--;
}

// at this point, the sum of the values in the array is now 55
// and the items have been modified as per your algorithm
}
}
}
``````
Isn't the time complexity to build the heap O(n*log(n)) though?
Despite the time complexity of the heap this is probably the most efficient algorithm. Honestly, this is the answer that should have been accepted.
Well, it depends on the complexity of the elements in the array. My solution would have some initial overhead to build the extra data structures, but after that it should require no searching, sorting, or looping to find the elements to adjust. Of course, as with all solutions, profile, profile, profile!
No, your solution is definitely faster in the worst than the accepted answer. The accepted answer has `O(n*m)` complexity where `n` is the number of elements in the list and `m` is the maximum value. Yours is `O(n*log(n)) + O(m)` so you have a better worst case complexity, but a worst best case complexity right? It really depends on which dominates `n` or `m`. At first I thought your answer would be slower, but that was before I realized I misundestood the question (along with most others).
A:

I'd do it something like this:

``````var splitValues = new List<double?>();

var listSum = splitValues.Sum(split => split.Value);
while (listSum != 100)
{
var value = listSum > 100 ? splitValues.Max() : splitValues.Min();
var idx = splitValues.IndexOf(value);
splitValues.RemoveAt(idx);
splitValues.Insert(idx, value + (listSum > 100 ? -1 : 1));
listSum = splitValues.Sum(split => split.Value);
}
``````

Note: This solution would work for any number of elements in the list.

This seems to do some odd things, such as using RemoveAt/Insert instead of just splitValues[idx]. For that matter, I don't believe it's necessary to keep looping when you can instead calculate the correct value to use. While the basic idea is right, and the code may well work, I don't believe it's currently of production quality.
No odd thing is done. It takes out the highest/lowest value and increments/decrements one then inserts it into the SAME place in the list. All according to the OPs "rules". It sure is necessary to keep looping until the target is hit since I assume the incremental/decremental value is 1 (one). Who said anything about production quality? The OP gave us what he was working with and I "fixed" his code. I would not necessarily write it like this if I could write everything myself. But in this case the OP gave us a starting point from where to begin. Hence you, my good sir, are wrong.
Although this works, it's definitely not an efficient way to do it. Thus, it's not what the OP asked for.
If you see mine and the OPs comments to his questions you'll find out exactly that with effieciency he does NOT mean fast, small memory footprint or short execution path, but rather clean, readable code. Sure I could make it even more readable but that is a personal preference of how readable you want your code. For me the above code is perfectly readable.
A:

``````        const double MIN_VALUE = 0.01;

var values = new List<double>();
var rand = new Random();
for (int i = 0; i < 100; i++)
{
}

double sum = 0, min = 0, max = 0;
for (int i = 0; i < values.Count; i++)
{
var value = values[i];
sum += value;
min = Math.Min(value, min);
max = Math.Max(value, max);
}

if (min == 0) min = MIN_VALUE;
if (max == 0) max = MIN_VALUE;
while (Math.Abs(sum - 100) > MIN_VALUE)
{
if (sum > 100)
sum -= max;

if (sum < 100)
sum += min;
}
``````
A:

Here's an implementation using Linq's `Aggregate` method (assuming `list` is a list or array of doubles, or anything that implements `IList<double>`) :

``````var stats = list.Aggregate(
StatsAggregate.Default,
(a, v) => a.ProcessValue(v));

if (stats.Sum > 100.0)
{
list[stats.MaxIndex] -= (stats.Sum - 100.0);
}
else if (stats.Sum < 100.0)
{
list[stats.MinIndex] += (100.0 - stats.Sum);
}

...

struct StatsAggregate
{
public static StatsAggregate Default
{
get
{
return new StatsAggregate
{
Sum = 0,
Min = double.MaxValue,
MinIndex = -1,
Max = double.MinValue,
MaxIndex = -1
};
}
}

private int currentIndex;

public double Sum { get; private set; }
public double Min { get; private set; }
public double Max { get; private set; }
public int MinIndex { get; private set; }
public int MaxIndex { get; private set; }

public StatsAggregate ProcessValue(double value)
{
return new StatsAggregate
{
Sum = this.Sum + value,
Max = Math.Max(this.Max, value),
MaxIndex = value > this.Max ? currentIndex : MaxIndex,
Min = Math.Min(this.Min, value),
MinIndex = value < this.Max ? currentIndex : MinIndex,
currentIndex = currentIndex + 1
};
}
}
``````

The advantage of this technique is that it iterates the list only once, and the code is clearer than with a foreach loop (IMHO...)

A:

It appears as though I misunderstood the question at first. Apparently the goal is not to find the highest/lowest and add +/-1 to that element until the sum is 100; the goal is to find the new highest/lowest every time you add +/-1.

Here's another answer, based on Sani's:

``````var splitValues = new List<double?>();