Friday Programming Quiz [modified]
-
As currently I am working on asynchronous programming (and my mind is spinning), this quiz is about a simple async programming problem. Given:
//C# delegates
delegate void ActionComplete();
delegate void Action(ActionComplete onComplete);Functions conforming to
Actionexecute asynchronously and invoke the function supplied in theonCompleteparameter when complete. For Example, the followingProcessReportfunction conforms to the delegateAction.void ProcessReport(ActionComplete onReportProcessed)
{
//Start a thread to do actual processing and return
//Call onReportProcessed from the thread when processing is done
}Now the real problem: You have a an array of such asynchronous functions and the objective is to execute them one by one in order and call a callback when all the functions have finished executing.
void ExecuteActions(Action[] actions, ActionComplete onAllActionsComplete)
{
}onAllActionsCompleteshould be called only once when all the actions have finished executing in order. If there are 3 actions,onAllActionsCompleteshould be called whenactions[2]completes,actions[2]should start afteractions[1]completes,actions[1]should start whenactions[0]completes.actions[0]should start first. -------------------------------------- Here is a C++ STL solution to last weeks quiz[^]. It is almost as simple as the python or haskell solution.bool SameSetOfCharacters(string str1, string str2)
{
typedef CharSet std::set<char>;
return CharSet(str1.begin(), str1.end()) == CharSet(str2.begin(), str2.end());
}-- modified at 16:57 Friday 17th November, 2006
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. -Brian Kernighan
Funny, I have a very similar problem to solve, with regards to re-encoding a movie into a different format, that must first be indexed, then multiple threads can run to actually encode the movie in different speed formats, and when all the encoding is done, the database is notified that the entire process is complete. And to make matters more interesting, the threads have to be prioritized so that certain encodes are done first, and the system optimizes encoding by creating one thread per CPU. Anyways, I ended up using a priority queue to generate the task list and then a separate process pulls tasks off and assigns them to processors. When the task is complete, the thread notifies the queue processor that it can assign a new task. In your particular case, I'd probably just wire up an event to notify a worker thread that the task was done, set up and an index for the first task, do the task, increment, do the next task, etc., then call the actions complete event. Marc
People are just notoriously impossible. --DavidCrow
There's NO excuse for not commenting your code. -- John Simmons / outlaw programmer
People who say that they will refactor their code later to make it "good" don't understand refactoring, nor the art and craft of programming. -- Josh Smith -
Now I'm curious. Why would you say that this isn't efficient? Robert
Actually, efficent may have been a poor choice of word. I should have said not really the best solution. The problem is that one thread is used up by the wait handle and nothing can execute on that thread. For situations like ASP.NET where there are some set threads that work on request processing, a vital request processing thread will be used up just for waiting.
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. -Brian Kernighan
-
Funny, I have a very similar problem to solve, with regards to re-encoding a movie into a different format, that must first be indexed, then multiple threads can run to actually encode the movie in different speed formats, and when all the encoding is done, the database is notified that the entire process is complete. And to make matters more interesting, the threads have to be prioritized so that certain encodes are done first, and the system optimizes encoding by creating one thread per CPU. Anyways, I ended up using a priority queue to generate the task list and then a separate process pulls tasks off and assigns them to processors. When the task is complete, the thread notifies the queue processor that it can assign a new task. In your particular case, I'd probably just wire up an event to notify a worker thread that the task was done, set up and an index for the first task, do the task, increment, do the next task, etc., then call the actions complete event. Marc
People are just notoriously impossible. --DavidCrow
There's NO excuse for not commenting your code. -- John Simmons / outlaw programmer
People who say that they will refactor their code later to make it "good" don't understand refactoring, nor the art and craft of programming. -- Josh SmithActually my problem was in JavaScript/Ajax so I could not create threads. But it was fun to solve using anonymous functions and closures. PS I am sorry for hijacking the Friday Programming Quiz started by you.
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. -Brian Kernighan
-
Actually, efficent may have been a poor choice of word. I should have said not really the best solution. The problem is that one thread is used up by the wait handle and nothing can execute on that thread. For situations like ASP.NET where there are some set threads that work on request processing, a vital request processing thread will be used up just for waiting.
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. -Brian Kernighan
Hi, if I understand you correctly one could overcome this problem by starting another thread where the waiting takes place. Thus the request processing thread won't be blocked. Nevertheless I agree that there is one thread more active than necessary. The best solution definitely depends on the context where the code is executed in. To be honest I also tried to just get the shortest solution I could think of. I think regarding this my code should be in the premier league :laugh:. Robert
-
Hi, if I understand you correctly one could overcome this problem by starting another thread where the waiting takes place. Thus the request processing thread won't be blocked. Nevertheless I agree that there is one thread more active than necessary. The best solution definitely depends on the context where the code is executed in. To be honest I also tried to just get the shortest solution I could think of. I think regarding this my code should be in the premier league :laugh:. Robert
Robert Rohde wrote:
I think regarding this my code should be in the premier league .
Sure! So far it is the shortest. But the no-wait solution is also possible with probably same amount of code in LINQ/JavaScript. I want to see whether the LINQ Boy[^] or the JavaScript Man [^] to come up with it.
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. -Brian Kernighan
-
As currently I am working on asynchronous programming (and my mind is spinning), this quiz is about a simple async programming problem. Given:
//C# delegates
delegate void ActionComplete();
delegate void Action(ActionComplete onComplete);Functions conforming to
Actionexecute asynchronously and invoke the function supplied in theonCompleteparameter when complete. For Example, the followingProcessReportfunction conforms to the delegateAction.void ProcessReport(ActionComplete onReportProcessed)
{
//Start a thread to do actual processing and return
//Call onReportProcessed from the thread when processing is done
}Now the real problem: You have a an array of such asynchronous functions and the objective is to execute them one by one in order and call a callback when all the functions have finished executing.
void ExecuteActions(Action[] actions, ActionComplete onAllActionsComplete)
{
}onAllActionsCompleteshould be called only once when all the actions have finished executing in order. If there are 3 actions,onAllActionsCompleteshould be called whenactions[2]completes,actions[2]should start afteractions[1]completes,actions[1]should start whenactions[0]completes.actions[0]should start first. -------------------------------------- Here is a C++ STL solution to last weeks quiz[^]. It is almost as simple as the python or haskell solution.bool SameSetOfCharacters(string str1, string str2)
{
typedef CharSet std::set<char>;
return CharSet(str1.begin(), str1.end()) == CharSet(str2.begin(), str2.end());
}-- modified at 16:57 Friday 17th November, 2006
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. -Brian Kernighan
As you suspected, this sort of thing is trivial in JS. Of course, it helps that JS is single-threaded, but functions as objects and closures make it even easier. Here's a quick-and-dirty (read: untested) solution:
function ExecuteActions(actions, onAllActionsComplete)
{
var loop = function(i)
{
if ( i < actions.length )
actions[i](function() { loop(i+1) });
else
onAllActionsComplete();
}
loop(0);
} -
As you suspected, this sort of thing is trivial in JS. Of course, it helps that JS is single-threaded, but functions as objects and closures make it even easier. Here's a quick-and-dirty (read: untested) solution:
function ExecuteActions(actions, onAllActionsComplete)
{
var loop = function(i)
{
if ( i < actions.length )
actions[i](function() { loop(i+1) });
else
onAllActionsComplete();
}
loop(0);
}Exactly, this is what I ended up implementing in JS (hence the quiz). :) BTW my version looked something like following:
function ExecuteActions(actions, onAllActionsComplete) {
var i = 0;
function nextAction() {
if ( i < actions.length )
actions[i++](nextAction);
else
onAllActionsComplete();
}
nextAction();
}
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. -Brian Kernighan
-
Exactly, this is what I ended up implementing in JS (hence the quiz). :) BTW my version looked something like following:
function ExecuteActions(actions, onAllActionsComplete) {
var i = 0;
function nextAction() {
if ( i < actions.length )
actions[i++](nextAction);
else
onAllActionsComplete();
}
nextAction();
}
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. -Brian Kernighan
-
Actually my problem was in JavaScript/Ajax so I could not create threads. But it was fun to solve using anonymous functions and closures. PS I am sorry for hijacking the Friday Programming Quiz started by you.
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. -Brian Kernighan
Rama Krishna Vavilala wrote:
I am sorry for hijacking the Friday Programming Quiz started by you.
No need to apologize! You're doing a fantastic job! :) Marc
People are just notoriously impossible. --DavidCrow
There's NO excuse for not commenting your code. -- John Simmons / outlaw programmer
People who say that they will refactor their code later to make it "good" don't understand refactoring, nor the art and craft of programming. -- Josh Smith -
Matt Gerrans wrote:
Isn't this a programming question
This is a programming quiz. The purpose is to have fun. The problems presented here are too trivial.
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. -Brian Kernighan
Sorry, I intended that to be a (good natured) parody of the Lounge posting police, but that apparently didn't work very well. :-O I do like the Programming Quiz and encourage you to continue! In fact, I'll provide a Python[^] (as usual) answer:
def ExecuteActions( actions, onAllActionsComplete ):
def doActions(actions):
if actions:
actions[0]( lambda: doActions(actions[1:]) )
else:
onAllActionsComplete()
doActions(actions)(My first answer worked, but was a lot more clunky; this is what occurred to me after pondering it a bit more.) Also, here is the code to test drive it:
def onAllActionsComplete():
print 'onAllActionsComplete!'actions = []
for l in 'abc':
exec( 'def %s(o):\n\tprint "%s!"\n\to()\nactions.append(%s)' % ((l,)*3) )ExecuteActions( actions, onAllActionsComplete )
(This could be made a little more terse by using lambda more, but that wouldn't necessarily be better.) By the way, thanks to IronPython[^], this would be an easy way to do it in .NET.
Matt Gerrans