complaints about no replies last week
Aaron Brady
A week ago, I posted a question and an idea about Python's garbage
collector. I got a few replies. Some days later, I posted a mock-up
implementation of it, and got *NO* replies. Does this mean:
a) It works
b) It doesn't work
c) It's not particularly applicable to Python at that point
(particularly)
d) It's not news
Thanks and sincerely.
P.S. Non-plugging links:
http://groups.google.com/group/comp.lang.python/browse_thread/thread/82ebfec89bcc906c/de901f689ae7a962
http://groups.google.com/group/comp.lang.python/browse_thread/thread/d3bb410cc6dcae54/f4b282e545335c30
r
> Hi,
>
> A week ago, I posted a question and an idea about Python's garbage
> collector. I got a few replies. Some days later, I posted a mock-up
> implementation of it, and got *NO* replies. Does this mean:
>
> a) It works
> b) It doesn't work
> c) It's not particularly applicable to Python at that point
> (particularly)
> d) It's not news
>
> Thanks and sincerely.
>
It's probably more like
e) You are not a member of the Illuminati, so the elite don't give a
monkey's toss!
Go back and look over my most infamous thread (i will not utter the
title here but you know of which i speak) and you will see first hand
the wall of resistance put before any non-member who has a good idea.
just ideas
Aahz
Aaron Brady <casti...@gmail.com> wrote:
>
>A week ago, I posted a question and an idea about Python's garbage
>collector. I got a few replies. Some days later, I posted a mock-up
>implementation of it, and got *NO* replies. Does this mean:
>
>a) It works
>b) It doesn't work
>c) It's not particularly applicable to Python at that point
>(particularly)
>d) It's not news
e) the best place to start these days with actual implementations of
ideas is the python-ideas list
--
Aahz (aa...@pythoncraft.com) <*> http://www.pythoncraft.com/
"At Resolver we've found it useful to short-circuit any doubt and just
refer to comments in code as 'lies'. :-)"
--Michael Foord paraphrases Christian Muirhead on python-dev, 2009-3-22
Aaron Brady
> In article <2d80ec1b-5eb5-4e82-9a4a-36934dd53...@z9g2000yqi.googlegroups.com>,
> Aaron Brady <castiro...@gmail.com> wrote:
>
>
>
> >A week ago, I posted a question and an idea about Python's garbage
> >collector. I got a few replies. Some days later, I posted a mock-up
> >implementation of it, and got *NO* replies. Does this mean:
>
> >a) It works
> >b) It doesn't work
> >c) It's not particularly applicable to Python at that point
> >(particularly)
> >d) It's not news
>
> e) the best place to start these days with actual implementations of
> ideas is the python-ideas list
I'm not convinced I'm altogether welcome there. I treated that list
as a social list for some time, not discovering its intensity until
after estranging everybody. Not to mention, I'm not primarily
proposing this idea as an improvement to the reference management;
it's an idea I would probably implement on the side, for an
extension. I just want to know if it's valid and functional. Should
I ask about it on comp.programming? Am I in the right place? Or, is
my idea sophisticated and relevant enough to test the waters again?
> "At Resolver we've found it useful to short-circuit any doubt and just
> refer to comments in code as 'lies'. :-)"
> --Michael Foord paraphrases Christian Muirhead on python-dev, 2009-3-22
P.S. No one read your sig or liked it.
P.P.S. Ok, not bad.
ajaksu
Aaron Brady wrote:
> A week ago, I posted a question and an idea about Python's garbage
> collector. I got a few replies.
Some very nice, too :)
> Some days later, I posted a mock-up
> implementation of it, and got *NO* replies. Does this mean:
It's not particularly clear to me what your goal is in that post.
Something like "I'm trying to model Python's GC" or "here's an
alternative way for the Python GC to work" would make it clear, so
that feedback could be more objective.
Also, a docstring with the executive overview on top of the module
helps a lot, as does including your usage examples as doctests. I've
heard these suggestion regarding my posts recently ;)
However, I think the kind of deep, conceptual feedback I believe you'd
like is available here and elsewhere[1]. It's just a matter of bad
luck/bad timing IMHO :)
Daniel
[1] http://groups.google.com/group/unladen-swallow/browse_thread/thread/c39e75ad6100893f
ajaksu
> Hi,
> c) It's not particularly applicable to Python at that point
> (particularly)
BTW, here's some interesting read:
http://mail.python.org/pipermail/python-3000/2006-September/003855.html
http://mail.python.org/pipermail/python-3000/2007-May/007129.html
http://mail.python.org/pipermail/python-dev/2007-October/074820.html
HTH,
Daniel
Aaron Brady
> Hi!
>
> Aaron Brady wrote:
> > A week ago, I posted a question and an idea about Python's garbage
> > collector. I got a few replies.
>
> Some very nice, too :)
Yes.
> > Some days later, I posted a mock-up
> > implementation of it, and got *NO* replies. Does this mean:
>
> It's not particularly clear to me what your goal is in that post.
> Something like "I'm trying to model Python's GC" or "here's an
> alternative way for the Python GC to work" would make it clear, so
> that feedback could be more objective.
>
> Also, a docstring with the executive overview on top of the module
> helps a lot, as does including your usage examples as doctests. I've
> heard these suggestion regarding my posts recently ;)
>
> However, I think the kind of deep, conceptual feedback I believe you'd
> like is available here and elsewhere[1]. It's just a matter of bad
> luck/bad timing IMHO :)
>
> Daniel
>
> [1]http://groups.google.com/group/unladen-swallow/browse_thread/thread/c...
Hi, Daniel,
I added an explanation of what I want-- a technical discussion of it.
I also included the output in a reply to the code. Unfortunately it's
367 lines long and rather obscure, albeit systematic.
If it works, of course Python could adopt it, but my self-esteem kind
of interferes with thinking that I could have improved something that
is a decade old and hundreds of people have stared at... even though I
do have a CS Bachelor's.
Besides, Martin Lowis said:
> There is an easy design pattern around it, so I'm
> -1 on complicating the GC protocol.
That doesn't mean that no one will help me add it to /my/ project
though.
prue...@latinmail.com
> Hi,
>
> A week ago, I posted a question and an idea about Python's garbage
> collector. I got a few replies. Some days later, I posted a mock-up
> implementation of it, and got *NO* replies. Does this mean:
>
> a) It works
> b) It doesn't work
> c) It's not particularly applicable to Python at that point
> (particularly)
> d) It's not news
>
> Thanks and sincerely.
>
e) It is a hard or complex problem that requires significant
investment of time on a problem or approach that few people are
interested in at the moment.
f) The description is confusing or incomplete or the source code is
long and difficult to read.
I myself asked about how to write a library to efficiently do union
and intersection of sets containing time intervals some time ago on
this list and got little to no answers. It is a tricky problem. Since
I was getting paid I got an O(n*n) solution working. People on this
list on the other hand do not get paid and answer whatever strikes
their fancy. Sometimes the question is hard or confusing and nobody is
motivated enough to answer.
Steven D'Aprano
> I myself asked about how to write a library to efficiently do union and
> intersection of sets containing time intervals some time ago on this
> list and got little to no answers. It is a tricky problem.
With all the confidence of somebody who doesn't need to solve it, I can
say, no, it's an easy problem, provided you use the correct data
structure. What you want is an interval tree:
http://en.wikipedia.org/wiki/Interval_tree
> Since I was
> getting paid I got an O(n*n) solution working.
Just off the top of my head, I *think* you should be able to get that
down to O(m * log n) where m is the size of one set and n the size of the
other. Don't quote me on that though.
> People on this list on the other hand do not get paid
We don't??? Damn! I was expecting a HUGE cheque at the end of the month!
BTW Aaron, I haven't replied to your post about the garbage collector
because that's one part of Python programing where I cherish my ignorance.
--
Steven
Arnaud Delobelle
[...]
> I myself asked about how to write a library to efficiently do union
> and intersection of sets containing time intervals some time ago on
> this list and got little to no answers. It is a tricky problem. Since
> I was getting paid I got an O(n*n) solution working. People on this
> list on the other hand do not get paid and answer whatever strikes
> their fancy. Sometimes the question is hard or confusing and nobody is
> motivated enough to answer.
I wasn't around when you posted this I guess. Do you mean intervals sets
on the (real) number line such as:
1-3, 6-10 meaning all numbers between 1 and 3 and all numbers
between 6 and 10.
In this case I think you can achieve union and intersection in O(nlogn)
where n is the total number of intervals in the interval sets to unify
or intersect. There is an implementation below. I have chosen a very
simple data structure for interval sets: an interval set is the list of
its endpoints. E.g.
1-3, 6-10 is the list [1, 3, 6, 10]
This means that I can't specify whether an interval is closed or open.
So in the implementation below all intervals are assumed to be open.
The method could be made to work for any kind of intervals with the same
complexity, there would just be a few more LOC. I'm focusing on the
principle - here it is:
--------------------------------------------------
# Implementation of union and intersection of interval sets.
from itertools import *
def combine(threshold, intsets):
endpoints = sorted(chain(*imap(izip, intsets, repeat(cycle([1,-1])))))
height = 0
compound = []
for x, step in endpoints:
old_height = height
height += step
if max(height, old_height) == threshold:
compound.append(x)
return compound
def union(*intsets):
return combine(1, intsets)
def intersection(*intsets):
return combine(len(intsets), intsets)
# tests
def pretty(a):
a = iter(a)
return ', '.join("%s-%s" % (a, b) for a, b in izip(a, a))
tests = [
([1, 5, 10, 15], [3, 11, 13, 20]),
([2, 4, 6, 8], [4, 7, 10, 11]),
([0, 11], [5, 10, 15, 25], [7, 12, 13, 15]),
]
for intsets in tests:
print "sets: ", "; ".join(imap(pretty, intsets))
print "union: ", pretty(union(*intsets))
print "intersection: ", pretty(intersection(*intsets))
print "-"*20
--------------------------------------------------
Is this what you were looking for?
--
Arnaud
Arnaud Delobelle
Arnaud Delobelle wrote:
I realised after posting last night that I must be
(1) solving the wrong problem
(2) solving it badly
- My implementation of the combine() function above is O(nlogn)
(because of the sorted() call) whereas it could be O(n) by iterating
over the interval in the parallel manner, hence (2). This would make
union() and intersection() O(n).
- As the problem was solved by the OP in O(n^2) I must be solving the
wrong problem (1).
I apologise for this.
However it was a nice and compact implementation IMHO :)
--
Arnaud
prue...@latinmail.com
> Arnaud Delobelle wrote:
I am pretty sure the problem can be solved in O(n log n). I just
wasn't feeling overly smart when I was writing the algorithm. N is on
average 4 and it had eventually to be implemented inside a framework
using C++ anyway, so it is pretty fast. I can’t believe that no
programmer has come over the same kind of problem before, yet my
Google fu didn’t do anything for me.
Well since I attracted a couple people's attention I will describe the
problem in more detail. Describing the problem properly is probably as
hard as solving it, so excuse me if I struggle a bit.
The problem is for a health insurance company and involves the period
of time a person is covered. Most insurance companies allow not only
for the main member to be insured but his family: the spouse and the
dependents (children). This additional coverage costs extra but less
than a full new insurance. So for example if Alice buys an insurance
worth at 100 dollars a month, she can insure her husband Bob for an
additional 50 dollars. Under certain circumstances Alice may go off
the insurance and only Bob stays. In that case the price goes back to
100 dollars or maybe there is a deal for 80 or something like that. In
other words the cost of the insurance is dependent on the combination
of family members that participate in it. Additionally not only do we
have different family compositions but also different insurance
products. So you can get medical, dental and vision insurance.
All that data is stored in a database that is not very tidy and looks
something like this:
First Day of Coverage, Last Day of Coverage, Relationship, Product
5/3/2005, 5/3/2005, D, M
9/10/2005, 10/10/2005, S, V
3/15/2005, 7/15/2005, M, M
3/1/2005, 6/1/2005, S, M
5/15/2005, 7/20/2005, D, D
9/10/2005, 1/1/2140, M, V
2/1/2005, 5/3/2005, M, M
Where
Relationship: M=Main Member, S=Spouse, D=Dependent
Product: M=Medical, D=Dental, V=Vision
As far as I know at the present time there are no deals based on
combination of products purchased so we will handle each product
independently. What I want is a simple algorithm that allows me to
calculate something like this out of it (hopefully I didn’t make a
mistake):
Medical:
2/1/2005, 2/28/2005, M
3/1/2005, 5/2/2005, M&S
5/3/2005, 5/3/2005, M&S&D
5/4/2005, 6/1/2005, M&S
6/2/2005, 7/15/2005, M
Dental:
5/15/2005, 7/20/2005, D
Vision:
9/10/2005, 10/10/2005, M&S
10/11/2005, 1/1/2140, M
Arnaud Delobelle
[...]
OK the approach I describe in my previous email works fine for this
particular problem. I implement it below - the function walk_ivals is at
the heart of it, I've made it as simple as possible and it's pretty
clear that it is O(nlogn).
The function that actually sorts the data is union(), and it's just a
call to walk_ivals with callback the function acc() which is constant
time, therefore union() itself has the same complexity as walk_ivals.
There are no comments - I don't have the time to add any, sorry!
--------------------------------------------------
import datetime
from collections import defaultdict
def walk_ivals(ivals, callback, endvals=(-1, 1)):
endpoints = [(x, data) for ival, data in ivals for x in zip(ival, endvals)]
endpoints.sort()
for (endpoint, endval), data in endpoints:
callback(endpoint, endval, data)
def union(ivals):
timelines = defaultdict(list)
mult = defaultdict(lambda: defaultdict(int))
def acc(date, step, data):
rel, prod = data
old_mult = mult[prod][rel]
mult[prod][rel] -= step
if not(old_mult and mult[prod][rel]):
rels = [rel for rel, m in mult[prod].iteritems() if m]
if timelines[prod] and timelines[prod][-1][0] == date:
timelines[prod][-1][1] = rels
else:
timelines[prod].append([date, rels])
walk_ivals(ivals, acc)
return timelines
test_data = """5/3/2005, 5/3/2005, D, M
9/10/2005, 10/10/2005, S, V
3/15/2005, 7/15/2005, M, M
3/1/2005, 6/1/2005, S, M
5/15/2005, 7/20/2005, D, D
9/10/2005, 1/1/2140, M, V
2/1/2005, 5/3/2005, M, M"""
def parse_date(date_string):
month, day, year = map(int, date_string.split('/'))
return datetime.date(year, month, day)
def parse_data(data_string):
data = []
for line in data_string.split("\n"):
start, end, rel, prod = line.split(",")
start, end = map(parse_date, (start + datetime.timedelta(1), end))
rel, prod = rel.strip(), prod.strip()
data.append([(start, end), (rel, prod)])
return data
def test():
ivals = parse_data(test_data)
timelines = union(ivals)
for prod, timeline in timelines.iteritems():
print "-"*20
print "Product", prod
for date, covers in timeline:
print date, ' & '.join(covers)
if __name__ == '__main__':
test()
--------------------------------------------------
Here is what it outputs:
marigold:junk arno$ python intervals2.py
--------------------
Product M
2005-02-01 M
2005-03-01 S & M
2005-05-03 S & M & D
2005-05-04 S & M
2005-06-02 M
2005-07-16
--------------------
Product D
2005-05-15 D
2005-07-21
--------------------
Product V
2005-09-10 S & M
2005-10-11 M
2140-01-02
--------------------------------------------------
The date output is slightly different from yours - I didn't realise you
had time intervals and now I don't have the time to change it, although
it's only a cosmetic change (the end-date of each interval is the
start-date of the next one minus 1 day).
HTH
PS: warning - I have done some minor editing of the code after pasting
it, so it might break (although it should be fine).
--
Arnaud
Aahz
Arnaud Delobelle <arn...@googlemail.com> wrote:
>
>There are no comments - I don't have the time to add any, sorry!
The margin is too small to contain the proof?
--
Aahz (aa...@pythoncraft.com) <*> http://www.pythoncraft.com/
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are, by
definition, not smart enough to debug it." --Brian W. Kernighan
Arnaud Delobelle
> Arnaud Delobelle <arn...@googlemail.com> wrote:
>>
>>There are no comments - I don't have the time to add any, sorry!
>
> The margin is too small to contain the proof?
I wish I could come up with such a resilient conjecture!
Ah but in this case, the proof is in the program, as Curry-Howard may
well have said.
--
Arnaud
prue...@latinmail.com
Thanks Arnaud,
indeed I got this error when running the program:
Traceback (most recent call last):
File "C:/Python26/timeint2.py", line 57, in <module>
test()
File "C:/Python26/timeint2.py", line 48, in test
ivals = parse_data(test_data)
File "C:/Python26/timeint2.py", line 42, in parse_data
start, end = map(parse_date, (start + datetime.timedelta(1), end))
TypeError: cannot concatenate 'str' and 'datetime.timedelta' objects
easy fix:
start, end = map(parse_date, (start , end))
end+=datetime.timedelta(1)
I am assuming you want close-open intervals.
I also added another line to the test:
test_data = """5/3/2005, 5/3/2005, D, M
9/10/2005, 10/10/2005, S, V
3/15/2005, 7/15/2005, M, M
3/1/2005, 6/1/2005, S, M
5/15/2005, 7/20/2005, D, D
9/10/2005, 1/1/2140, M, V
2/1/2005, 5/3/2005, M, M
3/1/2004, 7/1/2004, M, M"""
result:
--------------------
Product M
2004-03-01 M
2004-07-02
2005-02-01 M
2005-03-01 S & M
2005-05-03 S & M & D
2005-05-04 S & M
2005-06-02 M
2005-07-16
--------------------
Product D
2005-05-15 D
2005-07-21
--------------------
Product V
2005-09-10 S & M
2005-10-11 M
2140-01-02
The output will have to be massaged to get the begin and end of each
interval, but otherwise this is more or less what I was looking for.
The walk_ivals and union function are 20 lines of pretty dense code. I
will have to study it a bit to understand how it really works.
Thanks again
Aaron Brady
> a...@pythoncraft.com (Aahz) writes:
> > Arnaud Delobelle <arno...@googlemail.com> wrote:
>
> >>There are no comments - I don't have the time to add any, sorry!
>
> > The margin is too small to contain the proof?
>
> I wish I could come up with such a resilient conjecture!
>
> Ah but in this case, the proof is in the program, as Curry-Howard may
> well have said.
Is it simple, complex, or complicated? IS IT FLAT OR NESTED! </
shouting>