[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Time/size complexity of APL algorithms

From: Elias Mårtenson
Subject: Time/size complexity of APL algorithms
Date: Mon, 17 Feb 2020 15:11:03 +0800

First of all, I hope Jürgen is OK with me posting about an APL-related topic that doesn't have anything directly to do with GNU APL. I'm doing this because this is the best place to find like-minded people. Sorry about that.

The discussions around paralellisation let me to start thinking about ways to improve this in APL, and I was wondering if it would be possible to make a purely immutable APL implementation. If so, it would, at least in theory, bepossble to defer a lot of computations until a result is actually requested. This would be a lot easier to parallelise.

I hacked together a prototype which does this very thing. I've implemented some of the APL primitives that allows me to test different ideas.

Now, for my question: Do you have any examples of APL algorithms that are very slow, or uses a lot of memory? I want to know if my ideas actually work in practice.

If you are curious: Certain things a good. For example: +/⍳N runs in constant space. Others are not good. For example, debugging is a nightmare since evaluation can happen at any time (or not at all, or multiple times).

Also, x[N]←V is invalid code since arrays cannot be modified.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]