Showing posts with label computer science. Show all posts
Showing posts with label computer science. Show all posts

Friday, May 22, 2009

~socket(); // death of socket programming?

~socket(); // death of socket programming?
Interesting article on sockets, a technology created in 1982. It shows how some of the limitations that were around in 1982 are expressed in the sockets architecture and how we are still being affected by the design decisions in this stack.

It talks about the need for multihoming, but I also wonder on the implications for moving away from a client/server model, and the transistion to SOA/ESB/Cloud type technologies - do we need to rethink some of the lower level stack?

Saturday, October 25, 2008

Rotating a string

Code snippet to rotate a string:


static void Main(string[] args)
{
string subject = "abcdefg";

// test harness, check it handles multiples of size and negatives and zero
for (int amount = -subject.Length * 3; amount < subject.Length * 3; amount++)
{
string result = RotateStringTest(subject, amount);

char[] inplace = subject.ToCharArray();

RotateString(inplace, amount);

if (amount % subject.Length == 0)
Debug.Assert(result.CompareTo(subject) == 0);
Debug.Assert(result.CompareTo(new String(inplace)) == 0);
}
}

/// <summary>
/// Rotates a string
/// </summary>
/// <param name="subject">string to rotate</param>
/// <param name="amount">&lt; 0 left, 0 none, &gt; 0 right</param>
/// <returns></returns>
private static void RotateString(char[] subject, int amount)
{
int length = subject.Length;

// negate rotations can be re-expressed as positive amounts
if (amount < 0)
amount = length - (-amount % length);

// 0 rotation mean return unchanged
if (amount % length == 0)
return;

int dest = amount;
char prev = subject[0];

do
{
dest %= length;

Swap(ref subject[dest], ref prev);

dest += amount;
} while (dest != amount);
}

/// <summary>
/// swaps two chars wihout using temp variable
/// </summary>
private static void Swap(ref char a, ref char b)
{
a ^= b;
b ^= a;
a ^= b;
}

/// <summary>
/// Rotates a string test (slow)
/// </summary>
/// <param name="subject">string to rotate</param>
/// <param name="amount">&lt; 0 left, 0 none, &gt; 0 right</param>
/// <returns></returns>
private static string RotateStringTest(string subject, int amount)
{
char[] result = subject.ToCharArray();
int length = subject.Length;

// negate rotations can be re-expressed as positive amounts
if (amount < 0)
amount = length - (-amount % length);

// 0 rotation mean return unchanged
if (amount % length != 0)
{
for (int pos = 0; pos < length; pos++)
{
int dest = (pos + amount) % length;

result[dest] = subject[pos];
}
}

return new String(result);
}


ps this post was really just to test this javascript code hightlighter.. It seems to work very well for both Xaml and C# - cool!

Thursday, October 9, 2008

Permutations and Anagrams

I needed to generate some anagrams, which I know falls into the area Permutations (combinations being altogether the wrong thing for this). There is a nice code sample on Wikipedia that shows how to generate these for an unordered collection.

I implemented a generic class to carry out permutations for me, I changed it to be based on an iterator pattern as often you don't want to generate the whole set, mainly because of the big-oh O(n!), class is therefore:


class Permutation<T>
{
IEnumerable<T> set;

private Permutation()
{
}

public Permutation(IEnumerable<T> set)
{
this.set = set;
}

public IEnumerable<IEnumerable<T>> Mutations
{
get
{
int length = set.Count();

int factorialK = (int)Factorial(length);

for (int k = 0; k < factorialK; k++)
yield return GeneratePermutation(k, set, length);

}
}

private static IEnumerable<T> GeneratePermutation(long k, IEnumerable<T> set, int length)
{
T[] result = set.ToArray();
for (int j = 2; j <= length; j++)
{
k = k / (j - 1);
int dest = (int)(k % j);
int source = j - 1;
if (source != dest)
Swap(ref result[dest], ref result[source]);
}

return result;
}

private static void Swap(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
}

private static long Factorial(int n)
{
long result = 1L;

for (int integer = 2; integer <= n; integer++)
result *= integer;

return result;
}
}


which allowed me to write the following code to generate ananagrams:


static void Main(string[] args)
{
string word = "ape";

List<string> anagrams = GenerateAnagrams(word);

anagrams.Sort();

Console.WriteLine("{0} anagrams", anagrams.Count);
anagrams.ForEach(anagram => Console.WriteLine(anagram));
}

private static List<string> GenerateAnagrams(string word)
{
List<string> sets = new List<string>();

Permutation<char> perm = new Permutation<char>(word);
foreach (char[] combo in perm.Mutations)
sets.Add(combo.ToString());

return sets;
}

note that we are taking advantage of string being a char[], for other types such as int would need to be passed as an array, list or similar IEnumerable<T>

Thursday, September 18, 2008

Finding duplicates in an array

One of the problems I stumbled across recently was writing an efficient way to detect if a non-sorted integer array contains duplicates. Or more formally: an unsorted array of size N that contains values between 0 and N-1, find if it contains duplicated elements.

The trick being to avoid having to sort the array, or O(N2) loop within loops.

My solution was to use a bit array the size of N, which would flag if we had seen a value or not - we run through all the values in the array and check its position in the bit array, if it contains a 0 we have not seen it before, or a 1 if we have (duplicate). If we have not seen it before we set its position to 1 and continue.

In C# the is a great class that makes bit manipulation even easier "BitArray", it provides an efficient array class for handling bit operation.

The code:

static void Main(string[] args)
{
int[] numbers = { 1, 2, 3, 1, 5 };

bool duplicates = IsArrayDuplicated(numbers);
}

private static bool IsArrayDuplicated(int[] numbers)
{
bool result = false;

BitArray bits = new BitArray(numbers.Length+1);

foreach (int n in numbers)
{
result = !bits[n];

if (!result)
break;

bits[n] = true;
}

return result;
}

Sunday, September 14, 2008

Rotating an array

Over at polymathprogrammer there is an article about rotating an array, which was a response to Mr Chen's entry on an interview question

Reading the answers got me thinking as I had recently written a roate method in order in implement tic-tac-toe (don't ask why). My solution then had been along the lines of one of the suggested solutions:


for (int y = 0; y < n; y++)
for (int x = 0; x < n; x++)
output[n - y - 1,x] = input[x,y];


though I used a mapping intead of a direct move.

What was interesting was that someone else had suggested that you could just do it using two mirror operations (mirror horizontal and then a diagonal) which was a very elegant way of doing it.

I liked this and it made me think was there another way to do it (as in how many ways can this problem be solved. And I came up with this, which takes advantage of using a single dimension array for holding two dimensional data:


1 &124; 2 &124; 3
-----------
4 &124; 5 &124; 6
-----------
7 &124; 8 &124; 9


stored as


int[] array = new int[] { 1, 2, 3, 4 , 5, 6, 7, 8, 9};


which if rotated looks likes:


int[] array = new int[] { 7, 4, 1, 8, 5, 2, 9, 6, 3};


which looks like the mapping:


destinationOffset += w;
if (destinationOffset > l)
destinationOffset = destinationOffset % w;


in effect, offset its new position by the width of the matrix (3) and wrap overflows back to the start. This looked good until number 4 as it collided with 1, so I just moved it back a step if it collided. Problem solved for 90° right:

gives:


7 &124; 4 &124; 1
-----------
8 &124; 5 &124; 2
-----------
9 &124; 6 &124; 3


Now you could just apply the function multiple times for 180°, 270° rotations, but looking at the resultant arrays shows two things:
180°: results is the original array in reverse order
270°: results is the 90° array in reverse order

So it looks like reversing an array is the same as a diagonal mirror! which means you need just two functions, a rotate and an array reverse (which is part of most array implementations, .Net as Arrray.Reverse)

Code for just the single rotation is:


int size = 3*3;
int[] array = new int[size];
for (int i = 0; i < size; i++)
array[i] = i + 1;

int l = array.Length;
int w = (int)Math.Sqrt(array.Length);

int[] destination = Rotate(array, l, w);


private static int[] Rotate(int[] array, int l, int w)
{
int[] destination = new int[l];
int destinationOffset = -1;
for (int sourceOffset = 0; sourceOffset < l; sourceOffset++)
{
destinationOffset += w;

// wrap around
if (destinationOffset > l)
{
destinationOffset %= w;
// collision avoidance
destinationOffset--;
}

destination[destinationOffset] = array[sourceOffset];

}

return destination;
}


and of course given we know the size of the array, and we can use XOR to do swaps in place

swap(a, b) =>
a = a ^ b; // a^= b;
b = b ^ a; // b ^= a;
a = a ^ b; // a ^= b;


then the fast version (without working at a bit level) might be:


private static void RotateInPlace4by4(int[] array)
{
// corners (1,4 moves around)
swap(ref array[3], ref array[15]);
swap(ref array[0], ref array[3]);
swap(ref array[0], ref array[12]);

// left inner (2 moves around)
swap(ref array[7], ref array[14]);
swap(ref array[1], ref array[7]);
swap(ref array[1], ref array[8]);

// right inner (3 moves around)
swap(ref array[11], ref array[13]);
swap(ref array[2], ref array[11]);
swap(ref array[2], ref array[4]);

// middle square (6,7,10,11)
swap(ref array[5], ref array[9]);
swap(ref array[6], ref array[10]);
swap(ref array[6], ref array[9]);
}

private static void swap(ref int a, ref int b)
{
a ^= b;
b ^= a;
a ^= b;
}

Tuesday, September 9, 2008

Generic Heap and prioritized queues in C#

One of the systems I'm writing required a heap data structure so I've implemented it as a generic as its quite useful for guaranteed sort times and for prioritized queues.

which can be used:


string data = "an out of order string";


var heap = new Heap<char>();
foreach (char c in data)
heap.Push(c);

// in order becomes
while (heap.Count != 0)
Console.WriteLine(heap.Pop());

// or in reverse order, using a custom order

Comparison<char> comparison = delegate(char first, char second)
{
return second.CompareTo(first);
};

var heap2 = new Heap<char>(comparison);
foreach (char c in data)
heap2.Push(c);
while (heap2.Count != 0)
Console.WriteLine(heap2.Pop());


implemented as:

using System;
using System.Collections.Generic;
using System.Text;

namespace Heaps
{

/// <summary>
/// heap data stucture, guaranteed O(nlog n), acts as a priority queue
/// </summary>
/// <typeparam name="T">data to hold in heap tree</typeparam>

class Heap<TValue> where TValue : IComparable
{
// functions return if item not found
public const int NOTFOUND = -1;
// root offset
const int ROOT = 0;
// forward, backward step direction
const int FORWARD = 1;
const int BACKWARD = -FORWARD;
// storage of values
List<TValue> values = null;
// allow parameterisation of ordering and (min/max heap)
Comparison<TValue> comparison = null;

/// <summary>
/// creates a new heap, with ordering
/// defined by T : IComparable
/// </summary>

public Heap()
{
values = new List<TValue>();
}

/// <summary>
/// creates a new heap, with ordering
/// defined by Comparison<T>
/// </summary>
/// <param name="comparison"></param>

public Heap(Comparison<TValue> comparison): this()
{
this.comparison = comparison;
}

/// <summary>
/// return the value at offset position in the tree (pre-order traversal)
/// </summary>
/// <param name="position">offset in tree</param>
/// <returns></returns>

public TValue this[int position]
{
get
{
return values[position];
}
}

/// <summary>
/// number of values in tree
/// </summary>

public int Count
{
get
{
return Length();
}
}

/// <summary>
/// returns the offset of the parent
/// </summary>
/// <param name="position">the value position to find parent of</param>
/// <returns>offset of parent in tree</returns>

public int ParentOf(int position)
{
int result = NOTFOUND;
if (position > 0)
result = ((position+1) / 2) - 1;

return result;
}

/// <summary>
/// return the offset of the left child
/// </summary>
/// <param name="position">the value offset position to find the left child of</param>
/// <returns>offset of left child in tree</returns>

public int Left(int position)
{
int result = NOTFOUND;

result = (position * 2) + 1;

result = EnsureNotBeyond(result);

return result;
}

/// <summary>
/// return the offset of the right child
/// </summary>
/// <param name="position">the value offset position to find the right child of</param>
/// <returns>offset of right child in tree</returns>

public int Right(int position)
{
// right node is 1 more than the left
int result = Left(position);

if (result != NOTFOUND)
result++; // one position beyond left

result = EnsureNotBeyond(result);

return result;
}

/// <summary>
/// returns the root value
/// </summary>

public TValue Root
{
get
{
if (Length() == 0)
throw new InvalidOperationException("No items in heap");

return values[ROOT];
}
}

/// <summary>
/// returns the value with highest priority
/// </summary>
/// <returns>the value</returns>

public TValue Pop()
{
TValue result = Root;

int lastItem = EnsureNotBeyond(Length() - 1);

if (Length() > 1)
values[ROOT] = values[lastItem];

values.RemoveAt(lastItem);

MaintainHeapProperty(FORWARD);

return result;
}

/// <summary>
/// add the value to the tree
/// </summary>
/// <param name="value">value to add</param>

public void Push(TValue value)
{
values.Add(value);

MaintainHeapProperty(BACKWARD);
}

/// <summary>
/// number of nodes
/// </summary>
/// <returns>length</returns>

private int Length()
{
return values.Count;
}

/// <summary>
/// ensures a position is not beyond the tree storage
/// </summary>
/// <param name="position">offset</param>
/// <returns>offset, or NOTFOUND if out of bounds</returns>

private int EnsureNotBeyond(int position)
{
if (position >= Length())
position = NOTFOUND;

return position;
}

/// <summary>
/// adjusts tree to ensure heap property maintained after a push or pop
/// </summary>
/// <param name="direction">FORWARD for push, BACKWARD if pop</param>

private void MaintainHeapProperty(int direction)
{
int start = (direction == FORWARD) ? ROOT : Length();
int end = (direction == FORWARD) ? Length() : NOTFOUND;

for (int pos = start; pos != end; pos += direction)
{
int left = Left(pos);
int right = Right(pos);

// ensure this value is greater than chidren
if (left != NOTFOUND && Compare(pos, left) < 0)
Swap(pos, left);
if (right != NOTFOUND && Compare(pos, right) < 0)
Swap(pos, right);
}
}

/// <summary>
/// return integer indicating order
/// </summary>
/// <param name="first">offset of first</param>
/// <param name="second">offset of second</param>
/// <returns>.lt. zero=first,second;zero=first==second;.gt. zero=second,first</returns>

private int Compare(int first, int second)
{
int result = 0;

// if comparison delegate provided us it to compare
if (comparison != null)
result = comparison(values[first], values[second]);
else // default TValue compare
result = values[first].CompareTo(values[second]);

return result;
}

/// <summary>
/// swaps two offsets
/// </summary>
/// <param name="first">first offset</param>
/// <param name="second">second offset</param>

private void Swap(int first, int second)
{
TValue temp = values[first];
values[first] = values[second];
values[second] = temp;
}

public override string ToString()
{
StringBuilder sb = new StringBuilder();

sb.Append("[");
foreach (TValue value in values)
sb.Append(value.ToString());
sb.Append("]");

return sb.ToString();
}
}

}