Re: Slow Loop (alternatives in lisp?)

[WJ]

> > Hello, I'm trying to imitate the behaviour of the pivot-table in excel
> > where you take a list of items and another list of their values and
> > you sum similar ones together (see toy example below). I have a list
> > of 30000 items and their associated values and in excel using a pivot-
> > table the computation is done instantaneously (less than 2 seconds)
> > while the procedure I wrote in lisp will take about 12 hours !(I give
> > an example of only 15 items below, this goes fast of course because
> > only 15 items, but the 30,000 will take an estimate of about 12 hours;
> > I never reached that far because around 5 hours I give up). Do you
> > know why? Is there a way to enhance the procedure and make it as fast
> > as the pivot table? Thanks
>
>
> ;; Tabulate like the pivot table.
> (time
> (let ((ls (vector "a" "b" "c" "b" "a" "f" "e" "g"
> "h" "k" "z" "k" "r" "u" "f"))
> (counter (vector 1 5 8 7 14 8 3 7 9 4 3 21 5 7 9))
> (i 0))
> (loop while (< i (length ls)) do
> (let ((j (+ i 1)))
> (loop while (< j (length ls)) do
> (when (and (equal (elt ls i) (elt ls j))
> (not (equal (elt ls j) 'indic)))
> (incf (elt counter i) (elt counter j))
> (setf (elt ls j) 'indic
> (elt counter j) 'indic))
> (incf j)))
> (incf i))
> (values (delete 'indic ls)
> (delete 'indic counter))))
>
> Real time: 0.009765 sec.
> Run time: 0.012 sec.
> Space: 102408 Bytes
> #("a" "b" "c" "f" "e" "g" "h" "k" "z" "r" "u") ;
> #(15 12 8 17 3 7 9 25 3 5 7)

Incredibly crude.

OCaml:

let ls = [|"aa";"b";"c";"b";"aa";"f";"e";"g";
"h";"k";"z";"k";"r";"u";"f"|]
and counter = [|1;5;8;7;14;8;3;7;9;4;3;21;5;7;9|]
and table = Hashtbl.create 99 ;;

Array.iteri
(fun i x -> Hashtbl.(replace table x
(counter.(i) + (try find table x with Not_found -> 0))))
ls ;;

Hashtbl.iter
(fun k v -> Printf.printf "%-3s %3d\n" (k ^ ":") v)
table ;;

h: 9
z: 3
b: 12
u: 7
r: 5
k: 25
e: 3
c: 8
g: 7
f: 17
aa: 15

In Forth?

--
Jewish drug dealers, child porn pushers, and slave traders are free
from prosecution in Israel. Israel does not consider these to be
crimes ... so long as the victims are non-Jews.
www.theoccidentalobserver.net/2009/08/the-culture-of-deceit/

[Julian Fondren]

OK, the CL takes ~12 hours on 30k values.

How much time does your code need on 30k values?
How much memory does it use?

The performance characteristics are 100% of the issue here. The
poster did not ask "How can this code be less crude."

[Paul Rubin]

Julian Fondren <ayr...@gmail.com> writes:
> OK, the CL takes ~12 hours on 30k values.
> How much time does your code need on 30k values?

The issue is that the CL used a crazy O(n**2) algorithm to do the
lookups. WJ's version, like the one he criticized, was also incredibly
crude, using a beautiful functional programming language to code what
someone once called "a pig trampling in a rose garden". But it used
a hash table and should be able to do 30k values in close to no time.

Here's my Haskell version:

import qualified Data.HashMap.Strict as M
import Distribution.Simple.Utils (ordNub)

ks = ["a","b","c","b","a","f","e","g","h","k","z","k","r","u","f"]
vs = [1,5,8,7,14,8,3,7,9,4,3,21,5,7,9]
mm = foldl (\m (k,v) -> M.insertWith (+) k v m) M.empty $ (zip ks vs)
main = print $ [(k,v) | k <- ordNub ks, let Just v = M.lookup k mm]

Output (linebreak inserted):

[("a",15),("b",12),("c",8),("f",17),("e",3),("g",7),("h",9),
("k",25),("z",3),("r",5),("u",7)]

It does 30k values in about 0.07 seconds on my laptop.

[dhoff...@gmail.com]

include FMS-SI.f
include FMS-SILib.f

hash-table t 1 t init

${ a b c b a f e g h k z k r u f }
i{ 1 5 8 7 14 8 3 7 9 4 3 21 5 7 9 }

: run { s c -- }
s size: 0 do
i s at: @: ( kaddr klen) 2dup t get:
if i c at: +
else i c at:
then ( kaddr klen val) -rot t insert:
loop ;

run
:noname ( node -- ) dup cr key@: p: space val@: . ; t iterate:
k 25
z 3
a 15
b 12
c 8
r 5
e 3
f 17
u 7
g 7
h 9 ok

30k values under 0.01 sec, VFX, 2.5 GHz i5 Mac

-Doug

[foxaudio...@gmail.com]

Very cool Doug. I see your example as what Forth is about.

WJ doesn't seem to get the fact that one does not program IN Forth.
One programs on top of Forth.

Your included libraries give you the functionality of the example
languages that WJ keeps thrusting upon us.
(along with his perfidious signatures)

With that new language you solve the problem. That's how Forth operates.

Not let's see WJ show us a simple device driver for a machine with
no OS or C compiler, in LISP or Ruby.

BF

[dhoff...@gmail.com]

On Wednesday, August 24, 2016 at 10:09:57 AM UTC-4, foxaudio...@gmail.com wrote:

> Very cool Doug. I see your example as what Forth is about.

> One programs on top of Forth.

> That's how Forth operates.

Thanks. Yes, I agree that is how to best use Forth.

I see objects as just one way to easily enhance the inherent usefulness.
The hash-table class was not difficult to assemble from other
classes (dynamically sizable arrays and strings) and seemed a good
fit for an object solution for other reasons - many key/value
nodes must be created.

Handling the hash collision cases was instructive.

-Doug

[Albert van der Horst]

In article <87bn0jq...@jester.gateway.pace.com>,

Could you add some brain damaged comment in the style
+ \ add the two items on the stack leaving one item
for us who don't know Haskell?

Groetjes Albert
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst