6
\$\begingroup\$

Profiling shows MoveNext takes most time, which I guess is true as it is lazy. But I don't know in what direction I could improve the code. (Open pic in new tab would allow u see bigger chart.)

enter image description here

    IEnumerable<string> MixedBlock(List<string> reelLayout, string thisBlock, int length)
    {
        List<string> recentBlock = RecentBlock(length - 1, reelLayout);
        var upper = Enumerable.Range(1, length - 1);
        var lower = Enumerable.Range(1, totalWeight[thisBlock].Num);
        var query = from x in upper
                    from y in lower
                    where x + y == length
                    select Tuple.Create(x, y);
        foreach (var t in query)
        {
            string upperBlock = string.Join(",", recentBlock.Skip(length - 1 - t.Item1));
            string lowerBlock = string.Join(",", thisBlock.Split(',').Take(t.Item2));
            yield return upperBlock + "," + lowerBlock;
        }

    }
\$\endgroup\$
3
  • \$\begingroup\$ and who knows how does the 50.54-20.32=30.2% come from? weird \$\endgroup\$
    – colinfang
    Aug 25 '11 at 20:57
  • \$\begingroup\$ What is RecentBlock()? What is totalWeight? \$\endgroup\$ Aug 26 '11 at 1:44
  • 1
    \$\begingroup\$ @colinfang 50.5 - 20.3 = 30.2 somewhere there is rounding going on \$\endgroup\$
    – Malachi
    Nov 27 '13 at 16:49
4
\$\begingroup\$

You're doing way more iterations than are necessary.. you don't need 2 enumerables of ints just to do this, that's a lot more heap references when all your need are 2 integers right on the stack, and a nested for loop:

int upperLimit = length - 1;
int lowerLimit = totalWeight[thisBlock].Num;
List<string> recentBlock = RecentBlock(length - 1, reelLayout);
List<string> stringResults = new List<string>();

for(int upper = 1; upper < upperLimit; upper++)
{
  for(int lower = 1; lower < lowerLimit; lower++)
  {
    if (upper + lower = length)
    {
      stringResults.Add(
        string.Join(",", recentBlock.Skip(length - 1 - upper)) + "," +
        string.Join(",", splits.Take(lower)));
    }
  }
}

return stringResults;

also instead of doing the stringResults.Add you could just yield return the string right there if you wanted to allow delayed execution.

Remember, just because we now have tuples and all the happy linqiness, they can be used to simplify complex things, though sometimes they just make operations more complex. If performance is important, study up on what goes on underneath the linq before throwing it around too much.

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

I believe there is the the problem with MoveNext() from enumerator which is returned from MixedBlock(). Its MoveNext() just does a lot of lazy processing but doesn't cache results at all.

(1). When you iterare over the result from the MixedBlock() your iterate with help of the auto generated class that implements IEnumerable<T> and IEnumerator<T>. Its MoveNext() is a heavy function because it has to create all of the anononymouse functions in your code, maintain state and delegate calls to enumerator from SelectMany(). You can avoid this by removing this yield keyword.

(2). Removing yield keyword will also allow complier not to generate instances of helper functions but use only extenssion methods. Now it can look like this

            if (MyClass.CS$<>9__CachedAnonymousMethodDelegate5 == null)
            {
                MyClass.CS$<>9__CachedAnonymousMethodDelegate5 = new Func<int, int, <>f__AnonymousType0<int, int>>(MyClass.<MixedBlock>b__2);
            }
            if (MyClass.CS$<>9__CachedAnonymousMethodDelegate6 == null)
            {
                MyClass.CS$<>9__CachedAnonymousMethodDelegate6 = new Func<<>f__AnonymousType0<int, int>, bool>(MyClass.<MixedBlock>b__3);
            }
            if (MyClass.CS$<>9__CachedAnonymousMethodDelegate7 == null)
            {
                MyClass.CS$<>9__CachedAnonymousMethodDelegate7 = new Func<<>f__AnonymousType0<int, int>, int>(MyClass.<MixedBlock>b__4);
            }

(3). Before entering foreach over query I'd recommend to cache results of the preceding projection.

var query = from x in upper
                from y in lower
                where x + y == length
                select Tuple.Create(x, y).ToList();

(4). This statement can be computed only once when you enter the function. However you do the same work on every iteration.

  thisBlock.Split(',')

All in one you can have something like this.

IEnumerable<string> MixedBlock(List<string> reelLayout, string thisBlock, int length)
{
    List<string> result = new List<string>();

    string[] splits = thisBlock.Split(',');   
    List<string> recentBlock = RecentBlock(length - 1, reelLayout);
    var upper = Enumerable.Range(1, length - 1);
    var lower = Enumerable.Range(1, totalWeight[thisBlock].Num);
    var query = from x in upper
                from y in lower
                where x + y == length
                select Tuple.Create(x, y).ToList();
    foreach (var t in query)
    {
        string upperBlock = string.Join(",", recentBlock.Skip(length - 1 - t.Item1));
        string lowerBlock = string.Join(",", splits.Take(t.Item2));
        results.Add(upperBlock + "," + lowerBlock);
    }

    return (results);
}

I've tried both approaches on the code with the similar structure an in my case it seems to be 20% faster.

\$\endgroup\$
2
  • \$\begingroup\$ +1: great explanations ...#3 was the first issue I spotted. If you are going to query and then immediately use the results in a foreach, you should transform to list. \$\endgroup\$
    – IAbstract
    Aug 26 '11 at 14:48
  • \$\begingroup\$ Wait, why? That forces two iterations whereas foreach'ing the query straight to a yield return only incurs one. \$\endgroup\$ Sep 14 '11 at 13:38
1
\$\begingroup\$

I think you're doing a second loop that you don't need mathematically.

where x + y == length

So therefore

x = length - y

Since length is fixed and y is the variable. x seems to be calculated simply to satisfy the where, and can therefore be removed as an iterator and simply calculated.

Also the upper loop only went as far as length-1, so if totalWeight[thisBlock].Num is bigger, we use that instead.

var lower = Enumerable.Range(1, Math.Min(totalWeight[thisBlock].Num, length-1));
var query = from y in lower
            select Tuple.Create(length - y, y);

Doing this also collapses the LINQ query, which in turn allows us to remove the Tuple. Instead we can just subsitute (length - y) wherever we need the original x.

var lower = Enumerable.Range(1, Math.Min(totalWeight[thisBlock].Num, length-1));
foreach (var t in lower)
{
    string upperBlock = string.Join(",", recentBlock.Skip(length - 1 - (length-y)));
    string lowerBlock = string.Join(",", thisBlock.Split(',').Take(y));
    yield return upperBlock + "," + lowerBlock;
}

Turn the Enumerable.Range/Foreach into a for loop.
Also length - 1 - (length-y) becomes y - 1

for (int y = 1; y <= Math.Min(totalWeight[thisBlock].Num, length-1); y++)
{
    string upperBlock = string.Join(",", recentBlock.Skip(y - 1));
    string lowerBlock = string.Join(",", thisBlock.Split(',').Take(y));
    yield return upperBlock + "," + lowerBlock;
}

Optimize out the splitting of thisBlock just so it's not done in a loop.

Also combine the string join into 1 function using concat.

So you end up with...

IEnumerable<string> MixedBlock(List<string> reelLayout, string thisBlock, int length)
{
    List<string> recentBlock = RecentBlock(length - 1, reelLayout);
    var thisSplitBlock = thisBlock.Split(',');
    for (int y = 1; y <= Math.Min(totalWeight[thisBlock].Num, length-1); y++)
    {
        yield return string.Join(",", 
            recentBlock.Skip(y - 1)
            .Concat(thisSplitBlock.Take(y));
    }
}

Note: This will output items in the reverse order from the original. If the order is important simply reverse the for loop.

for (int y = Math.Min(totalWeight[thisBlock].Num, length-1); y >= 1; y--)
\$\endgroup\$

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