7
\$\begingroup\$

Let's say we need to create a store for selling prime numbers.

Users enter the store and ask to buy a number.

  1. If the number asked is a prime number,

    1.1. then it's either available for sale

    1.2. or was purchased earlier, hence not available for sale.

  2. If the number asked is not a prime number, then it doesn't exist.

Let us assume that the store contains the maximum possible number of primes that could be represented by a primitive type (in my implementation I assume the largest prime number isn't larger than Int32's MaxValue, and to actually run this in a reasonable time, I set a MAX_VALUE constant to 100000).

  • The store must handle concurrent calls.

  • Buying should be fast as possible!

  • When the store opens for business, it should already contain the numbers for sale.

  • Users cannot be blocked by shopping for numbers, nor by other buyers.

  • Example: UserA asks to purchase a number and then UserB arrives and asks to purchase a number, then UserB won't need to wait until the system's dealt with UserA's transaction. So when UserA's transaction finishes, a response will be delivered to UserA, then UserB's transaction will start and once finished a response will be delivered to UserB.


My Solution:

I define an enum called NumberType, that basically describes whats the buying state of each number.

According to the problem definition, every number could be either prime, then it may be available for sale or not available (because it was bought before), or the number isn't prime, so it doesn't exist.

NumberTypes.cs

namespace PrimeStore
{
    public enum NumberType
    {
        SoldSuccessfully,
        NotAvailable,
        NotExist
    }
}

Next, I define a Singleton class named Store, that is lazy-initiated on first-access to at most MAX_VALUE number of prime numbers in a Dictionary of {Int32, Boolean} pairs, initiating all the Boolean's to false since nothing was bought yet.

To calculate all those prime numbers on initialization, I use a very known algorithm AKA Sieve of Eratosthenes in parallel, because it takes very long to calculate.

This method was taken from the .NET 4.0 examples article.

Then the public method that is exposed outside is:

public void BuyNumber(Int32 number, Action {NumberType} callback)

The user may choose whatever number and supplies a callback method that takes a NumberType as a parameter and decides what to do whether the number was successfully bought, wasn't available or doesn't exist.

To verify that the number is prime (in the boundaries between 2..MAX_VALUE as defined in the source code) a simple ContainsKey check on the dictionary is enough.

But if the number does exist (it is prime) then a lock must be gained in order to exclusively buy the number by one user.

In each case, the user's callback is called with the right choice from the enum.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PrimeStore
{
    public sealed class Store
    {
        public const Int32 MAX_VALUE = 100000 - 2;
        private static Store _instance;
        private static object syncRoot = new Object();

        private readonly Dictionary<Int32, Boolean> _primes;

        private Store()
        {
            _primes = new Dictionary<int, bool>();

            IEnumerable<int> numbers = Enumerable.Range(2, MAX_VALUE);

            var parallelQuery =
              from n in numbers.AsParallel()
              where Enumerable.Range(2, (int)Math.Sqrt(n)).All(i => n % i > 0)
              select n;

            foreach (var number in parallelQuery)
            {
                _primes.Add(number, false);
            }
        }

        public static Store Instance
        {
            get
            {
                if (_instance == null)
                {
                    lock (syncRoot)
                    {
                        if (_instance == null)
                            _instance = new Store();
                    }
                }

                return _instance;
            }
        }

        public void BuyNumber(Int32 number, Action<NumberType> callback)
        {
            // no lock is needed here since just checking if a number is prime
            // and its a readonly operation.
            if (!_primes.ContainsKey(number))
            {
                callback(NumberType.NotExist);
            }
            else
            {
                BuyPrime(number, callback);
            }
        }

        private void BuyPrime(Int32 number, Action<NumberType> callback)
        {
            Boolean bought = false;

            // the number is prime, then obtain exclusive access
            // to the dictionary and try to buy it.
            lock (_primes)
            {
                if (_primes[number] == false)
                {
                    _primes[number] = true;
                    bought = true;
                }
            }

            if (bought)
            {
                callback(NumberType.SoldSuccessfully);
            }
            else
            {
                callback(NumberType.NotAvailable);
            }
        }
    }
}

Here's a simple program that makes concurrent buys (in parallel) of many numbers between 0..MAX_VALUE, then repeats itself for a few times in order to re-buy numbers who were already bought (that's the purpose of the outer for loop).

The callback simply writes the result of each case to the Console.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace PrimeStore
{
    public class Program
    {
        public static void Main(string[] args)
        {
            for (int i = 0; i < 3; i++)
            {
                Parallel.For(0, Store.MAX_VALUE, (number) =>
                    {
                        Store.Instance.BuyNumber(number, (numberType) =>
                            {
                                switch (numberType)
                                {
                                    case NumberType.NotAvailable:
                                        Console.WriteLine("{0} is not available for sale.", number);
                                        break;
                                    case NumberType.NotExist:
                                        Console.WriteLine("{0} is not a prime number.", number);
                                        break;
                                    case NumberType.SoldSuccessfully:
                                        Console.WriteLine("Successfully bought {0}.", number);
                                        break;
                                }
                            });
                    });
            }
        }
    }
}

Can anyone think of a better way to store the numbers, assuming that all prime numbers must already be stored when opening the store (in my implementation - on the first call to Store's BuyNumber) without causing transactions a run-time worse than \$O(1)\$?

What if we'd tried to increase MAX_VALUE to almost Int32.MaxValue?

What do you think will happen first, an OutOfMemoryException or 3 hours of waiting?

\$\endgroup\$
  • 1
    \$\begingroup\$ It's nice to see thoughtful questions. Thanks! \$\endgroup\$ – Quentin Pradet May 17 '13 at 6:53
  • \$\begingroup\$ Rolled back Rev 5 → 3. Please post a new question instead of continually revising the code. \$\endgroup\$ – 200_success May 21 '14 at 9:13
5
\$\begingroup\$
foreach (var number in parallelQuery)
{
    _primes.Add(number, false);
}

You could simplify this to:

_primes = parallelQuery.ToDictionary(n => n, n => false);

public void BuyNumber(Int32 number, Action<NumberType> callback)

I don't understand why are you using a callback here. The whole method is completely synchronous, so I think you should simply return the result from it.


// no lock is needed here since just checking if a number is prime
// and its a readonly operation.
if (!_primes.ContainsKey(number))

Read-only operation doesn't mean that you don't need a lock. The documentation for Dictionary says:

A Dictionary<TKey, TValue> can support multiple readers concurrently, as long as the collection is not modified.

The problem is, there could be a write occurring from another thread, so according to the documentation, you should use locking in this case (possibly using ReaderWriterLockSlim which allows multiple readers at the same time).

\$\endgroup\$
  • \$\begingroup\$ That documentation is inconclusive. I think that it refers to adding/removing, rather then changing the Boolean value, which is the only operation this method could do. Keeping in mind that its declared readonly (only initialized once, in the constructor). So since ALL of the primes are already inside the dictionary, and will not be removed and no more primes will be added, it is fine not to use a lock for reading purposes. \$\endgroup\$ – rycle May 17 '13 at 1:06
  • \$\begingroup\$ @rycle I really don't think the documentation is inconclusive. Setting the value for some key is modification. It's certainly possible that for a certain implementation of Dictionary, your code is actually thread-safe. But I don't think it's a good idea to rely on undocumented implementation details. \$\endgroup\$ – svick May 17 '13 at 1:18
  • 2
    \$\begingroup\$ @rycle That method is synchronous. If you think it isn't, then you don't know what “synchronous” means. Yes, it can wait on the lock, but it waits on it synchronously. Callbacks are useful for methods that are actually asynchronous, that is, return before their work is actually complete. But that's not the case with your code. If you changed the method to return its result, it would behave exactly the same. \$\endgroup\$ – svick May 17 '13 at 1:21
  • \$\begingroup\$ Yes, you were right! thanks SVICK (: Good work@ I've now edited and made it an asynchronous call. \$\endgroup\$ – rycle May 17 '13 at 1:47
  • \$\begingroup\$ About undocumented implementation details, I don't know if its documented or not (it seems not in the documentation on MSDN, the one you gave link to), But I simply think its obvious that a readonly dictionary's keys will forever stay the same, so you don't have to obtain a lock to just check if a key exist. \$\endgroup\$ – rycle May 17 '13 at 1:52

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.