4
\$\begingroup\$

I have some code that I posted as a possible answer on StackOverflow (and the code I post here is almost an exact duplicate of that, but I'd rather include complete information in this post as well so people don't have to jump back and forth between posts to understand the question). I truthfully haven't quite decided whether it's terrible, really clever, or something in between (which is why I'm asking for reviews here).

I'm perfectly aware that the use of dynamic in C# is somewhat controversial. That aside, though, I'll freely admit that I rarely use it and am curious as to whether this is what would normally be considered a "valid" use of it.

Basically, the problem is to create and then "flatten" an arbitrarily-nested array. At any given index, the array could contain either an integer or another array of integers, so you could have something like this:

[ 1 2 3 4 5
  [6 7
      [8 9
         [10 11 12]
       13 14 15]
  16 17]
18 19 20]

The resulting "flattened" array would be 1, 2, 3, 4, 5, 6, 7...20.

I use the following code to create the array:

Random random = new Random();
        dynamic array = new dynamic[random.Next(3, 10)];
        for (int i = 0; i < array.Length; i++)
        {
            if (random.NextBool())
            {
                array[i] = new dynamic[random.Next(3, 10)];

                for (int j = 0; j < array[i].Length; j++)
                {
                    if (random.NextBool())
                    {
                        array[i][j] = random.Next(1, 100);
                    }
                    else
                    {
                        array[i][j] = new int[random.Next(3, 10)];

                        for (int k = 0; k < array[i][j].Length; k++)
                        {
                            array[i][j][k] = random.Next(1000);
                        }
                    }
                }
            }
            else
            {
                array[i] = random.Next(1, 100);
            }
        }

where NextBool is an extension method on the Random class:

public static bool NextBool(this Random random)
    {
        return random.Next(0, 1) == 0;
    }

Once I've created this, I can use recursion to "flatten" the list. Essentially, at any point I determine if this is a "base" case (it's just an integer) or if it's a (potentially arbitrarily-nested) array. If it's an array, I just loop over it, add the integers to the final result, and do a recursive call on any arrays I find.

private void Flatten(dynamic item, List<int> flattened)
{
    // This is the base case - the item's just an integer
    if (item.GetType() == typeof(int))
    {
        flattened.Add((int)item);
    }
    else
    {
        foreach (dynamic itm in item)
        {
            // Handle the case where the current item's an int
            if (itm.GetType() == typeof(int))
            {
                flattened.Add(itm);
            }
            // If it's not an int, it must be an array - recursively process it
            else
            {
                Flatten(itm, flattened);
            }
        }
    }
}

I could probably simply this a little by simply making everything arrays - i.e. instead of "plain" integers I have an array of length 1 - but I'm not sure that this is a dramatic improvement.

Anyone have opinions on whether this is a good solution or not? (I honestly won't be offended if people think it's a terrible idea, I'd rather have the honest feedback). Are there ways I could improve this or solve it in a better way?

Edit: I'm using arrays here (rather than some kind of a Tree structure, which I think would be preferable for data structured like this) because of constraints in the post I was responding to on SO.

\$\endgroup\$
  • 2
    \$\begingroup\$ Are you looking for critique on the Flatten method, the creation of the underlying structure, the idea of storing the data in that form, or what? \$\endgroup\$ – Servy Dec 8 '16 at 16:44
8
\$\begingroup\$

There's never any reason to use dynamic here at all. You never use any of its features. You could literally copy-paste all instances of it with object and the code would function identically.

Now, that's not a particularly good design for storing data like this. If you actually want to store a tree of data you're better off with a more traditional tree setup. Create a Node type, and let those nodes have both values and child nodes, which can themselves have child nodes, and so on. You can then traverse that tree structure. That makes it much clearer what's going on, rather than just seeing an object that you happen to just know is a tree structure where it contains either a sequence of other objects, or a value, and where each object in the sequence may itself be a sequence or a value. It also means that when you create operations that work with these trees they can accept instances of those types, so people don't do weird things like pass in a string to your method here, only to have it crash, instead of just failing to compile.

As for the actual Flatten method, personally I'd prefer a non-recursive implementation. Most significantly because the stack in C# just isn't that big, and it's not really all that uncommon to have tree structures that are deeper than the stack can support, resulting in you getting stack overflow exceptions. It's a little bit easier code to write the recursive version for many people, but you're constraining yourself to only working with shallow trees by using it.

I'd also suggest making the Flatten method an iterator block. There's no sense computing the entire value right from the start, when the underlying algorithm itself is inherently computing one value at the time. Using an iterator block lets the consumer use each value as you compute it, and removes the need for you to do the work of computing values that may not be needed, and also prevents the entire result set from needing to be in memory all at once, assuming the resulting values can be processed one at a time (a common enough situation).

\$\endgroup\$
  • \$\begingroup\$ Fair points. For what it's worth I did point out in my SO post that a tree structure would be preferable here, the main reason I used an array was that the OP there was working with a constrained problem so I'm definitely in agreement with you on that point too. \$\endgroup\$ – EJoshuaS Dec 8 '16 at 16:51
2
\$\begingroup\$

You have a bug in this method:

public static bool NextBool(this Random random)
{
    return random.Next(0, 1) == 0;
}

Random.Next uses an inclusive lower bound and an exclusive upper bound. That means your code will always return true. It should instead be:

public static bool NextBool(this Random random)
{
    return random.Next(0, 2) == 0;
}
\$\endgroup\$
1
\$\begingroup\$
if(item.GetType() == typeof(int))

You can simplify this by using the is operator

  if(item is int)

This might be slightly slower but the difference is merely noticable even with 100.000.000 iterations. If you have a three of this length/depth you'll run into StackOverflowException long before you notice how slow it is anyway.

\$\endgroup\$
  • \$\begingroup\$ Oh, and if T implements IEnumerable in your case...bad things will happen. \$\endgroup\$ – Servy Dec 9 '16 at 16:02

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.