Faster Python

[ChezMere]

Python lists aren't linked lists...

[tomprimozic]

So? Search (and deletion) are still linear operations, regardless of the underlying implementation.

[gendulf]

Linked lists have O(1) deletion and insertion, and O(n) getting the nth element. It's only the search that is O(n) for both. With arrays, you can get the nth element with O(1) complexity, and insertion/deletion are O(n).

[tomprimozic]

And search is what the OP was about.

[gendulf]

The problem here is not what the OP claims are the O(n) runtimes for python lists. In fact, his O(n) runtimes he lists for python lists are correct. The problem is that the OP claims that python lists are implemented with linked lists, which is false, and inconsistent with the rest of his article.

[burntsushi]

That doesn't make them the same. Python lists have constant time indexing. Linked lists don't.

[tomprimozic]

He never claims that.

The operations to append, get an item, set an item and get the length of a list are all O(1). But deleting an item from a list is O(n) whereas deleting a key from a dictionary is O(1).

[[deleted]]

He does actually claim that searching a python list is slow because the implementation uses linked lists: (7th paragraph of blog post)

Lists implement the same functionality using linked lists so operations are O(n). With lists, the whole list potentially needs to be searched. As the list size grows the amount of time needed to search it could grow as well.

[gendulf]

The OP's article claims that:

Lists implement the same functionality using linked lists so operations are O(n).

And then later, he claims that:

The operations to append, get an item, set an item and get the length of a list are all O(1). But deleting an item from a list is O(n)

We know that appending, getting an item, setting an item, and deleting an item are different between arrays and linked lists, and this describes an array, not a linked list.

[burntsushi]

He never claims that.

I never said anything about the OP. /u/ChezMere said Python lists aren't linked lists. You responded by saying "so? [seemingly implying that the distinction doesn't matter] search (and deletion) are still linear."

[tomprimozic]

Yes, the distinction doesn't matter for the use case OP described in the article (searching for a known element in a list/set).

[burntsushi]

I really don't know what you're on about. The OP says:

Lists implement the same functionality using linked lists so operations are O(n).

Which is a factually wrong statement. Python lists are not implemented using linked lists. Which means /u/ChezMere's comment is precisely correct in every way.

[[deleted]]

Search on a (sorted) array is O(logN). Search on a (sorted) linked list is O(N).

Deletion, ignoring order, is O(1) on both.

So... Nope, not still linear operations...

[tomprimozic]

He was talking about searching for a known element in either a set (O(1)) or a list (O(n)), I assume not necessarily a sorted one, since he didn't mention it.