I have a piece of code that divides a group of numbers into two groups of numbers of which the sums are equal.
I created this because of a Stack Overflow question:
For example:
- {10,15,20,5} will result in: {10,15} + {20,5}
- {1,2,3,4} will result in: {1,4} + {2,3}
- {5,5,5,15} will result in: {5,5,5} + {15}
- {5, 6} will fail.
This is the code:
static public bool Partition(IList<int> numbers, out IList<int> group0, out IList<int> group1)
{
if (numbers == null)
throw new ArgumentNullException("numbers");
group0 = group1 = null;
if (numbers.Count <= 1)
return false;
int totalSum = numbers.Sum();
if (totalSum % 2 != 0)
return false;
int desiredSum = totalSum / 2;
BitArray groupPerNumber = new BitArray(numbers.Count);
while (true)
{
groupPerNumber.Increase(); // Increate the numberic value of the BitArray.
if (groupPerNumber.IsEmpty()) // If all bits are zero, all iterations have been done.
return false;
// Fill the groups. The bit in the groups-array determines in which group a number will be place.
int sumGroup1 = 0;
for (int index = 0; index < numbers.Count; index++)
{
int number = numbers[index];
if (groupPerNumber[index])
sumGroup1 += number;
}
// If both sums are equal, exit.
if (sumGroup1 == desiredSum)
{
group0 = new List<int>();
group1 = new List<int>();
for (int index = 0; index < numbers.Count; index++)
{
int number = numbers[index];
if (!groupPerNumber[index])
group0.Add(number);
else
group1.Add(number);
}
return true;
}
}
}
I created some supporting extension methods:
static public class BitSetExtensions
{
/// <summary>
/// Treats the bits as a number (like Int32) and increases it with one.
/// </summary>
static public void Increase(this BitArray bits)
{
for (int i = 0; i < bits.Length; i++)
{
if (!bits[i])
{
bits[i] = true;
bits.SetAll(0, i - 1, false);
return;
}
bits[i] = false;
}
bits.SetAll(false);
}
/// <summary>
/// Sets the subset of bits from the start position till length with the given value.
/// </summary>
static public void SetAll(this BitArray bits, int start, int length, bool value)
{
while (length-- > 0)
bits[start++] = value;
}
/// <summary>
/// Returns true if all bits in the collection are false.
/// </summary>
static public bool IsEmpty(this BitArray bits)
{
for (int i = 0; i < bits.Length; i++)
if (bits[i])
return false;
return true;
}
}
Criteria:
- The group of numbers must have any size.
- Only two sets have to be found.
- The order of the numbers may be mixed up. So sorting is allowed.
- The numbers must be greater than 0.
The real question is: How can this code be made any faster?
Results so far:
Original posting (by myself): 3.657.559 ticks = factor 1.0 (baseline)
All combined trics (answer of myself): 8.563 ticks = factor 427.1
Code of Ivan: 12.969 ticks = factor 282,0
Code of Stephen: 34.415 ticks = factor 106,3
Code of Jesse: 1.743.905 ticks = factor 2,097
Code of Eren: 16.108.289 ticks = factor 0,2270
Code of Servy: 225.239.100 ticks = factor 0,01623
Code of Bobson: 49.663.859.000 ticks = factor 0,000074
Things I have learned so far:
- Try to avoid interfaces if you have access to the real class. So
int[]
is faster thanIList<int>
. - Try to avoid complex structures in you have a basic structure. So
bool[]
is faster thanBitArray
. - Try to avoid any memory operations (like
new
). - Try to avoid
foreach
. Usefor
. Every time you useforeach
anIEnumerator
is created, resulting in a memory operation. - Try to avoid LINQ. LINQ is based on already existing methods. It is just one extra call. Further it relies on
IEnumerable
, which will create anIEnumerable
at every call, resulting in a memory operation. - My original code analyzed ALL combinations. The early out algorithm in my second posting saved me a lot of time.
- Skip on iteration by using the first number as a starting sum, instread of 0.
- Use for-loops counting back to 0.
The test
I use a few arrays of numbers:
var arrays = new int[][]
{
new[]{ 1, 12, 10, 2, 23 },
new[] {14,10,20,4},
new[] {5, 5, 15, 5},
new[] {1, 5, 30}, // Will fail.
new[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, // Will fail.
new[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16},
};
The time of a Partion-function is measured as follows:
Stopwatch st0 = Stopwatch.StartNew();
for (int i = iterations - 1; i >= 0; i--)
for (int n = arrays.Length - 1; n >= 0; n--)
if (PartitionOriginal(arrays[n], out list0, out list1))
sum = list0.Sum() + list1.Sum();
st0.Stop();
The value iterations
is a constant, by default set with 1000. If the partition succeeds, the first result result set (some functions return more than one result set) are summed. The reason behind this summing is to ensure that all search work is done. Sometimes when an IEnumerable
is returned, code (using yield return
) still needs to be executed.
0011
is the same as1100
. So if I would prevent that, it could result in more speed. And perhaps there are even more issues I am not aware of. \$\endgroup\$C
feature instead of theC#
one". There's a reason C is still used for most embedded systems I know of. \$\endgroup\$