Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Re^2: Comparing two arrays

by oiskuu (Pilgrim)
on Dec 16, 2013 at 10:49 UTC ( #1067307=note: print w/ replies, xml ) Need Help??


in reply to Re: Comparing two arrays
in thread Comparing two arrays

I wrote a crude implementation of merge(sort) to estimate the matching speed. 30 buckets each with ~10k sorted, "l/l" packed numbers (representing y-vector ID's). Merge and scan takes about 5 ms (unless I've botched it somewhere). Full search is ten minutes at that rate. Hm.

#! /usr/bin/perl -w use strict; use Inline C => Config => CC => 'clang', OPTIMIZE => '-O3'; use Inline C => <<'__CUT__', NAME => 'm300k'; #define elt I32 static void results(elt n, elt *v[]) { Inline_Stack_Vars; Inline_Stack_Reset; if (n == 1) { elt *p = v[0], c, i = -1 + *p++; for (;;) { for (c = 1; i > 0 && p[0] != p[1]; p++, i--) {} if (i <= 0) break; for (c = 1; i > 0 && p[0] == p[1]; p++, i--) { c++; } if (c < 4) continue; Inline_Stack_Push(sv_2mortal(newSViv(*p))); Inline_Stack_Push(sv_2mortal(newSViv(c))); } } Inline_Stack_Done; } static void merge2(elt *d, elt *a, elt *b) { elt i, *ae = a + *a + 1, *be = b + *b + 1; *d++ = *a++ + *b++; while (i = (ae-a < be-b ? ae-a : be-b)) { for (; i; i--) *d++ = *a < *b ? *a++ : *b++; } if (!(ae-a)) a = b, ae = be; memcpy(d, a, (ae-a) * sizeof(*a)); } // increase stack size if this segfaults (or use malloc) static void nmerge(elt n, elt *v[]) { elt i, j; if (n < 2) return results(n, v); for (j = 0, i = n&1; i < n; i++) { j += *v[i] + 1; } elt tmp[j]; for (j = 0, i = n&1; i < n; i++) { elt *a = v[i], *b = v[--n]; merge2((v[i] = &tmp[j]), a, b); j += *v[i] + 1; } nmerge(n, v); } void vmatch(AV *vv) { elt i, n = 1 + av_len(vv); elt *v[n]; for (i = 0; i < n; i++) { v[i] = (elt*)SvPV_nolen(*av_fetch(vv, i, 0)); } nmerge(n, v); } __CUT__ my @A; sub uniq { keys %{{map {$_ => 1} @_}} } push @A, pack "l/l", sort {$a <=> $b} uniq map int rand(5e6), 1..10000+rand(100) for 1..30; use Benchmark qw(timethis); timethis -5, sub { my @r = vmatch(\@A) };

Update. SSE4.1 version doubled the performance.


Comment on Re^2: Comparing two arrays
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1067307]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (7)
As of 2014-09-03 04:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (35 votes), past polls