Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.os.linux.advocacy > #349365
| From | DFS <nospam@dfs.com> |
|---|---|
| Newsgroups | comp.os.linux.advocacy |
| Subject | Algorithm to find data range |
| Date | 2016-04-11 11:23 -0400 |
| Organization | A noiseless patient Spider |
| Message-ID | <negfcb$4ee$1@dont-email.me> (permalink) |
Take a list of data:
ID Date
1 2004-05-04
2 2004-05-04
3 2004-05-05
4 2004-05-06
5 2004-05-08
...
500000 2014-05-03
I want to find the best approach to determine the unknown range of ID
numbers that correspond to a known range of dates.
That is:
* you know the date range you're interested in (say all of Sep 2008)
* you want to know the corresponding ID range (say 124385 to 125008).
The problem is you can't query or retrieve the data by date, only by ID
number. This restriction is what makes the whole thing an ordeal.
Other constraints:
* data is pulled off a busy server. You can't be hitting it
all day long.
* you can retrieve and examine max of 100 rows at a time. This is a
judgement call. I'll try 100 and see what works best, and
increase or decrease it based on performance.
* the numbers and dates are ordered low to high, but not continuous -
there are gaps in both numbers and dates.
* can't load the data into a SQL table and do min() or max(), so it's
a code-only solution (python here).
The brute-force way is to download all 500K rows, put them in a db table
and query them. That's not an option (well, it could technically be
done but then there's no thinking and creativity and challenge involved
- and what else is geek life for?).
I was thinking about three approaches that I call:
---------------------------------------------------------------------
1. Half-Height Elimination:
examine 1 row at a time (starting with the middle row), cutting the data
to be examined in half on each iteration. This will require some kind
of recursive coding methodology. With a domain of 500K rows, this
approach could require as many as 19 iterations (and each iteration
would involve a small request from the server) in its simplest form:
Iter Rows Remaining
500000
1 250000
2 125000
3 62500
4 31250
5 15625
6 7813
7 3906
8 1953
9 977
10 488
11 244
12 122
13 61
14 31
15 15
16 8
17 4
18 2
19 1 (found your search date)
This pic will help to see how it works:
http://i.imgur.com/AFfIjrI.png
---------------------------------------------------------------------
2. Decile Seek:
create N class objects and have each one scan a short range of data
simultaneous with the other objects, then on to the next range of data
an so on. Each object would be responsible for scanning up to 50K rows,
low to high. Eventually one will hit the beginning of the known date
range, and one will hit the end of the known date range, and then I'll
know the corresponding number range. This would probably be the slowest
and most "wasteful" approach I've come up with, but it could be
interesting to develop.
pic: http://i.imgur.com/iKjhbOM.jpg
---------------------------------------------------------------------
3. Date Distribution:
if you assume the ID numbers and the dates are evenly distributed across
time (ID 1 to 500000, 500K rows over 10 years, 50K per year, 4167 per
month, 962 per week, 137 per day, etc), then it's a simple calculation
to determine at which ID number your date range starts. It won't be
exact because the data isn't actually evenly distributed (gaps as
mentioned before), but it will be a good start.
Calculation:
A = first date of data
B = first date of search
C = last date of search
D = last date of data
firstID = earliest ID number
lastID = latest ID number
Start search ID at: ((B-A)/(D-A)) * (lastID - firstID)
End search ID at: ((C-A)/(D-A)) * (lastID - firstID)
Note: for most searches, A < B < C < D.
pic http://i.imgur.com/SQcq9Hz.jpg
---------------------------------------------------------------------
I haven't coded any of these approaches, but the Date Distribution
approach will probably be fastest and most efficient by far (as measured
by both server hits and processing time).
If you read this far you probably have an opinion or thought. Let's
hear it!
Back to comp.os.linux.advocacy | Previous | Next — Next in thread | Find similar | Unroll thread
Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-11 11:23 -0400
Re: Algorithm to find data range Sandman <mr@sandman.net> - 2016-04-11 17:09 +0000
Re: Algorithm to find data range owl <owl@rooftop.invalid> - 2016-04-11 19:25 +0000
Re: Algorithm to find data range Sandman <mr@sandman.net> - 2016-04-11 20:58 +0000
Re: Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-11 17:38 -0400
Re: Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-11 18:11 -0400
Re: Algorithm to find data range owl <owl@rooftop.invalid> - 2016-04-11 22:25 +0000
Re: Algorithm to find data range Sandman <mr@sandman.net> - 2016-04-12 06:16 +0000
Re: Algorithm to find data range owl <owl@rooftop.invalid> - 2016-04-11 21:46 +0000
Re: Algorithm to find data range Sandman <mr@sandman.net> - 2016-04-12 07:18 +0000
Re: Algorithm to find data range owl <owl@rooftop.invalid> - 2016-04-12 08:15 +0000
Re: Algorithm to find data range Sandman <mr@sandman.net> - 2016-04-12 10:34 +0000
Re: Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-12 13:32 -0400
Re: Algorithm to find data range Steve Carroll <fretwizzer@gmail.com> - 2016-04-12 10:39 -0700
Re: Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-12 13:58 -0400
Re: Algorithm to find data range Steve Carroll <fretwizzer@gmail.com> - 2016-04-12 11:59 -0700
Re: Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-11 23:23 -0400
Re: Algorithm to find data range Sandman <mr@sandman.net> - 2016-04-12 07:14 +0000
Re: Algorithm to find data range owl <owl@rooftop.invalid> - 2016-04-12 10:44 +0000
Re: Algorithm to find data range owl <owl@rooftop.invalid> - 2016-04-12 15:17 +0000
Re: Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-13 17:15 -0400
Re: Algorithm to find data range owl <owl@rooftop.invalid> - 2016-04-13 22:23 +0000
Re: Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-13 18:32 -0400
Re: Algorithm to find data range owl <owl@rooftop.invalid> - 2016-04-14 04:33 +0000
Re: Algorithm to find data range owl <owl@rooftop.invalid> - 2016-04-14 05:51 +0000
Re: Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-14 20:15 -0400
Re: Algorithm to find data range owl <owl@rooftop.invalid> - 2016-04-15 01:18 +0000
Re: Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-12 13:25 -0400
Re: Algorithm to find data range owl <owl@rooftop.invalid> - 2016-04-12 19:08 +0000
Re: Algorithm to find data range vallor <vallor@cultnix.org> - 2016-04-12 04:40 +0000
Re: Algorithm to find data range owl <owl@rooftop.invalid> - 2016-04-11 18:06 +0000
Re: Algorithm to find data range 7 <7@enemygadgets.com> - 2016-04-11 22:46 +0000
Re: Algorithm to find data range Omar <omarsayeed@linuxmail.org> - 2016-04-11 18:52 -0400
Re: Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-12 13:28 -0400
Re: Algorithm to find data range Omar <omarsayeed@linuxmail.org> - 2016-04-12 13:46 -0400
Re: Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-11 22:13 -0400
Re: Algorithm to find data range Fabian Russell <fb@zen.info> - 2016-04-11 23:22 +0000
Re: Algorithm to find data range vallor <vallor@cultnix.org> - 2016-04-12 00:06 +0000
Re: Algorithm to find data range Omar <omarsayeed@linuxmail.org> - 2016-04-11 20:26 -0400
Re: Algorithm to find data range Chris Ahlstrom <OFeem1987@teleworm.us> - 2016-04-12 05:30 -0400
Re: Algorithm to find data range chrisv <chrisv@nospam.invalid> - 2016-04-12 06:50 -0500
Re: Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-11 22:34 -0400
Re: Algorithm to find data range Fabian Russell <fb@zen.info> - 2016-04-12 09:25 +0000
Re: Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-12 13:32 -0400
Is it your own personal NNTP/Usenet server ? Jeff-Relf.Me <@.> - 2016-04-11 16:32 -0700
Re: Algorithm to find data range DFS <nospam@dfs.com> - 2016-04-12 12:47 -0400
Re: Algorithm to find data range Peter Köhlmann <peter-koehlmann@t-online.de> - 2016-04-12 20:46 +0200
Re: Algorithm to find data range chrisv <chrisv@nospam.invalid> - 2016-04-12 13:59 -0500
Re: Algorithm to find data range Silver Slimer <linux@sucks.balls> - 2016-04-12 17:08 -0400
My "newsReader" (X.ZIP) is also a console. Jeff-Relf.Me <@.> - 2016-04-12 12:27 -0700
My "newsReader" (X.ZIP) is also a console. Jeff-Relf.Me <@.> - 2016-04-12 12:31 -0700
csiph-web