1

Does this algorithm have a name? I've listed three examples of it below. I'm wanting to document some code that uses this algorithm, and I don't know what to call it. My version is way more complicated but it is fundamentally this.

Example 1:

var maxValue = Int32.MinValue;
foreach (var value in new [] {2, 3, 4, 4, -3, 1, 7})
{
    if (value > maxValue)
        maxValue = value;
}

Example 2:

var minValue = Int32.MaxValue;
foreach (var value in new [] {7, 6, 5, 4, 3, 2, 20, 42})
{
    if (value < maxValue)
        minValue = value;
}

Example 3:

var mostPrimeFactors = 0;
var valueWithMostPrimeFactors = 0
foreach (var value in new [] {2, 4, 6, 8, 12, 60, 360})
{
    var primeFactorCount = GetPrimeFactors(value).Count;
    if (primeFactorCount > mostPrimeFactors)
    {
        mostPrimeFactors = primeFactorCount
        mostPrimeFactors = value;
    }
}
  • 1
    These are pretty simple to be called "algorithms". I would call them functions: Maximum, Minimum, and, maximum with additional data (i.e. two things, one of which is compared). – Frank Hileman Feb 8 '17 at 22:33
  • 2
    Looks like the code is C#, if possible I would refactor the first two to use LINQ's .Max(), .Min(), then the purpose would be so clear that you don't need additional comments – RMalke Feb 8 '17 at 22:42
  • They don't even have the same signatures. How do you expect them to have a name? – paparazzo Feb 8 '17 at 23:56
  • 1
    @Paparazzi The apparently different details can be abstracted away into a higher-order function which has the same signature in all 3 cases. This function (or family of functions) is so common it has a name. – Andres F. Feb 9 '17 at 1:55
  • @AndresF. Wow lots of abstraction going on and not disclosed. – paparazzo Feb 9 '17 at 2:06
8

As @FrankHileman says, maxima and minima seem to be the operations being performed by these algorithms.

However, maxima and minima are mathematical continuous functions rather than things that reduce a discrete set of values to a single value.

As applied to an array or sequence, these particular algorithms are each a type of fold, which operates over the series of values and provides a smaller (single) output.

Some languages offer a fold operation that takes

  • a data set (the array or sequence),
  • a function (e.g. that captures the min or max algorithm in terms of a single comparison, i.e. rather than in terms of the full list/array/sequence), and
  • an initial value (first of the list), and

that returns a single value.

Fold will invoke the reducing function on each element (perhaps recursively) and will eventually return a single value as the final result.


See also MapReduce, a capability for doing map & fold/reduce, distributed across multiple computing nodes.

  • +1 fold is the fundamental abstraction here, at least from the point of view of functional programming. It's even more general because it may take anything that is "foldable", not just lists/sequences/arrays. – Andres F. Feb 9 '17 at 1:50
  • +1 In the third example you could extract a map operation: map (value => GetPrimeFactors(value).Count) – Giorgio Feb 9 '17 at 7:48
  • 1
    A fold is a concept; not an algorithm. An algorithm is a plan or set of ordered steps. In particular, a fold can be accomplished through several different algorithms, depending on the original structure and desired output. Algorithms are things like depth-first-search, breadth-first-search, sequential search, etc. – svidgen Feb 9 '17 at 15:30
2

In your examples, the common characteristic is iteration through a sequence to find a member matching a particular characteristic.

So, the general class of algorithms you might be looking for is just a sequential search (aka linear search). It's the general form of algorithms that, "sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched."

In your case, the characteristics you're matching on happen to be mathematical, but the comparisons aren't part of the algorithm. They're your match-criteria. The algorithmic aspect of all three examples is the iteration.

  • This is the correct answer: "iterating a list to find a single element with a desired characteristic" is a linear search. – user22815 Feb 9 '17 at 0:45
  • 1
    @Snowman, but to find the min you have to check every element. It's not the same as searching "until a match is found", no? – Erik Eidt Feb 9 '17 at 1:37
  • @erik the general algorithm covers both cases. If it helps, you could say that, for some criteria, you simply won't have "found a match" until after the whole set is iterated over. – svidgen Feb 9 '17 at 1:43
  • 1
    @svidgen, ok I see what you're saying. But these functions seem more like aggregations to me rather than searches, so let's consider avg for a moment, for which there is no "match" at all, it is instead a computation over all elements. – Erik Eidt Feb 9 '17 at 4:13
  • 1
    @ErikEidt I did not use the words "until" or "match" which have specific meanings in the context of these algorithms. "until" means "do this action and stop once a condition is satisfied." "match" means "find a specific element with a desired property." The fact that there is a constant storage used as "the best so far" does not undermine the overall description of the algorithm. – user22815 Feb 9 '17 at 16:26
2

To expand on what @Erik_Eidt said, maxima and minima fall into the category of percentiles. They just happen to be the largest and smallest percentiles. It can be useful to find other percentiles such as the median or mode.

For example, in image processing finding the median color of an area of pixels can be used to smooth out image noise while preserving object edges.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.