C#•2mo ago

✅ Can we find min and max values of any given array directly? (use of any built-in methods?)

Hi guys, I wanted to find min and max value of an array of numbers. I can do it using a loop, comparing each index. I have to manually set up everything and the algorithm is not as much efficient I think. So I was wondering if there was any in-built method or any better algorithm in terms of efficiency please

13 Replies

mg•2mo ago

There's Enumerable.Max() from LINQ, but under the hood it does the same thing You can't know what the min/max are without checking every element There are SIMD accelerated solutions that can check multiple pairs of entries simultaneously, but that's not something you need to worry about at this point

FakerOP•2mo ago

oki noted, thanks !

mg•2mo ago

sure thing

jcotton42•2mo ago

>algorithm is not much efficient Surely it’s O(n)? How did you do it @Faker?

MODiX•2mo ago

Cattywampus

REPL Result: Success

static void FindMax(int[] arr)
{
  ref var tref = ref MemoryMarshal.GetArrayDataReference(arr);
  var min = Vector128<int>.Zero;
        
  for(int i = 0; i < arr.Length; i+=4)
  {
     var val = Vector128.LoadUnsafe(ref Unsafe.Add(ref tref, i));
     min = Vector128.Max(min, val);
  }
        
  var max = min.ToScalar();
  max = Math.Max(max, min.GetElement(1));
  max = Math.Max(max, min.GetElement(2));
   max = Math.Max(max, min.GetElement(3));
        
        Console.WriteLine(max);
}
    
FindMax(new int[]{1,2,3,4,5,6,7,8,9,0,0, 12});

static void FindMax(int[] arr)
{
  ref var tref = ref MemoryMarshal.GetArrayDataReference(arr);
  var min = Vector128<int>.Zero;
        
  for(int i = 0; i < arr.Length; i+=4)
  {
     var val = Vector128.LoadUnsafe(ref Unsafe.Add(ref tref, i));
     min = Vector128.Max(min, val);
  }
        
  var max = min.ToScalar();
  max = Math.Max(max, min.GetElement(1));
  max = Math.Max(max, min.GetElement(2));
   max = Math.Max(max, min.GetElement(3));
        
        Console.WriteLine(max);
}
    
FindMax(new int[]{1,2,3,4,5,6,7,8,9,0,0, 12});

Console Output

Compile: 548.824ms | Execution: 64.503ms | React with ❌ to remove this embed.

Cattywampus•2mo ago

like that ☝️ it might not be faster due to GetElement()s, should be easily be tackled with shuffles then use myVec.ToScalar() which is free compared to GetElement tbfh, 100% sure Linq already be doing this under the hood

mg•2mo ago

surprisingly no at least not the file i checked oh wait, yes it does, i just can't read code properly

Cattywampus•2mo ago

yeah, min/max is like very easy to vectorized

FakerOP•2mo ago

euh I iterate through entire array, take the maximum as being the first element, then check for each subsequent element, time complexity of O(n) yeah what is the meaning of vectorized please ;c... I once saw the syntax of C++ where the term "vector" was used

mg•2mo ago

https://learn.microsoft.com/en-us/dotnet/standard/simd

SIMD-accelerated types in .NET - .NET

This article describes SIMD-enable types in .NET and demonstrates how to use hardware SIMD operations in C# and .NET.

mg•2mo ago

it's a somewhat advanced topic not the same vectors in C++, those are equivalent to C#'s lists https://www.meziantou.net/finding-maximum-value-in-an-array-using-vectorization.htm here's an example of finding max using it

FakerOP•2mo ago

oh ok, I will just scheme through, just to see what it is all about Thanks !

mg•2mo ago

sure thing

Gaming

Programming

✅ Can we find min and max values of any given array directly? (use of any built-in methods?)

Did you find this page helpful?