summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/elixir/lib/enum.ex67
-rw-r--r--lib/elixir/lib/list.ex71
-rw-r--r--lib/elixir/test/elixir/list_test.exs68
3 files changed, 179 insertions, 27 deletions
diff --git a/lib/elixir/lib/enum.ex b/lib/elixir/lib/enum.ex
index 8ff38418b..813822dbf 100644
--- a/lib/elixir/lib/enum.ex
+++ b/lib/elixir/lib/enum.ex
@@ -3081,11 +3081,12 @@ defmodule Enum do
iex> Enum.sort_by(["some", "kind", "of", "monster"], &byte_size/1, :desc)
["monster", "some", "kind", "of"]
- As in `sort/2`, avoid using the default sorting function to sort structs, as by default
- it performs structural comparison instead of a semantic one. In such cases,
- you shall pass a sorting function as third element or any module that implements
- a `compare/2` function. For example, to sort users by their birthday in both
- ascending and descending order respectively:
+ As in `sort/2`, avoid using the default sorting function to sort
+ structs, as by default it performs structural comparison instead of
+ a semantic one. In such cases, you shall pass a sorting function as
+ third element or any module that implements a `compare/2` function.
+ For example, to sort users by their birthday in both ascending and
+ descending order respectively:
iex> users = [
...> %{name: "Ellis", birthday: ~D[1943-05-11]},
@@ -3105,6 +3106,42 @@ defmodule Enum do
%{name: "Lovelace", birthday: ~D[1815-12-10]}
]
+ ## Performance characteristics
+
+ As detailed in the initial section, `sort_by/3` calculates the comparison
+ value for each element in the enumerable once instead of once for each
+ element in each comparison. This implies `sort_by/3` must do an initial
+ pass on the data to compute those values.
+
+ However, if those values are cheap to compute, for example, you have
+ already extracted the field you want to sort by into a tuple, then those
+ extra passes become overhead. In such cases, consider using `List.keysort/3`
+ instead.
+
+ Let's see an example. Imagine you have a list of products and you have a
+ list of IDs. You want to keep all products that are in the given IDs and
+ return their names sorted by their price. You could write it like this:
+
+ for(
+ product <- products,
+ product.id in ids,
+ do: product
+ )
+ |> Enum.sort_by(& &1.price)
+ |> Enum.map(& &1.name)
+
+ However, you could also write it like this:
+
+ for(
+ product <- products,
+ product.id in ids,
+ do: {product.name, product.price}
+ )
+ |> List.keysort(1)
+ |> Enum.map(&elem(&1, 0))
+
+ Using `List.keysort/3` will be a better choice for performance sensitive
+ code as it avoids additional traversals.
"""
@spec sort_by(
t,
@@ -3116,28 +3153,10 @@ defmodule Enum do
def sort_by(enumerable, mapper, sorter \\ &<=/2) do
enumerable
|> map(&{&1, mapper.(&1)})
- |> sort(to_sort_by_fun(sorter))
+ |> List.keysort(1, sorter)
|> map(&elem(&1, 0))
end
- defp to_sort_by_fun(sorter) when is_function(sorter, 2),
- do: &sorter.(elem(&1, 1), elem(&2, 1))
-
- defp to_sort_by_fun(:asc),
- do: &(elem(&1, 1) <= elem(&2, 1))
-
- defp to_sort_by_fun(:desc),
- do: &(elem(&1, 1) >= elem(&2, 1))
-
- defp to_sort_by_fun(module) when is_atom(module),
- do: &(module.compare(elem(&1, 1), elem(&2, 1)) != :gt)
-
- defp to_sort_by_fun({:asc, module}) when is_atom(module),
- do: &(module.compare(elem(&1, 1), elem(&2, 1)) != :gt)
-
- defp to_sort_by_fun({:desc, module}) when is_atom(module),
- do: &(module.compare(elem(&1, 1), elem(&2, 1)) != :lt)
-
@doc """
Splits the `enumerable` into two enumerables, leaving `count`
elements in the first one.
diff --git a/lib/elixir/lib/list.ex b/lib/elixir/lib/list.ex
index 5240f2b1d..46e410957 100644
--- a/lib/elixir/lib/list.ex
+++ b/lib/elixir/lib/list.ex
@@ -417,7 +417,13 @@ defmodule List do
@doc """
Receives a list of tuples and sorts the elements
- at `position` of the tuples. The sort is stable.
+ at `position` of the tuples.
+
+ The sort is stable.
+
+ A `sorter` argument is available since Elixir v1.14.0. Similar to
+ `Enum.sort/2`, the sorter can be an anonymous function, the atoms
+ `:asc` or `:desc`, or module that implements a compare function.
## Examples
@@ -427,12 +433,71 @@ defmodule List do
iex> List.keysort([a: 5, c: 1, b: 3], 0)
[a: 5, b: 3, c: 1]
+ To sort in descending order:
+
+ iex> List.keysort([a: 5, c: 1, b: 3], 0, :desc)
+ [c: 1, b: 3, a: 5]
+
+ As in `Enum.sort/2`, avoid using the default sorting function to sort
+ structs, as by default it performs structural comparison instead of a
+ semantic one. In such cases, you shall pass a sorting function as third
+ element or any module that implements a `compare/2` function. For example,
+ if you have tuples with user names and their birthday, and you want to
+ sort on their birthday, in both ascending and descending order, you should
+ do:
+
+ iex> users = [
+ ...> {"Ellis", ~D[1943-05-11]},
+ ...> {"Lovelace", ~D[1815-12-10]},
+ ...> {"Turing", ~D[1912-06-23]}
+ ...> ]
+ iex> List.keysort(users, 1, Date)
+ [
+ {"Lovelace", ~D[1815-12-10]},
+ {"Turing", ~D[1912-06-23]},
+ {"Ellis", ~D[1943-05-11]}
+ ]
+ iex> List.keysort(users, 1, {:desc, Date})
+ [
+ {"Ellis", ~D[1943-05-11]},
+ {"Turing", ~D[1912-06-23]},
+ {"Lovelace", ~D[1815-12-10]}
+ ]
+
"""
- @spec keysort([tuple], non_neg_integer) :: [tuple]
- def keysort(list, position) when is_integer(position) do
+ @spec keysort(
+ [tuple],
+ non_neg_integer,
+ (any, any -> boolean) | :asc | :desc | module() | {:asc | :desc, module()}
+ ) :: [tuple]
+ def keysort(list, position, sorter \\ :asc)
+
+ def keysort(list, position, :asc) when is_list(list) and is_integer(position) do
:lists.keysort(position + 1, list)
end
+ def keysort(list, position, sorter) when is_list(list) and is_integer(position) do
+ :lists.sort(keysort_fun(sorter, position + 1), list)
+ end
+
+ defp keysort_fun(sorter, position) when is_function(sorter, 2),
+ do: &sorter.(:erlang.element(position, &1), :erlang.element(position, &2))
+
+ defp keysort_fun(:asc, position),
+ do: &(:erlang.element(position, &1) <= :erlang.element(position, &2))
+
+ defp keysort_fun(:desc, position),
+ do: &(:erlang.element(position, &1) >= :erlang.element(position, &2))
+
+ defp keysort_fun(module, position) when is_atom(module),
+ do: &(module.compare(:erlang.element(position, &1), :erlang.element(position, &2)) != :gt)
+
+ defp keysort_fun({:asc, module}, position) when is_atom(module),
+ do: &(module.compare(:erlang.element(position, &1), :erlang.element(position, &2)) != :gt)
+
+ defp keysort_fun({:desc, module}, position) when is_atom(module),
+ do: &(module.compare(:erlang.element(position, &1), :erlang.element(position, &2)) != :lt)
+
@doc """
Receives a `list` of tuples and replaces the element
identified by `key` at `position` with `new_tuple`.
diff --git a/lib/elixir/test/elixir/list_test.exs b/lib/elixir/test/elixir/list_test.exs
index d1259f099..f022bc9f6 100644
--- a/lib/elixir/test/elixir/list_test.exs
+++ b/lib/elixir/test/elixir/list_test.exs
@@ -107,6 +107,74 @@ defmodule ListTest do
assert List.keysort([a: 4, c: 1, b: 2], 0) == [a: 4, b: 2, c: 1]
end
+ test "keysort/3 with stable sorting" do
+ collection = [
+ {2, 4},
+ {1, 5},
+ {2, 2},
+ {3, 1},
+ {4, 3}
+ ]
+
+ # Stable sorting
+ assert List.keysort(collection, 0) == [
+ {1, 5},
+ {2, 4},
+ {2, 2},
+ {3, 1},
+ {4, 3}
+ ]
+
+ assert List.keysort(collection, 0) ==
+ List.keysort(collection, 0, :asc)
+
+ assert List.keysort(collection, 0, &</2) == [
+ {1, 5},
+ {2, 2},
+ {2, 4},
+ {3, 1},
+ {4, 3}
+ ]
+
+ assert List.keysort(collection, 0, :desc) == [
+ {4, 3},
+ {3, 1},
+ {2, 4},
+ {2, 2},
+ {1, 5}
+ ]
+ end
+
+ test "keysort/3 with module and stable sorting" do
+ collection = [
+ {~D[2010-01-02], 4},
+ {~D[2010-01-01], 5},
+ {~D[2010-01-02], 2},
+ {~D[2010-01-03], 1},
+ {~D[2010-01-04], 3}
+ ]
+
+ # Stable sorting
+ assert List.keysort(collection, 0, Date) == [
+ {~D[2010-01-01], 5},
+ {~D[2010-01-02], 4},
+ {~D[2010-01-02], 2},
+ {~D[2010-01-03], 1},
+ {~D[2010-01-04], 3}
+ ]
+
+ assert List.keysort(collection, 0, Date) ==
+ List.keysort(collection, 0, {:asc, Date})
+
+ assert List.keysort(collection, 0, {:desc, Date}) == [
+ {~D[2010-01-04], 3},
+ {~D[2010-01-03], 1},
+ {~D[2010-01-02], 4},
+ {~D[2010-01-02], 2},
+ {~D[2010-01-01], 5}
+ ]
+ end
+
test "keystore/4" do
assert List.keystore([a: 1, b: 2], :a, 0, {:a, 3}) == [a: 3, b: 2]
assert List.keystore([a: 1], :b, 0, {:b, 2}) == [a: 1, b: 2]
View Lorry Controller Status