count sort

http://en.wikipedia.org/wiki/Counting_sort

In summary, the algorithm loops over the items, computing a histogram of the number of times each key occurs within the input collection. It then performs a prefix sum computation (a second loop, over the range of possible keys) to determine, for each key, the starting position in the output array of the items having that key. Finally, it loops over the items again, moving each item into its sorted position in the output array.[1][2][3]

In pseudocode, this may be expressed as follows:

''' calculate histogram: '''
# k is the right end of keys' range 
# allocate an array Count[0..k] ; THEN
# initialize each array cell to zero ; THEN
for each input item x:
    increment Count[key(x)]

''' calculate starting index for each key: '''
total = 0
for i = 0, 1, ... k:
    oldCount = Count[i]
    Count[i] = total
    total = total + oldCount

''' copy inputs into output array in order: '''
# allocate an output array Output[0..n-1] ; THEN
for each input item x:
    Output[Count[key(x)]] = x
    increment Count[key(x)]
return Output

After the first for loop, Count[i] stores the number of items with key equal to i. After the second for loop, it instead stores the number of items with key less than i, which is the same as the first index at which an item with key i should be stored in the output array. Throughout the third loop, Count[i] always stores the next position in the output array into which an item with key i should be stored, so each item is moved into its correct position in the output array.[1][2][3] The relative order of items with equal keys is preserved here; i.e., this is a stable sort.

Analysis

Because the algorithm uses only simple for loops, without recursion or subroutine calls, it is straightforward to analyze. The initialization of the Count array, and the second for loop which performs a prefix sum on the count array, each iterate at most k + 1 times and therefore take O(k) time. The other two for loops, and the initialization of the output array, each take O(n) time. Therefore the time for the whole algorithm is the sum of the times for these steps, O(n + k).[1][2]

Because it uses arrays of length k + 1 and n, the total space usage of the algorithm is also O(n + k).[1] For problem instances in which the maximum key value is significantly smaller than the number of items, counting sort can be highly space-efficient, as the only storage it uses other than its input and output arrays is the Count array which uses space O(k).[5]

Advertisements

Dutch national flag problem

http://en.wikipedia.org/wiki/Dutch_national_flag_problem

void threeWayPartition(int data[], int size, int low, int high) {
  int p = -1;
  int q = size;
  for (int i = 0; i < q;) {
    if (data[i] == low) {
      swap(data[i], data[++p]);
      ++i;
    } else if (data[i] >= high) {
      swap(data[i], data[--q]);
    } else {
      ++i;
    }
  }
}

test randomness

  1. http://en.wikipedia.org/wiki/Statistical_randomness
  • The frequency test, was very basic: checking to make sure that there were roughly the same number of 0s, 1s, 2s, 3s, etc.
  • The serial test, did the same thing but for sequences of two digits at a time (00, 01, 02, etc.), comparing their observed frequencies with their hypothetical predictions were they equally distributed.
  • The poker test, tested for certain sequences of five numbers at a time (aaaaa, aaaab, aaabb, etc.) based on hands in the game poker.
  • The gap test, looked at the distances between zeroes (00 would be a distance of 0, 030 would be a distance of 1, 02250 would be a distance of 3, etc.).
  • chi-square test,

https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test

https://en.wikipedia.org/wiki/Chi-squared_distribution

If a given sequence was able to pass all of these tests within a given degree of significance (generally 5%), then it was judged to be, in their words “locally random”.

  1. http://www.drdobbs.com/testing-random-number-generators/184403185

observer pattern

A very good article:

http://www.dofactory.com/Patterns/PatternObserver.aspx#_self2

Hide code

// Observer pattern — Structural example

using System;

using System.Collections.Generic;

 

namespace DoFactory.GangOfFour.Observer.Structural

{

/// <summary>

/// MainApp startup class for Structural

/// Observer Design Pattern.

/// </summary>

class MainApp

{

/// <summary>

/// Entry point into console application.

/// </summary>

static void Main()

{

// Configure Observer pattern

ConcreteSubject s = new ConcreteSubject();

 

s.Attach(new ConcreteObserver(s, “X”));

s.Attach(new ConcreteObserver(s, “Y”));

s.Attach(new ConcreteObserver(s, “Z”));

 

// Change subject and notify observers

s.SubjectState = “ABC”;

s.Notify();

 

// Wait for user

Console.ReadKey();

}

}

 

/// <summary>

/// The ‘Subject’ abstract class

/// </summary>

abstract class Subject

{

private List<Observer> _observers = new List<Observer>();

 

public void Attach(Observer observer)

{

_observers.Add(observer);

}

 

public void Detach(Observer observer)

{

_observers.Remove(observer);

}

 

public void Notify()

{

foreach (Observer o in _observers)

{

o.Update();

}

}

}

 

/// <summary>

/// The ‘ConcreteSubject’ class

/// </summary>

class ConcreteSubject : Subject

{

private string _subjectState;

 

// Gets or sets subject state

public string SubjectState

{

get { return _subjectState; }

set { _subjectState = value; }

}

}

 

/// <summary>

/// The ‘Observer’ abstract class

/// </summary>

abstract class Observer

{

public abstract void Update();

}

 

/// <summary>

/// The ‘ConcreteObserver’ class

/// </summary>

class ConcreteObserver : Observer

{

private string _name;

private string _observerState;

private ConcreteSubject _subject;

 

// Constructor

public ConcreteObserver(

ConcreteSubject subject, string name)

{

this._subject = subject;

this._name = name;

}

 

public override void Update()

{

_observerState = _subject.SubjectState;

Console.WriteLine(“Observer {0}’s new state is {1}”,

_name, _observerState);

}

 

// Gets or sets subject

public ConcreteSubject Subject

{

get { return _subject; }

set { _subject = value; }

}

}

}

write/read thread safe

http://www.artima.com/designtechniques/threadsafetyP.html (just FMI)

requirement:

1) when read, does not allow any write, but allow other read

2) when write, no read, no other write

int ReadCounter = 0; 
   get
        {
            slimLock.EnterReadLock();  // used to lock the operation on changing Readcounter (see comments)
            if (ReadCounter++ == 0) //when there is read, don't allow write
               { slimLock.EnterWriteLock(); }
            var returnValue = notSafeField;
            slimLock.ExitReadLock();  // need to keep it; because it locks only the part of increasing ReadCounter, 
                                     // the part of read or return value is not locked so other read can concurrency
                                     // should I move this one line above?

            if (--ReadCounter == 0)
                { slimLock.ExitWriteLock(); }

            return returnValue;
        }
 set
        {
            slimLock.EnterWriteLock();
            notSafeField = value;
            slimLock.ExitWriteLock();
        }

I delete the readLock in the get method to allow other read threads, is that correct?
I don't understand why it is there. 

singleton and thread safe for load balancer

http://www.codeproject.com/Articles/37976/Writing-Thread-Safe-Code-in-C

Using the code

ServerLoadBalancerEngine implements the Singleton pattern and here we need to ensure that multiple thread calls to GetServerLoadBalancerEngine should be synchronized.

The static object syncLock is used to implement a critical section in the GetServerLoadBalancerEngine function.

To synchronise static methods, we need to lock the private static object variable. Locking GetServerLoadBalancerEngine ensures that only one thread can operate on this method, so only one instance will be created of the ServerLoadBalancerEngine class.

Collapse | Copy Code
sealed class ServerLoadBalancerEngine
{
    private static ServerLoadBalancerEngine _instance;
    private List<Server> _servers;
    private Random _random = new Random();

    // syncLock object, used to lock the code block
    private static object syncLock = new object();

    // constructor is 'private'
    private ServerLoadBalancerEngine()
    {

        // Load list of available servers
        _servers = new List<Server>
        {
            new Server{ Name = "Server1", IPAddress = "120.14.220.18" },
            new Server{ Name = "Server2", IPAddress = "120.14.220.19" },
            new Server{ Name = "Server3", IPAddress = "120.14.220.20" },
            new Server{ Name = "Server4", IPAddress = "120.14.220.21" }, 
        };
    }

    public static ServerLoadBalancerEngine GetServerLoadBalancerEngine()
    {
        if (_instance == null)
        {
            //To ensure thread safety
            lock (syncLock)
            {
                if (_instance == null)
                {
                    _instance = new ServerLoadBalancerEngine();
                }
            }
        }
        return _instance;
    }

    // Simple, but effective load balancer
    public Server NextServer
    {
        get
        {
            int r = _random.Next(_servers.Count);
            return _servers[r];
        }
    }
}