Member Avatar for ogsirus

Hi guys,

I am trying to write a program which picks the closest number possible out of a dictionary.

The dictionary contains 50 doubles values, and I use a random double to pick the number i want to get the closest to if that makes sense.

Currently I am using linq to pick the first one which is less or equal to the random number. The problem I have found with this is that it is not reaching numbers which are closer and its most certainly picks the same key all the time. I have also tried the SkipWhile method but I have not seen much of a difference. Also tried to 'shuffle' the dictionary before finding the closest, which as help as now im not getting the same value.

Just curious, is there is a method I'm not trying which is better than what I am currently doing.

  • 4 Contributors
  • 4 Replies
  • 882 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by ogsirus

Dani AI

Generated

Short summary: for 50 values a single O(n) scan is the simplest, fastest and easiest to get correct; if you need to do many nearest-value queries, keep the dictionary (as wants) but build a sorted array of (value,key) pairs once and use binary search. As and hinted, sorting helps when you need nearest-of-two neighbors, but you do not have to lose the dictionary to get that behavior.

Example approaches (assume dict is Dictionary<TKey,double> and target is the random double):

Single-pass (O(n), simplest and deterministic)

// returns the Key whose Value is nearest to target
var nearestPair = dict.Aggregate((a,b) =>
    Math.Abs(a.Value - target) <= Math.Abs(b.Value - target) ? a : b);
var nearestKey = nearestPair.Key;

If you are on modern .NET (MinBy available) you can write:

var nearestKey = dict.MinBy(kv => Math.Abs(kv.Value - target)).Key;

If you will query many times, prepare a sorted array once and binary-search the insertion point (O(log n) per query):

var sorted = dict.OrderBy(kv => kv.Value).ToArray();
var values = sorted.Select(kv => kv.Value).ToArray();
int idx = Array.BinarySearch(values, target);
if (idx < 0) idx = ~idx; // insertion index
int left = idx - 1, right = idx;
var candidates = new[] { left >= 0 ? sorted[left] : default, right < sorted.Length ? sorted[right] : default }
                 .Where(kv => !kv.Equals(default(KeyValuePair<TKey,double>)));
var nearestKey = candidates.OrderBy(kv => Math.Abs(kv.Value - target)).First().Key;

Practical tips and gotchas:

  • Creating new Random() repeatedly can produce the same numbers; create one Random instance and reuse it.
  • Do not rely on Dictionary enumeration order for randomness — it is unspecified.
  • For doubles watch NaN/Infinity and consider a small tolerance for equality (use relative tolerance for large numbers).
  • If values can repeat, decide whether you want every matching key or just any one; return a list if needed.
  • For just 50 items, prefer the aggregate/min-by approach for clarity; only optimize if profiling shows a problem.

This keeps the dictionary for key lookups later while giving deterministic, correct nearest-value selection.

Recommended Answers

All 4 Replies

Member Avatar for pritaeas

Perhaps if you use a list instead of a dictionary. You can then order by value, find the one that is less or equal, and then take the next one if the difference between the value and your chosen number is less than the current one.

Member Avatar for ddanbe

Indeed, as priteas pointed out, a List and sorting is more appropriate here.
But if you must use a dictionary, this might help.

Member Avatar for overwraith

Just curious what kind of application needs to choose one of 50 doubles without going over? Is this some kind of guessing game?

Member Avatar for ogsirus

I wish to keep it as a dictionary as the Keys will be used later on. I managed to write a new method using Linq which get a closer value.

It possibly might be for a game later on, once i decided to install unity again. However, for now it just me getting used to Linq.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.