A little problem.

General APL language issues

A little problem.

Postby paulmansour on Fri Mar 24, 2017 4:54 pm

I would like to find the least (or most, same problem) frequently occurring item in a vector.

What is the simplest (don't need speed) for this?

My first conventional solution is:

      {↑({⍵=⌊/⍵}+/⍵∘.=⍵)/⍵}3 3 3 10 4 4 4 4 10


I've tried the key operator, but that gives me an even lengthier solution, though I am pretty sure I still don't fully understand key!

Is there a better way to do this?

Paul
paulmansour
 
Posts: 343
Joined: Fri Oct 03, 2008 4:14 pm

Re: A little problem.

Postby gil on Sat Mar 25, 2017 6:07 am

The key operator is the first thing I would have tried. Even if it is a longer expression, it seems the natural solution to the problem. Two things to take into account (apart from speed):

  1. The key operator approach works on a vector of any items where your solution requires scalars.
  2. More importantly perhaps is the amount of memory required to execute (if you work on large vectors).


      k←{↑{⍺⊃⍨⍵⍳⌊/⍵}/↓⍉{⍺,≢⍵}⌸⍵}
t←{↑({⍵=⌊/⍵}+/⍵∘.=⍵)/⍵}
v←1e4(?⍴)100
]runtime "k v" "t v" -compare

k v → 3.1E¯5 | 0%
t v → 1.1E¯1 | +363400% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
v←1e5(?⍴)100
t v
WS FULL
t[0] t←{↑({⍵=⌊/⍵}+/∘.=⍨⍵)/⍵}

k v
45
gil
 
Posts: 68
Joined: Mon Feb 15, 2010 12:42 am

Re: A little problem.

Postby Veli-Matti on Mon Mar 27, 2017 7:29 am

I agree with gil here: Key operator is really superior for these kinds of solutions. But I couldn't help looking at Paul's first attempt, and try to speed it up a little bit:
      t2←{({⍵⍳⌊/⍵}+/u∘.=⍵)⊃u←∪⍵}
v←1e4(?⍴)100
]runtime "t2 v" "t v" -compare

t2 v → 9.7E¯4 | 0%
t v → 1.1E¯1 | +11525% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

v←1e5(?⍴)100
]runtime "k v" "t2 v" -compare

k v → 1.8E¯4 | 0% ⎕
t2 v → 1.1E¯2 | +6040% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕


My 5c
-wm
Veli-Matti
 
Posts: 56
Joined: Sat Nov 28, 2009 3:12 pm

Re: A little problem.

Postby Phil Last on Mon Mar 27, 2017 10:04 am

Comparing Gil's answer with the examples in the Help for ⌸ I wonder why the two expressions
      {⍺,≢⍵}⌸
{⍺(≢⍵)}⌸
produce identical results as those shown on the left below. It seems to me that the second should involve additional enclosure of the item as the two expressions
      {⍺(≢⍵)}
{(⊂⍺),≢⍵}
are functionally identical but produce the left and right outputs respectively
      z
bravo charlie delta delta alpha bravo alpha charlie delta bravo
┌───────┬─┐ ┌─────────┬─┐
│bravo │3│ │┌─────┐ │3│
├───────┼─┤ ││bravo│ │ │
│charlie│2│ │└─────┘ │ │
├───────┼─┤ ├─────────┼─┤
│delta │3│ │┌───────┐│2│
├───────┼─┤ ││charlie││ │
│alpha │2│ │└───────┘│ │
└───────┴─┘ ├─────────┼─┤
│┌─────┐ │3│
││delta│ │ │
│└─────┘ │ │
├─────────┼─┤
│┌─────┐ │2│
││alpha│ │ │
│└─────┘ │ │
└─────────┴─┘
could it be something to do with idiom recognition or special cases?
User avatar
Phil Last
 
Posts: 557
Joined: Thu Jun 18, 2009 6:29 pm

Re: A little problem.

Postby paulmansour on Mon Mar 27, 2017 2:38 pm

Phil, one of the reasons I don't fully understand key yet is exactly that.

I think (I assume naively) that I can do things, anything I want, to alpha and omega inside the braces. But some things work, and somethings don't.
paulmansour
 
Posts: 343
Joined: Fri Oct 03, 2008 4:14 pm

Re: A little problem.

Postby Phil Last on Mon Mar 27, 2017 6:06 pm

Within the operand the rank of alpha is always one less than that of the keys - whether they be right the argument to the monadic derived function or the left in the dyad. Indeed alpha ia always a major cell of the keys. If keys form a matrix alpha is a string. No disclosure is involved in forming it. So if keys form a nested list of strings then alpha is an enclosed string.
User avatar
Phil Last
 
Posts: 557
Joined: Thu Jun 18, 2009 6:29 pm

Re: A little problem.

Postby Phil Last on Mon Mar 27, 2017 6:14 pm

p.s. Gil's solution remains correct. The problem I highlighted is in the "alternative" given in the help for ⌸ and affects only non-simple arguments.
User avatar
Phil Last
 
Posts: 557
Joined: Thu Jun 18, 2009 6:29 pm

Re: A little problem.

Postby Roger|Dyalog on Mon Mar 27, 2017 6:43 pm

All expressions executed in Dyalog 15.0.27982 Win64 Unicode.

There is indeed "idiom recognition" going on in the key operator, but it's not supposed to change the result. When in doubt, prepend one or more ⊢ onto the operand function to defeat the idiom recognition, and if it gives a different answer then there is a bug. (You can defeat the idiom recognition in other ways, such as saying (⍵) instead of ⍵.)

Code: Select all
      ]box on

      z←{1↓¨(' '=⍵)⊂⍵}' bravo charlie delta delta alpha bravo alpha charlie delta bravo'
      z
┌─────┬───────┬─────┬─────┬─────┬─────┬─────┬───────┬─────┬─────┐
│bravo│charlie│delta│delta│alpha│bravo│alpha│charlie│delta│bravo│
└─────┴───────┴─────┴─────┴─────┴─────┴─────┴───────┴─────┴─────┘

      ({⍺,≢⍵}⌸ {⍺⍵} {⊢⍺,≢⍵}⌸) z
┌───────────┬───────────┐
│┌───────┬─┐│┌───────┬─┐│
││bravo  │3│││bravo  │3││
│├───────┼─┤│├───────┼─┤│
││charlie│2│││charlie│2││
│├───────┼─┤│├───────┼─┤│
││delta  │3│││delta  │3││
│├───────┼─┤│├───────┼─┤│
││alpha  │2│││alpha  │2││
│└───────┴─┘│└───────┴─┘│
└───────────┴───────────┘
       ({⍺(≢⍵)}⌸ {⍺⍵} {⊢⍺(≢⍵)}⌸) z   ⍝ bug!  (left hand answer is wrong)
┌───────────┬─────────────┐
│┌───────┬─┐│┌─────────┬─┐│
││bravo  │3│││┌─────┐  │3││
│├───────┼─┤│││bravo│  │ ││
││charlie│2│││└─────┘  │ ││
│├───────┼─┤│├─────────┼─┤│
││delta  │3│││┌───────┐│2││
│├───────┼─┤│││charlie││ ││
││alpha  │2│││└───────┘│ ││
│└───────┴─┘│├─────────┼─┤│
│           ││┌─────┐  │3││
│           │││delta│  │ ││
│           ││└─────┘  │ ││
│           │├─────────┼─┤│
│           ││┌─────┐  │2││
│           │││alpha│  │ ││
│           ││└─────┘  │ ││
│           │└─────────┴─┘│
└───────────┴─────────────┘

      ⍝ for some arguments, the bug makes no difference
      ({⍺(≢⍵)}⌸ {⍺⍵} {⊢⍺(≢⍵)}⌸) z⍳z 
┌───┬───┐
│0 3│0 3│
│1 2│1 2│
│2 3│2 3│
│4 2│4 2│
└───┴───┘

      ({(⊂⍺),≢⍵}⌸ {⍺⍵} {⊢(⊂⍺),≢⍵}⌸) z
┌─────────────┬─────────────┐
│┌─────────┬─┐│┌─────────┬─┐│
││┌─────┐  │3│││┌─────┐  │3││
│││bravo│  │ ││││bravo│  │ ││
││└─────┘  │ │││└─────┘  │ ││
│├─────────┼─┤│├─────────┼─┤│
││┌───────┐│2│││┌───────┐│2││
│││charlie││ ││││charlie││ ││
││└───────┘│ │││└───────┘│ ││
│├─────────┼─┤│├─────────┼─┤│
││┌─────┐  │3│││┌─────┐  │3││
│││delta│  │ ││││delta│  │ ││
││└─────┘  │ │││└─────┘  │ ││
│├─────────┼─┤│├─────────┼─┤│
││┌─────┐  │2│││┌─────┐  │2││
│││alpha│  │ ││││alpha│  │ ││
││└─────┘  │ │││└─────┘  │ ││
│└─────────┴─┘│└─────────┴─┘│
└─────────────┴─────────────┘
Roger|Dyalog
 
Posts: 215
Joined: Thu Jul 28, 2011 10:53 am

Re: A little problem.

Postby gil on Tue Mar 28, 2017 9:11 am

I have seen similar issues with the key operator that I have reported and have since been fixed, but it took me some time to report in the first place as I was unsure of my own understanding of key.

These days I am using it quite often with complex operands and it works very well.
gil
 
Posts: 68
Joined: Mon Feb 15, 2010 12:42 am

Re: A little problem.

Postby paulmansour on Tue Mar 28, 2017 1:21 pm

I do need to spend more time with key.

I do like this little idiom that I recently used:

      ⊣⌸cm


for the getting the unique rows of a char mat.

I don't think it is any faster than other techniques as Roger has improved all those as well, but it is terse.
paulmansour
 
Posts: 343
Joined: Fri Oct 03, 2008 4:14 pm

Next

Return to Language

Who is online

Users browsing this forum: No registered users and 1 guest