Martin v. Löwis wrote:
>> The problem arises because we're systematically unbalancing the hash
>> table. The iterator returns the first valid entry in the hash table,
>> which we remove. Repeat several times and pretty soon the iterator has
>> to spend O(n) time scanning through empty entries to
On Mon, Nov 9, 2009 at 2:42 AM, "Martin v. Löwis" wrote:
> Interesting. Something goes wrong, it seems: if items get removed over
> and over again, I think the set should shrink (not sure whether it
> actually does). Then, I think you should end up with an amortized O(1)
> for selecting an element
On Mon, Nov 9, 2009 at 10:09 AM, Daniel Stutzbach
wrote:
> On Mon, Nov 9, 2009 at 2:42 AM, "Martin v. Löwis"
> wrote:
>>
>> Interesting. Something goes wrong, it seems: if items get removed over
>> and over again, I think the set should shrink (not sure whether it
>> actually does). Then, I think
2009/11/6 Raymond Hettinger :
> [me]
>>
>> Why not write a short, fast get_first() function for your utils directory
>> and be done with it?
>> That could work with sets, mappings, generators, and other containers and
>> iterators.
>> No need to fatten the set/frozenset API for something so trivial
On Tue, 10 Nov 2009 03:40:11 am Björn Lindqvist wrote:
> 2009/11/6 Raymond Hettinger :
> > [me]
> >
> >> Why not write a short, fast get_first() function for your utils
> >> directory and be done with it?
> >> That could work with sets, mappings, generators, and other
> >> containers and iterators.
Alexander Belopolsky wrote:
> On Mon, Nov 9, 2009 at 10:09 AM, Daniel Stutzbach
> wrote:
>> On Mon, Nov 9, 2009 at 2:42 AM, "Martin v. Löwis"
>> wrote:
>>> Interesting. Something goes wrong, it seems: if items get removed over
>>> and over again, I think the set should shrink (not sure whether it
> So the rationale is to ensure that only add operations perform a resize
> and so that sequential pop() operations don't incur excessive resizing
> costs.
I agree that the use case of repeated .pop() operations is reasonable,
and (IIUC) that case is also special-cased using a finger/index.
I thi
> I'm not sure, but isn't that thread-unsafe?
You are right; it's thread-unsafe.
I would fix it by catching the RuntimeError, and retrying. Given the
current GIL strategy (including proposed changes to it), it won't happen
two times in a row, so the number of retries would be bounded.
Regards,
M
> We repeatedly search through the slots sequentially and remove the first
> element we find. The first removal requires checking 1 slot, the second
> removal requires checking 2 slots, the third removal requires checking 3
> slots, and so forth. The hash table will shrink after the n/2-th
> remo
On Mon, Nov 9, 2009 at 3:50 PM, "Martin v. Löwis" wrote:
> I think for regular removal, the same logic should not apply: if a
> series of removals is performed, then further (non-pop) removals
> see increasing costs, as do regular lookups. So I think that a removal
> should trigger shrinking (with
Martin v. Löwis wrote:
>> I'm not sure, but isn't that thread-unsafe?
>
> You are right; it's thread-unsafe.
>
> I would fix it by catching the RuntimeError, and retrying. Given the
> current GIL strategy (including proposed changes to it), it won't happen
> two times in a row, so the number of r
Antoine Pitrou wrote:
> Nick Coghlan gmail.com> writes:
>> It's also one of the major reasons for not sharing mutable containers
>> between threads if you can avoid it (and serialising access to them if
>> you can't)
>
> Not necessarily, for example it is common to rely on the fact that
> list.a
[me]
Why not write a short, fast get_first() function for your utils directory and
be done with it?
That could work with sets, mappings, generators, and other containers and
iterators.
No need to fatten the set/frozenset API for something so trivial and so rarely
needed.
Forgot to post the c
On Thu, Nov 5, 2009 at 5:02 PM, Raymond Hettinger wrote:
> Forgot to post the code. It is short, fast, and easy. It is explicit about
> handing the case with an empty input. And it is specific about which value
> it returns (always the first iterated value; not an arbitrary one). There's
> no
> On Thu, Nov 5, 2009 at 5:02 PM, Raymond Hettinger wrote:
>> Forgot to post the code. It is short, fast, and easy. It is explicit about
>> handing the case with an empty input. And it is specific about which value
>> it returns (always the first iterated value; not an arbitrary one). There's
On Thu, Nov 5, 2009 at 11:43 PM, "Martin v. Löwis" wrote:
> I read Raymond's suggestion rather as a question: why bother with a
> tedious, multi-year process, when a three-line function will achieve
> exactly the same?
Because it doesn't achieve exactly the same. What I want is a
sane, ration
> The problem arises because we're systematically unbalancing the hash
> table. The iterator returns the first valid entry in the hash table,
> which we remove. Repeat several times and pretty soon the iterator has
> to spend O(n) time scanning through empty entries to find the first
> remaining
17 matches
Mail list logo
