Elixir中不区分大小写的快速排序 [英] Fast case-insensitive sorting in Elixir

问题描述

其他Elixir程序员。

Hi fellow Elixir programmers.

我有大约2.500个音乐曲目的列表，我想按不同的参数（例如曲目标题）进行排序。

I have list of about 2.500 music tracks that I would like to sort by different parameters, for example the title of the track.

排序不区分大小写。

下面的代码可以工作，但是对列表进行排序大约需要100ms到130ms。有更快的方法吗？对我来说是Node.js的参考，使用 Array.prototype.sort

The code below works, but takes about 100ms to 130ms to sort the list. Is there a faster way to do it? A reference for me is Node.js which does it in about 25ms when using Array.prototype.sort

编辑它大约需要25毫秒：抱歉，我实际上将表演的时机错误。排序发生在大约30毫秒内。但是，我仍然希望您的意见：可以更快地进行排序吗？

Sorry, I actually mistimed the performance. The sorting happens in about 30ms. However, I would still like your opinion: Can the sorting be done faster?

谢谢。

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 将调用比较器函数 n log（n ）次，这意味着 first_char 被称为 2n log（n）次， >可能成为这里的瓶颈。为了减少对 first_char 的调用，您可以切换到 Enum.sort_by ，它对每个元素都调用一次函数，然后进行缓存排序时的值：

Enum.sort will call the comparator function n log(n) times which means first_char will be called 2n log(n) times which might be the bottleneck here. To reduce calls to first_char, you can switch to Enum.sort_by which calls the function once for each element and then caches its value when sorting:

Enum.sort_by(tracks, fn track -> first_char(track["title"]) end)

对于长度为2500的列表，调用 first_char <的次数/ code>将从超过5万减少到2.5万。当然， sort_by 必须完成分配数据结构以存储计算值的工作，但是对于此输入而言，它应该仍然更快。使用它之前，您应该仔细自己进行基准测试！

For a list of length 2,500, the number of calls to first_char would reduce from over 50k to 2.5k. Of course sort_by will have to do work work allocating data structure to store the computed values but it should still be faster for this input. You should carefully benchmark this yourself before using it!

这篇关于Elixir中不区分大小写的快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！