0

I am trying to get minimum value from a set in python by using min().

Constraints:

  1. I am using a dictionary which maps a node to a value but this dictionary is constantly being updated.
  2. I am reducing the size of set constantly.

My set has 510650 elements. current = min(unvisited, key=lambda node: distanceTo[node]).

  1. Name of dictionary is 'distanceTo'.

  2. Name of set is 'unvisited'.

OneCricketeer
  • 179,855
  • 19
  • 132
  • 245
Dennis
  • 11
  • 1
  • 2
    Without a sorted data structure, you'd have to look at every element to find the min – OneCricketeer Dec 02 '21 at 14:59
  • 1
    A python set is completely unsorted, so no. There are, of course, ways to make a sorted set (that's the default in c++) which means it takes longer to add or look up elements, but you can get the minimum in O(1). – Kenny Ostrom Dec 02 '21 at 15:07
  • Why not update `current` when you update `distanceTo`? – John Coleman Dec 02 '21 at 15:15
  • If you are trying to do something like nearest neighbor for a geometric TSP, see [this question](https://stackoverflow.com/q/4350215/4996248) for some ideas. – John Coleman Dec 02 '21 at 15:20

1 Answers1

0

If I understand big-o notation correctly, I don't believe so.

"O(n) means that processing time increases linearly with the size of the input"

If you consider it logically, for each item you add to an unsorted list, that's one more element that you need to compare to see if it meets your specific requirement (in your case, having the least value)

https://en.wikipedia.org/wiki/Time_complexity#Linear_time

wikipedia big-o notation table

Edit: Of course, if someone simply wanted to find a specific value in a list, and that value happened to be towards the beginning of where he started searching, it would be found in less than O(n); probably not relevant but I felt it was worth mentioning.

Jyri Keir
  • 60
  • 1
  • 11