Monday, July 5, 2010
Volatile: You are forcing your compier not to be smart
class Gadget{
public:
void Wait() {
while (!flag_){
Sleep(1000); // sleeps for 1000 milliseconds
}
}
void Wakeup() {
flag_ = true;
}
private:
bool flag_;
};
Your compiler is so smart that he will find that nobody in this class could update flag_, so dont read flag_ from memory again and again, put it in register.
Oh shit!!!!!
It hang when I asked for wait..
Solution is to use 'volatile bool flag_'. So now if you will share this gadget object between multiple threads, it will hurt you ...
2) Other than optimization volatile works as const, even const cast works on it.
Summary
When writing multithreaded programs, you can use volatile to your advantage. You must stick to the following rules:
* Define all shared objects as volatile.
* Don't use volatile directly with primitive types.
* When defining shared classes, use volatile member functions to express thread safety.
If you do this, and if you use the simple generic component LockingPtr, you can write thread-safe code and worry much less about race conditions, because the compiler will worry for you and will diligently point out the spots where you are wrong.
A couple of projects I've been involved with use volatile and LockingPtr to great effect. The code is clean and understandable. I recall a couple of deadlocks, but I prefer deadlocks to race conditions because they are so much easier to debug. There were virtually no problems related to race conditions. But then you never know.
Mutex vs. Semaphore
The Toilet Example (c) Copyright 2005, Niclas Winquist ;)
Mutex:
Is a key to a toilet. One person can have the key - occupy the toilet - at the time. When finished, the person gives (frees) the key to the next person in the queue.
Officially: "Mutexes are typically used to serialise access to a section of re-entrant code that cannot be executed concurrently by more than one thread. A mutex object only allows one thread into a controlled section, forcing other threads which attempt to gain access to that section to wait until the first thread has exited from that section."
Ref: Symbian Developer Library
(A mutex is really a semaphore with value 1.)
Semaphore:
Is the number of free identical toilet keys. Example, say we have four toilets with identical locks and keys. The semaphore count - the count of keys - is set to 4 at beginning (all four toilets are free), then the count value is decremented as people are coming in. If all toilets are full, ie. there are no free keys left, the semaphore count is 0. Now, when eq. one person leaves the toilet, semaphore is increased to 1 (one free key), and given to the next person in the queue.
Officially: "A semaphore restricts the number of simultaneous users of a shared resource up to a maximum number. Threads can request access to the resource (decrementing the semaphore), and can signal that they have finished using the resource (incrementing the semaphore)."
Ref: Symbian Developer Library
Does it mean binary semaphore are mutexes?
Ideally yes. but binary semaphore is something more to it...
The mutex is similar to the principles of the binary semaphore with one significant difference:
the principle of ownership. Ownership is the simple concept that when a task locks (acquires) a mutex only it can unlock (release) it. If a task tries to unlock a mutex it hasn’t locked (thus doesn’t own) then an error condition is encountered and, most importantly, the mutex is not unlocked. If the mutual exclusion object doesn't have ownership then, irrelevant of what it is called, it is not a mutex.
So it means that in case of binary semaphore toilet can be signaled to open by the owner.
Please comment if my understanding is wrong. I will update the post.-Rhaul
Friday, July 2, 2010
C++: Mutable vs. constness
http://www.highprogrammer.com/alan/rants/mutable.html
Most of time mutable is described as a type which breeches the constness of the object. But it is actually to help constness for many purposes. eg.
1) Reference count of a the objects users.
2) Use it in the for storing the mutex object in the object so that you can apply lock when reading something from const object.
3) You can use it for a lazy evaluation of an expression object..
i.e.
class PI{
public:
pi():pi(0.0), evaluated(false) {}
double getValue(){
if(evaluated) return _pi;
for(int i=0; i< 1000000000000; i++){
//....
}
evaluated=true;
return _pi;
}
private:
mutable double _pi;
mutable bool evaluated;
};
In that case you can create and pass object of PI to any function as const, and it will be evaluated on use only.
How mutable will benefit you is design of the function which takes PI as input.
void PrintCircleAreaWithRadius(double radius, const PI& pi); //If _pi in PI class is not declared as mutable compiler will not allow you ..
Thursday, January 8, 2009
Dynamic Programming
Aur Chinti Phad chad jaati haii ...
Bekar Tukbandi ...
But dynamic programming is something like that.
By definition Dynamic programming is : To solve a Problem use Sub-problem's solution.
Most familiar problem most of us have already programmed is Prime number Generation Or Fibonacci.
Prob: print all prime numbers upto N.
And the solution will be ...
printPrime(int N){
int i,j;
for( i=2; i < N ;i++){
for( j=2; j < i ; j++) {
if(i%j == 0) break;
}
if(j==i-1)
cout<< j << " ";
}
}
something like that. Time requires is O(N*N) :(
Worst/naive solution.
On doing some analysis, we can easily prove that if number m is not divisible by primes up to m, then it will be a prime number. So if we have stored the primes we have find till i < m then very few iterations require in comparison to N. Which will give you a great improvement over O(n*n);
The change requires to use previously find solution for the next solution(i.e. for checking next prime number). AND a little analysis.
Aaj aapko DP ki definition pata hai ..
Kya Aap log santust ho ..
kya kha nahii...
Banna chahoge duniya ke sabse bade programmer
Tau phir hum ek aur DP problem open kare...
[thoda jayada ho gya, I cant do it. But still can try to be.]
Other Easy Problem is:
We need to find minimum number of coins required for finding sum S, using {c1, c2, c3, c4}, set of coins. Any coin can be used any number of times.
SOLUTION:
Dynamic Programming.........................
huh!
How could you say it? :?
That's the actual confusion which inspires me to write this post. If, I am navigating Dynamic Problem(DP) category, then we can say oh! that Problem will be solved using DP. But for now how can we find that its a DP prob.
The approach, I followed( must say observed)
0. UNDERSTAND PROBLEM CORRECTLY.
[ One of the problem area for difficult problem, because me too not spend actual required time for it]
1. How to solve the problem without using any Store (or say in the Generic manner).
[Every solvable problem can be solved by analyzing all the possible combination. And find the required best solution out of them].
If someone have created Quantum Computer in the stone age, Algo & DS don't required to be added in the CS stream course syllabus.
2. Analyze the special points.
[ e.g. In Prime Number Problem we find that divisibility need not to be checked with all the numbers, only Prime numbers divisibility check will be enough to do.]
3. Try to minimize solution using this Analysis.
[ Some early analysis, I have missed in the Prime Number Problem because Post is about DP.
Like, only sqrt(N) inner iterations will be enough,
and, iterate with the increment of 2 in the inner iterations.]
4. Cry!!!! oh shit!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Its to much time taking.
5. ASK to the problem, if old solutions will be helpful to find final solution faster.
[like in prime number problem Last prime number will be found too early if we have all prime number primes upto N]
6. Prepare required store. Use the store to minimize time.
7. Wakauuuuuuuuu!!!!!!!!!!!!
done dona done done.
My observation and Definitions to....
1. May be you will find that normally all the solutions are dumped to linear from recursive.
2. ---- As I will found other, I will put it here ---------------
Now Coin problem using these steps:
Step 0:
So problem is to find the number of coins only. Not the actual combination which form the sum S.
Any number of coin can be used of any type. So no limit on count.
Prepare one example.
{4, 5, 7} is coin set. and Sum is 20
Possible solutions are,
5,5,5,5 (ok)
7,5,4,4 (ok)
4,4,4,4,4 (ok)
7, 7,7 (X)
So, I find that on sum of different coins combination (l*C1+m*C2+n*C3) < S.
so problem is to find the different l, m, n values and then minimum l+m+n.
Oh Great!!
Step 1:
Generic Solution:
so, find all combination of l, m, n and see which of them can produce S.
find minimum of l+m+n.
Problem says that any l,m,n can be used BUT, as we have analyzed above "(l*C1+m*C2+n*C3) < S "
so if m=0, n=0 l=S/C1. will be the maximum value. Similarly,
0<= l <=S/C1
0<= m <=S/C2
0<= n <=S/C3
creq=2<<30; //infinite
for(i=0; i<=S/C1+1;i++)
for(j=0; j<=S/C2+1;j++)
for(k=0; k<=S/C2+1;k++)
if(i*C1+j*C2+k*C3 == S)
if(creq > i+j+k)
creq=i+j+k;
{That is on for three coins, but if there are N coins}
But still that also requires exponential time.
I have write some recursive solution for it.
We can find S, if we can find S-C1 or S-C2 or S-C3..
so, pseudo code will be like
fun coinCount(S){
if S< 0
return NOT_POSSIBLE;
if S==0
return 0; //Solution done with zero coin
foreach( COINS, c)
RES[i++]=coinCount(S-c)
return ( 1+minimum(RES) );
}
Do it looks Ok?
some correction may require, but looks Ok base to me.
Step 3:
Time to sleep....
Analyze above logics, we will append it tomorrow.
Thanks
for tolerating top 2 Lines
Thursday, January 1, 2009
MegaCoolNumbersEasy
Hi guys
Problem is the exclusive and proprietary property of SomeCompany, Inc. Any unauthorized use or reproduction of this information without the prior written consent of SomeCompany, Inc. is strictly prohibited.
Solution I wrote:
class MegaCoolNumbersEasy{
public:
int count(int N){
int nc=N>99?99:N;
if(N<100) return nc;
int tmp=0; int td=N<1000?N/100:9;
for(int j=1; j<= td; j++){
for(int i=-4; i< 5; i++){
if( i+j >=0 && i+j <=9 && j+2*i <=9 && j+2*i >=0){
tmp=j*100+(j+i)*10+(j+i+i);
if(N>= tmp) nc++;
tmp=0;
}
}
}
return nc;
}
} ;
And solution someone find for me is:
http://hi.baidu.com/liveroom/blog/item/22d9e645d9cda33886947343.html
Please comment which one is better.
I am not using for any commercial use. Please let me know if I am still violating the Rule.
Saturday, December 6, 2008
One more Print path
Given a binary tree, print out all of its root-to-leaf paths, one per line.
void printPaths(struct node* node)
Solution you can find easily at : http://cslibrary.stanford.edu/110/BinaryTrees.html
I have not find any new solution till date for this:
I have tried derive new one today (not implemented yet.. )
#include
using namespace std;
printPath(node* root){
string now="";
ppath(root, now);
}
ppath(node* root, string now){
if(!root) return;
if( root && ! root->left && ! root->right){
print("%s %d\n", now, root->data); return;
}
if(root->left) ppath(root->left, now+'0'+root->data);
if(root->right) ppath(root->right, now+'0'+root->data);
}
Although solution is very simple still like to point out the concept of using string.
string class have following properties:
string+char->string.
and passing string as value to a function will create a new string.
Please comment the correctness of solution.
Tuesday, November 25, 2008
My notes on yoga ..
I am following Baba Ramdev since 2-3 days. I think Yoga and exercise are more & more necessary for software engineers. We guys are not doing any physical work so we are in more critical stage for ..........
Our immunity systems are not good so more.
I am not trying to elaborate any saying or details about yoga. A lot many sites are doing the same in much better way I can do. I am going to post summary(one liners) of steps and time suggested for the daily yoga.
Source I will mention at last. Please do not hesitate googling for much details.
The list of Yoga/ Prayanam, I am able to follow by last watch are:
0) Try to have mild hot water at least in the day. At least have 2 glass of water in the morning.
1) BHASTRIKA PRAYANAM ( Bellow Breath)
How to do: Breath deep to lungs, and relive . Its for expansion & contraction of Lungs. Do it relaxed. Keep the back straight, chin parallel to floor, jaw relaxed.
Precaution: Do with empty stomach. High blood pressure, Ulcer & back pain patient should not do it fast. Pregnant women should not do it.
Time: 2-3 Min, 5 Min max
2) KAPAL BHATI PRAYANAM
How to do: Push air forcefully out. Stomach will itself go in. Force should not to much to sound from mouth. Your body posture should not change.
Precaution: Don't do it with full stomach.
Time: Try to make 30 times in 1 min. Start with 15 min to 30 min.
3) BAHARYA PRAYANAM
How to do: Breath air out as much you can, hold it. Try to move stomach only. Release air out calm.
Precaution: Don't do it with full stomach.
Time: Try to make 5 times . DON'T DO IT TOO MUCH. max 11 times.
4) UDGEETH PRAYANAM
How to do: Breathe in deeply, and chant 'Om'kar. OOOOOOm ( long O and small m )
Precaution:
Time: 10 Min or more according to time
5) ANULOM VILOM PRAYANAM
How to do: Breath air in from one of the nasal (like left), close other with thumb or finger. Release air from other nasal(like right) with closing the first nasal using finger or thumb. Do same for the this nasal.
Precaution:
Time: At least 10 minutes, do up to 20 minutes. (250 to 500 times a day)
6) BHRAMRI PRAYANAM
How to do: Close ears with thumb, index finger on forehead, and rest three on base of nose touching eyes. Breathe in. And now breathe out through nose while humming like a bee. Try to say OM.............. Try to release air as slow as you can.
Precaution:
Time: Up to 5 - 7 Times
7) UJJAYI PRAYANAM
How to do: Inhale, slowly drawing air by both the nostrils in such a way that while inhaling the touch of air is experienced in the throat and some sound is produced. Breath out slowly without sound form one of the nassal one by one.
Precaution:
Time: Up to 15 - 20 Times
Its karma time now.
Do it.
Daily 7 are over now.
I will update as soon as I will learn new.