Posts tagged time

Understanding C++ time complexity

0
658 days
by in C++, Programming

What functions are faster? Which ones are the most efficient? Understanding this will help you optimise your code and impove it's performance.

Each C++ function has a run time, and knowing that will allow you to combine the best methods always.

Here you have the different possible run times, explained and with an example of a function. (Note that they are ordered from fastest to slowest)

Constant time:

This is the fastest a function can work. An example is to measure an array's length:

// Using namespace std;
int a[32];
cout << a.size();

What this means is that no matter how large a is, it will always take the same amount of time to perform this operation.

Logarithmic time:

This is also in the fast group of times, there is a formula to get how much time it will actually take (That involves the logarithm of the size of the input)

An example of this would be a function that looks for a key in an array, returning it's index if found:

int binarySearch(int sortedArray[], int first, int last, int key) {
   // function:
   //   Searches sortedArray[first]..sortedArray[last] for key. 
   // returns: index of the matching element if it finds key,
   //         otherwise  -(index where it could be inserted)-1.
   // parameters:
   //   sortedArray in  array of sorted (ascending) values.
   //   first, last in  lower and upper subscript bounds
   //   key         in  value to search for.
   // returns:
   //   index of key, or -insertion_position -1 if key is not
   //                 in the array. This value can easily be
   //                 transformed into the position to insert it.

   while (first <= last) {
       int mid = (first + last) / 2;  // compute mid point.
       if (key > sortedArray[mid])
           first = mid + 1;  // repeat search in top half.
       else if (key < sortedArray[mid])
           last = mid - 1; // repeat search in bottom half.
       else
           return mid;     // found it. return position /////
   }
   return -(first + 1);    // failed to find key
}
Source: Fredosaurus.com

Linear time:

A bit slower than logarithmic time, but still fast. Functions that run in this type of time take a time proportional to the size of the input.

An example of this would be to iterate through an array:

int a[40];
// Fill a with data...
for(int i=0;i<40;i++){
     std::cout << a[i];
}

Linearithmic time:Quick Sort method

Well this one is a bit tricky, it's still fast, and it's run time depends on the size of the input but both linearly and logarithmically. All logarithmic functions that sort work this way, they are also linear because they depend on the size of the array to sort:

There are a lot of different ways of implementing the algorithm quicksort, here you have one sample demonstration of how it works.

Polynomial time:

This one is the slowest time inside the fast run times. It is the one that take up comparison sorts (Functions like insert, sort, select... )

Here you have a sample implementation of the function sort for arrays:

int array[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30 };
int elements = sizeof(array) / sizeof(array[0]);
std::sort(array, array + elements);
for (int i=0; i<elements; ++i)
     std::cout << array[i] << ' ';

Exponential time:

Algorithms and functions that run in this type of time are considered slow. This are algorithms of the type brute force, that is, algorithms that try all possibilities, like a solver for a Rubik Cube.

Factorial time:

This is the slowest of all, it corresponds to complex brute force algorithms, like an algorithm to solve the Travelling Salesman Problem by brute force.

I will probably add a bit more to this examples over time, but well to get a grasp of what these times mean I think this will be more than enough,

Alex

Display time since last visit in PHP

1
1113 days
by in PHP

Have you ever seen those social networking sites that display the time since your last visit? They do it in a very neat way actually, that is a lot more friendlier that simply "Last login date..."

Well, this little php snippet will allow you to display messages like "Last visit was 4 days ago" or "2 weeks ago" or whatever it was, up to a year.

To use simply include the function in your code and then you'll need two timestamps to compare. One is the one that should be in the database, and it should be the date of the last user activity on the site, or the last time user logged in. The other would be normally the current time ( time() )

 
function timeBetween($start,$end,$after=' ago',$color=1){
	//both times must be in seconds
	$time = $end - $start;
	if($time < = 60){
		if($color==1){
			return '<span style="color:#009900;">Online';
		}else{
			return 'Online';
		}
	}
	if(60 < $time && $time <= 3600){
		return round($time/60,0).' minutes'.$after;
	}
	if(3600 < $time && $time <= 86400){
		return round($time/3600,0).' hours'.$after;
	}
	if(86400 < $time && $time <= 604800){
		return round($time/86400,0).' days'.$after;
	}
	if(604800 < $time && $time <= 2592000){
		return round($time/604800,0).' weeks'.$after;
	}
	if(2592000 < $time && $time <= 29030400){
		return round($time/2592000,0).' months'.$after;
	}
	if($time > 29030400){
		return 'More than a year'.$after;
	}
}
 

And here an example of usage:

 
echo timeBetween($timeFromDatabase,time());
 

And an example output for that could be: 4 minutes ago

There are two configuration variables, $after and $color. $color sets online to a nice green color, and $after is what is displayed after the time. Default is " ago". But you can set it to anything you want.

Well I hope you find this useful ;)

Quantum Universe Simulation – The Unique beings paradox

12
1358 days
by in General talk

Completely off topic for this blog, but at the time it is the best place to write about this. Read through the whole thing before judging what you see, then think about it, and then express your opinion.

The Unique Beings paradox

To start off I will check with you certain easy experiments that are the base of this. We both agree that the same set of variables, done in the same order in the same way must always produce the same result. An example of this is that if we had two identical containers full of the same amount of the same water, and using a machine we dropped two identical steel balls of the same mass in the same point of the containers and we recorded each from the same angle and the same lighting we would have exactly identical results in the water, each second of one would match exactly each second of the other, until the water flattened again.
So following from here and using as a testing environment a simulation in a computer, identical sets of data and operations would produce identical results, which could be expanded to more complex things. So if we duplicated the brain of a rat, and the simulation of the rat was presented with a maze, exactly the same as the real rat, they would behave in the same way (Supposing that the simulated rat was duplicated successfully) So we could go further in our expansion, until we reached humans.
Can we create a simulation with real humans? The answer is yes, although it is too complex to even think about it, since the amount of variables to take into account are too many. But my goal is to simulate humans, and the only way of doing it accurately is simplifying the task of inserting into the simulation all of the variables, so we need a common start for all humans, which we could find three. The most recent was our evolution from pre-humans, but still we have to simulate them perfectly, and that is even harder because of the lack of knowledge, so we have to keep going back. The next common event was the apparition of living beings on the Earth, back when they were monocellullar. But still we could create some sort of "similar" simulation, that wouldn't be as accurate as needed, so to do it perfectly we need everything to be the same, and that was the creation of the Universe, the moment in which the Universe was condensed to the simplest form, and then it expanded to be what we know today. The Big Bang. All is needed are the exact data of it, and a computer with a computational potential enough to simulate this.
The first thing is needed, data, is not currently available, but it will be eventually discovered.
The second thing that we need is a computer fast enough to calculate the Universe. At the moment not even all the computers on the Earth would be enough for this task, but there is evidence that within the next 10-30 years quantum computers will be available, the technology has already been discovered and it is being developed. Its potential is supposed to be the so great that not even a modern computer can simulate how they will behave.

Now from here on I am supposing that the criteria before has been met, so that the simulation of the creation of the Universe has been successfully done, and all the data was exactly identical, so that the consequences are all the same. Now we should be able to run the simulation at a higher time rate than normal, so we can reach current dates fast enough.
(Take into account that I am supposing that all data was entered exactly the same as it happened, so all things evolving from it are all the same too)
We could take a look at the Earth in its early years, see the complete evolution again, but this time on a computer simulation, but the past is not the interesting part, it is the present and future.

Since all things in the Universe have grown accordingly to a set of "casual" occurrences, so has the simulation, reaching the point where humans appear. Although you might think we have the freedom to chose whatever we want, we chose exactly what our genetically-determined-brain, our past experiences, and another number of factors determine us to chose, so that in the simulation all of it would be the same.
At the point when we reach the present, with you and me, and the simulation (Now in the future, but imagine you are living in the moment the simulation is achieved), the simulation would recreate the moment when I propose this theory here, would recreate the moment when the simulation is started!
So we have another simulation starting up inside the simulation. Since it would be an infinite loop (Without going too deep into math you can see how the number of simulations approaches an infinite number, over time) there would be an infinite loop of conscious beings inside the simulations, and those beings (Merely simulations of ourselves) would think exactly as we do, so they would be reading this exactly like you, and if they knew about the simulation they would think they were the "originals", but this has to have an origin, the ones who started the infinite loop, so we would want to check if we are indeed the originals.
So after a lot of thinking, we decide to alter the simulation. So in a Monday, we run the simulation until Wednesday, and we insert a tree in some common place in a city. And we all wait to see what happens. The strange thing is that when we were in Monday and we looked at the simulation of our Monday, there where two options, that we saw them (I'll follow this option later on) and we didn't see them insert the tree. So by the time we inserted the tree, they had done the same, and so did all of the infinite simulations.
Expectantly we would wait for Wednesday to see what happened. In our simulation they found the tree we had inserted, and they had found out that they were a simulation, and what would happen if by Wednesday we did too? If we ourselves found out too that we had a tree we would also think that we were being simulated but what would the consequences of that be? What if we decided to shut down the simulation? Would the ones above us do the same? Suddenly all of the infinite simulated identical universes know they are not original, and what's more, the one that woke up without a tree knew that they were unique, that they were not a simulation. But now, the simulations would differ from reality, so the whole experiment would have served to create a parallel universe different from ours.
As you've seen I've supposed that all the people in the simulations could think by themselves, but if that was true, it means that other living creatures could have also reached the technology that permitted us simulate the Universe, and I mean by this that they could have done the same as us, without us knowing. So there could perfectly be an infinite amount of simulations being done at a time, without one true original universe, since there would be no way of testing with multiple simulations...

Following the other option now, that we saw our simulation insert the tree before we reached Monday. If that did happen though a complex paradox is reached. Imagine we are on Friday in the week before. No one has come up with the idea of inserting a tree in the simulation, but we decide to forward a bit the simulation to see what happens. Remember that the simulation is exactly the same as what would happen in our world. The result? It would be impossible for them to come up with ideas before us, because if we chose to do that on Friday, they would have done the same with their simulation, and would have come up with the same results. We have to keep in mind that all we do, they'll do it too, even if looked into their future, they will have looked into their simulation's future looping endlessly.

The final conclusion is that currently the probability of us belonging to a simulated Universe is so high that it is almost certain (Taking into account that the number of simulated Universes increases over time towards infinite), although we could prove ourselves unique in certain small subsystems such as the Earth. The consequences of this over us are close to none, unless a simulation can be achieved in our time, in which case we would be diving deep in time traveling, and other paradoxical problems.

The reasoning for all of this has been omitted, since it is based on complex quantum calculations and simulation algorithms. If any of you readers knows anything about quantum physics will find this extremely interesting, just as I do. Please comment your opinion.

To understand better this, you can watch this video where several quantum scientists (Gregg Braden David Icke, David Lynch, Wayne Dyer, Deepak Chopra, David Wilcock, David Icke, Michael Talbot, Gregg Braden, James J Traitz, Robert Anton Wilson, Neil Kramer, Grant Morrison, Bill Hicks) talk about this subject. (See the video)

This article expresses a hypothesis I've been working on for some time now, and it shall not be copied without citing the source and author. Thanks to Reda Bouchami for clarifying this when I missed it.

Enjoy all of the great things you'll have to think about after this,
Alex

Go to Top