Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.os.linux.advocacy > #349466
| From | vallor <vallor@cultnix.org> |
|---|---|
| Newsgroups | comp.os.linux.advocacy |
| Subject | Re: Algorithm to find data range |
| Date | 2016-04-12 04:40 +0000 |
| Message-ID | <dn3ci9Fq114U2@mid.individual.net> (permalink) |
| References | <negfcb$4ee$1@dont-email.me> <sandman-2ada1150bc27e3d11b868223a447a75e@individual.net> |
On Mon, 11 Apr 2016 17:09:19 +0000, Sandman wrote:
> In article <negfcb$4ee$1@dont-email.me>, DFS wrote:
>
>> 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).
>
> That's some strange limitations.
>
>> 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:
>
>> This pic will help to see how it works: http://i.imgur.com/AFfIjrI.png
>
> That supposes that for each cut, the date range is in the cut. I.e. it
> could just as easily be twice as many cuts.
>
> Also, given restriction 3 above, there is no way for you to know what ID
> is at the middle of a sample. If you have 500k rows of data, you'd think
> that ID 250,000 would be in the middle, but since it was stipulated that
> ID could contain caps and not be continuous, you may have cut two thirds
> up in the series. In fact, ID 250,000 may be the very last ID according
> to rule #3. Or the first, for that matter.
Two things:
A binary seek doesn't need recursion, just two loops.
First loop needs a left bracket, a right bracket, and a test point (which
I like to call the "gripping bracket").
$lb,$rb,$gb
set $lb to position 0, $rb to end of range
LOOP1:
$gb = split the difference
if $gb is within the desired range, break and do the next loop
if the desired range is to the left (msg-id less than) $gb,
then make $gb = $rb
similarly, if the desired range is to the right of $gb, make $lb = $gb
LOOP2:
this is where you have found the "neighborhood" of your data. At this
point you'll have to use heuristics to figure out the range, possibly by
making guesses based on the average number of posts within a time period.
> In the end, traversing 500k lines of data is just as quick with todays
> CPU's.
It sounds like he's building leet spy tools that won't hammer his nntp
server. The XOVER (or the new "OVER") NNTP command can grab the metadata
for a group, and servers are optimized to hand this data over very
quickly. Thinking in those terms might yield more fruitful results. For
example (because I'm a perl guy), I'd be looking into:
https://tools.ietf.org/html/rfc3977#page-81
and
https://metacpan.org/pod/Net::NNTP
BTW: back when Webster servers were in short supply (c. 1996), I wrote a
tool to perform a dictionary which included a binary seek.
Here is what the output looks like when I run the debugging version:
/opt/sdict/lib]_(scott@xxx)_
$ ./show.pl jerk
{ * } span
0 187018 374036 374036
0 93509 187018 187018
93509 140263 187018 93509
140263 163640 187018 46755
163640 175329 187018 23378
175329 181173 187018 11689
175329 178251 181173 5844
178251 179712 181173 2922
178251 178981 179712 1461
178251 178616 178981 730
1 jerk \'j*rk\ vb
1: to give a sharp quick push, pull, or twist
2: to move in short abrupt motions
2 jerk n
1: a short quick pull or twist : TWITCH
2: a stupid, foolish, or eccentric person
-- jerk.i.ly adv
-- jerky adj
--
-v
Kernel:4.6.0-rc2-sd Desktop:Xfce 4.12.2 Distro:Linux Mint 17.3 Rosa
Back to comp.os.linux.advocacy | Previous | Next — Previous in thread | 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