Steve Jorgensen wrote:
> What if, instead, there was an OrderedBag class that acts like a
> list and supports set operations.
> The advantage of this is that any hidden indexing that is used to optimize the
> operations could be efficiently created in the object that results from the
> set operati
Kyle Lahnakoski wrote:
> On 2019-09-20 9:52 p.m., Richard Higginbotham wrote:
> > Andrew Barnert wrote:
> > set(b).intersection(a) or set(a) & set(b) or
> > sb =
> > set(b) then [x for x in a if x in sb] and you’re done. They can easily
> > understand why it
Hey Everybody,
I do want to thank you for this souvenir. I've having it blown up and mounted
on the wall. I'm going to leave some space for the benchmarks that compare my
module and his with the standard set implementation.
"I haven’t tested performance at all. I expect it to be slower (when
Andrew Barnert wrote:
> On Sep 23, 2019, at 15:32, Richard Higginbotham higgi...@gmail.com wrote:
> > Considering
> > your use case however, I wonder, if you would not be better
> > going with the iterator approach (as Andrew has been hinting already for
> > some time i
Richard Musil wrote:
> On Mon, Sep 23, 2019 at 12:21 AM Richard Higginbotham higgi...@gmail.com
> wrote:
> > I really appreciate the time and thought you have put
> > into it (and others
> > here as well), and its been educational / fun for me too. One of the
> > conc
Andrew Barnert wrote:
> On Sep 22, 2019, at 15:28, Tim Peters tim.pet...@gmail.com wrote:
> > That's not by accident - the inspiration for
> > CPython's sort's basic
> > "galloping" approach was taken from this paper, which wasn't about
> > sorting at all:
> > "Adaptive Set Intersections, Unions, a
Tim Peters wrote:
> That's not by accident - the inspiration for CPython's sort's basic
> "galloping" approach was taken from this paper, which wasn't about
> sorting at all:
> "Adaptive Set Intersections, Unions, and Differences" (2000)
> Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro
>
>
Richard Musil wrote:
> On Sat, Sep 21, 2019 at 1:44 AM Richard Higginbotham higgi...@gmail.com
> wrote: .
> I wrote all this to show that without an insight it might be sometimes
> difficult or impossible to do it right (I was caught myself in several
> pitfalls on my origin
Steven D'Aprano wrote:
> On Fri, Sep 20, 2019 at 11:44:17PM -, Richard Higginbotham wrote:
> > Let me expand on the reasons for my post here. It
> > seems like
> > motivation has turned into a bit of a bike-shead.
> > I don't think that anyone is quest
Andrew Barnert wrote:
> On Sep 20, 2019, at 14:51, Richard Higginbotham higgi...@gmail.com wrote:
> > Andrew Barnert wrote:
> > What’s the goal here?
> > I'm not concerned about micro op, I'm concerned with macro op on large data
> > sets.
> > Right n
Let me expand on the reasons for my post here. It seems like motivation has
turned into a bit of a bike-shead. I have an algorithm I wanted to see if the
python devs would be interested in. It fulfills my use case as is. I've found
it useful for different problem areas and I haven't seen anythi
Andrew Barnert wrote:
> On Sep 20, 2019, at 09:21, Richard Higginbotham higgi...@gmail.com wrote:
> > Richard Musil wrote:
> > On Fri,
> > Sep 20, 2019 at 1:52 AM Andrew Barnert abarn...@yahoo.com wrote:
> > On Sep 19, 2019, at 15:18, Richard Musil risa20...@gmail.com wr
Chris Angelico wrote:
> On Fri, Sep 20, 2019 at 6:31 AM Richard Higginbotham higgi...@gmail.com wrote:
> >
> > That's exactly what I expected. It's the opposite
> > though. The time to check one list for all the elements
> > Please quote some text to g
Richard Musil wrote:
> On Fri, Sep 20, 2019 at 1:52 AM Andrew Barnert abarn...@yahoo.com wrote:
> > On Sep 19, 2019, at 15:18, Richard Musil risa20...@gmail.com wrote:
After some thought I don't think the the time comparisons are useful unless we
include the set init time. If we already have two
Tim Peters wrote:
> RE [Richard Higginbotham higgi...@gmail.com]
..
> Traversing via a set or dict instead reads the objects' data in
> pseudo-random memory order instead, which can give a very high rate of
> cache misses. In addition, the internal hash table probes also
Andrew Barnert wrote:
> On Sep 19, 2019, at 19:18, Richard Higginbotham higgi...@gmail.com wrote:
> > It's not really constant though.
> > It’s really hard to have a discussion when all of your posts are all
> > replies, but
> you don’t give us any clue what you’re re
It's not really constant though. Look at all of the test results here. Richard
Musil in the following post shows one value of A=1000,B=1 with .034 ms and
the next point A=1,B=5 If the hash were constant time and A increased
by 10x then the time should be 0.34ms but its not. It's 0.54
I think there is a problem here using timeit for this type of problem, look at
the large amount of time used by the set init time. Noticing this I changed my
sorts to in place and got better results. I assume there is some copying of
locals or other overhead but I can't explain the results.
htt
I meant a near linear time complexity. n log n is very very close to n even
when n is large. It's not constant, if it were it could be dropped entirely...
It's pretty close though.
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe
That's exactly what I expected. It's the opposite though. The time to check one
list for all the elements in another list was far longer. Granted this was a
Linux box using ext2. The other helpful element is that the filesystem returned
the files in the proper order. One of the tests runs I ment
>> For example are the file names in A in B and if so return a new list with
>> those items. Long story short, I wrote some functions to do that. They are
>> quite simple and fast (due to timsort in no small part).
>> Even the plain python code is faster than the built in set functions (afaik).
>
The value of the order is actually the critical part. If they are both ordered
I can complete all comparisons in one pass over both lists at the same time.
Lets think about in A and not B
a = [1,2,3,6]
b = [1,4,5,6,7]
start at a[0] and b[0],
0 -- a[i] == b[j] so increment both indexes.
1 -- a[i]
Its faster than the built in set type. Uniqueness of values isn't a
requirement. The values need to be comparable so that they can be sorted. This
allows a linear time complexity. That's basically the only restraint on the
values. Here are some speed test results and pseudocode.
def naive(a,b):
about naming, unique values (not necessary), and sort
order that would probably need to be ironed out if they were to be included
with the built in list type. I'm not qualified to do that work but I'd be happy
to help.
Best Regards,
Richa
24 matches
Mail list logo
