Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.tele.dk!feed118.news.tele.dk!news.tele.dk!small.news.tele.dk!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <CACwCsY6W3x+8QzkJ8GR7qeck9s4xkwkhUbRt4k2iBAGcFuUb2g@mail.gmail.com>
References: <CACwCsY6KBDVkS5jCMh9GyvhHyVgqcAH3YAYnGpMQvfBwexaTcw@mail.gmail.com> <CAPTjJmpGKzCbB4ZMZG=UAhh5hq8JowUOuerS1dk-rt3T6_qCyw@mail.gmail.com> <CACwCsY6W3x+8QzkJ8GR7qeck9s4xkwkhUbRt4k2iBAGcFuUb2g@mail.gmail.com>
Date: Mon, 13 Jan 2014 17:09:59 +1100
Subject: Re: efficient way to process data
From: Chris Angelico <rosuav@gmail.com>
Cc: "python-list@python.org" <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.5395.1389593409.18130.python-list@python.org>
Lines: 56
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:63812

On Mon, Jan 13, 2014 at 2:35 PM, Larry Martell <larry.martell@gmail.com> wrote:
> Thanks for the reply. I'm going to take a stab at removing the group
> by and doing it all in python. It doesn't look too hard, but I don't
> know how it will perform.

Well, if you can't switch to PostgreSQL or such, then doing it in
Python is your only option. There are such things as GiST and GIN
indexes that might be able to do some of this magic, but I don't think
MySQL has anything even remotely like what you're looking for.

So ultimately, you're going to have to do your filtering on the
database, and then all the aggregation in Python. And it's going to be
somewhat complicated code, too. Best I can think of is this, as
partial pseudo-code:

last_x = -999
x_map = []; y_map = {}
merge_me = []
for x,y,e in (SELECT x,y,e FROM t WHERE whatever ORDER BY x):
    if x<last_x+1:
        x_map[-1].append((y,e))
    else:
        x_map.append([(y,e)])
    last_x=x
    if y in y_map:
        merge_me.append((y_map[y], x_map[-1]))
    y_map[y]=x_map[-1]

# At this point, you have x_map which is a list of lists, each one
# being one group, and y_map which maps a y value to its x_map list.

last_y = -999
for y in sorted(y_map.keys()):
    if y<last_y+1:
        merge_me.append((y_map[y], last_x_map))
    last_y=y
    last_x_map=y_map[y]

for merge1,merge2 in merge_me:
    merge1.extend(merge2)
    merge2[:]=[] # Empty out the list

for lst in x_map:
    if not lst: continue # been emptied out, ignore it
    do aggregate stats, get sum(lst) and whatever else

I think this should be linear complexity overall, but there may be a
few aspects of it that are quadratic. It's a tad messy though, and
completely untested. But that's an algorithmic start. The idea is that
lists get collected based on x proximity, and then lists get merged
based on y proximity. That is, if you have (1.0, 10.1), (1.5, 2.3),
(3.0, 11.0), (3.2, 15.2), they'll all be treated as a single
aggregation unit. If that's not what you want, I'm not sure how to
handle it.

ChrisA