使用C#查找整型数组中的最小值

Question

如何在C#中查找int数组的最小值

- user500085

Answer 1

使用 LINQ：

int min = theArray.Min();

请注意，如果没有任何元素，这将出错；首先检查.Length（或者，作为替代方案，投影到int?，但这会增加开销）。

如果您没有可用的LINQ，则可以尝试：

public static int Min(int[] arr) {
    switch (arr.Length) {
        case 0: throw new InvalidOperationException();
        case 1: return arr[0];
        case 2: return Math.Min(arr[0], arr[1]);
        default:
            int min = arr[0];
            for (int i = 1; i < arr.Length; i++) {
                if (arr[i] < min) min = arr[i];
            }
            return min;
    }
}

- Marc Gravell

---

@SaeedAlg - 我正在检查数组的长度；如果它只有一个元素，那么最小值显然是第一个（唯一）元素；如果有两个，则将其视为另一种特殊情况因为我们可以方便地这样做 - 否则我们将遍历数组并找到最小值。 - Marc Gravell

你可以不用它们，如果你的数组大小为1或2，那么默认情况下就不需要在case中这样做，只需要一个简单的if语句即可。但是如果你认为这样做更易读，那也是可以接受的。 - Saeed Amiri

@SaeedAlg - 嗯，我们无论如何都需要检查长度，所以我们可以利用这个知识做些有用的事情... - Marc Gravell

我进行了测试，使用简单的if语句检查长度是否为0，然后循环，甚至稍微快一点（<1%），所以为什么要增加所有额外的代码呢？ - Doggett

@Doggett - 好的，你可以按照自己喜欢的方式来做。说实话，你分析得太多了吧？按照现有的代码将能正常工作并通过我所能想到的任何（合理的）测试。如果你想发布更简单的版本，请随意；我会很高兴地点赞！但请注意我的回答的第一部分....Min()... - Marc Gravell

Answer 2

我写了下面的代码来比较一下我和 @Marc Gravell 说的话，我说的方法在我的电脑上稍微快一些，而 Linq 的方法是最慢的。此外，如果你改变函数的位置（在代码中），你总是可以通过使用带有 if 的版本来获得更好的性能。

    static void Main(string[] args)
    {
        Dictionary<string, List<long>> dic = new Dictionary<string, List<long>>();

        dic["First"] = new List<long>();
        dic["Second"] = new List<long>();
        dic["Third"] = new List<long>();


        for (int i = 0; i < 500; i++)
        {
            int[] array = GetRandomArray();
            Stopwatch stopWacth = new Stopwatch();
            stopWacth.Restart();
            int n1 = FindMin(array);
            stopWacth.Stop();
            long firstTicks = stopWacth.ElapsedTicks;
            dic["First"].Add(firstTicks);

            stopWacth.Restart();
            int n2 = AnotherFindMin(array);
            stopWacth.Stop();
            long secondTick = stopWacth.ElapsedTicks;
            dic["Second"].Add(secondTick);

            stopWacth.Restart();
            int n3 = array.Min();
            stopWacth.Stop();
            long thirdTick = stopWacth.ElapsedTicks;
            dic["Third"].Add(thirdTick);

            Console.WriteLine("first tick : {0}, second tick {1}, third tick {2} ", firstTicks, secondTick, thirdTick);
        }

        Console.WriteLine("first tick : {0}, second tick {1}, third tick {2} ", dic["First"].Average(), dic["Second"].Average(), dic["Third"].Average());

        Console.ReadLine();
    }


    public static int[] GetRandomArray()
    {
        int[] retVal = new int[1000000];
        Random r = new Random();
        for (int i = 0; i < 1000000; i++)
        {
            retVal[i] = r.Next(1000000000);
        }
        return retVal;
    }

    public static int FindMin(int[] arr)
    {
        switch (arr.Length)
        {
            case 0: throw new InvalidOperationException();
            case 1: return arr[0];
            case 2: return Math.Min(arr[0], arr[1]);
            default:
                int min = arr[0];
                for (int i = 1; i < arr.Length; i++)
                {
                    if (arr[i] < min) min = arr[i];
                }
                return min;
        }
    }

    public static int AnotherFindMin(int[] arr)
    {
        if (arr.Length > 0)
        {
            int min = arr[0];
            for (int i = 1; i < arr.Length; i++)
            {
                if (arr[i] < min) min = arr[i];
            }
            return min;
        }
        else
        {
            throw new InvalidOperationException();
        }
    }
}
// revised test by Marc (see comments discussion)
static class Test {
    static void Main(string[] args)
    {
        Dictionary<string, List<long>> dic = new Dictionary<string, List<long>>();

        dic["First"] = new List<long>();
        dic["Second"] = new List<long>();
        dic["Third"] = new List<long>();

        const int OUTER_LOOP = 500, INNER_LOOP = 500000;
        for (int arrSize = 1; arrSize <= 3; arrSize++)
        {
            for (int i = 0; i < OUTER_LOOP; i++)
            {
                int[] array = GetRandomArray(arrSize);
                Stopwatch stopWacth = Stopwatch.StartNew();
                for (int j = 0; j < INNER_LOOP; j++)
                {
                    int n1 = FindMin(array);
                }
                stopWacth.Stop();
                long firstTicks = stopWacth.ElapsedTicks;
                dic["First"].Add(firstTicks);

                stopWacth = Stopwatch.StartNew();
                for (int j = 0; j < INNER_LOOP; j++)
                {
                    int n2 = AnotherFindMin(array);
                }
                stopWacth.Stop();
                long secondTick = stopWacth.ElapsedTicks;
                dic["Second"].Add(secondTick);

                stopWacth = Stopwatch.StartNew();
                for (int j = 0; j < INNER_LOOP; j++)
                {
                    int n3 = array.Min();
                }
                stopWacth.Stop();
                long thirdTick = stopWacth.ElapsedTicks;
                dic["Third"].Add(thirdTick);

                //Console.WriteLine("{3}: switch : {0}, 0-check {1}, Enumerable.Min {2} ", firstTicks, secondTick, thirdTick, arrSize);
            }

            Console.WriteLine("{3}: switch : {0}, 0-check {1}, Enumerable.Min {2} ", dic["First"].Average(), dic["Second"].Average(), dic["Third"].Average(), arrSize);
        }
        Console.WriteLine("Done");
        Console.ReadLine();
    }


    public static int[] GetRandomArray(int size)
    {
        int[] retVal = new int[size];
        Random r = new Random();
        for (int i = 0; i < retVal.Length; i++)
        {
            retVal[i] = r.Next(1000000000);
        }
        return retVal;
    }

    public static int FindMin(int[] arr)
    {
        switch (arr.Length)
        {
            case 0: throw new InvalidOperationException();
            case 1: return arr[0];
            case 2: return arr[0] < arr[1] ? arr[0] : arr[1];
            default:
                int min = arr[0];
                for (int i = 1; i < arr.Length; i++)
                {
                    if (arr[i] < min) min = arr[i];
                }
                return min;
        }
    }

    public static int AnotherFindMin(int[] arr)
    {
        if (arr.Length > 0)
        {
            int min = arr[0];
            for (int i = 1; i < arr.Length; i++)
            {
                if (arr[i] < min) min = arr[i];
            }
            return min;
        }
        else
        {
            throw new InvalidOperationException();
        }
    }
}

- Saeed Amiri

---

一个单次迭代的秒表不会给出有意义的答案；此外，这个测试只考虑了“默认”情况（公平地说，这是最有可能的情况）。而且那个数组是如此之大，以至于任何测试都几乎没有显示出来从这种逻辑选择中得到的数字... - Marc Gravell

不，我在 .Net 4 中使用了 using System.Diagnostics;，重启对我来说不是必要的。@Marc Gravell，你应该注意程序集跳转，因为这对我的方法来说更长。 - Saeed Amiri

@SaeedAlg - 测试中存在两个问题；数组太大了，所有时间都花在运行相同的代码上，即数组循环。你所争论的部分（switch）几乎没有被执行。实际上，在这里检查差异的理想数组大小应该是3，因为这将最小化在相同代码中花费的时间（从而突出显示不同的代码）- 即使这样，我们仍然只测试了switch的负面影响 - 要测试正面影响，您还需要重复长度为1和2的测试。 - Marc Gravell

@Marc Gravell，我不知道如何检查大小为1,2的数组，因为我认为所有时间都花在了方法调用上。但是，大小为2,1是所有可能性中最小的数字。 - Saeed Amiri

@SaeedAlg - 关于1,2的问题 - 我对此的反驳是，针对大型数组的测试同样毫无意义...你无法得到有关所讨论代码的任何数字。 - Marc Gravell