Python uses which algorithm for index method?

Question

I am trying to find out more about python built in methods

I know that python uses Tim Sort as base function in sort() I want to know what algorithm python use for searching? for list.index(valve) method and for x in list.

Answer 1

Both comments are correct: the Python standard doesn't mandate anything regarding the implementation of list.index(). We can somewhat bound our expectations with the fact that realistically, implementations of index are (probably) not evil, so even though it is possible to create an O(n!) variant, we can probably make the following observations:

• Pre-sorting a list and then performing a binary search, despite the tail-end of the algorithm being O(log n), would still be bounded by the sorting, which would be O(n log n) if comparison, or O(n) if we go beyond comparison. This adds quite a bit of overhead for an algorithm that would still be order O(n) on average (and list is not a sorted container, so we can't assume it's sorted anyway)

• It's not a requirement for objects to implement total ordering, and it's more than legal to create a barebones class that doesn't override __eq__ or any other relational dunder (e.g., __le__, __gt__) so implementations would likely err on the side of caution, as the default implementation of __eq__ is is

On the more pragmatic side of things, we can look at the CPython, the reference implementation of Python. The index method defined for list exists at listobject.c#L2601:

• This method takes in the object we are iterating over, self; the value we are looking for, as well as the start and stop indices (keeping in mind that the index method can be something like my_list.index(my_val, 10, 20) if we want to restrict the search to a certain slice).
• The two if statements at the beginning recover valid indices in the case where the caller supplies negative values (as Python allows you to specify -1 in case you want to refer to the last element, or -2 for the second last element). If a list has 10 elements and you want the -1'th element, then you want the 9th element, or -1 + 10 = 9. So, if an index is negative, we recover a valid index by adding len.
  • In this case, the len of the object is stored in the struct as ob_size, which to my knowledge, is a flexible array object accessible from the macro Py_SIZE (as you can see in the code)
• The for loop that follows is your run-of-the-mill iteration algorithm. There are some implementation details here that, again, aren't necessarily important:
  • Each iteration grabs the next PyObject by dereferencing the flexible array member ob_item
  • Py_INCREF and Py_DECREF are tallying functions used to increment and decrement the reference counter for the current object being examined within the list
  • Comparing equality is done using a three-way function PyObject_RichCompareBool which returns:
    • -1 on error
    • 0 if not equal (false)
    • 1 if equal (true)
  • In case that the value is found, then as one would expect, the index is returned. Otherwise a ValueError is raised

Similar things happen in PyPy, where we look instead at listobject.py#L874:

• We see PyPy JIT interpreter code here, with jit_merge_point signalling the start of a potential loop
• Every time objects are checked, they're first checked for identity, then equality