3
\$\begingroup\$

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 than IList<int>.
  • Try to avoid complex structures in you have a basic structure. So bool[] is faster than BitArray.
  • Try to avoid any memory operations (like new).
  • Try to avoid foreach. Use for. Every time you use foreach an IEnumerator 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 an IEnumerable 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.

\$\endgroup\$
  • \$\begingroup\$ What's slow about it? Have you measured it and determined the hot spot(s)? \$\endgroup\$ – Jesse C. Slicer May 9 '13 at 14:16
  • \$\begingroup\$ @Jesse: At stackoverflow there was a suggestion that each combination is analyzed twice. And he is right. Bit combination 0011 is the same as 1100. 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\$ – Martin Mulder May 9 '13 at 14:21
  • \$\begingroup\$ I disagree with everything you have in your list of things you've learned, except the last, for the record. \$\endgroup\$ – Bobson May 14 '13 at 19:40
  • \$\begingroup\$ Well, for the record they're all good advice for speed, but they're basically "Use a C feature instead of the C# one". There's a reason C is still used for most embedded systems I know of. \$\endgroup\$ – Bobson May 14 '13 at 19:54
2
\$\begingroup\$

The main idea is to find a biggest element, place it in the first bin and start recursion from the second element saving lots of tree spanning.

UPDATED CODE

Main Method

public static class ASolution
{
    public static bool TryPartitionBySum(int[] values, out int[] fstBin, out int[] scndBin)
    {
        #region Part I

        if (values == null)
            throw new ArgumentNullException("values");

        fstBin = scndBin = null;

        if (values.Length <= 1)
            return false;

        int totalSum = 0;
        int maxIdx = -1;
        int maxVal = -1;
        for (int i = 0; i < values.Length; i++)
        {
            int tmp = values[i];
            if (tmp <= 0)
                throw new ArgumentException("Numbers is not allowed to contain values less than one.");
            if (tmp > maxVal)
            {
                maxVal = tmp;
                maxIdx = i;
            }
            totalSum += tmp;
        }

        #endregion

        if (totalSum % 2 != 0)
            return false;

        //  Put max val at the first place
        values[maxIdx] = values[0];
        values[0] = maxVal;

        var activeIdx = new bool[values.Length];
        activeIdx[0] = true;
        int targetSum = totalSum / 2 - maxVal;

        if (targetSum < 0)
            return false;

        bool isSuccess = targetSum == 0 || RecursiveTryPartition(values, activeIdx, 1, targetSum);

        #region PART III

        if (isSuccess)
        {
            int fstBinIdx = 0, scndBinIdx = 0;
            int size = 0;

            for (int i = 0; i < activeIdx.Length; i++)
            {
                if (activeIdx[i])
                    size++;
            }
            fstBin = new int[size];
            scndBin = new int[activeIdx.Length - size];

            for (int i = 0; i < activeIdx.Length; i++)
            {
                if (activeIdx[i])
                    fstBin[fstBinIdx++] = values[i];
                else
                    scndBin[scndBinIdx++] = values[i];
            }
        }

        #endregion

        return isSuccess;
    }

    private static bool RecursiveTryPartition(int[] numbers, bool[] isActive, int headIdx, int sumLeft)
    {
        if (headIdx == numbers.Length)
            return false;

        int currVal = numbers[headIdx];
        isActive[headIdx] = true;

        if (currVal < sumLeft && RecursiveTryPartition(numbers, isActive, headIdx + 1, sumLeft - currVal))
            return true;

        if (currVal == sumLeft)
            return true;

        isActive[headIdx] = false;
        return RecursiveTryPartition(numbers, isActive, headIdx + 1, sumLeft);
    }
}

TEST ITEM

Unfortunately you need to plug-in your method to which defines whether a sequence is partitionable.

public class TestCase
{
    private const string Delim = ",";
    public int ExperimentsCount { get { return Values.Length; } }
    public int VectorSize { get { return Values[0].Length; } }
    public int PartitionableCount { get; private set; }

    private int[][] Values { get; set; }

    private TestCase() { }

    public IEnumerable<int[]> TestSample
    {
        get
        {
            return Values.Select(f => f.ToArray());
        }
    }

    public void ToFile(string path)
    {
        System.IO.File.WriteAllText(path, PartitionableCount + "\n");
        System.IO.File.AppendAllLines(path, Values.Select(f => string.Join(Delim, f)));
    }

    public TestCase Read(string path)
    {
        var lines = System.IO.File.ReadAllLines(path);
        return new TestCase
        {
            PartitionableCount = int.Parse(lines[0]),
            Values = lines.Skip(1)
                          .Select(line => line.Split(Delim[0])
                                              .Select(int.Parse)
                                              .ToArray())
                          .ToArray()
        };
    }

    public static TestCase CreateSample(int experimentsCount, int vectorSize, double targetedSuccessRate
                                        , Func<int[], bool> isPartitionable)
    {
        if (targetedSuccessRate < 0 || targetedSuccessRate > 1)
            throw new ArgumentException("Success rate must be a percentage value", "targetedSuccessRate");
        if (experimentsCount < 0)
            throw new ArgumentException("Experiments count must be a positive number");
        if (vectorSize < 5)
            throw new ArgumentException("Vector size should be at least 5");

        var rnd = new Random();
        var tmp = new TestCase
        {
            Values = new int[experimentsCount][],
            PartitionableCount = (int)(targetedSuccessRate * experimentsCount)
        };

        var successTriesLeft = tmp.PartitionableCount;

        int successIdx = experimentsCount - successTriesLeft;
        int failIdx = successIdx - 1;

        while (successIdx < experimentsCount || failIdx >= 0)
        {
            var vec = Enumerable.Range(0, vectorSize)
                                .Select(_ => rnd.Next(1, vectorSize * 3))
                                .ToArray();

            if (isPartitionable(vec))
            {
                if (successIdx < experimentsCount)
                {
                    tmp.Values[successIdx++] = vec;
                }
            }
            else
            {
                if (failIdx >= 0)
                {
                    tmp.Values[failIdx--] = vec;
                }
            }
        }
        return tmp;
    }

}

TEST RUNNER

public static class TestRunner
{
    public delegate bool Partitioner(int[] values, out int[] fstBin, out int[] scndBin);

    public static long RunTest(TestCase testData, Partitioner function)
    {
        var vals = testData.TestSample.ToArray();
        var sw = System.Diagnostics.Stopwatch.StartNew();
        int count = 0;
        foreach (var vector in vals)
        {
            int[] fstBin, sndBin;
            if (function(vector, out fstBin, out sndBin))
            {
                count++;
                //System.Diagnostics.Trace.Assert(fstBin.Sum() == sndBin.Sum());
            }
        }
        sw.Stop();

        //System.Diagnostics.Trace.Assert(count == testData.PartitionableCount);
        return sw.ElapsedTicks; 
    }
}

SAMPLE OF CODE USAGE

        var iterCount = 10000;
        var vectorSizes = new[] { 5, 10, 25, 50};
        var successRate = new[] { 0, 0.2, 0.5, 0.8, 1.0};

        var testList = vectorSizes.SelectMany(v => 
            successRate.Select(r => new { VectorSize = v, SuccessRate = r }));

        Console.WriteLine("{0,-10}{1,-10}{2,10}{3,10}", "Rate,%", "Size", "M sol", "I sol");
        foreach (var item in testList)
        {
            int[] a, b;
            var tmp = TestCase.CreateSample(iterCount, item.VectorSize, 
                item.SuccessRate, vals => Mulders.Partition(vals, out a, out b));
            //var tmp = TestCase.Read("MySavedCase.csv");
            Console.WriteLine("{0,-10:P}{1,-10}{2,10:N0}{3,10:N0}",
                (double)tmp.PartitionableCount / tmp.ExperimentsCount,
                tmp.VectorSize,
                TestRunner.RunTest(tmp, Mulders.Partition),
                TestRunner.RunTest(tmp, ASolution.TryPartitionBySum));
        }

Hope it'll help to run some tests for all solutions.

\$\endgroup\$
  • \$\begingroup\$ What's interesting the recursion part takes about 30% of execution time. \$\endgroup\$ – Ivan Nechipayko May 16 '13 at 0:41
  • \$\begingroup\$ At this moment (just out of bed and did a quick scan) it seems you are the fastest so far. More results tomorrow! :) \$\endgroup\$ – Martin Mulder May 16 '13 at 6:13
  • \$\begingroup\$ Actually you don't need to search the biggest element. You could try to put first element in the bin by default. Need to measure this. \$\endgroup\$ – Ivan Nechipayko May 16 '13 at 11:58
  • \$\begingroup\$ I toke some measurements. Your solution is in fact slower than the solution I already head. Finding the largest number consumes more time than the saving of the numbers. Still you gave me a good idea to skip at least ONE iteration. Besides that, your are by far the fastest solution compare to the other answers. \$\endgroup\$ – Martin Mulder May 19 '13 at 16:24
  • \$\begingroup\$ What's your testing sample? Could you post the test code? \$\endgroup\$ – Ivan Nechipayko May 20 '13 at 19:15
2
\$\begingroup\$

Here's some stuff I did to increase the performance. If there's any parts that you'd like explained fuller, let me know and I will.

    private static readonly IList<int> emptyList = Enumerable.Empty<int>().ToList();

    public static bool Partition(IList<int> numbers, out IList<int> group0, out IList<int> group1)
    {
        if (numbers == null)
        {
            throw new ArgumentNullException("numbers");
        }

        if (numbers.Count <= 1)
        {
            group0 = group1 = emptyList;
            return false;
        }

        var totalSum = numbers.Sum();

        if (totalSum % 2 != 0)
        {
            group0 = group1 = emptyList;
            return false;
        }

        var desiredSum = totalSum / 2;
        var groupPerNumber = Enumerable.Repeat(false, numbers.Count).ToList();
        Func<bool, bool> bitOff = BitOff;
        Func<int, int, bool> whereBitsOn = new WhereBitsOnContainer(groupPerNumber).WhereBitsOn;

        do
        {
            groupPerNumber.Increase(); // Increase the numeric value of the BitArray.

            if (!groupPerNumber.All(bitOff))
            {
                continue;
            }

            // If all bits are zero, all iterations have been done.
            group0 = group1 = emptyList;
            return false;
        }
        while (numbers.Where(whereBitsOn).Sum() != desiredSum); // If both sums are equal, exit.

        // Fill the groups. The bit in the groups-array determines in which group a number will be place.
        var balancedSizeGuess = numbers.Count / 2;

        group0 = new List<int>(balancedSizeGuess);
        group1 = new List<int>(balancedSizeGuess);
        for (var index = 0; index < numbers.Count; index++)
        {
            (groupPerNumber[index] ? group1 : group0).Add(numbers[index]);
        }

        return true;
    }

    private static bool BitOff(bool bit)
    {
        return !bit;
    }

    private sealed class WhereBitsOnContainer
    {
        private readonly IList<bool> groupPerNumber;

        public WhereBitsOnContainer(IList<bool> groupPerNumber)
        {
            this.groupPerNumber = groupPerNumber;
        }

        public bool WhereBitsOn(int number, int index)
        {
            return this.groupPerNumber[index];
        }
    }
}

public static class BitSetExtensions
{
    /// <summary>
    /// Treats the bits as a number (like Int32) and increases it with one.
    /// </summary>
    public static void Increase(this IList<bool> bits)
    {
        for (var i = 0; i < bits.Count; i++)
        {
            if (!bits[i])
            {
                bits[i] = true;
                bits.SetAllFalse(i);
                return;
            }

            bits[i] = false;
        }

        bits.SetAllFalse(bits.Count);
    }

    /// <summary>
    /// Sets the subset of bits from the start position till length to false.
    /// </summary>
    private static void SetAllFalse(this IList<bool> bits, int length)
    {
        var start = 0;

        while (--length > 0)
        {
            bits[start++] = false;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for the effort. I am going to take a look tomorrow. I do have one first question: why the empty list? I think this is dangerous and I prefer null. It is dangerous because a caller can modify this list by adding numbers which should not be allowed in there. And I do not think it will increase perfomance, right? \$\endgroup\$ – Martin Mulder May 9 '13 at 22:03
  • \$\begingroup\$ Question #2: Why use LINQ? In my experience LINQ slows down almost any operation. When it comes down to performance I'd never use LINQ. \$\endgroup\$ – Martin Mulder May 9 '13 at 22:30
  • \$\begingroup\$ Answer to question #1: stackoverflow.com/a/1970001/3312 . Answer to question #2: only if you're doing it wrong. LINQ is a highly tested and tuned library. It allows for expressing the what you want rather than how to do it. \$\endgroup\$ – Jesse C. Slicer May 9 '13 at 23:53
  • \$\begingroup\$ I tested it with some testcases. My original solution is a factor 1.6 faster than your solution. I gave my an idea though to replace my BitArray by an bool[]. This made it 1.3x faster. So thank you very much for that idea! The difference between my solution and your suggestion is now factor 2.1. And I still think it is because of LINQ... \$\endgroup\$ – Martin Mulder May 10 '13 at 0:01
  • \$\begingroup\$ Cool! Best of luck. \$\endgroup\$ – Jesse C. Slicer May 10 '13 at 0:38
2
\$\begingroup\$

I realize this isn't necessarily faster, but it will be much easier to maintain, and at least one example ought to be posted using LINQ.

So here's that example, using LINQ and the Combinatorics library to do it in a single statement, and in a more object-oriented manner*:

public IEnumerable<Group> Partition(IList<int> list)
{
    var results = new Permutations<int>(list)
                      .SelectMany(x => Enumerable.Range(1, list.Count() -1)
                                                 .Select(y => new Group{ 
                                                        Left = x.Take(y), 
                                                        Right = x.Skip(y)
                                                    }))
                      .Where(x => x.Left.Sum() == x.Right.Sum())
                      .Distinct();

    return results;
}

And here's the Group class I used:

class Group
{
    public IEnumerable<int> Left { get; set;}
    public IEnumerable<int> Right { get; set;}

    public override bool Equals(object b) {
        if (!(b is Group)) return false;
        var a1 = this.Left.OrderBy(x => x);
        var a2 = this.Right.OrderBy(x => x);
        var b1 = ((Group)b).Left.OrderBy(x => x);
        var b2 = ((Group)b).Right.OrderBy(x => x);
        return ((a1.SequenceEqual(b1) && a2.SequenceEqual(b2))
            || (a1.SequenceEqual(b2) && a2.SequenceEqual(b1)));
    }

    public override int GetHashCode() {
        return this.Left.OrderBy(x => x).Concat(this.Right.OrderBy(x => x))
                .Aggregate(0, (h, v) => h ^ v.GetHashCode());
    }

}

* Each grouping of numbers is an instance of a Group object, and we test if two Groups are equal based on the items in each Group.

\$\endgroup\$
2
\$\begingroup\$

I wanted to keep this a simple as possible, not creating any extra method calls if I did not have too.

I wanted to traverse the list in desending order. I wanted to fit the larger items into the the lists first. Then fill in with the smaller values.

I am using Linq for the order by, but could just have easily used the sort option and traversed the list from the last index to the first. (still might do that).

  static public bool Partition(IList<int> numbers, out IList<int> group0, out IList<int> group1)
  {
    if (numbers == null)
    {
      throw new ArgumentException("numbers");
    }

    group0 = null;
    group1 = null;

    var totalSum = numbers.Sum();
    if (totalSum % 2 == 1)
    {
      return false;
    }

    var listSum = totalSum / 2;

    var sorted = numbers.OrderByDescending(i => i).ToList();

    var group0Sum = 0;
    var rejects = new Stack<int>();
    var holder = new Stack<int>();        
    var tries = 0;
    var index = 0;

    group0 = new List<int>();
    rejects.Push(int.MaxValue);

    while (sorted.Count > 0)
    {
      if (sorted[index] < rejects.Peek() && group0Sum + sorted[index] <= listSum)
      {
        group0Sum += sorted[index];
        holder.Push(sorted[index]);
        sorted.RemoveAt(index);
      }

      if(group0Sum == listSum)
      {
        group0 = new List<int>(holder);
        group1 = new List<int>(sorted);
        return true;
      }

      index++;

      if(index >= sorted.Count && sorted.Count > 0)
      {
        index = ++tries;

        if (index >= sorted.Count)
        {
          return false;
        }

        while (holder.Count > tries)
        {
          group0Sum -= holder.Peek();
          rejects.Push(holder.Peek());
          sorted.Insert(0, holder.Pop());
        }
      }          
    }

    return false;
  }
\$\endgroup\$
1
\$\begingroup\$

This is a revised solution. It is way faster than my original posting. I replace the BitArray by a bool[] which had a little performance boost (hinted by Jesse). Also, I used recursion with an early out algorithm.

static public bool Partition(int[] numbers, out int[] group0, out int[] group1)
{
    if (numbers == null)
        throw new ArgumentNullException("numbers");
    group0 = group1 = null;

    if (numbers.Length <= 1)
        return false;

    int totalSum = 0;
    for (int i = 0; i < numbers.Length; i++)
    {
        int n = numbers[i];
        if (n <= 0)
            throw new ArgumentException("Numbers is not allowed to contain values less than one.");
        totalSum += n;
    }
    if (totalSum % 2 != 0)
        return false;
    int desiredSum = totalSum / 2;

    bool[] groupPerNumber = new bool[numbers.Length];

    if (!AnalyzeCombination(numbers, groupPerNumber, 0, 0, desiredSum))
        return false;

    int groupSize0 = 0;
    for (int i = 0; i < groupPerNumber.Length; i++)
        if (!groupPerNumber[i])
            groupSize0++;
    group0 = new int[groupSize0];
    group1 = new int[numbers.Length - groupSize0];

    int groupIndex0 = 0;
    int groupIndex1 = 0;
    for (int i = 0; i < numbers.Length; i++)
        if (!groupPerNumber[i])
            group0[groupIndex0++] = numbers[i];
        else
            group1[groupIndex1++] = numbers[i];
    return true;
}

static public bool AnalyzeCombination(int[] numbers, bool[] groupPerNumber, int position, int runningSum, int desiredSum)
{
    if (position == numbers.Length)
        return false;

    int currentNumber = numbers[position];
    runningSum += currentNumber;
    if (runningSum < desiredSum)
    {
        groupPerNumber[position] = true;
        if (AnalyzeCombination(numbers, groupPerNumber, position + 1, runningSum, desiredSum))
            return true;
        runningSum -= currentNumber;
        groupPerNumber[position] = false;
    }
    else if (runningSum == desiredSum)
    {
        groupPerNumber[position] = true;
        return true;
    }
    if (AnalyzeCombination(numbers, groupPerNumber, position + 1, runningSum, desiredSum))
        return true;

    return false;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.