51
Python Big O: the time complexities of different data structures in Python (www.pythonmorsels.com)
submitted 2 years ago by to c/python@programming.dev
9 comments fedilink hide all child comments
 

Trey Hunner writes:

This article is primarily meant to act as a Python time complexity cheat sheet for those who already understand what time complexity is and how the time complexity of an operation might affect your code. For a more thorough explanation of time complexity see Ned Batchelder's article/talk on this subject.

Read Python Big O: the time complexities of different data structures in Python

all 9 comments

sorted by: hot top controversial new old
[–] 4 points 2 years ago

Cheers, always good to be aware of these concepts even if Pythons is far from 'blazingly fast'

  • permalink
  • fedilink
  • source
    •
    [–] 2 points 2 years ago* (1 child)

    sorted_sequence.index(item)

    Shouldn't this be O(n log n)? I guess Python doesn't have a list that stays sorted.

    As a workaround, just use dict keys with no values instead.

  • permalink
  • fedilink
  • source
  • hideshow 2 child comments
    •
  • [–] 1 point 2 years ago (1 child)

    Sets stay sorted, no?

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 2 child comments
    •
  • [–] 3 points 2 years ago* (1 child)
  • permalink
  • fedilink
  • source
  • parent
  • hideshow 2 child comments
    •
  • [–] 1 point 2 years ago (1 child)

    Ah, sorry. Sets are unique, not ordered. Thanks!

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 2 child comments
    •
  • [–] 1 point 2 years ago

    Yeah, I just think it's kind of odd though. If a language only has lists and hash maps, my go-to is to use a hash map for uniqueness, and sort the list for ordered lists.

    But in Python, it's backwards where I use the hash map (dict) for ordered data and the set for uniqueness, because hash maps are unordered in most languages I've used.

  • permalink
  • fedilink
  • source
  • parent
    • [–] 2 points 2 years ago (1 child)

    Damn, I was hoping someone had python running a Megadeus.

  • permalink
  • fedilink
  • source
  • hideshow 2 child comments
    •