Some useful videos of C++ performance related development.
1. SIMD
- CppCon 2016: Pablo Halpern “Introduction to Vector Parallelism"
- CppCon 2016: Joel Falcou “Designing C++ portable SIMD support"
2. Parallel
- CppCon 2014: Pablo Halpern "Decomposing a Problem for Parallel Execution"
- CppCon 2016: Bryce Adelstein Lelbach “The C++17 Parallel Algorithms Library and Beyond"
3. Look-free
- CppCon 2014: Herb Sutter "Lock-Free Programming (or, Juggling Razor Blades), Part I"
- CppCon 2014: Herb Sutter "Lock-Free Programming (or, Juggling Razor Blades), Part II"
- CppCon 2016: D. Dechev & D. Zhang “High Performance C++ Concurrent Transactional Data Structures"
4. Compiler
- CppCon 2015: John Farrier “Demystifying Floating Point"
- CppCon 2016: Tim Haines “Improving Performance Through Compiler Switches..."
A lot more of CppCon videos available on youtube and don't miss out the latest development of C++ technologies.
Tuesday, 20 June 2017
Wednesday, 17 May 2017
C++11 - Data Sharing
1. Static Variables Initialization
Static variables are initialized when the very first thread runs through it. The data race could happen when multiple thread try to run through it at the same time.
Here are a few hazards. First the same object can be initialized a few times. Second there might be memory leak when the static variable is a pointer or it has memory allocation inside and are initialized a few times. Third static variables may lose its persistence if it is not stateless - some state may take from the first initialization, some may take from the 2nd initialization and so on. Last the program could crash due to inconsistent state show in the following code snippet.
//*********************************************************************************
class Bar
{
public:
Bar(int x, double y);
void DoSomething();
};
void Foo(int x, double y)
{
// C++ guarantees thread safe
static Bar localBar = Bar(x, y);
localPt.DoSomething();
}
//*********************************************************************************
For instance two threads run into Foo() at the same time and the first one initializes the localBar and carries on run DoSomething(). Then the second thread initializes the localBar again when the first thread is still in DoSomething(). Literally thread 1 is operating an object which is half completed and half destroyed. Crash could happen anytime.
C++11 noticed this issue and makes thread-safety of this scenario as standard. It means that C++11 guarantees that localBar is to be initialized only once. The rest threads will be blocked out until the first thread finishes the initialization. This also solves the famous singleton problem, Design pattern - Singleton pattern.
2. Data Race on Initialization
This scenario applies to those data that are needed to be protected at their first initialization. The typical case is calculation-on-demand and one of typical scenarios of this process is lazy-initialization of variables.
It is quite common in quantitative development to do the calculation-on-demand. For instance given a market and trades its risks are not calculated until they are required/query. And they are only recalculated until one of them changed.
*********************************************************************************
class Market;
class Trade;
class Risks
{
public:
double GetVega() {
std::call_once(m_VegaFlag, CalculateVega);
return m_Vega;
}
private:
void CalculateVega();
std::once_flag m_VegaFlag;
Market *m_Mkt;
Trade *m_Trd;
double m_Vega;
}
*********************************************************************************
std::call_once and std::once_flag are introduced into C++11 to achieve that functions that need to be run only once in the entire application life. And serves the first come the first server semantics.
This guarantees the following,
- CalculateVega() not called if not vega is not retrieved
- Guarantee that CalculateVega() called only once on demand
3. Reader-Writer Lock
Single-reader-and-single-writer is the simplest case. An atomic variable will do the job if the data is single primitive type. Otherwise std::mutex can be used to sync the read-and-write operation. Or even implement a lock-free guard via an atomic flag or bool.
Here we are focusing on multi-reader cases. The typical use case in quantitative world is lazy-calculation. Similar to lazy-initialization the variables are required to be re-calculated after its initialization. But the re-calculation happens rarely. For instance the market-data bumped or ref-data changed. The quick read access to the data is required because it might be frequently retrieved to calculate other derived risks. And at the same time no starvation happens to write access - in other word recalculation is served as soon as possible.
Semaphore solution:
A typical solution before C++11 is to use semaphores. It is not a part of C++ standard but a system-dependent implementation. Initialize the resources in semaphores as the total number of read-threads. Under the condition without write-access each read-thread have at least one resource for them and the read-access is quick and smooth. But when a write-access is required, the write-thread has to acquire the resources by lowest granularity until acquire all the resources in order to block all read-threads before writing. This will guarantee that it is a fairly implementation for write access - otherwise starvation of write access happens.
Semaphore Implementation
*********************************************************************************
// a simple Semaphore API (see QSemaphore implemention)
class Semaphore
{
public:
Semaphore(unsigned int totalResrouces);
void Acquire(unsigned int resource);
void Release(unsigned int resource);
unsigned int TotalResources() const;
};
class RiskVariable1
{
public:
double Read()
{
double val;
m_Sem.Acquire(1);
val = m_Value;
m_Sem.Release(1);
return val;
}
void Write(const Market &m, const RefData &rd)
{
const unsigned int TotalResources = m_Sem.TotalResources();
// Here if call "m_Sem.Acquire(TotalResources)" can cause write-thread starvation
// And have to acquire each resource in lowest granularity until all
// This implementation is only for single-write.
// Will cause dead-lock if multi-write try to access because each just holds part of resources
for (unsigned into i = 0; i < TotalResources; ++i) {
m_Sem.Aqcuire(1);
}
// hit here all resources are acquired by this write-thread
Calculate(m, rd);
m_Sem.Release(TotalResources);
}
private:
void Calculate(const Market &m, const RefData &rd)
{
// change the value of m_Value
}
double m_Value;
Semaphore m_Sem;
};
*********************************************************************************
The above implementation works only for multi-reader-single-writer scenario. It guarantees quick read access when no write access is in request and also fair service for write access (no starvation). As soon as read access gets out of away, write access is serviced. But the above implementation will cause deadlock for multi-reader-multi-writer. It needs only tiny tweak to make it work for multi-reader-multi-writer.
//*********************************************************************************
class Semaphore
{
// ......
};
class RiskVariable1
{
public:
// ...... code
void Write(const Market &m, const RefData &rd)
{
const unsigned int TotalResources = m_Sem.TotalResources();
// Here if call "m_Sem.Acquire(TotalResources)" can cause write-thread starvation
// And have to acquire each resource in lowest granularity until all
// This implementation is only for multi-write.
m_WLock.lock();
{
for (unsigned into i = 0; i < TotalResources; ++i) {
m_Sem.Aqcuire(1);
}
}
m_WLock.unlock();
// hit here all resources are acquired by this write-thread
Calculate(m, rd);
m_Sem.Release(TotalResources);
}
private:
// ...... code
double m_Value;
Semaphore m_Sem;
Mutex m_WLock;
};
//*********************************************************************************
The tweak is quite straightforward too. Use a mutex to guard the write thread when they come to acquire the resources of semaphore. It guarantees that only one write-thread in progress to acquire to semaphore's resource and the rest has to wait.
C++11 solution:
C++11 provides std::shared_mutex to solve this issue. And it works with any scenarios shown above including multi-reader-multi-writer.
//*********************************************************************************
class RiskVariable1
{
public:
double Read()
{
std::shared_lock<std::shared_mutex> guard(m_SMut);
return m_Val;
}
void Write(const Market &m, const RefData &rd)
{
std::unique_lock<std::shared_mutex> guard(m_SMut);
Calculate(m, rd);
}
private:
void Calculate(const Market &m, const RefData &rd)
{
// change the value of m_Value
}
double m_Value;
std::shared_mutex m_SMut;
};
//*********************************************************************************
C++11 provides std::shared_lock for quick read access and std::unique_lock for write access to guarantee mutual exclusion as only one write access allowed. Besides C++11 standard guarantees that there is starvation for write access.
4. Recursive Lock
Recursive lock is not a part of standard before C++11. However POSIX standard defines recursive lock. And both POSIX and Boost provides implementations.
Honestly speaking the application of requiring recursive lock is not that common. I did use it once and only once in my work. Here is the code snippet.
//*********************************************************************************
Both ServiceCharge() and Transfer() are valid APIs and need to be protected individually as both lock the mutex in the implementation. The recursive case happens in ComplexTransfer() that is to do two things in atomic sense - transfer the money and do service charge. Then the lock in ComplexTransfer() has to lock from the start to the end and the lock must be the same lock as in ServiceCharge() and Transfer(). Otherwise BankAccount might have data race on m_Balance.
In the above code snippet m_Lock is locked twice in ComplexTransfer() and it has to be std::recursive_mutex.
Comparing std::mutex and std::recursive_mutex the former is light-weighted on both memory footprint and speed, because it does not need to store information who (which thread) owns it and how many times it has been locked. However std::recursive_mutex is designed to have these information so that kernel can track them against thread to manage resources and threads. Read the comparison of these two type on Recursive Lock (Mutex) vs Non-Recursive Lock (Mutex). They also share a lot in common for instance both implement std::lockable interface and both are not copy able but movable.
Static variables are initialized when the very first thread runs through it. The data race could happen when multiple thread try to run through it at the same time.
Here are a few hazards. First the same object can be initialized a few times. Second there might be memory leak when the static variable is a pointer or it has memory allocation inside and are initialized a few times. Third static variables may lose its persistence if it is not stateless - some state may take from the first initialization, some may take from the 2nd initialization and so on. Last the program could crash due to inconsistent state show in the following code snippet.
//*********************************************************************************
class Bar
{
public:
Bar(int x, double y);
void DoSomething();
};
void Foo(int x, double y)
{
// C++ guarantees thread safe
static Bar localBar = Bar(x, y);
localPt.DoSomething();
}
//*********************************************************************************
For instance two threads run into Foo() at the same time and the first one initializes the localBar and carries on run DoSomething(). Then the second thread initializes the localBar again when the first thread is still in DoSomething(). Literally thread 1 is operating an object which is half completed and half destroyed. Crash could happen anytime.
C++11 noticed this issue and makes thread-safety of this scenario as standard. It means that C++11 guarantees that localBar is to be initialized only once. The rest threads will be blocked out until the first thread finishes the initialization. This also solves the famous singleton problem, Design pattern - Singleton pattern.
2. Data Race on Initialization
This scenario applies to those data that are needed to be protected at their first initialization. The typical case is calculation-on-demand and one of typical scenarios of this process is lazy-initialization of variables.
It is quite common in quantitative development to do the calculation-on-demand. For instance given a market and trades its risks are not calculated until they are required/query. And they are only recalculated until one of them changed.
*********************************************************************************
class Market;
class Trade;
class Risks
{
public:
double GetVega() {
std::call_once(m_VegaFlag, CalculateVega);
return m_Vega;
}
private:
void CalculateVega();
std::once_flag m_VegaFlag;
Market *m_Mkt;
Trade *m_Trd;
double m_Vega;
}
*********************************************************************************
std::call_once and std::once_flag are introduced into C++11 to achieve that functions that need to be run only once in the entire application life. And serves the first come the first server semantics.
This guarantees the following,
- CalculateVega() not called if not vega is not retrieved
- Guarantee that CalculateVega() called only once on demand
3. Reader-Writer Lock
Single-reader-and-single-writer is the simplest case. An atomic variable will do the job if the data is single primitive type. Otherwise std::mutex can be used to sync the read-and-write operation. Or even implement a lock-free guard via an atomic flag or bool.
Here we are focusing on multi-reader cases. The typical use case in quantitative world is lazy-calculation. Similar to lazy-initialization the variables are required to be re-calculated after its initialization. But the re-calculation happens rarely. For instance the market-data bumped or ref-data changed. The quick read access to the data is required because it might be frequently retrieved to calculate other derived risks. And at the same time no starvation happens to write access - in other word recalculation is served as soon as possible.
Semaphore solution:
A typical solution before C++11 is to use semaphores. It is not a part of C++ standard but a system-dependent implementation. Initialize the resources in semaphores as the total number of read-threads. Under the condition without write-access each read-thread have at least one resource for them and the read-access is quick and smooth. But when a write-access is required, the write-thread has to acquire the resources by lowest granularity until acquire all the resources in order to block all read-threads before writing. This will guarantee that it is a fairly implementation for write access - otherwise starvation of write access happens.
Semaphore Implementation
*********************************************************************************
// a simple Semaphore API (see QSemaphore implemention)
class Semaphore
{
public:
Semaphore(unsigned int totalResrouces);
void Acquire(unsigned int resource);
void Release(unsigned int resource);
unsigned int TotalResources() const;
};
class RiskVariable1
{
public:
double Read()
{
double val;
m_Sem.Acquire(1);
val = m_Value;
m_Sem.Release(1);
return val;
}
void Write(const Market &m, const RefData &rd)
{
const unsigned int TotalResources = m_Sem.TotalResources();
// Here if call "m_Sem.Acquire(TotalResources)" can cause write-thread starvation
// And have to acquire each resource in lowest granularity until all
// This implementation is only for single-write.
// Will cause dead-lock if multi-write try to access because each just holds part of resources
for (unsigned into i = 0; i < TotalResources; ++i) {
m_Sem.Aqcuire(1);
}
// hit here all resources are acquired by this write-thread
Calculate(m, rd);
m_Sem.Release(TotalResources);
}
private:
void Calculate(const Market &m, const RefData &rd)
{
// change the value of m_Value
}
double m_Value;
Semaphore m_Sem;
};
*********************************************************************************
The above implementation works only for multi-reader-single-writer scenario. It guarantees quick read access when no write access is in request and also fair service for write access (no starvation). As soon as read access gets out of away, write access is serviced. But the above implementation will cause deadlock for multi-reader-multi-writer. It needs only tiny tweak to make it work for multi-reader-multi-writer.
//*********************************************************************************
class Semaphore
{
// ......
};
class RiskVariable1
{
public:
// ...... code
void Write(const Market &m, const RefData &rd)
{
const unsigned int TotalResources = m_Sem.TotalResources();
// Here if call "m_Sem.Acquire(TotalResources)" can cause write-thread starvation
// And have to acquire each resource in lowest granularity until all
// This implementation is only for multi-write.
m_WLock.lock();
{
for (unsigned into i = 0; i < TotalResources; ++i) {
m_Sem.Aqcuire(1);
}
}
m_WLock.unlock();
// hit here all resources are acquired by this write-thread
Calculate(m, rd);
m_Sem.Release(TotalResources);
}
private:
// ...... code
double m_Value;
Semaphore m_Sem;
Mutex m_WLock;
};
//*********************************************************************************
The tweak is quite straightforward too. Use a mutex to guard the write thread when they come to acquire the resources of semaphore. It guarantees that only one write-thread in progress to acquire to semaphore's resource and the rest has to wait.
C++11 solution:
C++11 provides std::shared_mutex to solve this issue. And it works with any scenarios shown above including multi-reader-multi-writer.
//*********************************************************************************
class RiskVariable1
{
public:
double Read()
{
std::shared_lock<std::shared_mutex> guard(m_SMut);
return m_Val;
}
void Write(const Market &m, const RefData &rd)
{
std::unique_lock<std::shared_mutex> guard(m_SMut);
Calculate(m, rd);
}
private:
void Calculate(const Market &m, const RefData &rd)
{
// change the value of m_Value
}
double m_Value;
std::shared_mutex m_SMut;
};
//*********************************************************************************
C++11 provides std::shared_lock for quick read access and std::unique_lock for write access to guarantee mutual exclusion as only one write access allowed. Besides C++11 standard guarantees that there is starvation for write access.
4. Recursive Lock
Recursive lock is not a part of standard before C++11. However POSIX standard defines recursive lock. And both POSIX and Boost provides implementations.
Honestly speaking the application of requiring recursive lock is not that common. I did use it once and only once in my work. Here is the code snippet.
//*********************************************************************************
class BankAccount
{
public:
void Transfer(BankAccount &toAcc, double amount)
{
// lock the two mutex
std::lock(m_Lock, rhs.m_Lock);
std::lock_guard<std::mutex> lock1(m_Lock, std::adopt_lock);
std::lock_guard<std::mutex> lock2(rhs.m_Lock, std::adopt_lock);
std::lock_guard<std::mutex> lock1(m_Lock, std::adopt_lock);
std::lock_guard<std::mutex> lock2(rhs.m_Lock, std::adopt_lock);
// transfer the money
}
void ServiceCharge(double amount)
{
std::lock_guard<std::mutex> guard(m_Lock);
// take £10 out of this account for instance
}
void ComplexTransfer(BankAccount &toAcc, double amount)
{
std::lock_guard<std::mutex> guard(m_Lock);
Transfer(toAcc, amount);
ServiceCharge(10.00); // £10.00 service charge
}
private:
double m_Balance;
std::mutex m_Lock;
};
//*********************************************************************************
Both ServiceCharge() and Transfer() are valid APIs and need to be protected individually as both lock the mutex in the implementation. The recursive case happens in ComplexTransfer() that is to do two things in atomic sense - transfer the money and do service charge. Then the lock in ComplexTransfer() has to lock from the start to the end and the lock must be the same lock as in ServiceCharge() and Transfer(). Otherwise BankAccount might have data race on m_Balance.
In the above code snippet m_Lock is locked twice in ComplexTransfer() and it has to be std::recursive_mutex.
Comparing std::mutex and std::recursive_mutex the former is light-weighted on both memory footprint and speed, because it does not need to store information who (which thread) owns it and how many times it has been locked. However std::recursive_mutex is designed to have these information so that kernel can track them against thread to manage resources and threads. Read the comparison of these two type on Recursive Lock (Mutex) vs Non-Recursive Lock (Mutex). They also share a lot in common for instance both implement std::lockable interface and both are not copy able but movable.
Wednesday, 3 May 2017
C++11 Features - Solution for Deadlock
1. Problem Description
On my previous blog, Threading - Deadlock, an example of "BankAccount" shows how deadlock is to happen. Account A is to do a transfer to Account B and at the same time Account B is to do one to Account A. The first transaction is to lock A then lock B and do the transfer. The second transaction is to lock B then lock A and do the transfer. There is a good chance that only the first step happened during the two transactions. The first transaction locks A and the second locks B and both try to get the second locking. But fail to do so and two transaction are locked mutually.
The solutions proposed on Threading - Deadlock still work but C++11 and C++17 just have better solutions.
2. C++11 and C++17 Solutions
The solution proposed on Threading - Deadlock is to lock the mutex in the order to guarantee that only one thread can acquire all the resources at once. The solution of C++11 is std::lock, which is able to lock multiple lockable objects at once - in the scenario of none or all.
std::lock either locks all the lockable objects or locks none of them in case of failure (for instance one of lockable objects isn't called in parity of lock/unlock).
C++11 solutions
std::lock can used either with std::lock_guard or std::unique_lock. Comparing std::lock_guard and std::unique_lock, they have similar functionalities. std::lock_guard can be regarded as RAII wrapper of lockable objects via reference and however std::unique_lock can be regarded as RAII wrapper of lockable objects via pointer and with ownership indicator.
*******************************************************************************
class BankAccount{
public:
void Pay();
void Receive();
void Transfer(BankAccount& rhs, double amount)
private:
std::mutex m_Lock;
long long sort_code;
long long account_no;
std::string name;
std::string postcode
};
void BankAccount::Transfer(BankAccount& rhs, double amount)
{
if (*this == rhs) {
return;
}
// std::lock to lock both mutex
// std::adopt_lock is to tell std::guard to take ownership only
// rather than lock the object in the ctor
std::lock(m_Lock, rhs.m_Lock);
std::lock_guard<std::mutex> lock1(m_Lock, std::adopt_lock);
std::lock_guard<std::mutex> lock2(rhs.m_Lock, std::adopt_lock);
// do other stuff
}
void BankAccount::Transfer(BankAccount& rhs, double amount)
{
if (*this == rhs) {
return;
}
// std::defer_lock to tell std::unique_lock not to lock the object
// just take the ownership
// std::lock is to both mutex
std::unique_lock<std::mutex> lock1(m_Lock, std::defer_lock);
std::unique_lock<std::mutex> lock2(rhs.m_Lock, std::defer_lock);
std::lock(m_Lock, rhs.m_Lock);
// do other stuff
}
*******************************************************************************
Beside std::unique_lock is not copyable but movable but std::lock_guard is neither copyable nor movable. Therefore std::unique_lock takes extra memory, runs slower but is more flexible than std::lock_guard. A typical use of std::lock_gurad as the automatic variables for lock/unlock lockable objects. And std::unique_luck is to take the ownership of lockable objects and transfer the ownership between functions (for instance as a returning object of function).
C++17 solution
A solution to replace the combination of std::lock and std::lock_guard in C++11 is provided in C++17 as std::scoped_lock. It works as a RAII wrapper of std::lock and std::lock_guard in C++11. Very clean and beautiful.
*******************************************************************************
void BankAccount::Transfer(BankAccount& rhs, double amount)
{
if (*this == rhs) {
return;
}
std::scoped_lock sl(m_Lock, rhs.m_Lock);
// do other stuff
}
*******************************************************************************
On my previous blog, Threading - Deadlock, an example of "BankAccount" shows how deadlock is to happen. Account A is to do a transfer to Account B and at the same time Account B is to do one to Account A. The first transaction is to lock A then lock B and do the transfer. The second transaction is to lock B then lock A and do the transfer. There is a good chance that only the first step happened during the two transactions. The first transaction locks A and the second locks B and both try to get the second locking. But fail to do so and two transaction are locked mutually.
The solutions proposed on Threading - Deadlock still work but C++11 and C++17 just have better solutions.
2. C++11 and C++17 Solutions
The solution proposed on Threading - Deadlock is to lock the mutex in the order to guarantee that only one thread can acquire all the resources at once. The solution of C++11 is std::lock, which is able to lock multiple lockable objects at once - in the scenario of none or all.
std::lock either locks all the lockable objects or locks none of them in case of failure (for instance one of lockable objects isn't called in parity of lock/unlock).
C++11 solutions
std::lock can used either with std::lock_guard or std::unique_lock. Comparing std::lock_guard and std::unique_lock, they have similar functionalities. std::lock_guard can be regarded as RAII wrapper of lockable objects via reference and however std::unique_lock can be regarded as RAII wrapper of lockable objects via pointer and with ownership indicator.
*******************************************************************************
class BankAccount{
public:
void Pay();
void Receive();
void Transfer(BankAccount& rhs, double amount)
private:
std::mutex m_Lock;
long long sort_code;
long long account_no;
std::string name;
std::string postcode
};
void BankAccount::Transfer(BankAccount& rhs, double amount)
{
if (*this == rhs) {
return;
}
// std::lock to lock both mutex
// std::adopt_lock is to tell std::guard to take ownership only
// rather than lock the object in the ctor
std::lock(m_Lock, rhs.m_Lock);
std::lock_guard<std::mutex> lock1(m_Lock, std::adopt_lock);
std::lock_guard<std::mutex> lock2(rhs.m_Lock, std::adopt_lock);
// do other stuff
}
void BankAccount::Transfer(BankAccount& rhs, double amount)
{
if (*this == rhs) {
return;
}
// std::defer_lock to tell std::unique_lock not to lock the object
// just take the ownership
// std::lock is to both mutex
std::unique_lock<std::mutex> lock1(m_Lock, std::defer_lock);
std::unique_lock<std::mutex> lock2(rhs.m_Lock, std::defer_lock);
std::lock(m_Lock, rhs.m_Lock);
// do other stuff
}
*******************************************************************************
Beside std::unique_lock is not copyable but movable but std::lock_guard is neither copyable nor movable. Therefore std::unique_lock takes extra memory, runs slower but is more flexible than std::lock_guard. A typical use of std::lock_gurad as the automatic variables for lock/unlock lockable objects. And std::unique_luck is to take the ownership of lockable objects and transfer the ownership between functions (for instance as a returning object of function).
C++17 solution
A solution to replace the combination of std::lock and std::lock_guard in C++11 is provided in C++17 as std::scoped_lock. It works as a RAII wrapper of std::lock and std::lock_guard in C++11. Very clean and beautiful.
*******************************************************************************
void BankAccount::Transfer(BankAccount& rhs, double amount)
{
if (*this == rhs) {
return;
}
std::scoped_lock sl(m_Lock, rhs.m_Lock);
// do other stuff
}
*******************************************************************************
Wednesday, 22 February 2017
C++11 Features - std::thread
1. Creation
To create a thread in C++11 is to create a std::thread object by passing a function and its argument(s). The passing function can be a standalone function, functor, member function or lambda function. And the arguments are following the function as the extra arguments passed into std::thread.
Create std::thread object:
* Standalone Function
A standalone function is the first argument of std::thread and its arguments follow on as the 2nd, 3rd ... arguments of std::thread.
/*****************************************/
void Foo(int x, double y) {}
int x = 1;
double y = 2.0;
std::thread t1(Foo, x, y);
std::thread t2(Foo, 1, 2.0);
/*****************************************/
* Functor
Those programmers work on STL algorithms and iterator should not be unfamiliar with functor. It refers to a callable object. Literally it is a class with overloaded implementation of operator ().
/*****************************************/
struct Bar {
void operator() (int x, double y)
{}
};
Bar b;
int x = 1;
double y = 2.0;
std::thread t3(b, x, y);
std::thread t4(Bar(), 1, 2.0);
/*****************************************/
Most-Vexing Problem in Functor
It is interpreted as a function declaration to take a function pointer that takes no arguments and returns an object Bar as parameter and to return an object of std::thread
The first fix is to use brackets to enforce the compiler to evaluate "Bar()" first to get an object of Bar, then passed as an argument to std::thread.
The second fix is to use initialization list of std::thread to tell compiler explicitly to create/initialize std::thread object.
/*****************************************/
struct Bar {
void operator() ()
{}
};
std::thread(Bar()); // most-vexing problem
std::thread((Bar())); // fix
std::thread{Bar()}; // fix
/*****************************************/
* Member Function
The member function of a class type can be passed as the first argument of std::thread. And the second argument of std::thread has to be one of the following,
- an instance/object of this class type
- a reference to an instance/object of this class type
- a pointer to an instance/object of this class type
/*****************************************/
struct Bar {
void DoWork(int x, double y)
{}
};
Bar b;
int x = 1;
double y = 2.0;
std::thread t1(&B:DoWork, b, x, y);
std::thread t2(&B:DoWork, std::ref(b), x, y);
std::thread t3(&B:DoWork, &b, x, y);
/*****************************************/
* Lambda Function
std::thread can take a lambda function as the first argument. And the lambda's catch defines what has been passed, copy or reference.
/*****************************************/
struct Bar {
void DoWork(int x, double y)
{}
};
Bar b;
int x = 1;
double y = 2.0;
std::thread t1([=](){b.DoWork(x, y);});
std::thread t2([&](){b.DoWork(x, y);});
/*****************************************/
Passing Arugments:
By default std::thread is to make a copy of the passing arguments in the parent thread. Then move the copy into the child thread. Be particular careful about passing by reference. In order to make sure the reference is passed to the function associated with the child thread, std::ref is to be used.
/*****************************************/
void Foo(int x, double& y)
{
y += x;
}
int x = 1;
double y = 2.0;
std::thread t1(Foo, x, y); // y is not updated after Foo() returned
std::thread t1(Foo, x, std::ref(y)); // y is updated as expected
/*****************************************/
For something like a functor has states, then std::ref() or a pointer to the functor is required to pass into std::thread(). Otherwise the object will be copied and the state will only reflected on the newly-copied object in std::thread constrcutor.
/*****************************************/
struct Bar {
int x;
Bar() : x(0)
{}
void Increment() {
++x;
}
};
Bar b;
std::thread t1(&B:DoWork, b); // b.x = 0
std::thread t2(&B:DoWork, std::ref(b)); // b.x incremented by 1
std::thread t3(&B:DoWork, &b, x, y); // b.x incremented by 1
/*****************************************/
2. Destruction
C++11 standard says that std::terminate() is to be called and therefore causes the crash of the program, when std::thread object is destroyed before neither it is an empty object nor it becomes un-joinable. std::thread object has to call std::thread::join() or std::thread::detach() upon itself in order to become un-joinable. Call std::thread::joinable() to query its status.
Join
std::thread::join() is a very strong statement. Literally it says that the caller thread will block itself until the callee thread terminates - becoming un-joinable.
std::thread::join() is the way usually often used to make sure the multi-threading programming terminates gracefully. One of common practice is to join all children threads before returning from main() function.
Detach
std::thread::detach() is to tell this thread is to run in the background as daemon. After calling it std::thread object will become un-joinable and the parent thread will lose the control of the detached children thread because it does not hold a valid reference (std::thread object) to the children any more.
One of solutions to tackle this issue is to use RAII mechanism. Implement a class called like ScopedThread to call std::thread::join() or std::thread::detach() in the destructor if it is joinable.
3. Crashes
Thread Must Be Un-joinable before Out-Of-Life
C++11 standard says that std::terminate() will be called if a thread instance/object is still joinable before it comes out-of-life. This means that a std::thread object must call itself on function join() or detach() before its life comes out of scope, otherwise causes crash.
/*****************************************/
struct Bar {
void DoWork(int x, double y)
{}
};
{
Bar b;
int x = 1;
double y = 2.0;
std::thread t1(&B:DoWork, b, x, y);
// t1.join(); - block here until t1 returns
// t1.deatch(); - t1 runs as a daemon
} // must call join() or deatch() on t1 before hitting here.
/*****************************************/
The Function Associated with std::thread Object Throw Exception but Uncaught
C++11 standard says that any exception cannot be propagated outside of std::thread object. Exceptions have to be caught inside std::thread object, otherwise std::terminated() is called. (C++11 provides other facilities to catch exception thrown outside thread like std::future, std::async, std::packaged_task and etc.)
/*****************************************/
struct Bar {
void DoWork(int x, double y)
{
std::throw logic_error("Causing crash");
}
};
{
Bar b;
int x = 1;
double y = 2.0;
// std::terminated when DoWork() throws
std::thread t1(&B:DoWork, b, x, y);
t1.join(); - block here until t1 returns
}
/*****************************************/
Ownership
std::thread is not copy-able but move-able. The left hand side has to point to an empty or become an un-joinable std::thread object. Otherwise the left hand side std::thread object is to be destroyed when it is still joinable before the right hand side object is moved into it. C++11 standard says this cause std::terminate() to be called.
/*****************************************/
struct Bar {
void DoWork(int x, double y)
{
std::throw logic_error("Causing crash");
}
};
void Foo()
{
// do work
}
{
std::thread t1(Foo);
std::thread t2 = t1; // t1 points to nothing and t2 points to Foo
t1 = std::thread(Foo); // t1 points to Foo too
t2.deatch() // t2 becomes un-joinable now
t2 = std::thread(Foo) // t2 points to Foo too
t2 = t1; // Crash - t2 is still joinable
}
/*****************************************/
4. Deadlock
As I mentioned in Section 2 about std::thread::join(), it is a blocking function. Deadlock will happen if two threads are waiting for each other to terminate before they can carry on further.
/*****************************************/
std::thread t1;
std::thread t2
void Bar()
{
// do some work
t2.join(); // blocking until t2 to finish
// continue work
};
void Foo()
{
// do some work
t1.join(); // blocking until t1 to finish
// continue work
}
// in parent thread
{
t1 = std::thread(Bar);
t2 = std::thread(Foo);
}
/*****************************************/
To create a thread in C++11 is to create a std::thread object by passing a function and its argument(s). The passing function can be a standalone function, functor, member function or lambda function. And the arguments are following the function as the extra arguments passed into std::thread.
Create std::thread object:
* Standalone Function
A standalone function is the first argument of std::thread and its arguments follow on as the 2nd, 3rd ... arguments of std::thread.
/*****************************************/
void Foo(int x, double y) {}
int x = 1;
double y = 2.0;
std::thread t1(Foo, x, y);
std::thread t2(Foo, 1, 2.0);
/*****************************************/
* Functor
Those programmers work on STL algorithms and iterator should not be unfamiliar with functor. It refers to a callable object. Literally it is a class with overloaded implementation of operator ().
/*****************************************/
struct Bar {
void operator() (int x, double y)
{}
};
Bar b;
int x = 1;
double y = 2.0;
std::thread t3(b, x, y);
std::thread t4(Bar(), 1, 2.0);
/*****************************************/
Most-Vexing Problem in Functor
It is interpreted as a function declaration to take a function pointer that takes no arguments and returns an object Bar as parameter and to return an object of std::thread
The first fix is to use brackets to enforce the compiler to evaluate "Bar()" first to get an object of Bar, then passed as an argument to std::thread.
The second fix is to use initialization list of std::thread to tell compiler explicitly to create/initialize std::thread object.
/*****************************************/
struct Bar {
void operator() ()
{}
};
std::thread(Bar()); // most-vexing problem
std::thread((Bar())); // fix
std::thread{Bar()}; // fix
/*****************************************/
* Member Function
The member function of a class type can be passed as the first argument of std::thread. And the second argument of std::thread has to be one of the following,
- an instance/object of this class type
- a reference to an instance/object of this class type
- a pointer to an instance/object of this class type
/*****************************************/
struct Bar {
void DoWork(int x, double y)
{}
};
Bar b;
int x = 1;
double y = 2.0;
std::thread t1(&B:DoWork, b, x, y);
std::thread t2(&B:DoWork, std::ref(b), x, y);
std::thread t3(&B:DoWork, &b, x, y);
/*****************************************/
std::thread can take a lambda function as the first argument. And the lambda's catch defines what has been passed, copy or reference.
/*****************************************/
struct Bar {
void DoWork(int x, double y)
{}
};
Bar b;
int x = 1;
double y = 2.0;
std::thread t1([=](){b.DoWork(x, y);});
std::thread t2([&](){b.DoWork(x, y);});
/*****************************************/
By default std::thread is to make a copy of the passing arguments in the parent thread. Then move the copy into the child thread. Be particular careful about passing by reference. In order to make sure the reference is passed to the function associated with the child thread, std::ref is to be used.
/*****************************************/
void Foo(int x, double& y)
{
y += x;
}
int x = 1;
double y = 2.0;
std::thread t1(Foo, x, y); // y is not updated after Foo() returned
std::thread t1(Foo, x, std::ref(y)); // y is updated as expected
/*****************************************/
For something like a functor has states, then std::ref() or a pointer to the functor is required to pass into std::thread(). Otherwise the object will be copied and the state will only reflected on the newly-copied object in std::thread constrcutor.
/*****************************************/
struct Bar {
int x;
Bar() : x(0)
{}
void Increment() {
++x;
}
};
Bar b;
std::thread t1(&B:DoWork, b); // b.x = 0
std::thread t2(&B:DoWork, std::ref(b)); // b.x incremented by 1
std::thread t3(&B:DoWork, &b, x, y); // b.x incremented by 1
/*****************************************/
As I mentioned above, the reference (via std::ref) or a pointer can be passed into the function associated with the child thread, then it is programmer's responsibility that make sure the passed references or pointers are not referring/pointing to objects which are out-of-life. This causes dangling pointer/reference pointer and causes crashes.
2. Destruction
C++11 standard says that std::terminate() is to be called and therefore causes the crash of the program, when std::thread object is destroyed before neither it is an empty object nor it becomes un-joinable. std::thread object has to call std::thread::join() or std::thread::detach() upon itself in order to become un-joinable. Call std::thread::joinable() to query its status.
Join
std::thread::join() is a very strong statement. Literally it says that the caller thread will block itself until the callee thread terminates - becoming un-joinable.
std::thread::join() is the way usually often used to make sure the multi-threading programming terminates gracefully. One of common practice is to join all children threads before returning from main() function.
Detach
std::thread::detach() is to tell this thread is to run in the background as daemon. After calling it std::thread object will become un-joinable and the parent thread will lose the control of the detached children thread because it does not hold a valid reference (std::thread object) to the children any more.
One of solutions to tackle this issue is to use RAII mechanism. Implement a class called like ScopedThread to call std::thread::join() or std::thread::detach() in the destructor if it is joinable.
3. Crashes
Thread Must Be Un-joinable before Out-Of-Life
C++11 standard says that std::terminate() will be called if a thread instance/object is still joinable before it comes out-of-life. This means that a std::thread object must call itself on function join() or detach() before its life comes out of scope, otherwise causes crash.
/*****************************************/
struct Bar {
void DoWork(int x, double y)
{}
};
{
Bar b;
int x = 1;
double y = 2.0;
std::thread t1(&B:DoWork, b, x, y);
// t1.join(); - block here until t1 returns
// t1.deatch(); - t1 runs as a daemon
} // must call join() or deatch() on t1 before hitting here.
/*****************************************/
No Exception Thrown When Copying Arguments By Default
std::thread is to make a copy of every passing arguments into the function associated with it. C++11 standard says that std::terminated() is to be called if an exception is thrown during the copying process.
/*****************************************/
struct Bar {
Bar(const Bar&) {
std::throw logic_error("Copy inhibited");
}
void DoWork(int x, double y)
{}
};
Bar b;
int x = 1;
double y = 2.0;
// crash as b is passed as an instance and a copy to be made
// when creating std::thread object. But an exception is thrown
// in Bar's copy constructor
std::thread t1(&B:DoWork, b, x, y);
// Fine reference/pointer is passed, Bar's copy-constructor not called
std::thread t2(&B:DoWork, std::ref(b), x, y);
std::thread t3(&B:DoWork, &b, x, y);
/*****************************************/
struct Bar {
Bar(const Bar&) {
std::throw logic_error("Copy inhibited");
}
void DoWork(int x, double y)
{}
};
Bar b;
int x = 1;
double y = 2.0;
// crash as b is passed as an instance and a copy to be made
// when creating std::thread object. But an exception is thrown
// in Bar's copy constructor
std::thread t1(&B:DoWork, b, x, y);
// Fine reference/pointer is passed, Bar's copy-constructor not called
std::thread t2(&B:DoWork, std::ref(b), x, y);
std::thread t3(&B:DoWork, &b, x, y);
/*****************************************/
Dangling Reference or Pointer
This is nothing new for dangling reference/pointer causing crashes. But in std::thread there is one particular situation that need extra care - std::thread::deatch(), It means that a thread is running as daemon. It can still run on background when all other threads go out-of-scope. Make sure the daemon thread is not referring to any automatic variables from any other threads.
/*****************************************/
struct Bar {
void DoWork(int x, double& y)
{
// do some work and reference to y
}
};
{
Bar b;
int x = 1;
double y = 2.0;
// object b is fine as passed as an object and therefore
// an copy is made upon b.
// but y is not ok. its reference is passed and cause dangling
// if DoWork() has not return but t1.deatch() is called and run
// out of this block.
std::thread t1(&B:DoWork, b, x, std::ref(y));
t1.deatch(); - t1 runs as a daemon
}
/*****************************************/
struct Bar {
void DoWork(int x, double& y)
{
// do some work and reference to y
}
};
{
Bar b;
int x = 1;
double y = 2.0;
// object b is fine as passed as an object and therefore
// an copy is made upon b.
// but y is not ok. its reference is passed and cause dangling
// if DoWork() has not return but t1.deatch() is called and run
// out of this block.
std::thread t1(&B:DoWork, b, x, std::ref(y));
t1.deatch(); - t1 runs as a daemon
}
/*****************************************/
C++11 standard says that any exception cannot be propagated outside of std::thread object. Exceptions have to be caught inside std::thread object, otherwise std::terminated() is called. (C++11 provides other facilities to catch exception thrown outside thread like std::future, std::async, std::packaged_task and etc.)
/*****************************************/
struct Bar {
void DoWork(int x, double y)
{
std::throw logic_error("Causing crash");
}
};
{
Bar b;
int x = 1;
double y = 2.0;
// std::terminated when DoWork() throws
std::thread t1(&B:DoWork, b, x, y);
t1.join(); - block here until t1 returns
}
/*****************************************/
Ownership
std::thread is not copy-able but move-able. The left hand side has to point to an empty or become an un-joinable std::thread object. Otherwise the left hand side std::thread object is to be destroyed when it is still joinable before the right hand side object is moved into it. C++11 standard says this cause std::terminate() to be called.
/*****************************************/
struct Bar {
void DoWork(int x, double y)
{
std::throw logic_error("Causing crash");
}
};
void Foo()
{
// do work
}
{
std::thread t1(Foo);
std::thread t2 = t1; // t1 points to nothing and t2 points to Foo
t1 = std::thread(Foo); // t1 points to Foo too
t2.deatch() // t2 becomes un-joinable now
t2 = std::thread(Foo) // t2 points to Foo too
t2 = t1; // Crash - t2 is still joinable
}
/*****************************************/
As I mentioned in Section 2 about std::thread::join(), it is a blocking function. Deadlock will happen if two threads are waiting for each other to terminate before they can carry on further.
/*****************************************/
std::thread t1;
std::thread t2
void Bar()
{
// do some work
t2.join(); // blocking until t2 to finish
// continue work
};
void Foo()
{
// do some work
t1.join(); // blocking until t1 to finish
// continue work
}
// in parent thread
{
t1 = std::thread(Bar);
t2 = std::thread(Foo);
}
/*****************************************/
It is quite similar with the deadlock happening to data-race, when there is cyclic-locking between multiple std::mutex. In this case there is also a cyclic joining between threads. The solution is also quite similar - avoid cyclic joining and always join in an order. Practically join all threads in the main thread.
Friday, 13 January 2017
BTS - Find the Longest Consecutive Path
1. Problem Description
This is a Google interview question for software engineers from careercup. Here is the original thread description,
"
Find longest consecutive path in a binary tree.
1. the path can be decreasing or increasing, i.e [1,2,3,4] and [4,3,2,1] are both valid
2. the path can be child-parent-child, not necessarily a parent-to-child path
similar to this question: http://www.geeksforgeeks.org/longest-consecutive-sequence-binary-tree/
".
2. Data Structure and Algorithm
Pseudo-code
- Generate child-to-parent consecutive depth map for each node
* Find the longest ascending sequence if its left child < itself
* Find the longest descending sequence if its left child > itself
* Find the longest ascending sequence of its right child < itself
* Find the longest descending sequence if its right child > itself
* 0 sequence if any child is null
* 0 sequence if any child is equal to itself
- Find the node with longest consecutive node in above map
* Take the longer sequence if both children has same order sequence
* Sum the sequence if two children has difference order sequence
3. C++ Implementation
Some of utility function and class can be found on (also two similar problems) my two previous posts - BTS - Find the Longest Sequence and BTS - Find the Deepest Path.
// ********************************************************************************
// Implementation
// ********************************************************************************
template <typename T>
size_t GenerateOrderedDepthMap(TreeNode<T> *root, DepthMap<T> &depth)
{
if (!root) {
// special case - NULL pointer
return 0;
}
// depth of this node and save into the map
size_t leftDepth = GenerateOrderedDepthMap(root->left, depth);
size_t rightDepth = GenerateOrderedDepthMap(root->right, depth);
if (leftDepth != 0) {
// ascending order
if (*root->data > *root->left->data) {
auto itFound = depth.find(root->left);
assert(itFound != depth.end());
if (itFound->second.depthOfLeft) {
// ascending order
if (*root->left->data > *root->left->left->data) {
leftDepth = itFound->second.depthOfLeft + 1;
}
}
if (itFound->second.depthOfRight) {
// ascending order
if (*root->left->data > *root->left->right->data) {
if (leftDepth < itFound->second.depthOfRight + 1) {
leftDepth = itFound->second.depthOfRight + 1;
}
}
}
}
else if (*root->data < *root->left->data) {
// descending order
auto itFound = depth.find(root->left);
assert(itFound != depth.end());
if (itFound->second.depthOfLeft) {
// descending order
if (*root->left->data < *root->left->left->data) {
leftDepth = itFound->second.depthOfLeft + 1;
}
}
if (itFound->second.depthOfRight) {
// descending order
if (*root->left->data < *root->left->right->data) {
if (leftDepth < itFound->second.depthOfRight + 1) {
leftDepth = itFound->second.depthOfRight + 1;
}
}
}
}
else {
leftDepth = 0;
}
}
if (rightDepth != 0) {
// descending order
if (*root->data > *root->right->data) {
auto itFound = depth.find(root->right);
assert(itFound != depth.end());
if (itFound->second.depthOfLeft) {
// descending order
if (*root->right->data > *root->right->left->data) {
rightDepth = itFound->second.depthOfLeft + 1;
}
}
if (itFound->second.depthOfRight) {
// descending order
if (*root->right->data > *root->right->right->data) {
if (rightDepth < itFound->second.depthOfRight + 1) {
rightDepth = itFound->second.depthOfRight + 1;
}
}
}
}
else if (*root->data < *root->right->data) {
// ascending order
auto itFound = depth.find(root->right);
assert(itFound != depth.end());
if (itFound->second.depthOfLeft) {
// ascending order
if (*root->right->data < *root->right->left->data) {
rightDepth = itFound->second.depthOfLeft + 1;
}
}
if (itFound->second.depthOfRight) {
// ascending order
if (*root->right->data < *root->right->right->data) {
if (rightDepth < itFound->second.depthOfRight + 1) {
rightDepth = itFound->second.depthOfRight + 1;
}
}
}
}
else {
rightDepth = 0;
}
}
depth.insert(std::make_pair(root, TreeNodeDepth(leftDepth, rightDepth)));
return 1;
}
enum WhichChildToSearch
{
INVALID = 0,
LEFT,
RIGHT,
BOTH
};
template <typename T>
std::list<TreeNode<T>*> FindTheOrderedPathFromRoot(TreeNode<T> *root,
const DepthMap<T> & dm,
const size_t depth)
{
std::list<TreeNode<T>*> path;
if (!root) {
return path;
}
size_t tempDepth = depth;
auto itFound = dm.find(root);
while (itFound != dm.cend()) {
path.push_back(itFound->first);
if (itFound->second.depthOfLeft == tempDepth) {
itFound = dm.find(itFound->first->left);
}
else if (itFound->second.depthOfRight == tempDepth) {
itFound = dm.find(itFound->first->right);
}
if (tempDepth == 0) {
break;
}
--tempDepth;
}
assert(tempDepth == 0);
return path;
}
template <typename T>
std::list<TreeNode<T>*> FindTheLongestOrderedSeq(TreeNode<T> *root)
{
DepthMap<T> dm;
// generate depth map
GenerateOrderedDepthMap(root, dm);
auto itEnd = dm.cend();
TreeNode<T>* nodeFound = NULL;
size_t maxDepth = 0;
WhichChildToSearch maxDepthSearch = INVALID;
size_t tmp;
WhichChildToSearch search = INVALID;
// find the longest consecutive order
for (auto it = dm.cbegin(); it != itEnd; ++it) {
tmp = 0;
if (!it->first->left) {
tmp = it->second.depthOfRight;
search = RIGHT;
}
else if (!it->first->right) {
tmp = it->second.depthOfLeft;
search = LEFT;
}
else {
if ((*it->first->left->data < *it->first->data &&
*it->first->data < *it->first->right->data) ||
(*it->first->left->data > *it->first->data &&
*it->first->data > *it->first->right->data)) {
tmp = it->second.depthOfLeft + it->second.depthOfRight;
search = BOTH;
}
else {
if (it->second.depthOfLeft > it->second.depthOfRight) {
tmp = it->second.depthOfLeft;
search = LEFT;
}
else {
tmp = it->second.depthOfRight;
search = RIGHT;
}
}
}
if (tmp > maxDepth) {
maxDepth = tmp;
maxDepthSearch = search;
nodeFound = it->first;
}
}
// populate the sequence
std::list<TreeNode<T>*> path;
if (nodeFound && maxDepthSearch) {
if (maxDepthSearch == LEFT || maxDepthSearch == RIGHT) {
path = FindTheOrderedPathFromRoot(nodeFound,
dm,
maxDepth);
if (maxDepthSearch == LEFT) {
path.reverse();
}
}
else {
auto itFound = dm.find(nodeFound);
assert(itFound != dm.cend());
path = FindTheOrderedPathFromRoot(nodeFound->left,
dm,
itFound->second.depthOfLeft - 1);
std::list<TreeNode<T>*> rightPath = FindTheOrderedPathFromRoot(
nodeFound,
dm,
itFound->second.depthOfRight);
path.reverse();
path.splice(path.end(), rightPath);
}
assert(path.size() == maxDepth + 1);
}
return path;
}
// ********************************************************************************
// Test
// ********************************************************************************
void TestFindTheLongestOrderedSeq()
{
std::vector<double> input = { 1.0, 2.0, 3.0, 4.0, 5.0 };
TreeNode<double> *root = NULL;
// 3
// 1 4
// 2 5
root = ConstructTreeOnSortedValueBFS(input);
auto path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0 });
input = { 6.0, 7.0, 8.0, 9.0 };
TreeNode<double> *subTree1 = ConstructTreeOnSortedValueDFS(input);
input = { 10.0, 11.0, 12.0, 13.0 , 14.0 };
TreeNode<double> *subTree2 = ConstructTreeRecursive(input);
input = { 15.0, 16.0, 17.0, 18.0 };
TreeNode<double> *subTree3 = ConstructTreeOnSortedValueDFS(input);
input = { 19.0, 20.0, 21.0, 22.0 , 23.0 };
TreeNode<double> *subTree4 = ConstructTreeRecursive(input);
TreeNode<double> *leftestNode = FindLeftestNode(root);
assert(leftestNode != NULL);
leftestNode->left = subTree1;
// 3
// 1 4
// 8 2 5
// 6 9
// 7
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0 });
TreeNode<double> *rightestNode = FindRightestNode(root);
assert(rightestNode != NULL);
rightestNode->left = subTree2;
// 3
// 1 4
// 8 2 5
// 6 9 12
// 7 10 13
// 11 14
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });
TreeNode<double> *firstLeftRighestNode = FindRightestNode(root->left);
assert(firstLeftRighestNode != NULL);
firstLeftRighestNode->right = subTree3;
// 3
// 1 4
// 8 2 5
// 6 9 17 12
// 7 15 18 10 13
// 16 11 14
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });
TreeNode<double> *firstRightLeftestNodeOfS2 = FindRightestNode(subTree2->left);
assert(firstRightLeftestNodeOfS2 != NULL);
firstRightLeftestNodeOfS2->left = subTree4;
// 3
// 1 4
// 8 2 5
// 6 9 17 12
// 7 15 18 10 13
// 16 11 14
// 21
// 19 22
// 20 23
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });
TreeNode<double> *rightestNodeOfS2 = FindRightestNode(subTree2);
assert(rightestNodeOfS2 != NULL);
for (size_t i = 0; i < 8; ++i) {
rightestNodeOfS2->right = new TreeNode<double>(100.0 + i);
rightestNodeOfS2 = rightestNodeOfS2->right;
}
// 3
// 1 4
// 8 2 5
// 6 9 17 12
// 7 15 18 10 13
// 16 11 14
// 21 100
// 19 22 101
// 20 23 102
// 103
// 104
// 105
// 106
// 107
// clean up
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0, 100.0,
101.0, 102.0, 103.0, 104.0, 105.0, 106.0, 107.0});
// clean up
DeleteTree_TD(&root);
}
This is a Google interview question for software engineers from careercup. Here is the original thread description,
"
Find longest consecutive path in a binary tree.
1. the path can be decreasing or increasing, i.e [1,2,3,4] and [4,3,2,1] are both valid
2. the path can be child-parent-child, not necessarily a parent-to-child path
similar to this question: http://www.geeksforgeeks.org/longest-consecutive-sequence-binary-tree/
".
2. Data Structure and Algorithm
Pseudo-code
- Generate child-to-parent consecutive depth map for each node
* Find the longest ascending sequence if its left child < itself
* Find the longest descending sequence if its left child > itself
* Find the longest ascending sequence of its right child < itself
* Find the longest descending sequence if its right child > itself
* 0 sequence if any child is null
* 0 sequence if any child is equal to itself
- Find the node with longest consecutive node in above map
* Take the longer sequence if both children has same order sequence
* Sum the sequence if two children has difference order sequence
3. C++ Implementation
Some of utility function and class can be found on (also two similar problems) my two previous posts - BTS - Find the Longest Sequence and BTS - Find the Deepest Path.
// ********************************************************************************
// Implementation
// ********************************************************************************
template <typename T>
size_t GenerateOrderedDepthMap(TreeNode<T> *root, DepthMap<T> &depth)
{
if (!root) {
// special case - NULL pointer
return 0;
}
// depth of this node and save into the map
size_t leftDepth = GenerateOrderedDepthMap(root->left, depth);
size_t rightDepth = GenerateOrderedDepthMap(root->right, depth);
if (leftDepth != 0) {
// ascending order
if (*root->data > *root->left->data) {
auto itFound = depth.find(root->left);
assert(itFound != depth.end());
if (itFound->second.depthOfLeft) {
// ascending order
if (*root->left->data > *root->left->left->data) {
leftDepth = itFound->second.depthOfLeft + 1;
}
}
if (itFound->second.depthOfRight) {
// ascending order
if (*root->left->data > *root->left->right->data) {
if (leftDepth < itFound->second.depthOfRight + 1) {
leftDepth = itFound->second.depthOfRight + 1;
}
}
}
}
else if (*root->data < *root->left->data) {
// descending order
auto itFound = depth.find(root->left);
assert(itFound != depth.end());
if (itFound->second.depthOfLeft) {
// descending order
if (*root->left->data < *root->left->left->data) {
leftDepth = itFound->second.depthOfLeft + 1;
}
}
if (itFound->second.depthOfRight) {
// descending order
if (*root->left->data < *root->left->right->data) {
if (leftDepth < itFound->second.depthOfRight + 1) {
leftDepth = itFound->second.depthOfRight + 1;
}
}
}
}
else {
leftDepth = 0;
}
}
if (rightDepth != 0) {
// descending order
if (*root->data > *root->right->data) {
auto itFound = depth.find(root->right);
assert(itFound != depth.end());
if (itFound->second.depthOfLeft) {
// descending order
if (*root->right->data > *root->right->left->data) {
rightDepth = itFound->second.depthOfLeft + 1;
}
}
if (itFound->second.depthOfRight) {
// descending order
if (*root->right->data > *root->right->right->data) {
if (rightDepth < itFound->second.depthOfRight + 1) {
rightDepth = itFound->second.depthOfRight + 1;
}
}
}
}
else if (*root->data < *root->right->data) {
// ascending order
auto itFound = depth.find(root->right);
assert(itFound != depth.end());
if (itFound->second.depthOfLeft) {
// ascending order
if (*root->right->data < *root->right->left->data) {
rightDepth = itFound->second.depthOfLeft + 1;
}
}
if (itFound->second.depthOfRight) {
// ascending order
if (*root->right->data < *root->right->right->data) {
if (rightDepth < itFound->second.depthOfRight + 1) {
rightDepth = itFound->second.depthOfRight + 1;
}
}
}
}
else {
rightDepth = 0;
}
}
depth.insert(std::make_pair(root, TreeNodeDepth(leftDepth, rightDepth)));
return 1;
}
enum WhichChildToSearch
{
INVALID = 0,
LEFT,
RIGHT,
BOTH
};
template <typename T>
std::list<TreeNode<T>*> FindTheOrderedPathFromRoot(TreeNode<T> *root,
const DepthMap<T> & dm,
const size_t depth)
{
std::list<TreeNode<T>*> path;
if (!root) {
return path;
}
size_t tempDepth = depth;
auto itFound = dm.find(root);
while (itFound != dm.cend()) {
path.push_back(itFound->first);
if (itFound->second.depthOfLeft == tempDepth) {
itFound = dm.find(itFound->first->left);
}
else if (itFound->second.depthOfRight == tempDepth) {
itFound = dm.find(itFound->first->right);
}
if (tempDepth == 0) {
break;
}
--tempDepth;
}
assert(tempDepth == 0);
return path;
}
template <typename T>
std::list<TreeNode<T>*> FindTheLongestOrderedSeq(TreeNode<T> *root)
{
DepthMap<T> dm;
// generate depth map
GenerateOrderedDepthMap(root, dm);
auto itEnd = dm.cend();
TreeNode<T>* nodeFound = NULL;
size_t maxDepth = 0;
WhichChildToSearch maxDepthSearch = INVALID;
size_t tmp;
WhichChildToSearch search = INVALID;
// find the longest consecutive order
for (auto it = dm.cbegin(); it != itEnd; ++it) {
tmp = 0;
if (!it->first->left) {
tmp = it->second.depthOfRight;
search = RIGHT;
}
else if (!it->first->right) {
tmp = it->second.depthOfLeft;
search = LEFT;
}
else {
if ((*it->first->left->data < *it->first->data &&
*it->first->data < *it->first->right->data) ||
(*it->first->left->data > *it->first->data &&
*it->first->data > *it->first->right->data)) {
tmp = it->second.depthOfLeft + it->second.depthOfRight;
search = BOTH;
}
else {
if (it->second.depthOfLeft > it->second.depthOfRight) {
tmp = it->second.depthOfLeft;
search = LEFT;
}
else {
tmp = it->second.depthOfRight;
search = RIGHT;
}
}
}
if (tmp > maxDepth) {
maxDepth = tmp;
maxDepthSearch = search;
nodeFound = it->first;
}
}
// populate the sequence
std::list<TreeNode<T>*> path;
if (nodeFound && maxDepthSearch) {
if (maxDepthSearch == LEFT || maxDepthSearch == RIGHT) {
path = FindTheOrderedPathFromRoot(nodeFound,
dm,
maxDepth);
if (maxDepthSearch == LEFT) {
path.reverse();
}
}
else {
auto itFound = dm.find(nodeFound);
assert(itFound != dm.cend());
path = FindTheOrderedPathFromRoot(nodeFound->left,
dm,
itFound->second.depthOfLeft - 1);
std::list<TreeNode<T>*> rightPath = FindTheOrderedPathFromRoot(
nodeFound,
dm,
itFound->second.depthOfRight);
path.reverse();
path.splice(path.end(), rightPath);
}
assert(path.size() == maxDepth + 1);
}
return path;
}
// ********************************************************************************
// Test
// ********************************************************************************
void TestFindTheLongestOrderedSeq()
{
std::vector<double> input = { 1.0, 2.0, 3.0, 4.0, 5.0 };
TreeNode<double> *root = NULL;
// 3
// 1 4
// 2 5
root = ConstructTreeOnSortedValueBFS(input);
auto path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0 });
input = { 6.0, 7.0, 8.0, 9.0 };
TreeNode<double> *subTree1 = ConstructTreeOnSortedValueDFS(input);
input = { 10.0, 11.0, 12.0, 13.0 , 14.0 };
TreeNode<double> *subTree2 = ConstructTreeRecursive(input);
input = { 15.0, 16.0, 17.0, 18.0 };
TreeNode<double> *subTree3 = ConstructTreeOnSortedValueDFS(input);
input = { 19.0, 20.0, 21.0, 22.0 , 23.0 };
TreeNode<double> *subTree4 = ConstructTreeRecursive(input);
TreeNode<double> *leftestNode = FindLeftestNode(root);
assert(leftestNode != NULL);
leftestNode->left = subTree1;
// 3
// 1 4
// 8 2 5
// 6 9
// 7
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0 });
TreeNode<double> *rightestNode = FindRightestNode(root);
assert(rightestNode != NULL);
rightestNode->left = subTree2;
// 3
// 1 4
// 8 2 5
// 6 9 12
// 7 10 13
// 11 14
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });
TreeNode<double> *firstLeftRighestNode = FindRightestNode(root->left);
assert(firstLeftRighestNode != NULL);
firstLeftRighestNode->right = subTree3;
// 3
// 1 4
// 8 2 5
// 6 9 17 12
// 7 15 18 10 13
// 16 11 14
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });
TreeNode<double> *firstRightLeftestNodeOfS2 = FindRightestNode(subTree2->left);
assert(firstRightLeftestNodeOfS2 != NULL);
firstRightLeftestNodeOfS2->left = subTree4;
// 3
// 1 4
// 8 2 5
// 6 9 17 12
// 7 15 18 10 13
// 16 11 14
// 21
// 19 22
// 20 23
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });
TreeNode<double> *rightestNodeOfS2 = FindRightestNode(subTree2);
assert(rightestNodeOfS2 != NULL);
for (size_t i = 0; i < 8; ++i) {
rightestNodeOfS2->right = new TreeNode<double>(100.0 + i);
rightestNodeOfS2 = rightestNodeOfS2->right;
}
// 3
// 1 4
// 8 2 5
// 6 9 17 12
// 7 15 18 10 13
// 16 11 14
// 21 100
// 19 22 101
// 20 23 102
// 103
// 104
// 105
// 106
// 107
// clean up
path = FindTheLongestOrderedSeq(root);
TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0, 100.0,
101.0, 102.0, 103.0, 104.0, 105.0, 106.0, 107.0});
// clean up
DeleteTree_TD(&root);
}
Monday, 9 January 2017
DSA - Minimal Swaps to Reach Desired Position
1. Problem Description
This is a Google interview question for software engineer from careercup. Here is the original thread, "
An interesting question asked in Google’s phone interview : suppose a row of parking lot with n spots, one of them is empty and n-1 spots are occupied with cars. Only one operation is allowed: move one car from its position to the empty spot. Given a initial order of cars and a final order, output steps needed to convert initial order to final oder with that operation.
Follow up: Minimize steps needed.
ex:
{1 2 3 -1 4 5}
move car 1 to empty spot(denoted as -1) will make it {-1,2,3,1,4,5}
push 1 to the output list because you move car 1 to the empty spot
suppose you have a initial order {1 2 3 -1 4 5} and a final order {5,1,-1,3,2,4}, you need to transfer {1 2 3 -1 4 5} to {5,1,-1,3,2,4}, push each car moved into a output list.
".
2. Data Structure and Algorithm
Let's start from the simple cases. "-1" represents the empty space and "A, B, C, ......" represents the location of cars.
- One car
Desired position:
(-1, A)
Initial position:
1. (A, -1) - 1 swap
- Two cars
Desired position:
(-1, A, B)
Initial position:
1. (A, B, -1)
- all 3 out of position, then 2 swaps
2. (B, A, -1)
- A is at the same position, then become "One car" case and need 1 swap
3. (A, -1, B)
- B is at the same position, then become "One car" case and need 1 swap
4. (B, -1, A)
- all 3 out of position, then 2 swaps
5. (-1, B, A)
- -1 is at the same position
- swapping -1 with B becomes Case 4
- 1 + 2 = 3 swaps
- Three cars
Desired position:
(-1, A, B, C)
Initial position:
1. (A, B, C, -1)
- all 4 out of position - 3 swaps
2. (A, C, B, -1)
- all 4 out of position - 3 swaps
3. (B, A, C, -1)
- A is at the same position and become "Two cars" case - 2 swaps
4. (B, C, A, -1)
- all 4 out of position - 3 swaps
5. (C, A, B, -1)
- Both A and B are at the same position, become "One car" case - 1 swap
6. (C, B, A, -1)
- all 4 out of position - 3 swaps
7. (A, B, -1, C)
- C is at the same position and become "Two cars" case - 2 swap
8. (A, C, -1, B)
- all 4 out of position - 3 swaps
9. (B, A, -1, C)
- A and C are at the same position and become "One car" case - 1 swap
10. (B, C, -1, A)
- all 4 out of position - 3 swaps
11. (C, A, -1, B)
- A is at the same position and become "Two cars" case - 2 swaps
12. (C, B, -1, A)
- all 4 out of position - 3 swaps
13. (A, -1, B, C)
- B and C are at the same position and become "One car" case - 1 swap
14. (A, -1, C, B)
- all 4 out of position - 3 swaps
15. (B, -1, A, C)
- C is at the same position and become "Two cars" case - 2 swap
16. (B, -1, C, A)
- all 4 out of position - 3 swaps
17. (C, -1, A, B)
- all 4 out of position - 3 swaps
18. (C, -1, B, A)
- B is a the same position then become "Two cars" case - 2 swaps
19. (-1, A, C, B)
- A is at the same position, then becomes "Two car" case 5
- 3 swaps
20. (-1, B, A, C)
- C is at the same position, then becomes "Two car" case 5
- 3 swaps
21. (-1, B, C, A)
- Swapping -1 and B becomes case 16
- 1 + 3 = 4 swaps
22. (-1, C, A, B)
- Swapping -1 and C becomes case 17
- 1 + 3 = 4 swaps
23. (-1, C, B, A)
- B is at the same position, then becomes "Two car" case 5
- 3 swaps
Here is the conclusion to make:
1.If cars and empty space are not at the same position, then N cars needs N swaps to reach the desired position.
2. If empty space is at the same position but all cars are not, then N cars needs N+1 swaps to reach the desired position.
3. If there are cars at the same position, then remove them and reduce N to M. And take the case as of in 1 or 2.
Pseudo-code:
1. Remove all the cars at the same position between initial position and desired position
2. N as the all cars and M as after removing the cars at the same positions
- return M if -1 is not at the same position
- return M + 1 if -1 is at the same position.
This is a Google interview question for software engineer from careercup. Here is the original thread, "
An interesting question asked in Google’s phone interview : suppose a row of parking lot with n spots, one of them is empty and n-1 spots are occupied with cars. Only one operation is allowed: move one car from its position to the empty spot. Given a initial order of cars and a final order, output steps needed to convert initial order to final oder with that operation.
Follow up: Minimize steps needed.
ex:
{1 2 3 -1 4 5}
move car 1 to empty spot(denoted as -1) will make it {-1,2,3,1,4,5}
push 1 to the output list because you move car 1 to the empty spot
suppose you have a initial order {1 2 3 -1 4 5} and a final order {5,1,-1,3,2,4}, you need to transfer {1 2 3 -1 4 5} to {5,1,-1,3,2,4}, push each car moved into a output list.
".
2. Data Structure and Algorithm
Let's start from the simple cases. "-1" represents the empty space and "A, B, C, ......" represents the location of cars.
- One car
Desired position:
(-1, A)
Initial position:
1. (A, -1) - 1 swap
- Two cars
Desired position:
(-1, A, B)
Initial position:
1. (A, B, -1)
- all 3 out of position, then 2 swaps
2. (B, A, -1)
- A is at the same position, then become "One car" case and need 1 swap
3. (A, -1, B)
- B is at the same position, then become "One car" case and need 1 swap
4. (B, -1, A)
- all 3 out of position, then 2 swaps
5. (-1, B, A)
- -1 is at the same position
- swapping -1 with B becomes Case 4
- 1 + 2 = 3 swaps
- Three cars
Desired position:
(-1, A, B, C)
Initial position:
1. (A, B, C, -1)
- all 4 out of position - 3 swaps
2. (A, C, B, -1)
- all 4 out of position - 3 swaps
3. (B, A, C, -1)
- A is at the same position and become "Two cars" case - 2 swaps
4. (B, C, A, -1)
- all 4 out of position - 3 swaps
5. (C, A, B, -1)
- Both A and B are at the same position, become "One car" case - 1 swap
6. (C, B, A, -1)
- all 4 out of position - 3 swaps
7. (A, B, -1, C)
- C is at the same position and become "Two cars" case - 2 swap
8. (A, C, -1, B)
- all 4 out of position - 3 swaps
9. (B, A, -1, C)
- A and C are at the same position and become "One car" case - 1 swap
10. (B, C, -1, A)
- all 4 out of position - 3 swaps
11. (C, A, -1, B)
- A is at the same position and become "Two cars" case - 2 swaps
12. (C, B, -1, A)
- all 4 out of position - 3 swaps
13. (A, -1, B, C)
- B and C are at the same position and become "One car" case - 1 swap
14. (A, -1, C, B)
- all 4 out of position - 3 swaps
15. (B, -1, A, C)
- C is at the same position and become "Two cars" case - 2 swap
16. (B, -1, C, A)
- all 4 out of position - 3 swaps
17. (C, -1, A, B)
- all 4 out of position - 3 swaps
18. (C, -1, B, A)
- B is a the same position then become "Two cars" case - 2 swaps
19. (-1, A, C, B)
- A is at the same position, then becomes "Two car" case 5
- 3 swaps
20. (-1, B, A, C)
- C is at the same position, then becomes "Two car" case 5
- 3 swaps
21. (-1, B, C, A)
- Swapping -1 and B becomes case 16
- 1 + 3 = 4 swaps
22. (-1, C, A, B)
- Swapping -1 and C becomes case 17
- 1 + 3 = 4 swaps
23. (-1, C, B, A)
- B is at the same position, then becomes "Two car" case 5
- 3 swaps
Here is the conclusion to make:
1.If cars and empty space are not at the same position, then N cars needs N swaps to reach the desired position.
2. If empty space is at the same position but all cars are not, then N cars needs N+1 swaps to reach the desired position.
3. If there are cars at the same position, then remove them and reduce N to M. And take the case as of in 1 or 2.
Pseudo-code:
1. Remove all the cars at the same position between initial position and desired position
2. N as the all cars and M as after removing the cars at the same positions
- return M if -1 is not at the same position
- return M + 1 if -1 is at the same position.
Subscribe to:
Posts (Atom)