On Sat, 27 Apr 2013, Frank Shearar wrote:

> In Schlemiel's algorithm you have to traverse your string from the
> beginning. Here, the problem is that at every step you're making
> String after String after String that you just throw away.
>
> Unless perhaps you're suggesting that the Schlemielness comes from not
> doing things the way our particular garbage collector like to do
> things?

Your code looks right, and works well in a functional programming language 
which has the required optimizations to run such code efficiently. But in 
Smalltalk it creates 2n-1 intermediate strings, where the previous is the 
prefix of the current one, so each one is longer than the previous, which 
means that O(n^2) bytes are allocated, filled, read once, and then garbage 
collected. This means that the runtime cost is also O(n^2).


Levente

>
> frank
>
> On 27 April 2013 22:08, Nicolas Cellier
> <nicolas.cellier.aka.nice at gmail.com> wrote:
>> http://en.wikipedia.org/wiki/Schlemiel_the_Painter%27s_algorithm
>>
>>
>> 2013/4/27 <commits at source.squeak.org>
>>
>>> Levente Uzonyi uploaded a new version of Tests to project The Trunk:
>>> http://source.squeak.org/trunk/Tests-ul.200.mcz
>>>
>>> ==================== Summary ====================
>>>
>>> Name: Tests-ul.200
>>> Author: ul
>>> Time: 27 April 2013, 10:08:43.206 pm
>>> UUID: dfe70287-0768-42f9-97b7-d7ba6fbd6bb6
>>> Ancestors: Tests-fbs.199
>>>
>>> - avoid suboptimal string concatentation in ReleaseTest >>
>>> #testMethodsWithUnboundGlobals
>>>
>>> =============== Diff against Tests-fbs.199 ===============
>>>
>>> Item was changed:
>>>   ----- Method: ReleaseTest>>testMethodsWithUnboundGlobals (in category
>>> 'testing') -----
>>>   testMethodsWithUnboundGlobals
>>>         | unbound |
>>>         unbound := SystemNavigation default methodsWithUnboundGlobals.
>>>         Smalltalk cleanOutUndeclared.
>>> +       self assert: unbound isEmpty description: 'Unbound: ', unbound
>>> asCommaString!
>>> -       self assert: unbound isEmpty description: ('Unbound: ', (unbound
>>> reduce: [:acc :each | acc, ', ', each]))!
>>>
>>>
>>
>>
>>
>>
>
>