Максимум с индивидуальным заказом - PullRequest
Новая
       8

Максимум с индивидуальным заказом

4 голосов
/ 07 ноября 2019

У меня есть массив, подобный следующему: 

julia> list = [(x, rand(0:9), rand(0:9)) for x in 1:5]
5-element Array{Tuple{Int64,Int64,Int64},1}:
 (1, 7, 2)
 (2, 1, 3)
 (3, 4, 7)
 (4, 4, 8)
 (5, 8, 3)

Я бы хотел найти в этом списке элемент, у которого третье значение наибольшее. Если я просто делаю maximum(list), он использует порядок по умолчанию (лексикографический), а это не то, что мне нужно: 

julia> maximum(list)
(5, 8, 3)

Я могу использовать пользовательское преобразование / предикат by, если я сортирую весь список: 

julia> sort(list, by=x->x[3], rev=true)
5-element Array{Tuple{Int64,Int64,Int64},1}:
 (4, 4, 8)
 (3, 4, 7)
 (2, 1, 3)
 (5, 8, 3)
 (1, 7, 2)

Но это требует много дополнительной работы - все, что мне нужно, - это первое значение - но, похоже, maximum не поддерживает аргумент ключевого слова by: 

julia> maximum(list, by=x->x[3])
ERROR: MethodError: no method matching maximum(::Array{Tuple{Int64,Int64,Int64},1}; by=var"#21#22"())

И если я использую функцию «преобразования» первого аргумента, я получу только третье значение: 

julia> maximum(x->x[3], list)
8

Мне нужен весь элемент - (4, 4, 8) в этом случае. Как я могу это сделать?

Ответы [ 2 ]

6 голосов
/ 07 ноября 2019

Хотя maximum не поддерживает ключевое слово by, оно поддерживает функцию "преобразователь". В этом конкретном случае мы можем найти максимум перевернутых элементов, а затем повернуть его обратно: 

julia> reverse(maximum(reverse, list))
(4, 4, 8)

В более общем случае вы можете использовать инфраструктуру сортировки (со всеми ее изысками). by преобразователи и пользовательские lt сравнения) без фактической сортировки всего списка с помощью partialsort: 

julia> partialsort(list, 1, by=x->x[3], rev=true)
(4, 4, 8)

Это не так эффективно, но гораздо более эффективно - и экономит немалоперебрать всю вещь. С большим вектором: 

julia> using BenchmarkTools

julia> list = [(x, rand(0:9), rand(0:9)) for x in 1:10_000];

julia> @btime reverse(maximum(reverse, $list));
  7.833 μs (0 allocations: 0 bytes)

julia> @btime partialsort($list, 1, by=x->x[3], rev=true);
  37.772 μs (3 allocations: 234.48 KiB)

julia> @btime sort($list, by=x->x[3], rev=true);
  339.570 μs (5 allocations: 351.81 KiB)
3 голосов
/ 07 ноября 2019

Другая возможность - использовать sortperm для получения индексов перестановки сокращенного массива (содержащего только ключи, по которым вы хотите отсортировать), а затем использовать эти индексы для сортировки полного массива: 

a = [(x, rand(0:9), rand(0:9)) for x in 1:5]
perm = sortperm(a, by=x->x[3], rev=true)
b = a[perm]

Или, если вас интересует только максимум, используйте 

b_max = a[perm[1]]

или 

i_max = findmax(map(x->x[3], a)[2]
b_max = a[i_max]
...