Re: Union slowdown when SameTest is specified
- To: mathgroup at smc.vnet.net
- Subject: [mg101393] Re: Union slowdown when SameTest is specified
- From: Szabolcs <szhorvat at gmail.com>
- Date: Sat, 4 Jul 2009 06:44:40 -0400 (EDT)
- References: <h2kjfb$in3$1@smc.vnet.net>
On Jul 3, 12:36 pm, J Siehler <jsiehler at gmail.com> wrote:
> Hello group! I was a little surprised and puzzled by the following:
>
> In[1]:= $Version
> Out[1]= "7.0 for Mac OS X PowerPC (32-bit) (November 10, 2008)"
>
> In[2]:= data = RandomInteger[{1, 10}, {5000, 2, 12}];
> Timing[Union[data];]
> Out[3]= {0.008138, Null}
>
> So far so good; so far so speedy. But why does this happen:
>
> In[4]:= Timing[Union[data, SameTest -> Equal];]
> Out[4]= {15.313, Null}
>
> Or more egregiously,
>
> In[5]:= Timing[Union[data, SameTest -> (First@#1 == First@#2 &)];]
> Out[5]= {86.293, Null}
>
> There's nothing special about the form of the data here, just it
> happens to be similar in form to the data I was working on when I
> experienced terrible slowdown with the SameTest that I've shown in the
> third example - which doesn't seem like a demanding comparison. So
> can anyone explain the orders-of-magnitude change in times here? Much
> appreciated!
Without running any tests---my guess is that the default algorithm
used by Union exploits the fact that the elements of the list can be
sorted. When you specify your own SameTest, Union won't know any more
what less-than and greater-than comparison to use that is compatible
with your specific SameTest.