12
\$\begingroup\$

The idea is to have a data structure that holds any number of objects of any type. Objects can be retrieved, or removed permanently, at random. Also, it can be cleared (or emptied).

This class just provides the ability to select a random object from a collection, with the option of removing it.

public class Sack
{
    private List<object> objects;

    public Sack()
    {
        objects = new List<object>();
    }

    public void Add<T>(T obj)
    {
        objects.Add(obj);
    }

    public object Retrieve()
    {
        int numberObjects = objects.Count;

        Random rand = new Random();
        int selectedIndex = rand.Next(0, numberObjects);

        return objects[selectedIndex];
    }

    public object Remove()
    {
        int numberObjects = objects.Count;

        Random rand = new Random();
        int selectedIndex = rand.Next(0, numberObjects);

        object selectedObject = objects[selectedIndex];
        objects.RemoveAt(selectedIndex);

        return selectedObject;
    }

    public void Empty()
    {
        objects.Clear();
    }
}
\$\endgroup\$
  • 7
    \$\begingroup\$ Welcome to Code Review. I didn't DV, but you also got a close vote "Needs details or clarity". In its current form your question lacks context about why you created this class (what do you want to do with it) and how should it be used. \$\endgroup\$ – Heslacher Dec 14 '19 at 11:23
  • \$\begingroup\$ Thank you. I will add some more detail to the question. \$\endgroup\$ – Al2110 Dec 14 '19 at 11:24
  • 7
    \$\begingroup\$ Just for future reference, the statement There are no concrete uses for this class. could make this question off-topic. We are looking for real code that does something and generally an explanation of what the code does. \$\endgroup\$ – pacmaninbw Dec 14 '19 at 12:51
  • 8
    \$\begingroup\$ @pacmaninbw really? Well, this code certainly does something, and he does describe what it does. It may not be the most useful structure in the world, but I'd say it's a nice exercise... \$\endgroup\$ – Quintec Dec 15 '19 at 16:56
  • 1
    \$\begingroup\$ @AnthonyGrist I'm not sure what your point is. The Retrieve() method doesn't remove the item from the sack. If you're trying to disagree with me, then you've mistakenly proven my point that the method names are poor by making the very mistake I described. \$\endgroup\$ – Bacon Bits Dec 16 '19 at 19:20
19
\$\begingroup\$
  • You don't use any method which is specific to List<T>. You should always code against interfaces if possible, meaning you should use IList<T> instead of List<T>.
  • If Retrieved is called very often in a short time it is likely that you get the same object each time. This is because Random when instantiated will use the system clock to provide a seed value. You should have one Random object as a class-level field which should be instantiated in the constructor or directly.
  • The genericness of the method Add<T> doesn't buy you anything. A simple Add(object) would be enough and does the exact same.
  • objects should be made readonly because you don't change it.
  • For Retrieve and Remove I wouldn't introduce the numberObjects variable but if you want to keep it you should rename it to e.g numberOfObjects.

Implementing the mentioned points would look like this:

public class Sack
{
    private readonly IList<object> objects = new List<object>();
    private readonly Random rand = new Random();

    public void Add(object obj)
    {
        objects.Add(obj);
    }

    public object Retrieve()
    {
        int selectedIndex = rand.Next(0, objects.Count);

        return objects[selectedIndex];
    }

    public object Remove()
    {
        int selectedIndex = rand.Next(0, objects.Count);

        object selectedObject = objects[selectedIndex];
        objects.RemoveAt(selectedIndex);

        return selectedObject;
    }

    public void Empty()
    {
        objects.Clear();
    }
}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ What if I want to provide the option of emptying the contents to a specific collection, rather than just clearing it? Provide an overload for Empty() so that the data structure can be passed into it? \$\endgroup\$ – Al2110 Dec 14 '19 at 12:14
  • \$\begingroup\$ I would use an overloaded method which takes a Type and then I would remove all objects of this Type. \$\endgroup\$ – Heslacher Dec 14 '19 at 12:30
  • \$\begingroup\$ It seems a Count property would be in order as well - most collections-esque tend to have it \$\endgroup\$ – corsiKa Dec 15 '19 at 5:49
  • 4
    \$\begingroup\$ If objects is private, readonly and cannot be injected into Sack, there's no benefit to be had by coding against IList<T> rather than List<T>. \$\endgroup\$ – Rob Dec 16 '19 at 0:44
  • \$\begingroup\$ Worth noting that the comment about instances of Random created close together using the same seed only applies to .Net Framework. .Net Core uses a dedicated RNG instance to seed each new Random() instance, so the seed will be different. Source Code, Stack Overflow Question \$\endgroup\$ – Zac Faragher Dec 16 '19 at 1:22
7
\$\begingroup\$

Testing your code

To make your code testable, you should allow the code that uses this Sack to supply a custom random number generator.

In your unit test for the Sack class, you should create a custom TestingRandom class that derives from Random and overrides the Next(int, int) method. In your TestingRandom class you should ensure that the amount of requested randomness is exactly what you expect.

Given a set of 5 things, when you take them all out of the Sack, your random number generator must have generated randomness 5 * 4 * 3 * 2 * 1. Not more, not less. This ensures that the distribution of objects returned by the Sack can be fair. It doesn't guarantee that, but it detects mistakes quickly.

Performance

Do you use this class to manage millions of objects? Because if you do, the RemoveAt call will make it very slow as that method needs to copy half of the array on average.

To improve performance, you can change the code so that it always removes the element at the end:

var index = RandomIndex();
var obj = objects[index];
objects[index] = objects[objects.Count - 1];
objects.RemoveAt(objects.Count - 1);
return obj;
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

I would go and encourage you to use Generics instead of object. When you use object you're adding a casting operations in the back-scene, which means you might have a chance of getting casting exceptions at run-time. So, using generics would avoid that, and it would perform faster.

Also, in your code, you're using List, which is fine, but why you don't benefit from the existed interfaces such as ICollection, IList ..etc. These would give you many advantages, for instance, use ICollection such as Sack<T> : ICollection<T> you'll be able to use foreach loop (because it implements IEnumerable interfaces). So, make use of .NET existing interfaces, and don't take the long road.

Also, You can create an interface say ISack<T> : ICollection<T> add the additional methods that you want, then do Sack<T> : ISack<T>

for your random index, you can declare the Random and SelectedIndex at the class level, and then create a method that returns a random index.

example :

public class Sack<T>
{

    private readonly IList<T> objects = new List<T>();

    private readonly Random rand = new Random();

    private int SelectedIndex = -1;


    public T Retrieve()
    {
        RandomIndex();
        return objects[SelectedIndex];
    }

    public T Remove()
    {
        RandomIndex();
        var removedObject = objects[SelectedIndex];
        objects.Remove(removedObject);
        return removedObject;

    }

    private void RandomIndex()
    {
        // keep creating a new random index until you get a non-null object. 
        // [ToDo] : what if object.Count == 0 ? how should you handle it ? 
        while (true)
        {
            if ((SelectedIndex == -1 || objects[SelectedIndex] == null))
            {
                SelectedIndex = rand.Next(0, objects.Count);
            }
            else
            {
                break;
            }
        }
    }

}

I have added ICollection<T> to the class, which would give you more options and customization

 public class Sack<T> : ICollection<T>
    {
        private readonly IList<T> objects = new List<T>();

        private readonly Random rand = new Random();

        private int SelectedIndex = -1;

        public T this[int index]
        {
            get => this[index];
            set => this[index] = value;

        }
        public int Count => objects.Count;

        public bool IsReadOnly => objects.IsReadOnly;

        public void Add(T item)
        {
            objects.Add(item);
        }

        public void Clear() => objects.Clear();

        public bool Contains(T item) => objects.Contains(item);

        public void CopyTo(T[] array, int index) => objects.CopyTo(array, index);

        public IEnumerator<T> GetEnumerator() => objects.GetEnumerator();

        public int IndexOf(T item) => objects.IndexOf(item);

        public void Insert(int index, T item) => objects.Insert(index, item);

        public bool Remove(T item) => objects.Remove(item);

        public void RemoveAt(int index) => objects.RemoveAt(index);

        IEnumerator IEnumerable.GetEnumerator() => objects.GetEnumerator();

        public T Retrieve()
        {
            RandomIndex();
            return objects[SelectedIndex];
        }

        public T Remove()
        {
            RandomIndex();
            var removedObject = objects[SelectedIndex];
            objects.Remove(removedObject);
            return removedObject;

        }

        private void RandomIndex()
        {
            while (true)
            {
                if ((SelectedIndex == -1 || objects[SelectedIndex] == null))
                {
                    SelectedIndex = rand.Next(0, objects.Count);
                }
                else
                {
                    break;
                }

            }

        }

    }
}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Since the objects in the sack are unordered, it doesn't make sense to implement IndexOf for it. Making the sack an IEnumerable sounds fine to me, but ICollection is simply wrong. \$\endgroup\$ – Roland Illig Dec 15 '19 at 9:59
  • \$\begingroup\$ @RolandIllig, as long as OP is using objects.Add(item) as is, it's sorted Collection, so I thought the OP only needs to (Retrieve and Remove) at random index. If OP really needs to put the objects in unordered indexes, then HashTable would be more appropriate on that matter. \$\endgroup\$ – iSR5 Dec 15 '19 at 11:44
  • \$\begingroup\$ The "sorted Collection" is only an implementation detail, and the important point is not that it is ordered but that it allows fast access by index. Exactly for this reason, HashTable would not make sense. \$\endgroup\$ – Roland Illig Dec 15 '19 at 12:00
  • \$\begingroup\$ @RolandIllig maybe I was't clear enough, if I just did objects.Add(..) then do objects[object.Count] I'll get the last inserted element. meaning, It's still sorted list, I should do some resorting or shuffle the elements inside the list to a different order so when I do objects.Add(..) then objects[object.Count] I should get a total different element than the one I just added. \$\endgroup\$ – iSR5 Dec 15 '19 at 14:43
  • \$\begingroup\$ @iSR5 I wouldn't shuffle the list internally just because the collection isn't ordered. If the collection isn't ordered, it just doesn't make sense to index it, so don't provide that functionality. Also note that objects[object.Count] will throw an ArgumentOutOfRangeException. \$\endgroup\$ – JAD Dec 16 '19 at 7:47
1
\$\begingroup\$

Since the Retrieve and the Remove methods share much of the same code, and since Remove also retrieves, I would suggest merging the 2. Adding a default argument and a conditional, to the Retrieve method, would do the trick:

public object Retrieve(bool remove = false)
{
    int selectedIndex = rand.Next(0, objects.Count);
    object selectedObject = objects[selectedIndex];
    if(remove)
    {
        objects.RemoveAt(selectedIndex);
    {
    return selectedObject;
}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ While I agree that removing redundancy is a good thing, this is not the way, I would choose. Having one method behaving two very different operations based on a bool parameters, makes the API very unintuitive to use. \$\endgroup\$ – Tim Pohlmann Dec 16 '19 at 14:34
1
\$\begingroup\$

I'd inherit from List to avoid proxying functions like Clear() with no value-add, or write an extension method over List for the randomized retrieval.

public static class RandomRemover
{
    private static readonly Random rand = new Random();

    public static object Retrieve(this List<object> target)
    {
        int selectedIndex = rand.Next(0, target.Count);
        return target[selectedIndex];
    }
}

cf. open/closed principle

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Retrieve and Remove both share this piece of code:

int numberObjects = objects.Count;

Random rand = new Random();
int selectedIndex = rand.Next(0, numberObjects);

I would recommend refactoring it into a private helper:

int GetRandomIndex()
{
    int numberObjects = objects.Count;

    Random rand = new Random();
    int selectedIndex = rand.Next(0, numberObjects);
}

And then just call it like this:

public object Retrieve()
{
    int selectedIndex = GetRandomIndex();

    return objects[selectedIndex];
}
|improve this answer|||||
\$\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.