Re: Code review requested, Accelerated C++

Discussion in 'C++' started by Vyacheslav Kononenko, Oct 18, 2004.

  1. Joe Van Dyk wrote:
    > On 2004-10-17 07:56:02 -0700, "Andrew Koenig" <> said:
    >
    >> "Joe Van Dyk" <> wrote in message
    >> news:2004101617264416807%joevandyk@nospamgmailcom...
    >>
    >>> The resulting program seems reasonably fast, searching through a
    >>> dictionary of 300,000+ words in 3 seconds on my PowerBook G4.

    >>
    >>
    >> I haven't read the code in detail, but I did read enough of it to make
    >> a strategic suggestion.
    >>
    >> Your program works by making a vector of all of the palindromes, then
    >> sorting it to determine the largest smallest. This technique is
    >> legitimate, but takes substantiallly more space and time than needed.
    >>
    >> Consider: If there are n palindromes, your program creates an
    >> n-element vector, all the elements of which must fit in memory at the
    >> same time. Moreover, sorting those elements takes time proportional to
    >> n*log(n).
    >>
    >> I am not generally fond of optimizing programs too early, but I make a
    >> distinction between local optimizations and writing code in a way that
    >> changes the exponent in the expression of how much time or space a
    >> program takes. In this case, for example, storing an n-element array
    >> means you have a space exponent of 1 (that is, the amount of space is
    >> proportional to the 1st power of the amount of input), and if you can
    >> reduce that to 0, it may well be worth doing.
    >>
    >> The way to do it is to stop remembering every palindrome, and remember
    >> only the shortest and longest you've seen so far. Each time you find
    >> a new one, print it, check whether it's shorter than the current
    >> shortest or longer than the current longest, and then throw it away.
    >>
    >> This strategy has the advantage of running in time proportional to n,
    >> rather than to n*log(n), and in space proportional to the longest word
    >> in the file, rather than proportional to the sum of the lengths of all
    >> the palindromes. That could be a big saving.
    >>
    >> Of course you then give up the possibility of printing the palindromes
    >> in alphabetical order, but I don't think you were doing that anyway.
    >>
    >>
    >>
    >> Regards,
    >>
    >> Andrew Koenig

    >
    >
    > Thanks for the idea. I tried it the way you suggested and it actually
    > took longer (4 seconds compared to 3 seconds on my first approach) to do
    > on a 300K word set. I think it's because of the repeated cout calls,
    > right? (i.e. we're calling cout everytime we find a palindrome, and not
    > once at the end.)
    >
    > I also tried adding all the palindromes to a string (what's the best way
    > to do string concatenation?) and then printing that out at the end, but
    > that took about the same amount of time as my first approach.
    >
    > Joe
    >

    How about to combine both methods? Keep palindromes in a vector but do
    not sort it. Have two index variebles that will point to shortest and
    longest palindrome in the vector.
    --
    Regards,
    Slava
     
    Vyacheslav Kononenko, Oct 18, 2004
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ian Pilcher

    Code review requested

    Ian Pilcher, Dec 15, 2003, in forum: Java
    Replies:
    0
    Views:
    347
    Ian Pilcher
    Dec 15, 2003
  2. Ed

    Code review requested

    Ed, Jul 19, 2004, in forum: Java
    Replies:
    1
    Views:
    365
    Filip Larsen
    Jul 19, 2004
  3. Mike Wahler
    Replies:
    1
    Views:
    399
    E. Robert Tisdale
    Oct 18, 2004
  4. www
    Replies:
    51
    Views:
    1,500
  5. luserXtrog

    A little light code review requested

    luserXtrog, Aug 18, 2010, in forum: C Programming
    Replies:
    2
    Views:
    344
    luserXtrog
    Aug 18, 2010
Loading...

Share This Page