Most of the algorithm is like solving a puzzle, it is interesting, but it lacks of math. I came across an algorithm problem, which is interesting to me, at least more math involved.
Given a complete binary search tree in form of array. Write a sort function to sort the given array in O(n)time complexity and constant memory.
________100
_____50_______150
___25___75__125___200
then array is {100 50 150 25 75 125 200}
the trick is the tree is a full binary tree.
if the node is left most node: its index = (0 + parent node's index) / 2
if the node is right most node: its index = (n + parent node's index) / 2
other nodes: its index = (parent's index + grandparent's index) / 2
with this formula, it is easy to pin point the location.
Wednesday, May 4, 2011
Monday, May 2, 2011
Prepare for a move - threading and parallel
Finally, it is time to prepare for some move in the future. When you buried in everyday work, you must have got tunnel vision, I hope this preparation process will give me some fresh air. You might use the low performance statement every day or totally lose your mind when being ask what is "algorithm X" with O(n). :-) Let us start my journey and hopefully learn something new.
The first topic I want to touch is to use lock keyword in the C#.
if there are some variables in the class and how to use lock to update it.
if it is a int or long, use the interlock.increament if that is possible. Otherwise, the general rule is
1. declare a private or protected variable as syncroot
2. if the variable is value type, then lock the syncroot
if the variable is ref type, lock the variable itself.
Actually, if you want to get your work done, use the data structure under System.Collection.Concurrent namespace (new .net 4.0) , which is usually get rid of the need for explicit synchronization.
One catch I found is that on 32-bit system, the reading a 64-bit int is NOT atomic. You have to use Interlock.Read(). In a 64-bit system, reading 64-bit int is atomic.
Today I found the [ThreadStatic] attribute is very useful when design the multi-thread application. It has unique value for each thread!
The first topic I want to touch is to use lock keyword in the C#.
if there are some variables in the class and how to use lock to update it.
if it is a int or long, use the interlock.increament if that is possible. Otherwise, the general rule is
1. declare a private or protected variable as syncroot
2. if the variable is value type, then lock the syncroot
if the variable is ref type, lock the variable itself.
Actually, if you want to get your work done, use the data structure under System.Collection.Concurrent namespace (new .net 4.0) , which is usually get rid of the need for explicit synchronization.
One catch I found is that on 32-bit system, the reading a 64-bit int is NOT atomic. You have to use Interlock.Read(). In a 64-bit system, reading 64-bit int is atomic.
Today I found the [ThreadStatic] attribute is very useful when design the multi-thread application. It has unique value for each thread!
Subscribe to:
Posts (Atom)