Can someone post an example of dynamic lists? Like this:
1 - tree
2 - house
3 - car
if data in 1 is removed, then 2 will be moved to 1 and 3 will be moved to 2.
1 - house
2 - car
Thanks in advance. 
a pythonic list will do this. If you remove the item, it will shift the items to âfill the gapâ (in reality the key indexes just change)
this is a list:
L=[âaâ, âbâ, âcâ]
you want delete the first(âaâ)âŚyou write:
del L[0]
0 is the first itemâŚ
automatically âbâ and âcâ become the first and the second item of the listâŚ
you can also delete a precise index ,⌠if you not know the position of âcâ
L.remove(âcâ)
This would be the appropriate method, in this case (in my opinion):
objects = ["tree", "house", "car"]
objects.pop(0) # objects = ["house", "car"]
While a list will work fine for what youâre trying to do, removing an arbitrary item from a list takes linear time. This means that if you make your list 100 times larger, it will take 100 times longer to remove an item.
If youâre planning on making a large list, I would suggest using another data type such as a dictionary, set, or deque. Dictionaries and sets have constant insertion and deletion time. Deques do as well, but you can only remove and insert items at the ends of the deque.
Itâs O(n), but I think n represents the distance between the item in question, and the last item in the list - in that case, I donât think it would be directly related to the length of the list.
If youâre planning on making a large list, I would suggest using another data type such as a dictionary, set, or deque. Dictionaries and sets have constant insertion and deletion time. Deques do as well, but you can only remove and insert items at the ends of the deque.
The dictionary doesnât really seem like the right structure in this case, because it doesnât guarantee a specific order.
As for the deque: Assuming that the requirements are for pop in constant time from one side or the other, and using the regular python list is noticeably slow in that respect, the deque would probably be the proper alternative.
Big O notation drops any constants infront of the dominating factor in addition to any other smaller factors. Youâre correct that the distance of the item from the end of the list affects the time it takes to delete, and the actual time it takes would be something like N - I (which happens to equal the distance from the end of the list as you noted), where I is the index of the item to be removed.
However, the time to remove an element from an arbitrary position from the list is still directly proportional to the number of items in the list (which is what N represents). For example, removing the item from the middle of a list would take time proportional to N - N/2 = N/2 which is still directly proportional to N.
L.pop(0)
is more elegant than del , which is fuxia and can be âdangerousâ
âŚhow using deque? ever seen (you need a particular module?)
Removing the item at index -3 would take the same amount of time, irrespective of list length.
I will admit that Iâm not exactly clear on all the theoretical underpinnings of Big O notation, but I donât remember any rules that restrict the definition of N to the length of some arbitrary sequence.
In either case, I just wanted to point out the key determining factor, which is not list length; saying itâs O(n), with n defined as distance from the end seemed fairly reasonable.
A simple google search will provide you with relevant information.
However, I would recommend using a regular list, and the pop method, until you actually start to see performance problems.
Unless youâre dealing with really large lists, then itâs not going to be a problem, and you shouldnât waste your time, or complicate matters, with alternative data structures.
N almost always represents the size of the input unless otherwise stated. As I noted, the distance from the end of the list is equivalent to size - index, which is still proportional to the size of the list when given a constant index.
The reason using negative indexing takes constant time regardless of the list size is because negative indexing implicitly includes the length of the list. List[-3] is equivalent to List[N - 3] which varies as the size of the list varies. The time it would take for this is then N - (N - 3) = 3 which is constant. Regular indexing, on the other hand, does not include the length of the list. List[3] takes time proportional to N - 3 which does vary with N.
Sorry if Iâm being nit-picky about this. I took a computer algorithms course recently that covered a lot of time-complexity stuff.
I stated otherwise.
As I noted, the distance from the end of the list is equivalent to size - index, which is still proportional to the size of the list when given a constant index.
When given a constant index, but only in that special case.
In the general case, the distance from the end of the list is completely disconnected from the length of the list.
I mean, you can have a list of length 10, and the element that you want to pop out is 5 units from the end. However, you can also have a list of 100, where the element you want to pop out is only 2 units away from the end.
The operation in the second case is faster, even thought the list is longer. So, the argument that performance time is proportional to the length of the list is simply incorrect.
The reason using negative indexing takes constant time regardless of the list size is because negative indexing implicitly includes the length of the list.
In the case where we have a constant negative index, the distance from the end is also a constant, and thatâs the true reason. Again - nothing to do with list length.
List[-3] is equivalent to List[N - 3] which varies as the size of the list varies. The time it would take for this is then N - (N - 3) = 3 which is constant.
The value of the index varies, but the distance from the end (which we agreed to be the determining factor for performance time) remains the same.
List[3] takes time proportional to N - 3 which does vary with N.
Only when the index is constant.
Sorry if Iâm being nit-picky about this. I took a computer algorithms course recently that covered a lot of time-complexity stuff.
No problem. I like talking about this.
According to the Python wiki:
âGenerally, ânâ is the number of elements currently in the container.â
The whole point of time-complexity is to note the time it takes for the same operation across varying input sizes. The only case when youâre doing the same operation is when the index is constant.
Of course the time of the operation changes when you change the index (it will change even when you keep the size of the list constant).
Removing List[3] is the same operation no matter what the size of the list is, and it will therefore take time proportional to the length of the list. Removing the third to last item from the list (List[-3]) is a different operation depending on the size of the list, so comparing the time it takes across lists of different sizes wonât tell you anything.
You have a discontinuity in that case: You canât make a performance analysis for an âoperationâ where the index in question is greater than length - 1.
Doesnât that break the formality of time-complexity analysis?
I donât think you can really define the âsame operationâ in that way, for that reason. The only way to avoid those pitfalls is to define n properly, as the distance from the end of the list.
There is no rule in Big O notation that restricts n to be the length of some sequence, even though thatâs usually the case.
*Edit
Or more specifically: You can think of it as a sequence, but a sequence of elements between the element in question, and the end of the list.
I agree with Goran.
ânâ is a proxy for the number of elements the function runs at.
O() is the comparison to a well known function with known complexity. As far as I remember it is the function with the worst costs [ O(n+n²) == O(n²) ].
O(n) means the costs double on doubled input on any large n. In case of lists double number of entries.
Why only on large n? Because n² is better than n on small numbers.
Now you could discuss what large is. From my experience 3 is not large for any implementation of Python lists.
BTW: The costs depend on the implementation. As far as I remember the Python documentation includes some recommendations and alternatives.
The most important fact is:
v2rockets already marked this thread as solved 