# Efficiently traversing a list

Suppose I have a large list of algebraic expressions, sorted by their equivalent numerical value (under a certain set of assumptions). Some of these expressions are identical, but commands like Simplify leave them in distinct forms.

I wish to pare down the list to expressions with a unique numerical value. To decide among several expressions which evaluate to the same number, I'd like to use ByteCount, keeping only the simplest expression.

Here's what I have so far:

data = {...list of algebraic expressions...};
assumptions = {...list of numerical replacement rules...};
numData = data /. assumptions;
reducedNumData = DeleteDuplicatesBy[Sort[numData], Round[#, 0.00000001] &]
reducedData = First[SortBy[Pick[data, numData, #], ByteCount]] & /@ reducedNumData


This last line goes through each unique numerical value, finds all expressions equal to that value, sorts them by byte count, and chooses the first (simplest) expression.

The problem is that the last line evaluates very slowly. This is due to the size of the list, and the $O(n^2)$ complexity of the operation I chose. Since the list is easily sorted by numerical value, there must be an efficient way to traverse the list only once, using pattern-matching and a 'cons'-like operator to build the reduced list. This would be the preferred method in many languages, but I realized I don't know how to do this in Mathematica.

Essentially, I want to traverse the list, looking at the numerical value and complexity of its elements, and keep only those expressions with unique numerical values, discarding redundant expressions with higher complexity.

I don't know if limiting yourself to a single traversal really helps that much. I would sort, split the list, and find the element with the smallest ByteCount in three separate passes, perhaps like this:

SimplestEquivalents[exprs_, assumptions_, tol_: 10*^-8] :=
With[{nums = exprs /. assumptions},
Flatten[Map[
MinimalBy[exprs[[#]], ByteCount, 1] &,
Split[Ordering[nums], nums[[#2]] - nums[[#1]] <= tol &]]]];


It's not the fastest thing in the world, but it should be linearithmic, as you'd expect based on the need to sort the numerical values.

EDITed to fix bug noted by @phosgene in comments.

• Great idea to split the list! However, nums[[#2]] - nums[[#1]] gives non-numerical results. I used this instead Split[Ordering[nums], nums[[#2, 1]] - nums[[#1, 1]] <= tol &] and it works perfectly. Much faster than my n^2 rubbish. Commented Nov 1, 2015 at 6:36