Glossary talks about list access complexity, but the actual list definition doesn't. I think glossary entries should have more information than actual definitions.

PR adds list access complexity to list definition.

I don't think this should be documented at all, not in the glossary, nor the stdtypes section. A quick search through of the glossary and stdtypes indicates that the glossary entry of list is the only place where a time complexity is documented.

The problem with documenting this is that the underlying complexity is an implementation detail, by saying its always O(1), alternative implementations like PyPy etc cannot freely implement lists in whatever way they wish.

If O(1) time complexity for element access is not a requirement (which it seems it's not), I agree that this PR as it is should be closed, and the Glossary entry should have this detail removed.

In that case, can I edit the PR or should I open a new one?

I'd say edit the PR and the bug tracker issue to reflect the change. Though you might want to wait for the opinion of a core dev or someone with more documentation experience than me.

List is documented in “sequence” section and O(1) index access is typical for sequences.  At least, every builtin types have it.
So adding such note only to list seems a bit curious to me.

INADA, I believe that piece of information is on the Glossary just to make the difference with a "linked list", but in that case, it should be in the list definition too, as it's fair to think people can learn what a list is by reading its definition first, instead of the Glossary entry.

I believe Ammar's reasoning is right, though. If the time complexity of the task is not required, then we should remove those mentions.

Benjamin, I'm adding you as you introduced the change. Perhaps you can bring some light? Even if 10 years have passed? :P

In case of "difference with linked-list", I don't want to make list definition longer and longer for readers only small part of people.  I think that's why difference with "linked-list" is documented only in glossary.

By adding all information for non-zero group of people, resulting document will be very long, redundant, and suitable for no one.

We should effort to make document "necessary and sufficient" state.

---

In case of time complexity, I agree it's useful for users.  Not only for list, but also for all basic operation of basic types, too.

But at my understanding, we don't have formal spec for time complexity of stdtypes.  We use consensus instead.

I think we can say random access is O(1) for bytes, bytearray, tuple, list, and range (except time for building large numeric value).

On the other hand, I'm not sure about str.  Other Python implementation will want to use UTF-8 based implementation of str.

IMHO, if we deem it useful for users not to expect the time complexity of a linked list for list elements access to the extent of adding a comment in the glossary, there's no reason it isn't useful to someone who is reading the actual list definition. Moreover, I don't see the reason why someone would read the list glossary entry after reading the list definition.

I believe glossary entries should be a (rather small) subset of the topics they touch.

All of this, of course, if Ammar is not right about list not requiring O(1) time complexity.

Please note that, while interesting, I'm not proposing to document the time complexity in list definition per se, but only because it's already documented in the glossary.

Andrés Delfino <report@bugs.python.org>:

>
> Andrés Delfino <adelfino@gmail.com> added the comment:
>
> IMHO, if we deem it useful for users not to expect the time complexity of
> a linked list for list elements access to the extent of adding a comment in
> the glossary, there's no reason it isn't useful to someone who is reading
> the actual list definition.

I didn't deny "it is useful to someone."

I just worry about adding many random notes "useful to someone" in document
"everyone" reads.  It's worse than nothing.

When writing document for wide readers, adding such "useful to someone"
note is bad idea.
We should focus on "important to everyone" or "critical for someone".

Moreover, I don't see the reason why someone would read the list glossary
> entry after reading the list definition.
>

That's why "useful to only someone" information can be noted on glossary,
but no on main document.

I believe glossary entries should be a (rather small) subset of the topics
> they touch.
>

I don't think so. Glossary is the best place to document "no definition,
but used conventionally" word which is not defined in other document

Current glossary has random tips and notes like this.  They don't bother
readers of main document.

I don't think "document in glossary" is not enough reason to add it on main
definition, because it may lead bad S/N ratio.

Of course, if it's very common pitfall for many people, it's worth enough
to note in the definition.

But IList in C# is sequence and LinkedList doesn't implement it. If many
people feel the word "list" implies "linked list", why they choose the name
"IList"?  That's why I think the note is only for someone, not for
 most readers.

So I'm -0.5 on adding it in list definition, and +0 on removing it from
glossary.

I concur with INADA. I don't prefer to add such implementation choice in definition. As for glossary, it may be unnecessary either but since it's already there, I don't think it needs to be removed.

-1 We've historically chosen to not include such implementation specific details and it seems to have not been a problem for users.  The glossary in particular is no place to talk about such specifics.