1
\$\begingroup\$

can you give me your impression of my implementation of Pascal triangle problem? I'm especially interested in space complexity evaluation thank you all!

public List<List<int>> generate(int A)
{
    List<List<int>> result = new List<List<int>>();

    int currenctRowLength = 1;
    List<int> previousRow = new List<int>();
    for (int i = 0; i < A; i++)
    {
        List<int> row = new List<int>();
        row.Add(1);
        currenctRowLength = i + 1;
        int j = 1;
        while (j < currenctRowLength - 1)
        {
            row.Add(previousRow[j] + previousRow[j - 1]);
            j++;
        }

        if (i > 0)
        {
            row.Add(1);
        }            

        previousRow=row;
        result.Add(row);
    }
    return result;
}
\$\endgroup\$
  • \$\begingroup\$ (Welcome to CR!) space complexity reads asymptotic analysis to me: what operations are to be supported with what constraints satisfied? My take: don't fret about ("per item") storage required(yet): if it takes more space than you are willing to pay, it will be taxing your patience in the first place. \$\endgroup\$ – greybeard Jan 28 '18 at 11:24
  • \$\begingroup\$ (my implementation of [a] problem reads funny.) \$\endgroup\$ – greybeard Jan 28 '18 at 11:24
  • \$\begingroup\$ I was wondering if there is a better solution, I guess there is. \$\endgroup\$ – Luke Jan 28 '18 at 14:23
  • 1
    \$\begingroup\$ You didn't edit into your code/question what interface the result is to support - IList<IList<ulong>>pascalTriangle() would open up a lot of possibilities List<List<int>>(int) obstructs. (Note: it wouldn't even need a numberOfRows parameter (what the hell is A?)) \$\endgroup\$ – greybeard Jan 28 '18 at 15:11
  • \$\begingroup\$ I agree but in this case the return type was fixed \$\endgroup\$ – Luke Feb 20 '18 at 17:16
2
\$\begingroup\$

As I think greybeard was trying to say, unless you are know that memory consumption/allocation costs are a serious concern, then this code is fine from a memory point of view. The space-complexity is the same as the output (quadratic in A), so you can't do better than that.

There a couple of small things to be said:

  • as GreyBeard says, A is completely meaningless, and should really have a lowerCamelCase name as a parameter (e.g. dimension, size?); generate ought to be GeneratePascalTriangle or something meaningful (public -> UpperCamelCase) (msdn reference)

  • currenctRowLength should be currentRowLength, and should only be defined inside the for loop (i.e. where it is assigned); I like that this is its own variable.

  • you are using a while loop over j, when a for could be more readable (simply because people are used to reading for-loops), and doesn't leak j into the outer scope.

  • List<List<int>> is a pretty horrid type to be returning: much better to have IReadOnlyList<IReadOnlyList<T>> if the return value is meant to be immutable (which is assignable from List<List<T>> or T[][]).

  • I'd be inclined to initialise previousRow to null, rather than an empty list: it isn't read until i == 2; assigning it to a 'meaningful' value is defensive and only can work to obscure bugs in the rest of the code.

Mindless Performance Musing

If memory usage/allocations/GC hammering is a real concern, then you can improve matters by not using resizing lists. You havn't given us any idea of what the code is actually meant to do, so it's a bit hard to suggest an alternative, but you could either use arrays (which obvious are non-dynamic) or you can preserve the signature by creating lists with a given initial capacity with the .ctor(int) overload. Note that this will give a performance benefit, but change the time-complexity (which is also quadratic in A).

Code

Putting all of that together (and using arrays instead of lists, because mindless performance is fun, and I don't think it harms the readability here much):

/// <summary>
/// Generates a pascal triangle with the given number of rows
/// </summary>
public static IReadOnlyList<IReadOnlyList<int>> GeneratePascalTriangle(int numberOfRows)
{
    int[][] result = new int[numberOfRows][];

    int[] previousRow = null;
    for (int i = 0; i < numberOfRows; i++)
    {
        int currentRowLength = i + 1;

        int[] row = new int[currentRowLength];
        result[i] = row;

        // start and end
        row[0] = 1;
        row[currentRowLength - 1] = 1;

        // middle
        for (int j = 1; j < currentRowLength - 1; j++)
        {
            row[j] = previousRow[j] + previousRow[j - 1];
        }            

        previousRow = row;
    }

    return result;
}
\$\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.