How can I make this code block more efficient?

Question

// Gets the least Scored key.
int getLeastScoredKey()
{
double tempScore = 0;
double score = 0;
int key = 0;

for (Node n : map.values())
{
tempScore = n.getScore();
if (score == 0)
{
score = tempScore;
key = n.key;
}
else if (score > tempScore)
{
score = tempScore;
key = n.key;
}
}

return key;
}

https://code.sololearn.com/cPyrWbx8pRNm/?ref=app

Answer 1

For that one algorithm, you have an optimal solution. It can't be written much more efficiently. You wrote something that is O(n) and you can't find a minimum value from a container of n unordered values in less than O(n).

The only way to get a better time complexity for the getLeastScoredKey would be to change your data structure. If you frequently want to get the least scored key and also frequently want to access a value at a random key, you could maintain the values in both a HashMap and a PriorityQueue: https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
The main drawback to performance in maintaining both is that your insert operation will increase from O(1) average time to O(log n) since inserting to the priority queue is O(log n). That isn't nearly as significant as the difference between O(log n) and O(n) for retrieving the least scored element, though.

Using both HashMap and PriorityQueue together would lead to the following efficiencies for each operation:
put - O(log n) - the priority queue will change this from O(1) to O(log n).
get - O(1) - you can perform get using just the HashMap.
getLeastScoredKey - O(1) - you can perform this with the priority queue. priority queue will decrease this from O(n) to O(1) since the lowest stored element will be maintained at 1 place in the queue.
deleteExcess - O(log n) priority queue will take O(log n) to perform a "poll".

With just HashMap like you have now, the efficiency for each operation would be:
put - O(1)
get - O(1)
getLeastScoredKey - O(n)
deleteExcess - O(n)

Answer 2

Thanks Josh,

Since getLeastScoredKey will only be called when the Cache has reached it's maximum capacity, it's best to leave things the way they are.

Answer 3

Code Kitten, you're right for the current code that deleteExcess should be O(n). I edited my previous answer with the correction you pointed out.