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.
    Vyacheslav Kononenko, Oct 18, 2004
    1. Advertisements

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
    Ian Pilcher
    Dec 15, 2003
  2. Ed

    Code review requested

    Ed, Jul 19, 2004, in forum: Java
    Filip Larsen
    Jul 19, 2004
  3. Mike Wahler
    E. Robert Tisdale
    Oct 18, 2004
  4. www
  5. luserXtrog

    A little light code review requested

    luserXtrog, Aug 18, 2010, in forum: C Programming
    Aug 18, 2010

Share This Page