Mailing List Archive: Python: Dev

Re: Retrieve an arbitrary element from a set withoutremoving it

Index | Next | Previous | View Threaded

solipsis at pitrou

Oct 26, 2009, 1:19 PM

Post #1 of 8 (196 views)
Permalink

Re: Retrieve an arbitrary element from a set withoutremoving it

Jesse Noller <jnoller <at> gmail.com> writes:
>
> So far, fiddling with the PEP, I'm on the fence - adding a method to a
> built-in object type is sort of a grey area (at least in my mind). It
> depends on if doing so significantly alters the language/syntax.

We have recently added things like float.fromhex() which IMHO shouldn't be
blocked by the moratorium (*), although they technically add a method to a
built-in.

(*) it is a minor new feature aimed at catching up with some established
standard for an exact, non-ambiguous string representation of floats

Regards

Antoine.

_______________________________________________
Python-Dev mailing list
Python-Dev[at]python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

guido at python

Oct 26, 2009, 1:32 PM

Post #2 of 8 (185 views)
Permalink

Re: Retrieve an arbitrary element from a set withoutremoving it [In reply to]

On Mon, Oct 26, 2009 at 1:19 PM, Antoine Pitrou <solipsis[at]pitrou.net> wrote:
> Jesse Noller <jnoller <at> gmail.com> writes:
>>
>> So far, fiddling with the PEP, I'm on the fence - adding a method to a
>> built-in object type is sort of a grey area (at least in my mind). It
>> depends on if doing so significantly alters the language/syntax.
>
> We have recently added things like float.fromhex() which IMHO shouldn't be
> blocked by the moratorium (*), although they technically add a method to a
> built-in.
>
> (*) it is a minor new feature aimed at catching up with some established
> standard for an exact, non-ambiguous string representation of floats

Okay, so it remains a gray area.

--
--Guido van Rossum

PS. My elbow needs a couple more weeks of rest. Limiting myself to
ultra-short emails.
_______________________________________________
Python-Dev mailing list
Python-Dev[at]python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

phd at phd

Oct 27, 2009, 11:30 AM

Post #3 of 8 (174 views)
Permalink

Re: Retrieve an arbitrary element from a set withoutremoving it [In reply to]

On Tue, Oct 27, 2009 at 02:20:04PM -0400, geremy condra wrote:
> On Tue, Oct 27, 2009 at 1:59 PM, Antoine Pitrou <solipsis[at]pitrou.net> wrote:
> > Raymond Hettinger <python <at> rcn.com> writes:
> > set.getone() then ?
>
> ugh- other spellings much preferred.

set[] ? (Just kidding, really.)

Oleg.
--
Oleg Broytman http://phd.pp.ru/ phd[at]phd.pp.ru
Programmers don't die, they just GOSUB without RETURN.
_______________________________________________
Python-Dev mailing list
Python-Dev[at]python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

ncoghlan at gmail

Oct 27, 2009, 11:40 PM

Post #4 of 8 (168 views)
Permalink

Re: Retrieve an arbitrary element from a set withoutremoving it [In reply to]

Guido van Rossum wrote:
> My gut tells me it is bad API design to collapse these two use cases.
> Probably because the implementations won't have much in common: (1)
> should just pick the first valid element, while (2) should use the
> normal hash lookup algorithm (shared with 'in', .add() etc.).

As a side note, a fairly obvious method name for "add if missing and
then return canonical representation" did occur to me: s.intern(x)

I'd be -0 on expanding the set API for this though (since the cookbook
recipe overloading __eq__ already provides an efficient solution).

As far as the moratorium in general goes, perhaps we should draw a line
between API changes that affect the ABCs in collections and numbers and
new convenience methods on the builtin types themselves?

Cheers,
Nick.

--
Nick Coghlan | ncoghlan[at]gmail.com | Brisbane, Australia
---------------------------------------------------------------
_______________________________________________
Python-Dev mailing list
Python-Dev[at]python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

solipsis at pitrou

Nov 3, 2009, 3:21 PM

Post #5 of 8 (117 views)
Permalink

Re: Retrieve an arbitrary element from a set withoutremoving it [In reply to]

Guido van Rossum <guido <at> python.org> writes:
>
> You're obviously talking about a *random* element. This is a separate
> use case (though I agree many people don't know the difference).
>
> Picking a random element can be done in O(1) only if the data
> structure supports access by index, which Python's hash tables don't.

Well, at the implementation level, they can. You'd just have to pick a new
random index until it points to a non-empty slot.

Regards

Antoine.

_______________________________________________
Python-Dev mailing list
Python-Dev[at]python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

greg.ewing at canterbury

Nov 3, 2009, 5:00 PM

Post #6 of 8 (115 views)
Permalink

Re: Retrieve an arbitrary element from a set withoutremoving it [In reply to]

Antoine Pitrou wrote:
> Guido van Rossum <guido <at> python.org> writes:
>
>>Picking a random element can be done in O(1) only if the data
>>structure supports access by index, which Python's hash tables don't.
>
> Well, at the implementation level, they can. You'd just have to pick a new
> random index until it points to a non-empty slot.

But that's hardly O(1).

--
Greg
_______________________________________________
Python-Dev mailing list
Python-Dev[at]python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

solipsis at pitrou

Nov 3, 2009, 5:10 PM

Post #7 of 8 (115 views)
Permalink

Re: Retrieve an arbitrary element from a set withoutremoving it [In reply to]

Greg Ewing <greg.ewing <at> canterbury.ac.nz> writes:
> >
> >>Picking a random element can be done in O(1) only if the data
> >>structure supports access by index, which Python's hash tables don't.
> >
> > Well, at the implementation level, they can. You'd just have to pick a new
> > random index until it points to a non-empty slot.
>
> But that's hardly O(1).

It is, assuming that the set has a built-in minimum fill level (e.g. it always
keeps at least x% of its entries filled), and the random generator is good.

(of course, it is "statistically O(1)", like lookups in a hash table actually)

Regards

Antoine.

_______________________________________________
Python-Dev mailing list
Python-Dev[at]python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

guido at python

Nov 3, 2009, 6:11 PM

Post #8 of 8 (117 views)
Permalink

Re: Retrieve an arbitrary element from a set withoutremoving it [In reply to]

On Tue, Nov 3, 2009 at 5:10 PM, Antoine Pitrou <solipsis[at]pitrou.net> wrote:
> Greg Ewing <greg.ewing <at> canterbury.ac.nz> writes:
>> >
>> >>Picking a random element can be done in O(1) only if the data
>> >>structure supports access by index, which Python's hash tables don't.
>> >
>> > Well, at the implementation level, they can. You'd just have to pick a new
>> > random index until it points to a non-empty slot.
>>
>> But that's hardly O(1).
>
> It is, assuming that the set has a built-in minimum fill level (e.g. it always
> keeps at least x% of its entries filled), and the random generator is good.
>
> (of course, it is "statistically O(1)", like lookups in a hash table actually)

Clever. But I don't think the set implementation should have a
dependency on random(), so it would have to expose an "indexing"
operation, which smells like it would expose too much of the
implementation for comfort.

--
--Guido van Rossum (python.org/~guido)
_______________________________________________
Python-Dev mailing list
Python-Dev[at]python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact lists@gossamer-threads.com