On 7/14/17, Steve D'Aprano wrote:
> On Fri, 14 Jul 2017 09:06 am, Ned Batchelder wrote:
>
>> Steve's summary is qualitatively right, but a little off on the
>> quantitative
>> details. Lists don't resize to 2*N, they resize to ~1.125*N:
>>
>> new_allocated = (size_t)newsize + (newsize >> 3) +
On Fri, 14 Jul 2017 09:06 am, Ned Batchelder wrote:
> Steve's summary is qualitatively right, but a little off on the quantitative
> details. Lists don't resize to 2*N, they resize to ~1.125*N:
>
> new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
>
> (https://github
Rustom Mody writes:
> Yeah I know append method is supposedly O(1).
It's amortized O(1).
--
https://mail.python.org/mailman/listinfo/python-list
On Thursday, July 13, 2017 at 10:59:52 AM UTC-4, Pavol Lisy wrote:
> On 7/13/17, Steve D'Aprano wrote:
>
> > [1] Actually, CPython's lists initially quadruple the size of the array, up
> > to a
> > certain point, and then switch to doubling. This ensures that small lists
> > have
> > even fewer e
On Fri, Jul 14, 2017 at 2:26 AM, Steve D'Aprano
wrote:
> On Fri, 14 Jul 2017 01:09 am, Rustom Mody wrote:
>
>> Couple that with the fact that space-time are not unrelated on any modern VM
>> based OS + cache based hw. Doubly so for "managed" languages where gc buys
>> space for time.
>
> I don't u
On 7/13/17, Steve D'Aprano wrote:
> On Fri, 14 Jul 2017 12:59 am, Pavol Lisy wrote:
>
>> On 7/13/17, Steve D'Aprano wrote:
>>
>>> [1] Actually, CPython's lists initially quadruple the size of the array,
>>> up
>>> to a
>>> certain point, and then switch to doubling. This ensures that small lists
On Fri, 14 Jul 2017 12:59 am, Pavol Lisy wrote:
> On 7/13/17, Steve D'Aprano wrote:
>
>> [1] Actually, CPython's lists initially quadruple the size of the array, up
>> to a
>> certain point, and then switch to doubling. This ensures that small lists
>> have
>> even fewer expensive resizes, at th
On Fri, 14 Jul 2017 01:09 am, Rustom Mody wrote:
> Couple that with the fact that space-time are not unrelated on any modern VM
> based OS + cache based hw. Doubly so for "managed" languages where gc buys
> space for time.
I don't understand that comment. Space/time have *never* been unrelated.
On 13/07/17 16:09, Rustom Mody wrote:
Pavol Lisy wrote:
IMHO problem is doubling size for huge lists.
Or waste big memory for huge frozensets. I mean resize it to 2*N if
its size is just N+1.
Couple that with the fact that space-time are not unrelated on any modern VM based OS +
cache base
Pavol Lisy wrote:
> IMHO problem is doubling size for huge lists.
> Or waste big memory for huge frozensets. I mean resize it to 2*N if
> its size is just N+1.
Couple that with the fact that space-time are not unrelated on any modern VM
based OS + cache based hw. Doubly so for "managed" langua
On 7/13/17, Steve D'Aprano wrote:
> [1] Actually, CPython's lists initially quadruple the size of the array, up
> to a
> certain point, and then switch to doubling. This ensures that small lists
> have
> even fewer expensive resizes, at the cost of wasting a bit more memory, but
> its
> only a sm
On Thu, 13 Jul 2017 10:10 pm, Rustom Mody wrote:
> Yeah I know append method is supposedly O(1).
> I find that surprising...
> More so when the article
> https://wiki.python.org/moin/TimeComplexity
> talks of average case Vs amortized-worst case(!) Whatever does that mean?
"Average case" refers
Marko wrote:
> Simple, yes, but is the worst case
> insertion/deletion time still within
> O(log n)?
Good point; and needs to be applied to Steven's
append-using OP as well
Yeah I know append method is supposedly O(1).
I find that surprising...
More so when the article
https://wiki.python.or
Paul Rubin :
> Chris Angelico writes:
>> Maybe I'm completely on the wrong track here, but the last time I
>> implemented a self-balancing tree, it usually involved a fair amount
>> of mutation.
>
> AVL trees are fairly simple to implement without mutation. Red-black
> trees are traditionally im
Chris Angelico writes:
> Maybe I'm completely on the wrong track here, but the last time I
> implemented a self-balancing tree, it usually involved a fair amount
> of mutation.
AVL trees are fairly simple to implement without mutation. Red-black
trees are traditionally implemented with mutation,
On Thu, Jul 13, 2017 at 6:15 PM, Paul Rubin wrote:
> Chris Angelico writes:
>> some point it'll need to be rebalanced, which could at worst case
>> be O(n).
>
> No, you use a structure like an AVL tree or red-black tree, so it's
> within a constant factor of balanced after each insertion. You re
Chris Angelico writes:
> some point it'll need to be rebalanced, which could at worst case
> be O(n).
No, you use a structure like an AVL tree or red-black tree, so it's
within a constant factor of balanced after each insertion. You rewrite
O(log n) of the nodes, and juggle around a constant nu
On Wed, Jul 12, 2017 at 7:52 PM, Paul Rubin wrote:
> Not so easily in Python since the built-in list and dict types are
> designed for mutation update. In Haskell, the list type is a linked
> list and the dictionary type is a balanced tree. So, you can make a new
> list consisting of a new item
Steven D'Aprano writes:
> for parrot in parrots:
> accumulator[parrot.colour].append(parrot)
>
> That's pretty compact and understandable, but it require mutating a bunch
> of pre-allocated lists inside an accumulator. Can we re-write this in a
> functional style?
Not so easily in Python si
On Wed, 12 Jul 2017 17:47:50 +1200, Gregory Ewing wrote:
> Steve D'Aprano wrote:
>> - Greg's dict comprehension version requires N+1 passes through the
>> data,
>> one to convert to a list, and 1 per each possible key.
>
> Just to be clear, my solution was a response to the requirement that it
On Tuesday, July 11, 2017 at 4:11:50 PM UTC+5:30, Alain Ketterlin wrote:
> Steven D'Aprano writes:
>
> > I have a colleague who is allergic to mutating data structures. Yeah, I
> > know, he needs to just HTFU but I thought I'd humour him.
> >
> > Suppose I have an iterator that yields named tuple
Steve D'Aprano wrote:
- Greg's dict comprehension version requires N+1 passes through the data,
one to convert to a list, and 1 per each possible key.
Just to be clear, my solution was a response to the requirement
that it be written in a purely functional style. It's not now I
would actually
On Tue, 11 Jul 2017 04:58 pm, Chris Angelico wrote:
> On Tue, Jul 11, 2017 at 4:11 PM, Steven D'Aprano wrote:
[...]
>> accumulator = {'blue': [], 'green': [], 'red': []}
>> for parrot in parrots:
>> accumulator[parrot.colour].append(parrot)
[...]
> It's a partitioning filter. (Three way, not
On 7/11/17, Steven D'Aprano wrote:
> I have a colleague who is allergic to mutating data structures. Yeah, I
> know, he needs to just HTFU but I thought I'd humour him.
>
> Suppose I have an iterator that yields named tuples:
>
> Parrot(colour='blue', species='Norwegian', status='tired and shagged
On Tue, Jul 11, 2017 at 12:47 AM, Wolfgang Maier
wrote:
> On 07/11/2017 08:11 AM, Steven D'Aprano wrote:
>>
>> I have a colleague who is allergic to mutating data structures. Yeah, I
>> know, he needs to just HTFU but I thought I'd humour him.
>>
>> Suppose I have an iterator that yields named tup
Steven D'Aprano writes:
> I have a colleague who is allergic to mutating data structures. Yeah, I
> know, he needs to just HTFU but I thought I'd humour him.
>
> Suppose I have an iterator that yields named tuples:
>
> Parrot(colour='blue', species='Norwegian', status='tired and shagged out')
>
On 7/11/2017 2:11 AM, Steven D'Aprano wrote:
I have a colleague who is allergic to mutating data structures. Yeah, I
know, he needs to just HTFU but I thought I'd humour him.
Suppose I have an iterator that yields named tuples:
Parrot(colour='blue', species='Norwegian', status='tired and shagge
Steven D'Aprano wrote:
> I have a colleague who is allergic to mutating data structures. Yeah, I
> know, he needs to just HTFU but I thought I'd humour him.
>
> Suppose I have an iterator that yields named tuples:
>
> Parrot(colour='blue', species='Norwegian', status='tired and shagged out')
>
On Tue, Jul 11, 2017 at 4:11 PM, Steven D'Aprano wrote:
> I have a colleague who is allergic to mutating data structures. Yeah, I
> know, he needs to just HTFU but I thought I'd humour him.
>
> Suppose I have an iterator that yields named tuples:
>
> Parrot(colour='blue', species='Norwegian', stat
On 07/11/2017 08:11 AM, Steven D'Aprano wrote:
I have a colleague who is allergic to mutating data structures. Yeah, I
know, he needs to just HTFU but I thought I'd humour him.
Suppose I have an iterator that yields named tuples:
Parrot(colour='blue', species='Norwegian', status='tired and shag
Steven D'Aprano wrote:
Help me humour my colleague.
class Parrot:
def __init__(self, color, species, status):
self.color = color
self.species = species
self.status = status
def __repr__(self):
return "%s/%s/%s" % (self.species, self.color, self.status)
31 matches
Mail list logo
