## RE: Re: Concrete and Abstract Stuff (was: Re: Re: Re : Prerequisite learning?)

Expand Messages
• ... But something that takes exactly 10 machine instructions takes O(1), rather than O(10). Using an array of pointers to structs has the same complexity as
Message 1 of 2 , Mar 4, 2002
On Mon, 4 Mar 2002, Chen Shapira wrote:

>
> > Machine language - geez. While writing stuff in Assembler makes sense
> > sometimes (but usually is considered harmful needlessly), I
> > don't think
> > fully thinking of how those instructions translate to machine
> > language is
> > necessary. One should be aware that they do, and how the do,
> > but for most
> > case thinking in the Assembler level is enough.
>
> I think you are missing Knuth's point.
>
> The guy was writing the most complete reference for algorithms.
> Now, a large part of his work was analyzing complexity.
> To analyze complexity, we must agree which operations can be said to take
> O(1), and we can all agree that operations which take exectly 1 machine
> instruction can be said to take O(1).
>

But something that takes exactly 10 machine instructions takes O(1),
rather than O(10). Using an array of pointers to structs has the same
complexity as using an array of structuts. However, sorting the former is
a relatively small O(n*log(n)) while sorting the large is much slower.

Complexity (O's, Thetas and their ilk) is nice, but it's not the only way
to evaluate an algorithm. I was told that in some forms of Real-Time
programming people had to count the number of clock ticks it would take to
execute every code.

> So, he figured that the correct way to write algorithms is to use machine
> code.
>

That's a slightly wrong conclusion. When I studied my Algorithms course,
a friend of mine asked me what is the complexity of an if statement. I
told him that even if an if fails it is still O(1), because it still has
to compute the condition. (assuming of course, the condition is not a
function call). I think he knew Assembler, but he did not make the
connection between it and algorithms.

So, yes, knowledge of Assembler (or machine language) helps in
programmer with a much better understanding of how algorithms and code
works.

Then there are faux-amies. You would not put 20! permutations in a C
array, would you? But in haskell defining a lazy list of them is quite
common, and will not blow out memory.

Lazy eval can make some very nice tricks possible. Without good
understanding of it one will write Haskell code which is much less
elegant.

> Once you know that extractMin() takes O(log n), there's no point in looking
> at the machine version ever again.
>
> (Unless you have a data structures test on Thursday, which of course none of
> us do)
>

Do you have one? If you do - Good Luck! If not - flame away.

Regards,

Shlomi Fish

> Thanks,
> Chen.
>
>
>
> To unsubscribe from this group, send an email to:
> hackers-il-unsubscribe@egroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

----------------------------------------------------------------------
Shlomi Fish shlomif@...