Am 04.07.2013 20:36, schrieb James K. Lowden:
Yes, and there's your O(N log N): N for the SCAN and log(N) for the
SEARCH. To process 1,000,000 rows takes 1,000,000 accesses. To produce
the rank requires roughly 20 searches per row (given an appropriate
index), or 20,000,000 total accesses. Plus some work, depending on
memoization, to count the nodes beneath the found one.
Inefficient? It's the theoretical *minimum* for the general case.
>... snip ...
>
Did I miss something, or have I answered your efficiency concerns?
What you missed, is apparently *testing* your own suggestions...
You know, those "practical things" some of us do from time to time...
;-)
Well, I just did so (using a small Table with an index on ID
for your self-join-suggestion):
Create Table T (ID Integer Primary Key, Item Text)
Select Count(Lesser.ID), T.ID, T.Item From T As T
Left Outer Join T As Lesser
On T.ID > Lesser.ID
Group By T.ID
Order By T.ID
I don't know, what I'm doing wrong - but my timing-trend
comes out like this:
RecordCount in T msec for the above query
100 3msec
1000 186msec
10000 17857msec
And so, after waiting already for about 18 seconds for the query
to complete with only 10000 records in T, I will of course not
try it with the "1,000,000 rows" you were mentioning above. <g>
Olaf
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
