Mercurial > lbo > hg > juliaplay

changeset 4:00f57653128a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
jl/arrays: slow memoized LCSS implementation
author Lewin Bormann <lbo@spheniscida.de>
date Tue, 14 Feb 2023 23:41:19 +0100
parents c1db337c15be
children 1ae2e0c2ea18
files julia/arrays.jl julia/mergesort.jl python/sorting.py
diffstat 3 files changed, 26 insertions(+), 2 deletions(-) [+]
line wrap: on
line diff
--- a/julia/arrays.jl	Tue Feb 14 21:12:06 2023 +0100
+++ b/julia/arrays.jl	Tue Feb 14 23:41:19 2023 +0100
@@ -187,3 +187,28 @@
     end
     seq
 end
+
+function lcss_slow_memoize(a::AbstractArray{T}, b::AbstractArray{T};
+    d::Matrix=fill(0, length(a), length(b)),
+    c::Vector{Vector{T}}=Vector{Vector{T}}())::Vector{T} where {T}
+
+    if 0 == min(length(a), length(b))
+        return []
+    end
+    ck = (length(a), length(b))
+    if d[ck...] > 0
+        return c[d[ck...]]
+    end
+    nexts = [lcss_slow_memoize((@view a[i:end]), (@view b[j:end]); d=d, c=c) for i = 2:length(a) for j = 1:length(b)]
+    longest = isempty(nexts) ? [] : nexts[findmax(length, nexts)[2]]
+    if a[begin] == b[begin]
+        r = vcat([a[begin]], longest)
+        push!(c, r)
+        d[length(a),length(b)] = length(c)
+        return r
+    else
+        push!(c, longest)
+        d[length(a),length(b)] = length(c)
+        return longest
+    end
+end
--- a/julia/mergesort.jl	Tue Feb 14 21:12:06 2023 +0100
+++ b/julia/mergesort.jl	Tue Feb 14 23:41:19 2023 +0100
@@ -38,7 +38,7 @@
         a[1], a[2] = (a[1] < a[2] ? (a[1],a[2]) : (a[2],a[1]))
         return
     else
-        mid = div(1+length(a), 2)
+        mid = div(length(a), 2)
         mergesort!(@view a[begin:mid])
         mergesort!(@view a[mid+1:end])
         merge!(a, mid, aux)
--- a/python/sorting.py	Tue Feb 14 21:12:06 2023 +0100
+++ b/python/sorting.py	Tue Feb 14 23:41:19 2023 +0100
@@ -44,7 +44,6 @@
                 aux[i] = a[r]
                 r += 1
         i += 1
-    print(a[lo:hi+1], aux[0:i])
     a[lo:hi+1] = aux[0:i]
 
 def mergesort(a, lo=0, hi=-1, aux=None):