[xptypeprogrammer]

guys please answer. thank you

[calvinthedestroyer]

Can you provide some more details about your question?

[xptypeprogrammer]

calvinthedestroyer, on 26 August 2012 - 10:34 PM, said:

Can you provide some more details about your question?

i'll just say the purpose of having space-time take off. space-time take off pertains to a algorithm method. space–time or time–memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution (and, conversely, the computation time can be reduced at the cost of increased memory use).

[calvinthedestroyer]

Can you post an example of your code?

[karabasf]

The importance of it is mainly dependent on the amount of resources and requirements you have. If you'd live (and maybe in situations now, like embedded systems) a few decades ago, memory was very scarce, so you had to be careful in the allocation of memory. However, as a consequence, your performance deteriorates because you had to carefully allocate memory (and thus taking more time)

So let's take a look at an example.

Suppose we have an (unsorted) array X containing 10 numeric elements ranging from 0..9. I want to check this array if it has double entries.

One way to do it:

bool hasDoubleEntry = false;
// Loop through the array to retrieve elements
for i = 0 to length X
    temp = X[i];

    //Loop again to compare element temp against the other elements
    for j = 0 to length X
        if j == i
           continue;
        
        if temp == X[j]
            hasDoubleEntry = true;

As you can see, I don't use additional memory to store data in order to solve the problem (so I only use O(n) amount of memory for my original array). However, the performance of this algorithm is O(n²) because I have to loop twice. (n is the amount of elements in my array X)

Compare it with this algorithm (same problem)

bool hasDoubleEntry = false;

//Initialize a boolean array with the range of the number
numEntries = bool [10]; //We can only have numbers from 1 to 10

//Loop through array X. 
for i = 1 to length X
    //Retrieve the entry. If it was not found before, set the numEtries entry to true
    if(numEntries[X[i]] == false)
       numEntries[X[i]] = true;
    // if the corresponding entry was true, then it has a double entry
    else
      hasDoubleEntry = true;
      break;

Now, we observe that this algorithm only loops through the data once, hence the order is O(n). However, to do so we needed an additional array containing m elements, where m is equal to the data range we have. So instead of using O(n) memory, with n being the amount of elements in my array, we need O(n+m) memory.

Both these examples show a clear tradeoff between memory vs. performance.

Note that all my code is sort of pseudocode and not actual code

This post has been edited by karabasf: 27 August 2012 - 05:52 AM

[macosxnerd101]

This isn't really a Java question. Moved to Computer Science.

[jon.kiparsky]

xptypeprogrammer, on 27 August 2012 - 01:18 AM, said:

calvinthedestroyer, on 26 August 2012 - 10:34 PM, said:

Can you provide some more details about your question?

i'll just say the purpose of having space-time take off. space-time take off pertains to a algorithm method. space–time or time–memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution (and, conversely, the computation time can be reduced at the cost of increased memory use).

To me, "space-time take-off" sounds like you're launching your hyper-drive space ship. I suspect the question should be asking about "trade-off" instead.

[Skydiver]

I feel that there is another dimension to this problem that I call "cognitive load" but can simply be thought of as complexity. Note that instead of "complexity" in terms of runtime performance, I'm talking about the complexity of what it takes for the programmer to understand what is happening in the code and if needed refactor it.

I've been guilty of this: Writing code that improves things either on the time or space side of things, but the code has grown so complex that six months later, the code looks like gibberish even if I'd left myself comments as to what the code is trying to do as well as why I made those choices. The code runs really fast or is really space efficient, but it's going to be a pain to change a part of it.

For example, look at the various solutions to the C# challenge of simply counting the number of characters. Nothing there is really esoteric, and the various solutions are simple enough, but you have to apply a little bit more brain power to understand what is happening.

Or as another example, look at the pseudo code for the Sieve of Atkin. Now look at a slightly optimized version. Again, the changes make sense, but it requires applying a little more brainpower.

Like the straw that breaks the camel's back, how many recursive iterations of "apply a little bit more brainpower" can you keep doing? If a year from now, you have to fix a critical bug, will you know exactly how to fix it with the confidence that no unit or regression tests have to be run? Or even better, will you be confident that somebody else who has not seen your code before will be able to fix that critical bug within couple of hours without calling you at 3AM in the morning?

[jon.kiparsky]

Good point. Put simply, you have to factor in developer time as a cost, and it's often more expensive than the gains it buys. This is fine when you're optimizing the hell out of a fun project, but not on paid hours.
Clarity of code is not an optional feature. It's an absolute requirement, and failing to write for clarity is a cardinal sin of development.