Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Shlomi Fish
    ... 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
    • 0 Attachment
      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
      understanding. However, only experience can help you become a good
      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@...
      Home Page: http://t2.technion.ac.il/~shlomif/
      Home E-mail: shlomif@...

      "Let's suppose you have a table with 2^n cups..."
      "Wait a second - is n a natural number?"
    Your message has been successfully submitted and would be delivered to recipients shortly.