Привет, товарищи, программисты Эликсира.
У меня есть список из примерно 2,500 музыкальных треков, которые я хотел бы отсортировать по различным параметрам, например по названию трека.
Сортировка должна производиться без учета регистра.
Приведенный ниже код работает, но для сортировки списка требуется от 100 до 130 мс. Есть ли более быстрый способ сделать это? Ссылка для меня - Node.js, который делает это примерно за 25 мс при использовании Array.prototype.sort
.
Обновлено: извините, я на самом деле не вовремя выступил. Сортировка происходит примерно за 30 мс. Однако мне все же хотелось бы узнать ваше мнение: можно ли сделать сортировку быстрее?
Спасибо.
defmodule MusicServer.Tracks.SortTracks do
def sort_tracks(tracks, "title", "desc") do
Enum.sort(tracks, fn track1, track2 ->
first_char(track1["title"]) <= first_char(track2["title"])
end)
end
def first_char(string) do
string
|> String.at(0)
|> String.downcase()
end
end
Пример структуры данных:
[
%{
"artist" => "Rolling Stones",
"title" => "Start It Up",
"bpm" => 100,
"createdAt" => "2018-04-27T09:08:04.428Z",
"updatedAt" => "2018-07-14T14:28:17.771Z"
},
%{
"artist" => "Al Green",
"title" => "Let's Stay Together",
"bpm" => 123,
"createdAt" => "2018-04-27T09:08:04.428Z",
"updatedAt" => "2018-07-14T14:28:17.771Z"
},
...
]
Невероятно быстро! Когда я использую Enum.sort_by
, как вы предложили, {time, result} = :timer.tc (fn -> MusicServer.Tracks.SortTracks.sort_tracks(tracks, "title", "desc") end)
дает мне 7433, 6969, 6356 (микросекунды) ... Спасибо!
И гораздо более читабельным!
Мне любопытно, почему это так. Есть идеи, Догберт?
По крайней мере, он сначала вычисляет первые символы каждого заголовка, а затем начинает сортировку github.com/elixir-lang/elixir/blob/v1.7.2/lib/elixir/lib/…
поэтому first_char (строка) вызывается n раз вместо количества сравнений (> n)
@ChristopheDeTroyer: С Enum.sort_by
документы: sort_by/3
отличается от sort/2
тем, что вычисляет значение сравнения для каждого элемента в перечисляемом только один раз, а не для каждого элемента в каждом сравнении. (Я немного изменил формулировку, чтобы было понятнее, что пытаются сказать документы.)
Enum.sort
будет вызывать функцию компаратора n log(n)
раз, что означает, что first_char
будет вызываться 2n log(n)
раз, при этом мог будет здесь узким местом. Чтобы уменьшить количество обращений к first_char
, вы можете переключиться на Enum.sort_by
, который вызывает функцию один раз для каждого элемента, а затем кэширует ее значение при сортировке:
Enum.sort_by(tracks, fn track -> first_char(track["title"]) end)
Для списка длиной 2 500 количество вызовов first_char
уменьшится с 50 000 до 2,5 000. Конечно, sort_by
должен будет выполнить работу по распределению структуры данных для хранения вычисленных значений, но это все равно должно быть быстрее для этого ввода. Вы должны тщательно протестировать это самостоятельно, прежде чем использовать!
Престижность за осведомленность об асимптотических (думаю, я правильно понял свой термин) характеристиках поведения!
Можете попробовать синхронизировать
Enum.sort_by(tracks, fn track -> first_char(track["title"]) end)
?