Быстрая сортировка без учета регистра в elixir

Привет, товарищи, программисты Эликсира.

У меня есть список из примерно 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(tracks, fn track -> first_char(track["title"]) end)?

Dogbert 10.08.2018 15:28

Невероятно быстро! Когда я использую Enum.sort_by, как вы предложили, {time, result} = :timer.tc (fn -> MusicServer.Tracks.SortTracks.sort_tracks(tracks, "title", "desc") end) дает мне 7433, 6969, 6356 (микросекунды) ... Спасибо!

skovmand 10.08.2018 15:33

И гораздо более читабельным!

skovmand 10.08.2018 15:35

Мне любопытно, почему это так. Есть идеи, Догберт?

Christophe De Troyer 10.08.2018 15:35

По крайней мере, он сначала вычисляет первые символы каждого заголовка, а затем начинает сортировку github.com/elixir-lang/elixir/blob/v1.7.2/lib/elixir/lib/…

Igor Drozdov 10.08.2018 15:38

поэтому first_char (строка) вызывается n раз вместо количества сравнений (> n)

Igor Drozdov 10.08.2018 15:38

@ChristopheDeTroyer: С Enum.sort_byдокументы: sort_by/3 отличается от sort/2 тем, что вычисляет значение сравнения для каждого элемента в перечисляемом только один раз, а не для каждого элемента в каждом сравнении. (Я немного изменил формулировку, чтобы было понятнее, что пытаются сказать документы.)

7stud 10.08.2018 18:37
7
7
513
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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 должен будет выполнить работу по распределению структуры данных для хранения вычисленных значений, но это все равно должно быть быстрее для этого ввода. Вы должны тщательно протестировать это самостоятельно, прежде чем использовать!

Престижность за осведомленность об асимптотических (думаю, я правильно понял свой термин) характеристиках поведения!

Onorio Catenacci 10.08.2018 20:51

Другие вопросы по теме