Edited at

ElixirでSleep Sort書いてみた

More than 1 year has passed since last update.


Sleep Sortとは

http://qiita.com/snsk/items/33c01951ef27bbd2b093


コード


sleep_sort.exs

defmodule SleepSort do

def order(list, order\\:assending) when is_list(list) do
collector_pid = spawn(SleepSort, :collector, [[], self()])
spawn(SleepSort, :order_element, [list, 0, collector_pid])

list = receive do
{:result, result} ->
result
end

{:ok, list}
end

def order_element([], time, collector) do
Process.sleep(time + 1)
send collector, { :terminate }
end

def order_element([ head | tail ], max_time, collector) do
time = head * 2
spawn(SleepSort, :launch, [head, time, collector])
order_element(tail, max(max_time, time), collector)
end

def launch(element, msec, collector) when is_integer(msec) do
Process.sleep(msec)
send collector, {:append, element}
end

def collector(list, result_receiver) when is_list(list) and is_pid(result_receiver) do
receive do
{:append, element} ->
collector([element | list], result_receiver)
{:terminate} ->
send result_receiver, {:result, Enum.reverse(list)}
end
end
end

list = (0..100)
|> (fn (a) -> fn -> Enum.random(a) end end).()
|> Stream.repeatedly()
|> Enum.take(20)
{:ok, result} = list |> SleepSort.order()
IO.inspect result


Concurrent Programmingの練習になるのかもしれないと思って書いてみた。やってることは割とシンプルな気がする、こういうのが書きやすいのは良いなって思いました。

とりあえずOrderが並び替えるものの最大値の倍になる(O(Nmax * 2)?)のでなんとかしたいなぁとか

なんで倍にしてるかと言うと数値分だけProcess.sleep()させたときに順番が前後したりしたからです。プロセスの生成にかかる時間とかで誤差が出るのかなと。2に根拠はないですが…

うまくSleepの時間をバラけさせつつ全体としてあんまり時間のかからない方法が思いつけばなー


こっちのが簡潔だった


defmodule SleepSort do

def sort(collection) do
me = self
collection
|> Enum.map(fn (n) ->
spawn_link fn -> (send me, { :timer.sleep(n * 10) && n }) end
end)
|> Enum.map(fn (_pid) ->
receive do { result } -> result end
end)
end
end

Elixir で Sleep Sort を実装する http://sinsoku.hatenablog.com/entry/2016/11/13/225019

ただ、すべてをspawn_linkし終わってから回数分のrecieveを始めているので、あまりにも戻ってくるのが早いと(もしくはListがめっっちゃ長いと)キャッチしそこねそうな気がする。どうなんでしょう。

(その不安から自分の実装では受取用のプロセスを先にspawnしている)

これProgramming Elixirにある例(Parallel Map)とほぼ同じなんですね。てことはいいのか