[A Friday translation of the 1999 article by one of the authors of the Thief game engine, Sean Barrett]
Unpleasant situation in "Sapper"In this situation, I know that there are a lot of mines around me, but I can not determine where they are. Several mines can be in one of two places (pink or blue), a group of mines can be located in one of two combinations (light / dark green). In addition, there is still a difficult situation with "5" and "6" in the upper left corner, which I did not single out.
Blue / pink - mutually exclusive pair, light / dark green - mutually exclusive group
"Sapper": logic or probabilityIn "Sapper" you can play in two ways: as a logical or probabilistic game.
Technically, probability implies logic. If you can logically prove that the mine must be in a certain place, then the probability is 100%. If you can prove that it is not in this place, then the probability is 0%. That is, in a sense, only probabilities are important to us. However, the player uses logical deduction to recognize such 100% situations. Sometimes, especially at low levels of complexity, it is enough to pass a level, no calculation of probabilities is required.
But there are situations when the whole logic of the world can not save you. A simple example is the situation with the "T", which can be seen down the center. It is slightly complicated by additional neighboring mines. (In the simplest case, "2" is replaced by "1", and "5" - by "3", so that the situation is symmetrical.)
An amusing find was shared today by the user fj333 with Reddit . Analyzing Qualcomm Technologies' proprietary code for Android, which appeared one year ago, he found that an unknown programmer decided to use the sorting with a bubble in production-code in order to find ... maximum in the array.
You can view the original file by under the link to Github or under the cut, and any owner of the device with Qualcomm Snapdragon 200 MSM8610 running Android can estimate it in operation.
As anyone who is familiar with sorting algorithms knows, sorting by a bubble is an educational algorithm, and in industrial code it is usually not used due to its inefficiency ; The matter is that in the worst and average cases it has the complexity O (n2) , besides its capacitive complexity in this case - O (n) . Whom it was not convinced - to use the sorting by a bubble does not recommend even Barack Obama .
And this is all not taking into account the fact that to search for the maximum would be enough and a simple search.
Long ago, when I was a naive schoolboy, I suddenly felt curious. What is a magical way that data takes up less space in an archive? I started surfing the Internet in order to find an answer. So I found many interesting articles with fairly detailed information on this topic. But all of them did not seem to me easy, the code listings were very difficult to understand.
Let us consider a situation when you need to handle collisions between some objects. What do you do in this case? Probably, the easiest solution would be to check interaction between these objects. This is the right decision, and everything will be fine until you get a lot of objects. As soon as their number gets up to a few thousand, you will notice that everything works much slower. What if you get thousands of the particles? Then everything stops. Here things get much more interesting. What tricks and optimizations would you use to solve this problem?
Let us consider 2D case to make it simple, the particles are round, and the radius of the particles is the same for all of them.
Table of contents
1. Overview of algorithms
1.1. Exhaustive search
1.2. Sweep & Prune
1.3. Regular grid
2. Some optimizations
2.1. Sweep & Prune
2.2. Regular grid
3. Speed comparison
4. Application (software and source code)
Timsort is a hybrid sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python, OpenJDK 7 and Android JDK 1.5. Here is a table in order to understand that better from Wikipedia.
There are only 7 of adequate algorithms among a huge selection in the table (with complexity O(n logn)), but only two of them have stability and complexity of O(n) at best. One of the two is long well known to everyone "Tree sort that builds a binary search tree", and the second one is Timsort.
This article discusses the algorithms’ sieves for finding prime numbers. We consider in detail the classic Sieve of Eratosthenes, particularly its implementation in the popular programming languages, parallelization and optimization, and then we will describe a modern and fast Sieve of Atkin.
Here is a picture of the Sieve of Eratosthenes sculpture that was created by abstract expressionist Mark Di Suvero, constructed on the campus at Stanford University.
Basilio Noris PhD from the Federal Polytechnic School of Lausanne created a remarkable program that is perfect for the demo of some tasks that solve the machine learning algorithms (classification, clustering, and regression using the various methods). In one program are captured the libraries, algorithms and code patches that could be found. Unlike Matlab, here GUI runs fast in the interactive mode, thus it comes out very well.
MLDemos 0.3.2 for Windows (minimum requirements: XP SP3)
MLDemos 0.3.2 for Mac (minimum requirements: Snow Leopard)
MLDemos 0.1.3 for Linux 32bit (deb) (build for: Ubuntu 10.04)