Joe Van Dyk wrote:
> On 20041017 07:56:02 0700, "Andrew Koenig" <(EMail Removed)> said:
>
>> "Joe Van Dyk" <(EMail 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
>> nelement 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 nelement 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
