The APL Orchard

« first day (2543 days earlier) ← previous day next day → last day (104 days later) »

1:00 PM

Welcome to APL Quest, 2023-2! Today's quest is Put It In Reverse:

> Write a function that:
• takes a scalar or vector left argument
• takes a scalar or vector right argument
• returns a Boolean result that is the same shape as the right argument where 1's mark the ends of occurrences of the left argument in the right argument

Richard

⍷ _U_ ⌽
(1∘-∘≢⊣)⌽⍷

Adám

Hehe. For the uninitiated, _U_←{⍺←{⍵ ⋄ ⍺⍺} ⋄ ⍵⍵⍣¯1⊢(⍵⍵ ⍺)⍺⍺(⍵⍵ ⍵)}

Btw, you don't need the first ∘ there.

RubenVerg

I had ⌽⍤⍷⍥⌽, which is pretty much just Under in disguise

Adám

You don't need ⍤

RubenVerg

oh, right

Adám

1:02 PM

At the actual competition, someone submitted this little gem: {1-≢⍺}⌽⍷ which is the same algorithm as @Richard's second one, but hybrid explicit-tacit — and shorter for it.

Anyone wants to speculate on the relative performance of these two ways?

Richard

under is slowest probably

rotate is perhaps faster than mirroring twice

rabbitgrowth

I just realized I've never thought about what under does in the dyadic case

Adám

It is like Over.

So, I defined:

      _U_←{⍺←{⍵ ⋄ ⍺⍺} ⋄ ⍵⍵⍣¯1⊢(⍵⍵ ⍺)⍺⍺(⍵⍵ ⍵)}
      'cmpx'⎕CY'dfns'
      Under←⍷_U_⌽
      Minus←{1-≢⍺}⌽⍷
      Over←⌽⍷⍥⌽
      h←?1e6⍴10
      n←⍳5
      +/n⍷h
14

And then measured:

      cmpx'n Under h' 'n Minus h' 'n Over h'
  n Under h → 1.4E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  n Minus h → 1.3E¯3 | -12% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  n Over h  → 1.5E¯3 |  +2% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

Richard

Depends a lot on the size of the vector. Large vector mirroring might be faster , a lot of smal vectors shifting is faster ?

Adám

@Richard It isn't twice, but three times.

No, the important thing is the amount of data being change, as it all has to be rewritten no matter if we are reversing or rotating.

Assuming the left argument is small, its impact is negligible.

Richard

1:08 PM

ah, ok

Adám

But the huge right argument is likely to be 8, 16, 32, or even 64 times as much data as the equally large result.

Why?

Richard

bits versus characters

Silas

vs ints, but yes

Adám

Well, h was numbers here, but yes 1-byte numbers. Had they been bigger than 127 (I limited them to ≤ 10) then they would have been 2 bytes each.

In fact, they could even be 128 bits each, if they were complex or decimal floats.

RubenVerg

are complex decimal floats 256 bits, or do complex numbers always use float64's?

Adám

1:14 PM

For now, complex are always two float64s jammed together.

In general, people that need complex, don't need (that) much precision.

I've been experimenting a bit with larger arguments of larger types, but the performance result tends to be about the same. Once, I got:

      (h n)×←0J1
      cmpx'n Under h' 'n Minus h' 'n Over h'
  n Under h → 1.6E¯1 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  n Minus h → 1.3E¯1 | -23% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  n Over h  → 1.5E¯1 |  -8% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

rabbitgrowth

Why should the result be 0 with e.g. ,1 on the left and 1 on the right?

Adám

But I have my doubts about its validity. Under and Over should be completely equivalent, since the data processing drowns out the overhead.

@rabbitgrowth Because ,1 doesn't appear anywhere in 1.

Vectors contain scalars, but scalars do not contain vectors.

rabbitgrowth

I see, that makes sense

      1⍷1
1
      1⍷,1
1
      (,1)⍷1
0
      (,1)⍷,1
1

Adám

If you want homework, go investigate if empty arrays appear in other (empty) arrays. What if the types don't match? Can you infer a rule for how ⍷ works?

Richard

wow, just tried, how nice

Adám

1:24 PM

lol, I spent a lot of time discussing this with Roger Hui.

Richard

'⎕←(2 2 ⍴ 2) ⍷ 3 3 ⍴ 2'

Adám

The bot is long gone, but you can install this.

rabbitgrowth

Wouldn't you be unable to tell if ⍷ thinks an empty array appears in another empty array, since the result is also an empty array?

Richard

how many possibllities to fit a small cube in large one :)
+/,(2 2 2 ⍴ 2) ⍷ (3 3 3 ⍴ 2)

Adám

@rabbitgrowth Correct.

Anyway, have a look at ⍷ follies if this subject interests you.

You have a week until 2023-3: Caesar Salad!

RubenVerg

1:29 PM

oh, I remember this one, I had a nice solution but turned it quite ugly because I was forcing myself to make it tacit

Richard

next week!

rabbitgrowth

@Adám That looks interesting, will give it a read. Thanks!

3 hours later…

tosh

5:00 PM

I'm looking at Project Euler #8 with `k` but looking at it in general from an array language point of view and also in general

https://projecteuler.net/problem=8

I was wondering: is there an approach for solving that makes sense that is not the naive approach with a sliding window and doing all the products?

A few thoughts I had on it:

* every product that has a 0 in it goes to 0 so the calculation does not have to happen, and there are a lot of 13-item windows with at least one 0 in them
* if i split the string of numbers on all zeroes I get a bunch of strings that I can work on in parallel
* then there also is an approach of intead of a sliding window and doing all products to take 13, do the product, then move 1 further, divide by the digit that is no longer in the considered digits and multiply again by the new digit

Silas

5:54 PM

Another thought to avoid sliding windows is maybe reshape into matrix of shape n 13 and then dropping or rotating data so rows become the windows.

Shifting by multiply divide might be ok, but division is typically considered slow. Know there's a string ?search algorithm that follows similar idea to produce the hash though can't remember details

tosh

@Silas that's a great point @ reshaping, I still need to learn thinking like that, ty

LdBeth

One thing is you can check the sum instead of the product

then it is just adding and subtraction instead of doing division

for all a, b, c, d : Nat. a ≥ c AND b ≥ d IMPLIES a × b ≥ c × d

LdBeth

6:21 PM

Welp that doesn't work.

3 hours later…

Marshall

9:01 PM

@tosh There's a way to decompose any associative windowed operation into scans that take linear time, known as the van Herk/Gil-Werman algorithm in image processing. This article does something like it for min or max in q, but it overlaps the scans in a way that prevents it from working for other functions.

I did a tutorial that focuses on it in Singeli (jump to "Here, I wrote up a little prototype!"), and there's a version on bqncrate too.

tosh

9:45 PM

@Marshall ty for the pointer

« first day (2543 days earlier) ← previous day next day → last day (104 days later) »

all rooms