Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Re: Code review requested, Accelerated C++

Reply
Thread Tools

Re: Code review requested, Accelerated C++

 
 
Vyacheslav Kononenko
Guest
Posts: n/a
 
      10-18-2004
Joe Van Dyk wrote:
> On 2004-10-17 07:56:02 -0700, "Andrew Koenig" <(E-Mail Removed)> said:
>
>> "Joe Van Dyk" <(E-Mail Removed)> 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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
What is code review? (Java code review) www Java 51 05-15-2007 01:10 PM
help understand source code in charpter 14.4 of accelerated C++ baumann@pan C++ 6 05-19-2005 08:46 AM
"Accelerated" certification testing programs Jameson D MCSE 2 11-26-2004 01:47 PM
Re: Code review requested, Accelerated C++ Mike Wahler C++ 1 10-18-2004 03:43 AM
Accelerated C++ Sample Solutions Martin C++ 8 10-23-2003 05:32 PM



Advertisments