MeterArchive.fetch is ridiculously slow

[BlackCapCoder]

arbeidskrav/V18_1_basic/MeterArchive.java

Lines 49 to 56 in d7fd8bf

	public Meter fetch(String identification) {
	for (Meter meter : meters) {
	if (meter.getIdentification() == identification) {
	return meter;
	}
	}
	return null;
	}

MeterArchive.fetch (and consequently all of the other methods in MeterArchive) has time complexity O(N) - this is ridiculously slow for a lookup! With as little as a couple of million meters in the archive the user would have to wait for seconds to do a lookup, and in that time they might as well go look themselves. Yuck!

There are approximately two solutions to this:

Change data-structure

Arrays are not meant for lookup, they are for fast access if you know the index of what you want. Consider switching from ArrayList to something like a HashMap that has O(1) lookup.
Have a look at the big o cheat sheet for the time complexity of different data-structures.

Be clever

If you have to store the Meters in an array, you can store them in sorted order (sorted on the reference number). Then when you want to look for a Meter you can play the number guessing game:
Take the middle meter out of the list and compare its reference number against the one you are looking for. If it is smaller/greater you repeat for the lower/upper half of the list. Continue doing this until you find an element that is equal. This has time complexity O(log N).

[olaven]

I will definitely have a look at the link later today 👍
Since this is just a small scool project and not something to be deployed as a paid service or anything, I am not sure I will worry to much about the inefficiency. That said, I enjoy (and agree with) the principle of making things as good as they can be no matter the scale of the project 😄

[BlackCapCoder]

Indeed