A little problem.

[paulmansour]

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

[gil]

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

[Veli-Matti]

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

[Phil Last]

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?

[paulmansour]

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.

[Phil Last]

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.

[Phil Last]

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.

[Roger|Dyalog]

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│  │ ││
││└─────┘  │ │││└─────┘  │ ││
│└─────────┴─┘│└─────────┴─┘│
└─────────────┴─────────────┘


[gil]

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.

[paulmansour]

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.