Главная

Эффективная сортировка данных типа Struct

2020-01-02 в 10:28, admin, рубрики: comparison, Elixir/Phoenix, sorting

Все, пришедшие в Elixir / Erlang из других языков, скорее всего, имеют некоторые ожидания относительно того, как должны работать операторы сравнения >, <, == и т. п. Можно было бы ожидать, что 1 < 2, (и это действительно так). В принципе, можно сказать, что сравнение работает как надо. Но не всегда.

В Elixir / Erlang можно сравнивать все что угодно. Вообще. В то время как для двух операндов одного типа результат не обескураживает, как в приведенном выше примере, сравнение двух операндов разных типов приводит к довольно неожиданным последствиям. Потому что сами по себе типы «упорядочены для сравнения». Вот таким образом:

number < atom < reference < function < port < pid < tuple < map < list < bitstring

Что внезапно приводит к тому, что полностью легитимное сравнение 42 < nil возвращает true.

Кроме того, maps (и, как следствие, structs, которые на самом деле те же maps под капотом) сравниваются в соответствии с их полями в алфавитном порядке. Иными словами, даты (которые реализованы в Elixir структурой Date) будут сравниваться последовательно по значениям полей day, затем month, а затем year, а это, скорее всего, не совсем то, чего бы мы хотели.

Начиная с v1.10.0, Elixir обеспечивает удобную сортировку стандартным Enum.sort/2, если структура экспортирует функцию compare/2:

defmodule User do
  defstruct [:name]
  def compare(%User{name: n1}, %User{name: n2}) when n1 < n2,
    do: :lt
  def compare(%User{name: n1}, %User{name: n2}) when n1 > n2,
    do: :gt
  def compare(%User{}, %User{}), do: :eq
end

users = [
  %User{name: "john"},
  %User{name: "joe"},
  %User{name: "jane"}
]

Enum.sort(users, {:asc, User})
#⇒ [%User{name: "jane"},
#   %User{name: "joe"},
#   %User{name: "john"}]

Любой модуль, который определяет struct, и экспортирует функцию compare/2, может быть передан как второй параметр в вызов Enum.sort/2 либо как есть, либо как кортеж {:asc | :desc, StructModule}. Enum.sort/2 теперь достаточно умен, чтобы вызвать функцию compare/2 модуля, переданного Enum.sort/2. Ниже приведен отрывок из модуля Enum, реализующий именно этот функционал:

...
defp to_sort_fun(module) when is_atom(module),
  do: &(module.compare(&1, &2) != :gt)
defp to_sort_fun({:asc, module}) when is_atom(module),
  do: &(module.compare(&1, &2) != :gt)
defp to_sort_fun({:desc, module}) when is_atom(module),
  do: &(module.compare(&1, &2) != :lt)

Это позволяет правильно сортировать даты в приведенном ниже примере (спасибо существующей уже давно Date.compare/2), как и любую определенную пользователем структуру (если она экспортирует compare/2, конечно), как в примере со структурой User выше.

dates = [~D[2019-01-01], ~D[2020-03-02], ~D[2019-06-06]]

Enum.sort(dates) # wrong
#⇒ [~D[2019-01-01], ~D[2020-03-02], ~D[2019-06-06]]

Enum.sort(dates, {:asc, Date}) # correct
#⇒ [~D[2019-01-01], ~D[2019-06-06], ~D[2020-03-02]]

Удачных сортировок!

Автор: Aleksei Matiushkin

Источник