Re: [GENERAL] Creation of tsearch2 index is very slow

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On Fri, Jan 20, 2006 at 05:50:36PM -0500, Tom Lane wrote:
> Yeah, but fetching from a small constant table is pretty quick too;
> I doubt it's worth getting involved in machine-specific assembly code
> for this.  I'm much more interested in the idea of improving the
> furthest-distance algorithm in gtsvector_picksplit --- if we can do
> that, it'll probably drop the distance calculation down to the point
> where it's not really worth the trouble to assembly-code it.

I've played with another algorithm. Very simple but it's only O(N). It
doesn't get the longest distance but it does get close. Basically you
take the first two elements as your starting length. Then you loop over
each remaining string, each time finding the longest pair out of each
set of three.

I've only tried it on random strings. The maximum distance for 128
random strings tends to be around 291-295. This algorithm tends to find
lengths around 280. Pseudo code below (in Perl).

However, IMHO, this algorithm is optimising the wrong thing. It
shouldn't be trying to split into sets that are far apart, it should be
trying to split into sets that minimize the number of set bits (ie
distance from zero), since that's what's will speed up searching.
That's harder though (this algorithm does approximate it sort of)
and I havn't come up with an algorithm yet

sub MaxDistFast
{
  my $strings = shift;
 
  my $m1 = 0;
  my $m2 = 1;
  my $dist = -1;

  for my $i (2..$#$strings)
  {
    my $d1 = HammDist( $strings->[$i], $strings->[$m1] );
    my $d2 = HammDist( $strings->[$i], $strings->[$m2] );

    my $m = ($d1 > $d2) ? $m1 : $m2;
    my $d = ($d1 > $d2) ? $d1 : $d2;
    
    if( $d > $dist )
    {
      $dist = $d;
      $m1 = $i;  
      $m2 = $m;
    }
  }
  return($m1,$m2,$dist);
}

Full program available at:
http://svana.org/kleptog/temp/picksplit.pl

Have a nice day,
-- 
Martijn van Oosterhout   <kleptog@xxxxxxxxx>   http://svana.org/kleptog/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.

Attachment: signature.asc
Description: Digital signature


[Postgresql General]     [Postgresql PHP]     [PHP Users]     [PHP Home]     [PHP on Windows]     [Kernel Newbies]     [PHP Classes]     [PHP Books]     [PHP Databases]     [Yosemite]

  Powered by Linux