I think that Apache under GPL would have a higher market share, for 3 reasons:
a) There wouldn't be big proprietary forks such as WebSphere splitting the user and resource base. Bg companies such as IBM wanting to get involved would have to contribute to the main tree.
b) Several talented developers might have contributed to a GPL-based Apache when they wouldn't otherwise, thus making it a better product. If I write something the I want to be free for the rest of the world to use, I don't want someone else taking it proprietary.... hance GPL is perfect for this philosophy.
c) Apache and Linux under the same license might have reduced the developer hours wasted over licensing flamewars:-)
That's certainly a good conspiracy theory but AFAIK not proved.
What is certain is that Microsoft (and Sun!) paid SCO quite a few millions for "intellectual property licenses" which makes them pretty major backers in the sense of supporting SCO's business if not in the financial sense.
There's probably a commercial reason (companies agreed to support a common standard or something like that?).
There's also a problem with compression ratios - PNG is lossless so it's improssible to compress beyond a certain point. With JPG you have much more ability to choose a point on the compression/quality tradeoff curve.
Yep - just shows the power of the free market once again!
Think how little progress we'd see if large segments of the IT industry were dominated by single large corporations with no incentive to innovate..... oh wait.....
That's an eminently sensible suggestion, and something that I've beleived for a long time.
Just to add one point: It would also resolve all the stupid and expensive legal conflicts resulting from disputes over trademarks in completely different industries or different countries, where there is absolutely no risk of consumers being confused.
Hmmm... suspected it might be something like that, though I did get it working before with WinCVS (nice little free tool BTW for people like me who like developing with GUIs).
Guess I'll just keep plugging away till I find some configuration that works...
...and it keeps getting better and better. I'm off to download my copy right now!
I seriously think that more open source developers should get behind eclipse, even if they don't use Java as their primary language. Right now it's probably the *only* free software IDE that has the potential to match Visual Studio, which like it or not is an awesome product for developers.
Want to contribute to open source? Write some quality plugins for eclipse and you can't go far wrong.
Meanwhile, does anyone have any tips for getting Eclipse for Sourceforge? I'm using it for my own little free software project but haven't been able to connect the damn thing to CVS. Perhaps v3.0 has fixed that?
It's a pretty basic principle that in order to have a fair contract, a person must have a full understanding of what they are agreeing to. Free markets require informed consent on every transaction in order to work effectively.
In general that's not the case. That's a fundamental flaw with EULAs - people simply don't read them.
On top of that - people make mistakes. Perhaps just *once* you forget to tick the no spyware checkbox. Do you therefore deserve a permanently compromised machine?
This all makes Spyware look like a deceptive trade practice in my book. Even if people do install it themselves, they've almost cetainly been duped into doing so.
I agree they aren't going to get very close to a perfect fitness function.
But what this kind of technique could be really great for is in-race optimisation. Can't decide whether the come in for a pit stop this lap or the next? Let the GA run a few hundred thousand simulations of the possible ways the race will progress and get a probablity weighted average of the payoffs from each strategy, taking into account current race position, likely pit-stop times, track condition etc.
However, holding patents for defensive purposes isn't much use against pure "IP litigation" companies.
Since these companies don't produce actual products they can't be caught out for infringing any of your patents.
It's only really useful against other large companies (e.g. IBM) since it gives you better bargaining power for cross-licensing. And for locking out new competitors, of course:-)
Not much about investor confidence. Mostly it says a lot about the deficiencies of accounting in capturing the real value of a company.
The value of assets on the balance sheet are determined by a multitude of archaic accounting rules, so don't actually correspond very closely to the real value of the assets. Some assets like human capital, brand and intellectual property don't appear on the balance sheet at all.
For example, Red Hat has a pretty good brand for a company of its size, which isn't included in the assets but contributes a lot to the market cap.
There's also the issue of how much debt a company has (which can allow it to purchase more assets without a corresponding increase in market cap) which can distort comparisons like this. Though IIRC neither Sun nor Red Hat has much debt in this case.
In theory, a company's Assets should be equal to the value of its Liabilities(Debt) plus its Market Cap, but in practice it never works out that way for all the reasons mentioned above.
Your algorithm is of course O(1) but it doesn't allow for differing priority levels between processes. You need this if you want high priority processes to pre-empt low priority background processes at appropriate moments, which is pretty much essential for real-time or interactive applications.
The Linux O(1) scheduler does this. It implements a queue for each of 140 different priority levels, and then using an O(1) technique to find the queue with the highest priority that still contains a process waiting to run. It doesn't distinguish between processes in the same priority level, so effectively it's doing round-robin for processes of the same priority.
I think the Linux scheduler is pretty excellent from an algorithmic perspective. I don't see any really big trade-offs that have been made. You could write a faster, simpler scheduler that was optimized to handle a very small number of processes but that wouldn't scale well and could only really make sense for specialised embedded applications.
Remember that the real overhead in scheduling typically isn't actually the algorithm itself - it's the large cost of doing context switches, cache flushes etc involved in switching to a new process.
You therefore gain far more by making intelligent scheduling decisions than by squeezing a few cycles out of the scheduler itself. There's therefore still plenty to be done in the fine tuning of the current O(1) scheduler, e.g. getting the best scheduling behaviour for particular classes of processor architecture or application workload.
Note though that there's an advantage to the linux scheduler method over a priority queue: although both can access the (joint) highest priority process in O(1) time, it generally takes O(ln n) time to insert/delete a process in a priority queue, whereas the linux scheduler technique can do this in O(1) time as well.
I have to say that I still think that humans and computers use essentially the same algorithm. Even the very best chess players search and prune a tree of moves.
Of course, grandmasters don't think of this as searching and pruning a tree, but that's what they are doing subconciously. If they didn't, they'd get obliterated in tactical exchanges.
The main difference between the human and computer tree searches is simply that the computers are far better (faster) at searching while the humans are far better at pruning and evaluation (thanks to the pattern matching you mention).
Humans simply ignore (prune) the vast majority of possible moves, so their "search tree" has a very low branching factor. I wouldn't be surprised if the average was less than 2 for top players, so they can look very deeply into a position without considering many alternative lines.
The other advantage that humans have is that they are much better at considering "strategic" aspects when evaluationg a position. It's very hard to get computers to recognise these. But in effect, this just means that the human has a much better evaluation function, so this is still consistent with the fundamental tree search approach. Like the parent post says, this ability doubtless involves considering groups of pieces using pattern matching etc.
The other interesting thing that humans do is remember aspects of the position which they subconciously make use of while doing move search and position evaluation, e.g. the existence of a pin or potential fork threat. My own style of play uses this quite a bit - I like to look for threats and weaknesses then try to find lines that will help me exploit them.
In this way, humans seem to be doing a kind of "directed search" which is theoretically possible in a computer's tree search but I've never seen actually implemented in computer chess. Anyone seen anything like this in a tree search algorithm? I think there could be potential for research in this area.
I've written a simple Go-playing computer program so can offer some insights.
Basically, evaluating the position is *very* difficult. You certainly can't use simple heuristics like "number of stones" because certain stones may be guaranteed or likely to die.
You can't really use localised evaluation functions because stones right on the other side of the board can often affect your valuation.
There's also the concept of "ko threats" which are valuable even if the opponent has a guaranteed way to protect a group of stones.
Given all of this, I don't think it's feasible for a human to write a sensible evaluation function for a general go position. I think the problem will ultimately be cracked, but it'll need some proper AI techniques such as genetic algorithms to "learn" an evaluation function.
Re:Especially in the fog of marketese that is .NET
on
Advanced .NET Remoting
·
· Score: 4, Informative
Broadly speaking, it's the ability to call methods on remote objects (e.g. a separate machine over the network). Think of it as something like Java RMI. The framework takes care of things like serializing the parameters and return values.
I think it's a decent technology for the right kind of applications, e.g. a cluster of servers that need to share data. However, if you want to expose services to other systems in a more general way, web services are probably a much better way to go.
The obvious solution to that technical hitch is to publicly cancel your starwars laser project but carry on building it in secret with the hope that your opponents will not bother to paint their missiles a nice shiny colour.
Would only work once, but the short term advantage might be decisive.
I agree with you in that AI and physics are definitely the big things in the next generation of games.
Haveing said that, it's still quite tricky to write games to take advantage of multi-threaded operations. Your physics engine can't very easily go around moving bits of geometry around while another thread is rendering the scene or you could get into all kinds of trouble.
Of course, you can get around all this with clever locking, timeslicing and making copies of game state etc. but this all adds overhead both in terms of clock cycles and development time.
My guess is that it'll still be a while before any significant number of games really make the most out of multiple processors.
On the contrary, it sometimes makes sense to code before you design.
I rather like the XP approach of designing only when you need to, and refactoring when you come across something you need to change. In my experience this is far more productive than lengthy design processes.
The knowledge that you will have to refactor tends to push you towards writing very clean and modular code from the outset, so design changes are usually very simple to implement.
Often the thorniest design decisions you will have to make only become apparent when you have a functioning prototype system and really start to understand the key implementation issues. There's nothing like a bunch of automated tests (another key XP practice) to help you here.
Yeah, sometimes you might have to tear up a whole subsystem and start again, but even then you will have learned more than you ever could have through a paper exercise. You've also probably spent less time doing this than you would have done on a single upfront design phase.
Agreed, though I would argue that it's the complexity and the heterogeneity of human decision making rules that make them more difficult to predict, rather than their ability to reason per se.
Rationality isn't really an issue - it can be considered just another decision rule that can be formulated pretty much as "do whatever is in my best interest" where best interest is defined to include the value gained (if any?!?) from helping others, altruism etc.
Many experts in the field of rationality and choice theory would of course argue that humans are not fully rational and frequently make decisions not ultimately in their own interests. People are for example generally bad at making tradeoffs between short and long term goals, and also at evaluating risks.
This shouldn't be taken as an argument for paternalism, but rather that the ability of an individual to calculate the outcomes of their decisions is not good enough to calculate the best decision in a limited time with imperfect information.
Basically humans seem to operate on the level of "bounded rationality" where they operate according to fairly simple "rules of thumb" and only deviate from these when they experience or anticipate a significant positive or negative outcome that encourages them to think more carefully about the issue. After which, of course, they devise a slightly more sophisticated rule of thumb and continue as before.....
Re:Dijkstra's Algorithm: All-pairs, shortest-path
on
Deep Algorithms?
·
· Score: 2
I agree that radix sorting rocks.
I remember a programming contest where I had to sort a *huge* list of words into length order.
My algorithm was by far the fastest. Most fools seemed to think that you need painfully slow O(n log n) time algotithms like QuickSort for sorting.:-)
Don't think the "if (a!=b)" is a good idea in many cases.
Isn't the other great advantage of your variable swapping algorithm to avoid a branch instruction which is costly on some architectures?
Re:Euclid's Algorithm?
on
Deep Algorithms?
·
· Score: 3, Interesting
GCD is used for simplifying rational numbers. So it's used in pretty much any decent maths library.
And rational numbers have a *lot* of uses. CAD, spreadsheets, high precision calculations, financial figures where rounding is unacceptable etc.
I expect GCD also has implications for packing problems and complex scheduling algorithms where you need a quick check on which items are likely to "fit" together effectively. Anyone have experience of this?
Slashdot Mirror
How are you so sure?
:-)
I think that Apache under GPL would have a higher market share, for 3 reasons:
a) There wouldn't be big proprietary forks such as WebSphere splitting the user and resource base. Bg companies such as IBM wanting to get involved would have to contribute to the main tree.
b) Several talented developers might have contributed to a GPL-based Apache when they wouldn't otherwise, thus making it a better product. If I write something the I want to be free for the rest of the world to use, I don't want someone else taking it proprietary.... hance GPL is perfect for this philosophy.
c) Apache and Linux under the same license might have reduced the developer hours wasted over licensing flamewars
That's certainly a good conspiracy theory but AFAIK not proved.
What is certain is that Microsoft (and Sun!) paid SCO quite a few millions for "intellectual property licenses" which makes them pretty major backers in the sense of supporting SCO's business if not in the financial sense.
There's probably a commercial reason (companies agreed to support a common standard or something like that?).
There's also a problem with compression ratios - PNG is lossless so it's improssible to compress beyond a certain point. With JPG you have much more ability to choose a point on the compression/quality tradeoff curve.
Yep - just shows the power of the free market once again!
Think how little progress we'd see if large segments of the IT industry were dominated by single large corporations with no incentive to innovate..... oh wait.....
That's an eminently sensible suggestion, and something that I've beleived for a long time.
Just to add one point: It would also resolve all the stupid and expensive legal conflicts resulting from disputes over trademarks in completely different industries or different countries, where there is absolutely no risk of consumers being confused.
Hmmm... suspected it might be something like that, though I did get it working before with WinCVS (nice little free tool BTW for people like me who like developing with GUIs).
Guess I'll just keep plugging away till I find some configuration that works...
...and it keeps getting better and better. I'm off to download my copy right now!
I seriously think that more open source developers should get behind eclipse, even if they don't use Java as their primary language. Right now it's probably the *only* free software IDE that has the potential to match Visual Studio, which like it or not is an awesome product for developers.
Want to contribute to open source? Write some quality plugins for eclipse and you can't go far wrong.
Meanwhile, does anyone have any tips for getting Eclipse for Sourceforge? I'm using it for my own little free software project but haven't been able to connect the damn thing to CVS. Perhaps v3.0 has fixed that?
It's a pretty basic principle that in order to have a fair contract, a person must have a full understanding of what they are agreeing to. Free markets require informed consent on every transaction in order to work effectively.
In general that's not the case. That's a fundamental flaw with EULAs - people simply don't read them.
On top of that - people make mistakes. Perhaps just *once* you forget to tick the no spyware checkbox. Do you therefore deserve a permanently compromised machine?
This all makes Spyware look like a deceptive trade practice in my book. Even if people do install it themselves, they've almost cetainly been duped into doing so.
I agree they aren't going to get very close to a perfect fitness function.
But what this kind of technique could be really great for is in-race optimisation. Can't decide whether the come in for a pit stop this lap or the next? Let the GA run a few hundred thousand simulations of the possible ways the race will progress and get a probablity weighted average of the payoffs from each strategy, taking into account current race position, likely pit-stop times, track condition etc.
However, holding patents for defensive purposes isn't much use against pure "IP litigation" companies.
:-)
Since these companies don't produce actual products they can't be caught out for infringing any of your patents.
It's only really useful against other large companies (e.g. IBM) since it gives you better bargaining power for cross-licensing. And for locking out new competitors, of course
Not much about investor confidence. Mostly it says a lot about the deficiencies of accounting in capturing the real value of a company.
The value of assets on the balance sheet are determined by a multitude of archaic accounting rules, so don't actually correspond very closely to the real value of the assets. Some assets like human capital, brand and intellectual property don't appear on the balance sheet at all.
For example, Red Hat has a pretty good brand for a company of its size, which isn't included in the assets but contributes a lot to the market cap.
There's also the issue of how much debt a company has (which can allow it to purchase more assets without a corresponding increase in market cap) which can distort comparisons like this. Though IIRC neither Sun nor Red Hat has much debt in this case.
In theory, a company's Assets should be equal to the value of its Liabilities(Debt) plus its Market Cap, but in practice it never works out that way for all the reasons mentioned above.
Your algorithm is of course O(1) but it doesn't allow for differing priority levels between processes. You need this if you want high priority processes to pre-empt low priority background processes at appropriate moments, which is pretty much essential for real-time or interactive applications.
The Linux O(1) scheduler does this. It implements a queue for each of 140 different priority levels, and then using an O(1) technique to find the queue with the highest priority that still contains a process waiting to run. It doesn't distinguish between processes in the same priority level, so effectively it's doing round-robin for processes of the same priority.
I think the Linux scheduler is pretty excellent from an algorithmic perspective. I don't see any really big trade-offs that have been made. You could write a faster, simpler scheduler that was optimized to handle a very small number of processes but that wouldn't scale well and could only really make sense for specialised embedded applications.
Remember that the real overhead in scheduling typically isn't actually the algorithm itself - it's the large cost of doing context switches, cache flushes etc involved in switching to a new process.
You therefore gain far more by making intelligent scheduling decisions than by squeezing a few cycles out of the scheduler itself. There's therefore still plenty to be done in the fine tuning of the current O(1) scheduler, e.g. getting the best scheduling behaviour for particular classes of processor architecture or application workload.
You're exactly right.
Note though that there's an advantage to the linux scheduler method over a priority queue: although both can access the (joint) highest priority process in O(1) time, it generally takes O(ln n) time to insert/delete a process in a priority queue, whereas the linux scheduler technique can do this in O(1) time as well.
I have to say that I still think that humans and computers use essentially the same algorithm. Even the very best chess players search and prune a tree of moves.
Of course, grandmasters don't think of this as searching and pruning a tree, but that's what they are doing subconciously. If they didn't, they'd get obliterated in tactical exchanges.
The main difference between the human and computer tree searches is simply that the computers are far better (faster) at searching while the humans are far better at pruning and evaluation (thanks to the pattern matching you mention).
Humans simply ignore (prune) the vast majority of possible moves, so their "search tree" has a very low branching factor. I wouldn't be surprised if the average was less than 2 for top players, so they can look very deeply into a position without considering many alternative lines.
The other advantage that humans have is that they are much better at considering "strategic" aspects when evaluationg a position. It's very hard to get computers to recognise these. But in effect, this just means that the human has a much better evaluation function, so this is still consistent with the fundamental tree search approach. Like the parent post says, this ability doubtless involves considering groups of pieces using pattern matching etc.
The other interesting thing that humans do is remember aspects of the position which they subconciously make use of while doing move search and position evaluation, e.g. the existence of a pin or potential fork threat. My own style of play uses this quite a bit - I like to look for threats and weaknesses then try to find lines that will help me exploit them.
In this way, humans seem to be doing a kind of "directed search" which is theoretically possible in a computer's tree search but I've never seen actually implemented in computer chess. Anyone seen anything like this in a tree search algorithm? I think there could be potential for research in this area.
I've written a simple Go-playing computer program so can offer some insights.
Basically, evaluating the position is *very* difficult. You certainly can't use simple heuristics like "number of stones" because certain stones may be guaranteed or likely to die.
You can't really use localised evaluation functions because stones right on the other side of the board can often affect your valuation.
There's also the concept of "ko threats" which are valuable even if the opponent has a guaranteed way to protect a group of stones.
Given all of this, I don't think it's feasible for a human to write a sensible evaluation function for a general go position. I think the problem will ultimately be cracked, but it'll need some proper AI techniques such as genetic algorithms to "learn" an evaluation function.
Broadly speaking, it's the ability to call methods on remote objects (e.g. a separate machine over the network). Think of it as something like Java RMI. The framework takes care of things like serializing the parameters and return values.
I think it's a decent technology for the right kind of applications, e.g. a cluster of servers that need to share data. However, if you want to expose services to other systems in a more general way, web services are probably a much better way to go.
The obvious solution to that technical hitch is to publicly cancel your starwars laser project but carry on building it in secret with the hope that your opponents will not bother to paint their missiles a nice shiny colour.
Would only work once, but the short term advantage might be decisive.
As someone who actually wrote to my MEPs about this issue, I'm pretty pleased about this...
I agree with you in that AI and physics are definitely the big things in the next generation of games.
Haveing said that, it's still quite tricky to write games to take advantage of multi-threaded operations. Your physics engine can't very easily go around moving bits of geometry around while another thread is rendering the scene or you could get into all kinds of trouble.
Of course, you can get around all this with clever locking, timeslicing and making copies of game state etc. but this all adds overhead both in terms of clock cycles and development time.
My guess is that it'll still be a while before any significant number of games really make the most out of multiple processors.
On the contrary, it sometimes makes sense to code before you design.
I rather like the XP approach of designing only when you need to, and refactoring when you come across something you need to change. In my experience this is far more productive than lengthy design processes.
The knowledge that you will have to refactor tends to push you towards writing very clean and modular code from the outset, so design changes are usually very simple to implement.
Often the thorniest design decisions you will have to make only become apparent when you have a functioning prototype system and really start to understand the key implementation issues. There's nothing like a bunch of automated tests (another key XP practice) to help you here.
Yeah, sometimes you might have to tear up a whole subsystem and start again, but even then you will have learned more than you ever could have through a paper exercise. You've also probably spent less time doing this than you would have done on a single upfront design phase.
Agreed, though I would argue that it's the complexity and the heterogeneity of human decision making rules that make them more difficult to predict, rather than their ability to reason per se.
Rationality isn't really an issue - it can be considered just another decision rule that can be formulated pretty much as "do whatever is in my best interest" where best interest is defined to include the value gained (if any?!?) from helping others, altruism etc.
Many experts in the field of rationality and choice theory would of course argue that humans are not fully rational and frequently make decisions not ultimately in their own interests. People are for example generally bad at making tradeoffs between short and long term goals, and also at evaluating risks.
This shouldn't be taken as an argument for paternalism, but rather that the ability of an individual to calculate the outcomes of their decisions is not good enough to calculate the best decision in a limited time with imperfect information.
Basically humans seem to operate on the level of "bounded rationality" where they operate according to fairly simple "rules of thumb" and only deviate from these when they experience or anticipate a significant positive or negative outcome that encourages them to think more carefully about the issue. After which, of course, they devise a slightly more sophisticated rule of thumb and continue as before.....
I agree that radix sorting rocks.
:-)
I remember a programming contest where I had to sort a *huge* list of words into length order.
My algorithm was by far the fastest. Most fools seemed to think that you need painfully slow O(n log n) time algotithms like QuickSort for sorting.
Don't think the "if (a!=b)" is a good idea in many cases.
Isn't the other great advantage of your variable swapping algorithm to avoid a branch instruction which is costly on some architectures?
GCD is used for simplifying rational numbers. So it's used in pretty much any decent maths library.
And rational numbers have a *lot* of uses. CAD, spreadsheets, high precision calculations, financial figures where rounding is unacceptable etc.
I expect GCD also has implications for packing problems and complex scheduling algorithms where you need a quick check on which items are likely to "fit" together effectively. Anyone have experience of this?
I agree it's extremely difficult in many cases, but that is because of the human/management dimension rather than the programming complexity.
The coding is easy.