My first reaction to all this was...why use SQL to do this?
Then after I saw 333450 results I was wondering if that was accurate.
Out of 10,000 records there should be 384.62 average name matches
The odds of being < 10 with 0-99 position is approx 10000*.1
This gives us 384.62*(10000-384.62)*0.1 or 369,822 matches -- it will be a
little less due to the edge conditions.
I'm averaging 363,000 or so matches. That's a 10% difference.
I've got 10,000 records with 'a'-'z' name and 0-99 position.
So here's C++ that runs in 0.068 seconds -- about 34 times faster than the
fastest query shown.
#include <iostream>
#include <vector>
using namespace std;
#define N 10000
#define POS 100
#define DX 10
struct s_datum
{
unsigned char name;
unsigned char pos;
} datum;
int
main (int argc, char *argv[])
{
vector < struct s_datum >v;
srandom (time (NULL));
for (int i = 0; i < N; i++) {
datum.name = (random () % 26) + 'a';
datum.pos = random () % POS;
v.push_back (datum);
//cout << datum.name << "," << (int)datum.pos << endl;
}
int match = 0;
for (int i = 0; i < 10000; i++) {
for (int j = i; j < N; j++) {
if (v[i].name != v[j].name) {
continue;
}
int dx = abs (v[i].pos - v[j].pos);
if (dx != 0 && dx <= DX) {
match++;
// cout << v[i].name << "," << (int)v[i].pos << "," <<
v[j].name << "," << (int)v[j].pos << "," "dx=" << dx << endl;
}
}
}
cout << match << endl;
}
Michael D. Black
Senior Scientist
Advanced Analytics Directorate
Northrop Grumman Information Systems
________________________________
From: sqlite-users-boun...@sqlite.org on behalf of ve3meo
Sent: Sat 8/21/2010 4:25 PM
To: sqlite-users@sqlite.org
Subject: EXTERNAL:Re: [sqlite] What is the most efficient way to
gettheclosebynumbers?
"Simon Slavin" ...
>
>> Here's how I have interpreted Simon's suggested chunky query:
>>
>> select * from A as A1, A as A2 where A1.name=A2.name and
>> A1.position != A2.position and
>> A2.chunk between A1.chunk - 1 and A1.chunk + 1 and
>> A2.position between A1.position - 10 and A1.position + 10 ;
>
> That's exactly what I meant. It allows you to reject everything not in
> those three chunks immediately, before even working out what 'position -
> 10' and 'position + 10' are. But looking again at your formulation with
> 'between' in ...
>
>> select * from A as A1, A as A2 where A1.name=A2.name and
>> A1.position != A2.position and
>> A2.position between A1.position - 10 and A1.position + 10 ;
>
> I think that that might be just as fast, and not require you to work out
> the chunks, or take up all the space the chunk indexes will take up, or
> the time it will take to generate them. So we're back to the same old
> song: Try the simpler solution. If it's fast enough, use it. Only if it
> isn't fast enough is it worth optimizing.
>
> By the way, you might find that swapping the last two lines makes it
> faster:
>
>
>> select * from A as A1, A as A2 where A1.name=A2.name and
>> A2.position between A1.position - 10 and A1.position + 10 and
>> A1.position != A2.position ;
>
> But you might not: SQLite's optimizer may already have spotted it.
I did some tests on a 10,000 row table similar to Peng's example with name a
random alpha and random position 0-99, distance 10: each query returned
333,450 results.
~62s: Peng's original query with no index, either order of constraints
~4s: Peng's original query with idxNamePos, either order
~2.3s: Jim's 'between' query with idxNamePos, either order
~2.7s: Simon's 'chunky' addition to Jim's with idxNameChunkPos, any order
So:
1. Simpler is best, in this case. The 'chunking' option paid a ~16% penalty
in speed and added considerable complexity and storage requirement.
2. The order of the where constraints did not seem to matter - I guess the
optimiser sorts it out or maybe the random nature of the data offers no
advantage to any particular order.
Tom
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
