On Mon, Aug 31, 2020 at 04:01:06AM -0000, junkneno...@gmail.com wrote: > I have a use case which relates to this request: iterating over a dict > starting from a given key. I would like to achieve this without having > to pay the full O(n) cost if I'm going to be iterating over only a few > items.
>From the description of your task, it sounds like the cost of iterating over the full dict is trivial compared to the work you would do in the loop, even if you end up skipping the bulk of the items. On my computer, it takes 7ms to iterate over a million-item dict. So even if you had a million keys, and had to skip over all but the very last, you're saving 7ms. Or chances are your computer is faster and more powerful than mine, in which case that's likely to be more like 0.7ms. So I'd like to see some profiling information that conclusively demonstrates that the bottleneck here is not the work you do within each loop, but skipping over the keys to get to the starting point. [...] > as is storing keys in an associated list as this would > ~double the memory used. If you are storing only the keys, you're not doubling the memory. You're only storing pointers to the same keys as being used in the dict. On a 64-bit machine, each pointer is 8 bytes, while the key itself is likely to be sufficiently larger: even a small int is 28 bytes. If your hash values are large, they might be 40 bytes or more. And of course you're not duplicating the values either. So realistically, I would expect perhaps a 15% increase, not 100% increase in memory. -- Steve _______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/C5FUBACWRYPWLOABGCDPS5QLYKG4RRKD/ Code of Conduct: http://python.org/psf/codeofconduct/
