rings - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: General (https://python-forum.io/forum-1.html) +--- Forum: News and Discussions (https://python-forum.io/forum-31.html) +--- Thread: rings (/thread-30318.html) Pages:
1
2
|
RE: rings - Gribouillis - Oct-17-2020 buran Wrote:I may misunderstand your point thoughdeques are perfect if the program pushes and pops many items at the ends of the deque. It is perfect for stacks and fifos, but if the programs wants to access many times an element in the middle of the deque, it could be very inefficient because accessing the n-th element involves dereferencing n pointers. The getitem has a performance in O(n) RE: rings - buran - Oct-17-2020 Yes, that's what I understood is your point. And that's why agreed it may be sub-optimal for random access. Same apply for e.g. list As far as I understood the discussion so far it was about implementation of ring/stack/buffer where optimized pop/insert on both ends is what we look for RE: rings - Gribouillis - Oct-17-2020 buran Wrote:Same apply for e.g. listThis is not true. Random access in lists is in O(1). Of course, if you want to insert elements, that's another matter. Again in the case of the deque, if you want to rotate often by large amounts, it will probably have worse performances than a list with a pointer to the head index. I think it all depends on how one wants to use the structure. Actually, you need many items to feel any difference from collections import deque from timeit import timeit L = list(range(200000)) D = deque(L) print('list', timeit('L[100000]', 'from __main__ import L')) print('deque', timeit('D[100000]', 'from __main__ import D'))
RE: rings - Skaperen - Oct-19-2020 i think he means accessing an arbitrary item somewhere in the middle. a list indexed modulo its len() can do that with consistent performance, though doing modulo for every access can be an overall performance hit. not every in C was there a single ideal construction although my Virtual Ring Buffer improved byte performance by creating a view of the buffer in the page that followed the buffer as long as the buffer size was made a multiple of the page size. i heard that the HP architecture could not do it but i tested it in x86, Sparc, S/370, ARM, and MIPS. RE: rings - Skaperen - Oct-19-2020 linked list is not a list? |