Re: Code review requested, Accelerated C++
Joe Van Dyk wrote:
> On 2004-10-17 07:56:02 -0700, "Andrew Koenig" <firstname.lastname@example.org> said:
>> "Joe Van Dyk" <email@example.com> 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
>> 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.
>> 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.
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.
|All times are GMT. The time now is 02:20 PM.|
Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.