求效率最高的求数组最大值的索引方法。

数组data容量400个。要进行上百万次循环计算data。每次都要求data里最大值的索引号。因此速度要求比较高。
现在的写法

int Maxindex= Array.FindIndex(data,val=>val==data.Max());

执行耗时太久
有没有什么更好 高效的算法

21 个解决方案

#1

引用 楼主 u011672494 的回复:

数组data容量400个。要进行上百万次循环计算data。每次都要求data里最大值的索引号。因此速度要求比较高。
现在的写法

int Maxindex= Array.FindIndex(data,val=>val==data.Max());

执行耗时太久
有没有什么更好 高效的算法

这是个传统排序问题，你用这种标准方法解决速度不一定最合适你，建议你找找冒泡法、木桶法等多种排序方法然后根据你数据的实际情况选择最合适的排序方法。

#2

有一点lz没有描述清楚，
这400个数据是每一轮计算后都更新吗？
只要数据不是全部更新，那就可以优化
对不变的数据使用快速排序或堆排序等获取最大值，记录索引；
下一轮排序时就不需要再参与排序。
只需对变化的数据进行排序，然后两部分进行比较

#3

你数组排序后，直接用最后一个反向循环查找不就行了？
当然你也可以采用二分逼近法，但既然最大，从概率上讲，怎么都是倒序遍历快

#4

排序算法的时间复杂度 O(n*n)到 O(n*log2n) 之间
通用的 data.Max() 显然要经过排序的
FindIndex(data,val=>val==data.Max()) 有得经历一次遍历 O(n)
所以肯定是慢的

或许你可以下一个 for 循环，只遍历一次就一并找到

int k = 0;
for(int i = 1; i < array.Llength; i++) 
{
  if(array[i] > array[k]) k = i;
} 
//array[k] 就是最大值
//k 就是对应下标

#5

4楼正解，哪里需要什么排序算法，遍历一边就够了。有什么要求都满足了。

#6

在存入数据的时候就使用二叉排序树，那么随时可以得到最大值。

#7

既然每次都需要这个索引，那么就排序吧，400容量，排序很开的
排序后（升序）就好办了，399是最大索引，398是第二大，397是第三大……

#8

晕！你这个对于400个数字，要判断 400*400 次也就是10几万次比较啊？怎么能这么写？应该学点算法课程，接触点算法复杂性的分析概念才好。你说“速度要求比较高”这可不对头，明明是只要进行一趟 for 循环就能查询出来最大值来的算法，你写为那种算法本身就不是正常的编程啊。

要查找数组中的最大数字的位置，可以写类似这样的函数

static int MaxIndex<T>(T[] arr) where T: IComparable<T>
{
    var p = 0;
    var v = arr[0];
    for (var i = 1; i < arr.Length; ++i)
    {
        var w = arr[i];
        if (w.CompareTo(v)>0  )
        {
            v = w;
            p = i;
        }
    }
    return p;
}

如果你不想写成独立函数，那就写成委托，例如

var MaxIndex = new Func<double[], int>(arr =>
{
    var p = 0;
    var v = arr[0];
    for (var i = 1; i < arr.Length; ++i)
    {
        var w = arr[i];
        if (w > v)
        {
            v = w;
            p = i;
        }
    }
    return p;
});
var m = MaxIndex(data);

无论如何，跟编程语言毫无关系地是，不论你用任何编程语言，都应该有一个直观地分析算法时间复杂度和空间复杂度的公式推到知识。扫描一趟数组只需要 o(n) 级别的比较，而你的算法则需要 o(n*n) 级别的比较，可以说是1秒钟跟10分钟的巨大差别。

#9

如果对同一个 data 集合要进行“上百万次”处理，如果 data 不变，那么你只要把 MaxIndex 保存起来以后直接使用就行了。如果 data 集合是随时改变的，那么你的 data 本身就应该是排序的数据结构，并且 在插入数据时保证顺序，而绝非你那种查询计算概念了！！！

#10

所谓“更好 高效的算法”，对你来说其实可能还不是算法问题，是数据结构设计的问题。

#11

明明可以循环一次解决的问题,搞这么复杂

#12

引用 2 楼 xian_wwq 的回复:

有一点lz没有描述清楚，
这400个数据是每一轮计算后都更新吗？
只要数据不是全部更新，那就可以优化
对不变的数据使用快速排序或堆排序等获取最大值，记录索引；
下一轮排序时就不需要再参与排序。
只需对变化的数据进行排序，然后两部分进行比较

每一轮计算后都更新

#13

每一轮都会变的话，可以写成一个方法（#8）或是一个扩展

     public static class ex
       public static int MaxIndex<T>(this IEnumerable<T> arr) where T : IComparable<T>
        {
            var i = 0;
            var p = arr.First();
            var r = 0;
            foreach (var v in arr)
            {
                if (v.CompareTo(p) > 0)
                {
                    p = v;
                    r = i;
                }
                i++;
            }
            return r;
        }
    }

            var a = new int[] { 1, 3, 4, 5, 7, 8, 5, 4, 3 };
            var b = new List<int>() { 1, 3, 4, 5, 7, 8, 5, 4, 3 };
            Console.WriteLine(b.MaxIndex()); //5
            Console.WriteLine(a.MaxIndex()); //5

#14

引用 4 楼 xuzuning 的回复:

排序算法的时间复杂度 O(n*n)到 O(n*log2n) 之间
通用的 data.Max() 显然要经过排序的
FindIndex(data,val=>val==data.Max()) 有得经历一次遍历 O(n)
所以肯定是慢的

或许你可以下一个 for 循环，只遍历一次就一并找到

int k = 0;
for(int i = 1; i < array.Llength; i++) 
{
  if(array[i] > array[k]) k = i;
} 
//array[k] 就是最大值
//k 就是对应下标

嗯 是的 可以这么做

#15

引用 13 楼 xuzuning 的回复:

每一轮都会变的话，可以写成一个方法（#8）或是一个扩展

     public static class ex
       public static int MaxIndex<T>(this IEnumerable<T> arr) where T : IComparable<T>
        {
            var i = 0;
            var p = arr.First();
            var r = 0;
            foreach (var v in arr)
            {
                if (v.CompareTo(p) > 0)
                {
                    p = v;
                    r = i;
                }
                i++;
            }
            return r;
        }
    }

            var a = new int[] { 1, 3, 4, 5, 7, 8, 5, 4, 3 };
            var b = new List<int>() { 1, 3, 4, 5, 7, 8, 5, 4, 3 };
            Console.WriteLine(b.MaxIndex()); //5
            Console.WriteLine(a.MaxIndex()); //5

我具体项目需求是这样的 版主 您看下 我的思路写法是否合理：
 1： 手头生成了400幅图片 (这个是外部触发生成的。所以后续工作都是在这基础上做的)
2： 遍历图片 把每幅图片转化成灰度数组并放进 灰度数组图的键值对arr。
3： 遍历arr的每一个像素点，用400幅图的同位置像素点组成新数组供处理。Length是图像with*height。改进后 找索引如下

  for (int i = 0; i < Length; i++)
            {
              byte max = 0;
             int Maxindex = 0;
             foreach (var item in arr.Values)
                    {
                    if (item[i] > max)
                    {
                        max = item[i];
                        Maxindex = num;
                    }
                        data[num++] = item[i];
                    }
。。。。。。。。。。//操作data
}

#16

你纠结这个问题似乎已经很久了，如果 arr.Values 在每轮 foreach 中都是不一样的话
建议你在读取 灰度 值时就对整体数据做行列转置
由你现在的每行一张图片，改成每列一张图片
这样就不再需要耗时的取列循环了

#17

引用 16 楼 xuzuning 的回复:

你纠结这个问题似乎已经很久了，如果 arr.Values 在每轮 foreach 中都是不一样的话
建议你在读取 灰度 值时就对整体数据做行列转置
由你现在的每行一张图片，改成每列一张图片
这样就不再需要耗时的取列循环了

明白意思 。我这个arr是 add方法添加进来 .如何转置呢

  for (int i = 0; i < imageList.Count; i++)
                {
                    byte[] temp=ToArray(imageList[i]);
                    arr.Add(i, temp);
                    imageList[i].Dispose();
                    GC.Collect();
                }

#18

这可能要改写你的读取灰度值方法

#19

引用 18 楼 xuzuning 的回复:

这可能要改写你的读取灰度值方法

是在排列上要处理吧。。现在就用的最简单的

 public unsafe byte[] ToArray(Bitmap b)
        {
            BitmapData data = b.LockBits(new Rectangle(0, 0, b.Width, b.Height), ImageLockMode.ReadOnly, b.PixelFormat);

            int height = data.Height;
            int stride = data.Stride;

            IntPtr ptr = data.Scan0;
            int scanBytesLength = stride * height;

            byte[] rgbValues = new byte[scanBytesLength];
            unsafe
            {
                Marshal.Copy(ptr, rgbValues, 0, scanBytesLength);
            }
            b.UnlockBits(data);
            return rgbValues;
        }

那我再试试

#20

            var a = new int[] { 1, 3, 4, 5, 7, 8, 5, 4, 3 };
            var b = new List<int[]>() { a, a, a, a };
            var res = b[0].Zip(b[1], (x,y)=> new []{x,y});
            for(var i=2;i<b.Count;i++)
            {
                res = res.Zip(b[i], (x,y)=> x.Concat(new []{y}).ToArray());
            }
            foreach(var x in res)
              Console.WriteLine(string.Join(",", x));

你可以测试一下速度，大多情况下，直接写循环要快的多，但高级的写法容易被理解

#21

int Maxindex= Array.FindIndex(data,val=>val==data.Max());

一段标准的 LINQ 语法。

那 LINQ 解决了什么？
> LINQ 性能比 传统 for  foreach 循环慢一些（不可能快）
> LINQ 能节省大量代码行
> —— LINQ 除了代码少，没有任何性能优势。
> 为什么LINQ性能慢，还要推广LINQ？ —— 因为代码少，所以逻辑清，因此好维护。

再看你的代码，理论上： data.Max() 这段 脚本，已经 把数组 循环了一遍，FindIndex() 又把数组循环了一遍，而且还引入了 委托。
—— 原本找最大值索引，循环一次就能解决，你用 LINQ语法，循环了 两遍。