Groups > comp.os.linux.advocacy > #349396

Re: Algorithm to find data range

From	owl <owl@rooftop.invalid>
Newsgroups	comp.os.linux.advocacy
Subject	Re: Algorithm to find data range
Date	2016-04-11 19:25 +0000
Organization	O.W.L.
Message-ID	<hgjdke902.ata34p@rooftop.invalid> (permalink)
References	<negfcb$4ee$1@dont-email.me> <sandman-2ada1150bc27e3d11b868223a447a75e@individual.net>

Show all headers | View raw

Sandman <mr@sandman.net> 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.
> 

It would be left or right, unless that cut just happened to hit somewhere
in the middle of the range.  If it's a hit, then you test how far left
and right that date it extends.  If this is usenet, I don't think that
for a single group you're going to need to do too many more cuts once
you've landed on a date match.  (Even a Snit-based cola probably had
fewer than 1000 posts in a single day).


> 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.
> 

I took it to mean 500,000 items, not necessarily ID 1 - ID 500,000.

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