朱莉亚中选择数组中最长数组的最有效方法是什么？

Question

我有一个二维数组A，它是一个长度为N的整型数组Array{Array{Int64,1},1}。现在我想用Julia编程语言找到A中最大的子数组。

例如：

A =  [[1, 2], [3, 4], [5, 6, 7], [1, 2, 5, 8]]

在Python中，我会简单地使用以下代码：max(A, key=len)，但在Julia中我不知道该怎么做。

我的解决方法是这样的：

L = []
for a in A
    push!(L, length(a))
end
A[findmax(L)[2]]

谢谢！

- Jarbou

---

上面粘贴的Julia代码的输出是什么？ - Steve Davis

输出结果为：4个元素的数组{Int64,1}：1 2 5 8 - Jarbou

Answer 1

< p > @Colin 提供了一个简洁、方便的答案。然而，如果速度很重要（op 要求最有效的方法），那么这应该接近最优解。 < /p >

function findlongest(A)
    idx = 0
    len = 0
    @inbounds for i in 1:length(A)
        l = length(A[i])
        l > len && (idx = i; len=l)
    end
    return A[idx]
end

请注意，这种实现方法在Python中可能是个非常糟糕的想法 :)

快速基准测试：

julia> using BenchmarkTools

julia> A = [[1,2], [1,2,3,4,5,6], [1,2,3]]
3-element Array{Array{Int64,1},1}:
 [1, 2]            
 [1, 2, 3, 4, 5, 6]
 [1, 2, 3] 

julia> @btime findlongest(A);
  26.880 ns (0 allocations: 0 bytes)

julia> @btime A[indmax(length.(A))];
  9.813 μs (25 allocations: 1.14 KiB)

这个例子的速度提升了约365倍。

编辑：更好的基准测试（评论中建议）

julia> @btime findlongest($A);
  9.813 ns (0 allocations: 0 bytes)

julia> @btime $A[indmax(length.($A))];
  41.813 ns (1 allocation: 112 bytes)

$ 符号避免了设置分配和时间。加速约为 4。 快速解释

• 在 Julia 中，for 循环很快，所以为什么不使用它们
• 避免分配 (length.(A) 分配了一个新的整数数组)
• a && b 是“如果 a 那么 b”的快捷方式
• @inbounds 避免对 A[i] 进行边界检查

- carstenbauer

---

尝试使用@btime $A[indmax(length.($A))];以避免设置分配，从而获得更好的计时。 - Dan Getz

Answer 2

更新：对于v1+，您需要将此答案中的indmax替换为argmax。

编辑：请注意，还值得查看@crstnbr的其他答案。

考虑以下示例代码：

julia> A = [[1,2], [1,2,3,4,5,6], [1,2,3]]
3-element Array{Array{Int64,1},1}:
 [1, 2]            
 [1, 2, 3, 4, 5, 6]
 [1, 2, 3]         

julia> length(A)
3

julia> length.(A)
3-element Array{Int64,1}:
 2
 6
 3

julia> indmax(length.(A))
2

julia> A[indmax(length.(A))]
6-element Array{Int64,1}:
 1
 2
 3
 4
 5
 6

length第一次调用得到的是A中外部向量的长度，这并不是我们想要的。在第二次调用中，我使用广播运算符.，这样我可以得到每个内部向量的长度。在indmax行中，我找到了length.(A)中最大值的索引，即最长内部向量的索引。如果你想返回最长的内部向量，你只需要使用indmax行的结果作为A的索引即可。

- Colin T Bowers

---

简明扼要的答案 - Jon

谢谢。如果A是一个字典，是否可以这样做？例如，Dict(1=>[1,2],10=>[1,2,3,45])，我想返回最大数组的key。在这里，我想返回10。 - Jarbou

@Jarbou 这有点不太整洁，因为广播操作不能与字典一起使用。我认为 collect(keys(x))[indmax([ length(v) for v in values(x) ])] 可以完成任务，虽然我不是字典专家，所以其他人可能知道更有效的方法。 - Colin T Bowers

length.(A)会创建数组的副本，这可能不是最好的方法。不幸的是，我没有找到任何正常的解决方案（我还是个初学者！）。我能提出的最好的“一行代码”是-> maxx(a, keyfun) = a[mapreduce((x) -> (x[1], keyfun(x[2])), (x,y) -> y[2]>x[2]?y:x, enumerate(a))[1]]; maxx(A, length) 这很丑陋，可能最好编写带有空数组检查和for循环的函数。 - Liso

在 Julia 1.3 中未定义 indmax。 - JoseOrtiz3

@OrangeSherbet 感谢提醒。我会将答案更新为 argmax。 - Colin T Bowers

Answer 3

indmax在Julia中不再被定义（至少1.3版本如此）。

请使用argmax代替。

>>> A = [[1,2], [1,2,3]]
2-element Array{Array{Int64,1},1}:
 [1, 2]   
 [1, 2, 3]

>>> length.(A)
2-element Array{Int64,1}:
 2
 3

>>> argmax(length.(A))
2

>>> A[argmax(length.(A))]
3-element Array{Int64,1}:
 1
 2
 3

- JoseOrtiz3