June 08, 2010
On 06/08/2010 04:53 PM, Simen kjaeraas wrote:
> Simen kjaeraas <simen.kjaras@gmail.com> wrote:
>
>> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote
>>
>>> max of n elements is O(n).
>>
>> T max( T )( T[] values ) {
>> T result = values[0];
>> foreach ( i, e; values[1..$] ) {
>> if ( max( values[i+1..$] ) > result ) {
>> result = max( values[i+1..$] );
>> }
>> }
>> return result;
>> }
>
> Better:
>
>
> T max( T )( T[] values ) {
> if ( values.length == 1 ) {
> return values[0];
> } else {
> return max( values[0..values.length/2] ) > max(
> values[values.length/2..$] ) ? max( values[0..values.length/2] ) : max(
> values[values.length/2..$] );
> }
> }
>

I'm not sure I understand the point. Could you please elaborate?

Andrei
June 08, 2010
"Andrei Alexandrescu" <SeeWebsiteForEmail@erdani.org> wrote in message news:humfgd$1l7$2@digitalmars.com...
> On 06/08/2010 04:53 PM, Simen kjaeraas wrote:
>> Simen kjaeraas <simen.kjaras@gmail.com> wrote:
>>
>>> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote
>>>
>>>> max of n elements is O(n).
>>>
>>> T max( T )( T[] values ) {
>>> T result = values[0];
>>> foreach ( i, e; values[1..$] ) {
>>> if ( max( values[i+1..$] ) > result ) {
>>> result = max( values[i+1..$] );
>>> }
>>> }
>>> return result;
>>> }
>>
>> Better:
>>
>>
>> T max( T )( T[] values ) {
>> if ( values.length == 1 ) {
>> return values[0];
>> } else {
>> return max( values[0..values.length/2] ) > max(
>> values[values.length/2..$] ) ? max( values[0..values.length/2] ) : max(
>> values[values.length/2..$] );
>> }
>> }
>>
>
> I'm not sure I understand the point. Could you please elaborate?
>

He's being a smart-ass and making implementations of max() that are worse than O(n) :)

Hee hee. Obfuscation is fun :)


June 09, 2010
Tue, 08 Jun 2010 16:14:51 -0500, Andrei Alexandrescu wrote:

> On 06/08/2010 04:05 PM, Walter Bright wrote:
>> Andrei Alexandrescu wrote:
>>> On 06/08/2010 01:27 PM, "Jérôme M. Berger" wrote:
>>>> Please define "reasonable performance"...
>>>
>>> Within 15% of hand-optimized code specialized for the types at hand.
>>
>> I would have said O(n) or O(log n), as opposed to, say, O(n*n).
>>
>> General rules for performance improvements:
>>
>> 1. nobody notices a 10% improvement
>>
>> 2. users will start noticing speedups when they exceed 2x
>>
>> 3. a 10x speedup is a game changer
> 
> max of n elements is O(n).

This probably means that D 2 won't be very efficient on multicore until the authors learn some basic parallel programming skills. Now where did you get your PhD - I'm collecting a list of toy universities people should avoid.
June 09, 2010
"retard" <re@tard.com.invalid> wrote in message news:hun6ok$13s5$1@digitalmars.com...
> Tue, 08 Jun 2010 16:14:51 -0500, Andrei Alexandrescu wrote:
>
>> On 06/08/2010 04:05 PM, Walter Bright wrote:
>>> Andrei Alexandrescu wrote:
>>>> On 06/08/2010 01:27 PM, "Jérôme M. Berger" wrote:
>>>>> Please define "reasonable performance"...
>>>>
>>>> Within 15% of hand-optimized code specialized for the types at hand.
>>>
>>> I would have said O(n) or O(log n), as opposed to, say, O(n*n).
>>>
>>> General rules for performance improvements:
>>>
>>> 1. nobody notices a 10% improvement
>>>
>>> 2. users will start noticing speedups when they exceed 2x
>>>
>>> 3. a 10x speedup is a game changer
>>
>> max of n elements is O(n).
>
> This probably means that D 2 won't be very efficient on multicore until the authors learn some basic parallel programming skills. Now where did you get your PhD - I'm collecting a list of toy universities people should avoid.

You used to have meaningful things to say. Now you're just trolling.


June 09, 2010
 :D Wow. This troll is getting increasingly desperate. Now it resorts to straw man.

On Tue, 08 Jun 2010 23:53:41 -0500, retard <re@tard.com.invalid> wrote:

> Tue, 08 Jun 2010 16:14:51 -0500, Andrei Alexandrescu wrote:
>
>> On 06/08/2010 04:05 PM, Walter Bright wrote:
>>> Andrei Alexandrescu wrote:
>>>> On 06/08/2010 01:27 PM, "Jérôme M. Berger" wrote:
>>>>> Please define "reasonable performance"...
>>>>
>>>> Within 15% of hand-optimized code specialized for the types at hand.
>>>
>>> I would have said O(n) or O(log n), as opposed to, say, O(n*n).
>>>
>>> General rules for performance improvements:
>>>
>>> 1. nobody notices a 10% improvement
>>>
>>> 2. users will start noticing speedups when they exceed 2x
>>>
>>> 3. a 10x speedup is a game changer
>>
>> max of n elements is O(n).
>
> This probably means that D 2 won't be very efficient on multicore until
> the authors learn some basic parallel programming skills. Now where did
> you get your PhD - I'm collecting a list of toy universities people
> should avoid.


-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
June 09, 2010
Wed, 09 Jun 2010 01:13:43 -0400, Nick Sabalausky wrote:

> "retard" <re@tard.com.invalid> wrote in message news:hun6ok$13s5$1@digitalmars.com...
>> Tue, 08 Jun 2010 16:14:51 -0500, Andrei Alexandrescu wrote:
>>
>>> On 06/08/2010 04:05 PM, Walter Bright wrote:
>>>> Andrei Alexandrescu wrote:
>>>>> On 06/08/2010 01:27 PM, "Jérôme M. Berger" wrote:
>>>>>> Please define "reasonable performance"...
>>>>>
>>>>> Within 15% of hand-optimized code specialized for the types at hand.
>>>>
>>>> I would have said O(n) or O(log n), as opposed to, say, O(n*n).
>>>>
>>>> General rules for performance improvements:
>>>>
>>>> 1. nobody notices a 10% improvement
>>>>
>>>> 2. users will start noticing speedups when they exceed 2x
>>>>
>>>> 3. a 10x speedup is a game changer
>>>
>>> max of n elements is O(n).
>>
>> This probably means that D 2 won't be very efficient on multicore until the authors learn some basic parallel programming skills. Now where did you get your PhD - I'm collecting a list of toy universities people should avoid.
> 
> You used to have meaningful things to say. Now you're just trolling.

Max of n unordered elements can be solved in O(log log n) time assuming you have enough cores and constant time memory access. Happy now?
June 09, 2010
"retard" <re@tard.com.invalid> wrote in message news:hunc9t$1c9e$1@digitalmars.com...
> Wed, 09 Jun 2010 01:13:43 -0400, Nick Sabalausky wrote:
>
>> "retard" <re@tard.com.invalid> wrote in message news:hun6ok$13s5$1@digitalmars.com...
>>> Tue, 08 Jun 2010 16:14:51 -0500, Andrei Alexandrescu wrote:
>>>
>>>> On 06/08/2010 04:05 PM, Walter Bright wrote:
>>>>
>>>> max of n elements is O(n).
>>>
>>> This probably means that D 2 won't be very efficient on multicore until the authors learn some basic parallel programming skills. Now where did you get your PhD - I'm collecting a list of toy universities people should avoid.
>>
>> You used to have meaningful things to say. Now you're just trolling.
>
> Max of n unordered elements can be solved in O(log log n) time assuming you have enough cores and constant time memory access. Happy now?

Yes, actually :)


June 09, 2010
Nick Sabalausky <a@a.a> wrote:

> He's being a smart-ass and making implementations of max() that are worse
> than O(n) :)

Well, I tried. Second try I was apparently too drunk to write bad code.

-- 
Simen
June 09, 2010
== Quote from retard (re@tard.com.invalid)'s article
> Wed, 09 Jun 2010 01:13:43 -0400, Nick Sabalausky wrote:
> > "retard" <re@tard.com.invalid> wrote in message news:hun6ok$13s5$1@digitalmars.com...
> >> Tue, 08 Jun 2010 16:14:51 -0500, Andrei Alexandrescu wrote:
> >>
> >>> On 06/08/2010 04:05 PM, Walter Bright wrote:
> >>>> Andrei Alexandrescu wrote:
> >>>>> On 06/08/2010 01:27 PM, "Jérôme M. Berger" wrote:
> >>>>>> Please define "reasonable performance"...
> >>>>>
> >>>>> Within 15% of hand-optimized code specialized for the types at hand.
> >>>>
> >>>> I would have said O(n) or O(log n), as opposed to, say, O(n*n).
> >>>>
> >>>> General rules for performance improvements:
> >>>>
> >>>> 1. nobody notices a 10% improvement
> >>>>
> >>>> 2. users will start noticing speedups when they exceed 2x
> >>>>
> >>>> 3. a 10x speedup is a game changer
> >>>
> >>> max of n elements is O(n).
> >>
> >> This probably means that D 2 won't be very efficient on multicore until the authors learn some basic parallel programming skills. Now where did you get your PhD - I'm collecting a list of toy universities people should avoid.
> >
> > You used to have meaningful things to say. Now you're just trolling.
> Max of n unordered elements can be solved in O(log log n) time assuming you have enough cores and constant time memory access. Happy now?

Technically true, but when's the last time you needed to find the max of n unordered elements, where n was large enough to justify the overhead of using even 2 threads?  Even if you use some kind of pool, there's still the synchronization overhead.
June 09, 2010
retard wrote:
> Tue, 08 Jun 2010 19:43:26 +0800, KennyTM~ wrote:
> 
>> On Jun 8, 10 15:55, retard wrote:
>>> Mon, 07 Jun 2010 18:16:15 -0400, Nick Sabalausky wrote:
>>>
>>>> "Nick Sabalausky"<a@a.a>  wrote in message
>>>> news:hujd9m$11of$1@digitalmars.com...
>>>>> "Nick Sabalausky"<a@a.a>  wrote in message
>>>>> news:hujd6a$11e8$1@digitalmars.com...
>>>>>> Assuming, of course, a 'max' that works on a range, which would be
>>>>>> easy enough to do. Probably something like:
>>>>>>
>>>>>>
>>>>> ElementType!T max(T range)  // Corrected
>>>>>
>>>>>> {
>>>>>>     return reduce!ordinaryMax(range);
>>>>>>     // Or
>>>>>>     return reduce!"a>b?a:b"(range);
>>>>>> }
>>>>>>
>>>>>>
>>>>>>
>>>> Or:
>>>>
>>>> alias reduce!"a>b?a:b" max;
>>>>
>>>> God, I love D :)
>>> max = reduce>
>>>
>>> FSM, I love<funfunfun>. :)
>> If there's any language allowing defining a max like this, it has
>> implemented reduce (a.k.a. fold) wrongly.
> 
> Right, I should not have used the symbol >, but last post was right after I woke up. Let's say it depends on the definition of > :)

Hey retard, you are a legend.