On Jun 13, 2016 6:16 PM, "MRAB" <python at mrabarnett.plus.com> wrote: > > On 2016-06-14 01:47, Larry Hastings wrote: >> >> On 06/13/2016 05:05 PM, MRAB wrote: >>> >>> This could be avoided by expanding the items to include the index of >>> the 'previous' and 'next' item, so that they could be handled like a >>> doubly-linked list. >>> >>> The disadvantage would be that it would use more memory. >> >> >> Another, easier technique: don't fill holes. Same disadvantage >> (increased memory use), but easier to write and maintain. >> > When iterating over the dict, you'd need to skip over the holes, so it would be a good idea to compact it a some point, when there are too many holes. Right -- but if you wait for some ratio of holes to filled space before compacting, you can amortize the cost down, and have a good big-O complexity for both del and iteration simultaneously. Same basic principle as using proportional overallocation when appending to a list, just in reverse. I believe this is what pypy's implementation actually does. -n -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://mail.python.org/pipermail/python-dev/attachments/20160613/76158ad7/attachment.html>
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4