a-conjecture-of-mine

An exercise on polyglossy: the same problem solved on multiple languages

git clone: git://git.pablopie.xyz/a-conjecture-of-mine
Log
Files
Refs

Commit: fa487a0aad28fc9038b6f6cbe11a00e2a629833c
Parent: 92f58e67c5dab7593b4eb27d519c40cfa6158206
Author: Pablo Escobar Gaviria <gark.garcia@protonmail.com>
Date: Sat, 28 Dec 2019 11:19:01 -0200

Finished optimizing the Elixir implementation.

Improved performance by storing the caches of `sum n` in an ETS table instead of in an accumulated map, reducing message-passaging between processes.

Diffstat

1 file changed, 26 insertions, 35 deletions

Status	File Name	N° Changes	Insertions	Deletions
Modified	Elixir/digital_sum.ex	61	26	35

diff --git a/Elixir/digital_sum.ex b/Elixir/digital_sum.ex
@@ -12,10 +12,11 @@ defmodule Conjecture do
       :invalid_input
     else
       parent_id = self()
+      :ets.new(:sums_cache, [:set, :public, :named_table])
 
       # Spawn a new process for each starting index from 0 to `max`
       f = fn i -> spawn fn -> counterexpl i, max, n_processes, parent_id end end
-      Enum.map 1..n_processes, f
+      Enum.map 0..(n_processes - 1), f
 
       listen n_processes, %{}
     end
@@ -28,53 +29,52 @@ defmodule Conjecture do
     receive do
       :ok -> listen (n - 1), sums_cache
       :fail -> :fail
-      {child_id, m} ->
+      {:get, child_id, m} ->
         if Map.has_key? sums_cache, m do
-          send child_id, sums_cache[m]
-          listen n, sums_cache
+          send child_id, {:found, sums_cache[m]}
         else
-          sum_m = sum m
-          send child_id, sum_m
-          listen m, Map.put(sums_cache, m, sum_m)
+          send child_id, :notfound
         end
+        listen n, sums_cache
+      {:put, m, sum_m} ->
+        listen n, Map.put(sums_cache, m, sum_m)
     end
   end
 
   def counterexpl a, max, step, parent_id do
     cond do 
-      iter a, 0, parent_id -> send parent_id, :found
+      iter a, 0 -> send parent_id, :fail
       a + step <= max ->
         counterexpl (a + step), max, step, parent_id
       true -> send parent_id, :ok
     end
   end
 
-  def iter a, b, parent_id do
-    IO.puts (test a, b, parent_id)
+  def iter a, b do
     cond do
-      test a, b, parent_id -> true
-      b + 1 < a -> iter a, b + 1, parent_id
+      test a, b -> true
+      b + 1 < a -> iter a, b + 1
       true -> false
     end
   end
 
-  def test a, b, parent_id do
-    self_id = self()
-    send parent_id, {self_id, a}
+  def test a, b do
+    c = a + b
+    sum_a = lookup a
+    sum_b = lookup b
+    sum_c = lookup c
 
-    receive do
-      sum_a ->
-        send parent_id, {self_id, b}
+    0 != rem(sum_c - sum_a - sum_b, 9)
+  end
 
-        receive do
-          sum_b ->
-            send parent_id, {self_id, a + b}
+  def lookup n do
 
-            receive do
-              sum_a_b ->
-                 0 != rem(sum_a_b - sum_a - sum_b, 9)
-            end
-        end
+    case :ets.lookup(:sums_cache, n) do
+      [{_, sum_n}] -> sum_n
+      [] ->
+        sum_n = sum n
+        :ets.insert(:sums_cache, {n, sum_n})
+        sum_n
     end
   end
 
@@ -86,13 +86,4 @@ defmodule Conjecture do
 
     d + sum r
   end
-
-  def lookup map, n do
-    if Map.has_key? map, n do
-      {map, map[n]}
-    else
-      sum_n = sum n
-      {Map.put(map, n, sum_n), sum_n}
-    end
-  end
 end