Быстрая сортировка без учета регистра в 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
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
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

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