Re^6: list of unique strings, also eliminating matching substrings

[lindsay_grey]

I seem to be having a problem with Inline. Maybe I just need to get one of the "apple-darwin" files it is looking for. I will keep trying. Thanks for posting your code.

  Starting "make" Stage
i686-apple-darwin10-gcc-4.2.1: Module: No such file or directory
i686-apple-darwin10-gcc-4.2.1: no input files
i686-apple-darwin10-gcc-4.2.1: Module: No such file or directory
i686-apple-darwin10-gcc-4.2.1: no input files
powerpc-apple-darwin10-gcc-4.2.1: Module: No such file or directory
powerpc-apple-darwin10-gcc-4.2.1: no input files
lipo: can't figure out the architecture type of: /var/folders/Jx/Jx+cO
+TNTFTSKERHsDjE+nU+++TI/-Tmp-//cch73GJV.out
make: *** [_906020.o] Error 1

A problem was encountered while attempting to compile and install your
+ Inline
C code. The command that failed was:
  make

[BrowserUk]

That looks like you do not have Inline::C installed correctly, but I can't help you with that. If it is the case...ie. if the Inline::C installation tests are failing, then you shoudl post a new thread about that to get help.

In the interim, you can try this pure perl version which is only half as fast as the inline version, but that should still be 7 times faster than your current solution. Let me know how you get on.

#! perl -slw
use strict;
use Time::HiRes qw[ time ];

$|++;

sub uniq{ my %x; @x{@_} = (); keys %x }

my $start = time;
my @uniq = uniq <>;
chomp @uniq;

@uniq = sort{ length $a <=> length $b } @uniq;

my $all = join chr(0), @uniq;
my $p = 0;

for my $x ( @uniq ) {
    $p += 1+ length $x;
    next if 1+ index $all, $x, $p; ## COrrected per LanX below.
    print $x;
}

printf STDERR "Took %.3f\n", time() - $start;

[LanX]

I had a similar idea but with some modifications:

1. starting with the longest string and continuing in descending order

2. then only appending the non-embeddable strings to $all

like this $all is in average significantly shorter and the tests with index should be faster.

I'm also wondering if the reallocation of new memory when appending to $all could be avoided by starting with a maximal length string and then shortening $all again.

Maybe uniq() from List::MoreUtils is faster or could be completely avoided (after sorting identical strings always appear in a sequence)

All of this highly depends on the nature of the unknown data and should only be tested with identical sets...

[BrowserUk]

1. 1. starting with the longest string and continuing in descending order

   I don't get the idea of putting the longest first?

   The idea of putting the shortest first is that you can use the third parameter to index to skip over the shorter strings as you've checked them. Longer strings can never be contained by the shorter ones, and starting the search part way into the string is much cheaper than trimming the shorter ones off the end.

2. 2. then only appending the non-embeddable strings to $all

   I do not know what you mean by "non-embeddable" in this context?

3. I'm also wondering if the reallocation of new memory when appending to $all could be avoided by starting with a maximal length string and then shortening $all again.

   If you mean counting the space required for $all, allocating to that final size and then copying the elements into the string--rather than building it up by appending each element in turn--that is exactly what join does.

4. Maybe uniq() from List::MoreUtils is faster

   Not in my tests. Mine usually works out ~15% faster.

5. or could be completely avoided (after sorting identical strings always appear in a sequence)

   That would mean sorting the duplicates. Sorting is O(N log N); de-duping O(1). And after the sorting, you;d still need to make a complete pass with grep to remove the dups before joining.

[LanX]

just noticed that index returns -1 for a missing match.

you say this worked?

    next if index $all, $x, $p;

did you manipulate $[ somewhere???

[BrowserUk]

You're right. I edited rather than c&p :( and forgot my usual 1+.

 next if 1+index $all, $x, $p;

Code above amended.