CodeSOD: Dictionary Definition of a Loop

Ah, the grand old Dictionary/Map structure. It's so useful, languages like Python secretly implement most of their objects using it, and JavaScript objects imitate it. One of its powers is that it allows you to create a sparse array, indexed by any data type you want to index it by.

Catherine's cow-orker certainly thought this was pretty great, so they went ahead on and used the Dictionary to map interest rates to years. Years, for this application, were not tracked as actual years, but relative to an agreed upon "year zero"- the first year of the company's operation. There was a new annual interest rate tracked for each year since.

If you're saying to yourself, "wait" this sounds like a use case for arrays"", you're onto something. Pity you didn't work with Catherine. You probably wouldn't have left this behind:

private static double FindInterestRate(int operationYear, Dictionary<int, double> yearToInterestRates) //where 0 is the first year{ if (operationYear < 0) return 0; else { for(int i = 1; i < yearToInterestRates.Count; i++) { if (operationYear < yearToInterestRates.ElementAt(i).Key - 1) return yearToInterestRates.ElementAt(i - 1).Value; } return yearToInterestRates.Last().Value; }}

Now, even if you don't know C#, this is obviously pretty bad, but it's actually worse than you think. Let's talk for a minute about the ElementAt method. Accessing a key in a dictionary is an O(1) operation, but that's not what ElementAt does. ElementAt finds elements by indexes, essentially treating this Dictionary like an array. And how does ElementAt actually find elements in a non-linear structure? By iterating, meaning ElementAt is an O(n) operation, making this loop O(n²).

Remember, our goal, is to find a specific index in an array. Compare the efficiency.

[Advertisement] Universal Package Manager - store all your Maven, NuGet, Chocolatey, npm, Bower, TFS, TeamCity, Jenkins packages in one central location. Learn more today!