Prime Numbers Store

Question

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?

Answer 1

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).