Question 288263 in Visual Studio Code Question posted in
View the official documentation.

Visual Studio Code – Efficiently find the indices of the 3 highest values in an array of 5 positive integers in C#

There are elsewhere good discussions on sorting of 5 things, which can be done with a maximum 7 comparisons.

It should be quicker to do what I want because we don’t care about the order of the 3 biggest integers (or the 2 smallest).

Context:
My program is playing the game Splendor, traversing the game tree as fast as possible. Just prior to the code below, it has populated the

var GemWeight = new int[5];

array to decide how important each of the five coloured gems are for procurement in the current state (the three highest weighted colors will be procured).

The elements are non-negative and no greater than 127.

I am presently finding the array indices (and respective integers) of the top 3 integers with this Linq:

var ThreeGemsWithIndices = 
   GemWeight
  .Select((TotalWeight, ColorIndex) => new { v=TotalWeight, ColorIndex })
  .OrderByDescending(x => x.v)
  .Take(3)
  .ToArray();

The Visual Studio profiler says my program is spending almost 20% of the time in this Linq, so it is ripe for attack.

What is the fastest c# algorithm to find the biggest 3 numbers, not necessarily sorted, and choosing the 3rd arbitrarily if there is a tie.

Eg: From array [2,6,10,43,6] we get an array or three variables containing 1,2,3 or 4,2,3 in any order.

[N.B.: Any suggestions on speeding up the Linq within the requirement of “Top 3 unordered” are welcome, although I suspect its speed will not match an imperative solution.]
Tags:

2

Answers


  1. 0

    Here two possible solutions are there

    1. If input data size is 5 then we can directly use the simple sorting which is much faster and easy.
    2. If input data size is varies in coming days and not control on it, then look for Linq solution with OrderByDescending

    Code with simple sorting

        public static int[] FindTopThreeValues(int[] array)
    {
        int first = int.MinValue, second = int.MinValue, 
        third = int.MinValue;

        foreach (int num in array)
        {
            if (num > first)
            {
                third = second;
                second = first;
                first = num;
            }
            else if (num > second && num != first)
            {
                third = second;
                second = num;
            }
            else if (num > third && num != second && num != first)
            {
                third = num;
            }
        }

        return new int[] { first, second, third };
    }

    Code with LINQ OrderByDescending

    var distinctValues = array.Distinct().OrderByDescending(x => x).Take(3).ToArray();
    Login or Signup to reply.
  2. 0

    A more generic approach to be used is to go with LINQ based solution :

    using System;
using System.Linq;
                    
public class Program
{
    public static void Main()
    {
        int[] numbers = { 10, 8, 15, 7, 20 };

        var indicesOfTopThree = GetIndicesOfTopThree(numbers);

        Console.WriteLine("Indices of the top three values: " + string.Join(", ", indicesOfTopThree));
    }
    
    static int[] GetIndicesOfTopThree(int[] array)
    {
        var indices = Enumerable.Range(0, array.Length)
                                .OrderByDescending(i => array[i])
                                .Take(3)
                                .ToArray();

        return indices;
    }
}

    Working .NetFiddle link here

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search