Python Forum
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
rings
#11
buran Wrote:I may misunderstand your point though
deques 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)
Reply
#12
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
If you can't explain it to a six year old, you don't understand it yourself, Albert Einstein
How to Ask Questions The Smart Way: link and another link
Create MCV example
Debug small programs

Reply
#13
buran Wrote:Same apply for e.g. list
This 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'))
Output:
list 0.022696959997119848 deque 6.838809543995012
ndc85430 and buran like this post
Reply
#14
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.
Tradition is peer pressure from dead people

What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Reply
#15
linked list is not a list?
Tradition is peer pressure from dead people

What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020