Nub Sieve: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
m (Text replacement - "<source" to "<syntaxhighlight")
Tags: Mobile edit Mobile web edit
(7 intermediate revisions by 3 users not shown)
Line 4: Line 4:


Nub Sieve returns a 1 for each [[major cell]] in the argument that is unique, and a 0 if it's a duplicate:
Nub Sieve returns a 1 for each [[major cell]] in the argument that is unique, and a 0 if it's a duplicate:
<source lang=apl>
<syntaxhighlight lang=apl>
       ≠ 'Hello, World'
       ≠ 'Hello, World'
1 1 1 0 1 1 1 1 0 1 0 1
1 1 1 0 1 1 1 1 0 1 0 1
</source>
</syntaxhighlight>
Using [[Key]] we can see which elements were labelled unique and duplicate:
Using [[Key]] we can see which elements were labelled unique and duplicate:
<source lang=apl>
<syntaxhighlight lang=apl>
       (≠ {⍺⍵}⌸ ⊢) 'Hello, World!'
       (≠ {⍺⍵}⌸ ⊢) 'Hello, World!'
┌─┬──────────┐
┌─┬──────────┐
Line 16: Line 16:
│0│lol      │
│0│lol      │
└─┴──────────┘
└─┴──────────┘
</source>
</syntaxhighlight>
{{Works in|[[Dyalog APL]]}}
{{Works in|[[Dyalog APL]]}}
Nub Sieve can be used to filter a [[matrix]] by some of its columns, or find its unique rows.
Nub Sieve can be used to filter a [[matrix]] by some of its columns, or find its unique rows.
<source lang=apl>
<syntaxhighlight lang=apl>
       a ← (⍳6) ∘.! 3+⍳3
       ⎕← a ← (⍳6) ∘.! 3+⍳3
4  5  6
4  5  6
6 10 15
6 10 15
Line 36: Line 36:
       ∧⌿ ≠ a                  ⍝ All of them.
       ∧⌿ ≠ a                  ⍝ All of them.
1
1
</source>
</syntaxhighlight>


== Description ==
== Description ==


While the Nub Sieve satisfies <source lang=apl inline>(∪A) ≡ (≠A)⌿A</source>, this criterion is not a full definition because it doesn't specify which cell should be selected from among duplicates. The Nub Sieve should indicate cells by following the same procedure as [[Unique]], that is, by considering all [[major cells]] in order and indicating those which do not match any cell already indicated.
While the Nub Sieve satisfies <syntaxhighlight lang=apl inline>(∪A) ≡ (≠A)⌿A</syntaxhighlight>, this criterion is not a full definition because it doesn't specify which cell should be selected from among duplicates. The Nub Sieve should indicate cells by following the same procedure as [[Unique]], that is, by considering all [[major cells]] in order and indicating those which do not match any cell already indicated.


Formally, let <source lang=apl inline>x</source> be an array of [[rank]] at least 1. The Nub Sieve <source lang=apl inline>m</source> of <source lang=apl inline>x</source> is the array which satisfies the following two axioms (with <source lang=apl inline>⎕IO←0</source>) for all <source lang=apl inline>i</source> in <source lang=apl inline>⍳≢x</source>.
Formally, let <syntaxhighlight lang=apl inline>x</syntaxhighlight> be an array of [[rank]] at least 1. The Nub Sieve <syntaxhighlight lang=apl inline>m</syntaxhighlight> of <syntaxhighlight lang=apl inline>x</syntaxhighlight> is the array which satisfies the following two axioms (with <syntaxhighlight lang=apl inline>⎕IO←0</syntaxhighlight>) for all <syntaxhighlight lang=apl inline>i</syntaxhighlight> in <syntaxhighlight lang=apl inline>⍳≢x</syntaxhighlight>.
<source lang=apl>
<syntaxhighlight lang=apl>
notin ← (⍳=≢⍤⊣)⍨              ⍝ Extension of (~∊) to rank >1
notin ← (⍳=≢⍤⊣)⍨              ⍝ Extension of (~∊) to rank >1
(⍴m) ≡ ,≢x                    ⍝ Shape of m
(⍴m) ≡ ,≢x                    ⍝ Shape of m
m[i] ≡ (i⌷x) notin m⌿⍥(i∘↑)x  ⍝ Items of m
m[i] ≡ (i⌷x) notin m⌿⍥(i∘↑)x  ⍝ Items of m
</source>
</syntaxhighlight>
The search <source lang=apl inline>⍳</source> in <source lang=apl inline>notin</source> depends on <source lang=apl inline>⎕CT</source> and so the Nub Sieve depends on [[comparison tolerance]]. The two comparisons <source lang=apl inline>≡</source> are taken to be independent of <source lang=apl inline>⎕CT</source>; <source lang=apl inline>m</source> is exactly [[Boolean]].
The search <syntaxhighlight lang=apl inline>⍳</syntaxhighlight> in <syntaxhighlight lang=apl inline>notin</syntaxhighlight> depends on <syntaxhighlight lang=apl inline>⎕CT</syntaxhighlight> and so the Nub Sieve depends on [[comparison tolerance]]. The two comparisons <syntaxhighlight lang=apl inline>≡</syntaxhighlight> are taken to be independent of <syntaxhighlight lang=apl inline>⎕CT</syntaxhighlight>; <syntaxhighlight lang=apl inline>m</syntaxhighlight> is exactly [[Boolean]].


When the argument is a [[scalar]], Unique returns its [[ravel]], an instance of [[scalar rank extension]]. Correspondingly, Nub Sieve of a scalar is defined to be the [[singleton]] [[vector]] <source lang=apl inline>,1</source>.
When the argument is a [[scalar]], Unique returns its [[ravel]], an instance of [[scalar rank extension]]. Correspondingly, Nub Sieve of a scalar is defined to be the [[singleton]] [[vector]] <syntaxhighlight lang=apl inline>,1</syntaxhighlight>.


=== APL models ===
=== APL models ===


An implementation based on the above definition follows:
An implementation based on the above definition follows:
<source lang=apl>
<syntaxhighlight lang=apl>
UniqueMask ← {
UniqueMask ← {
     ⎕IO←0
     ⎕IO←0
Line 63: Line 63:
     m ⊣ {m,←(⍵⌷x) notin m⌿⍵↑x}¨ ⍳≢x
     m ⊣ {m,←(⍵⌷x) notin m⌿⍵↑x}¨ ⍳≢x
}
}
</source>
</syntaxhighlight>


The Unique Mask can also be derived from the [[self-classify]] or index-in-nub function <source lang=apl inline>(∪⍳1/⊢)</source>. The following two implementations arise from the fact that 1s in the Unique Mask appear exactly when a new value appears in the self-classify.
The Unique Mask can also be derived from the [[self-classify]] or index-in-nub function <syntaxhighlight lang=apl inline>(∪⍳1/⊢)</syntaxhighlight>. The following two implementations arise from the fact that 1s in the Unique Mask appear exactly when a new value appears in the self-classify.
<source lang=apl>
<syntaxhighlight lang=apl>
(⍳⍤≢=⍳⍨)⍤(∪⍳1/⊢)      ⍝ Pre-correction of "bad meme" (⍳≢⍵)=⍵⍳⍵
(⍳⍤≢=⍳⍨)⍤(∪⍳1/⊢)      ⍝ Pre-correction of "bad meme" (⍳≢⍵)=⍵⍳⍵
(2≠/¯1,⌈\)⍤(∪⍳1/⊢)    ⍝ Optimised self-classify → Nub Sieve conversion
(2≠/¯1,⌈\)⍤(∪⍳1/⊢)    ⍝ Optimised self-classify → Nub Sieve conversion
</source>
</syntaxhighlight>


== Use cases ==
== Use cases ==


One use of Nub Sieve is to remove duplicates from one array and also corresponding arrays, which may contain attributes of cells in that array. The statement <source lang=apl inline>a b⌿⍨←⊂≠a</source> filters <source lang=apl inline>a</source> and corresponding <source lang=apl inline>b</source> in this way. A minor variation is to filter an array based on only one attribute of its major cells: <source lang=apl inline>a⌿⍨≠3⌷⍤1⊢a</source> gets the rows of matrix <source lang=apl inline>a</source> which introduce new values in column 3. Code like this might be used to compute, for example, the first Nobel prize winner from each country given a list of winners sorted by date. While [[Key]] can be used for such computations (for instance <source lang=apl inline>{⊣⌿⍵}⌸⍨</source> in place of <source lang=apl inline>⌿⍨∘≠</source>), the Nub Sieve is slightly simpler and considerably faster in most implementations: Key recomputes uniqueness information for its left argument each time.
One use of Nub Sieve is to remove duplicates from one array and also corresponding arrays, which may contain attributes of cells in that array. The statement <syntaxhighlight lang=apl inline>a b⌿⍨←⊂≠a</syntaxhighlight> filters <syntaxhighlight lang=apl inline>a</syntaxhighlight> and corresponding <syntaxhighlight lang=apl inline>b</syntaxhighlight> in this way. A minor variation is to filter an array based on only one attribute of its major cells: <syntaxhighlight lang=apl inline>a⌿⍨≠3⌷⍤1⊢a</syntaxhighlight> gets the rows of matrix <syntaxhighlight lang=apl inline>a</syntaxhighlight> which introduce new values in column 3. Code like this might be used to compute, for example, the first Nobel prize winner from each country given a list of winners sorted by date. While [[Key]] can be used for such computations (for instance <syntaxhighlight lang=apl inline>{⊣⌿⍵}⌸⍨</syntaxhighlight> in place of <syntaxhighlight lang=apl inline>⌿⍨∘≠</syntaxhighlight>), the Nub Sieve is slightly simpler and considerably faster in most implementations: Key recomputes uniqueness information for its left argument each time.


The combination with [[Indices]] <source lang=apl inline>⍸≠A</source> finds the [[Index|indices]] of unique elements of an array, which might be useful to iterate through these elements without extracting them into a separate array (it could even be used to modify them in their original positions). Again, this combination can be computed with Key, using <source lang=apl inline>{⊣⌿⍵}⌸A</source>, but the Nub Sieve implementation is more obvious and readable ("Where is A unique?") and much faster (while the particular Key operand <source lang=apl inline>{⊣⌿⍵}</source> could be sped up, the function can be written in many ways, and recognising all of them is difficult).
The combination with [[Indices]] <syntaxhighlight lang=apl inline>⍸≠A</syntaxhighlight> finds the [[Index|indices]] of unique elements of an array, which might be useful to iterate through these elements without extracting them into a separate array (it could even be used to modify them in their original positions). Again, this combination can be computed with Key, using <syntaxhighlight lang=apl inline>{⊣⌿⍵}⌸A</syntaxhighlight>, but the Nub Sieve implementation is more obvious and readable ("Where is A unique?") and much faster (while the particular Key operand <syntaxhighlight lang=apl inline>{⊣⌿⍵}</syntaxhighlight> could be sped up, the function can be written in many ways, and recognising all of them is difficult).


Nub Sieve can be used to find all elements of an array that ''are'' duplicates, by inverting the result. This is useful in order to see or manipulate what is being discarded by Unique. A program might print duplicate values before discarding them:
Nub Sieve can be used to find all elements of an array that ''are'' duplicates, by inverting the result. This is useful in order to see or manipulate what is being discarded by Unique. A program might print duplicate values before discarding them:
<source lang=apl>
<syntaxhighlight lang=apl>
m←≠vals
m←≠vals
⎕←'Discarding duplicate elements: ',⍕(~m)⌿vals
⎕←'Discarding duplicate elements: ',⍕(~m)⌿vals
vals⌿⍨←m
vals⌿⍨←m
</source>
</syntaxhighlight>
The same method can be used with a sieve derived from a function of an array rather than the array itself, for instance to keep only one namespace with a given <source lang=apl inline>id</source> property but retain the discarded ones for future use.
The same method can be used with a sieve derived from a function of an array rather than the array itself, for instance to keep only one namespace with a given <syntaxhighlight lang=apl inline>id</syntaxhighlight> property but retain the discarded ones for future use.


== History ==
== History ==
Line 89: Line 89:
:''See also [[Unique#History]].''
:''See also [[Unique#History]].''


Nubsieve (<source lang=apl inline>≠</source>) first appeared in [[A Dictionary of APL]] in 1987, and was eventually added to [[SHARP APL]]. It appears [https://code.jsoftware.com/wiki/Vocabulary/tildeco in J] as <source lang=j inline>~:</source> or Nub Sieve. It is also included in [[Dyalog APL 18.0]], slated for release in 2020.
In [[A Programming Language]], the ''forward set selector'' <math>\sigma/\mathbf{v}</math> is a special notation indicating the nub sieve of <math>\mathbf{v}</math>, so that unique elements are found with a [[Compress]]ion <math>(\sigma/\mathbf{v})/\mathbf{v}</math>.
 
The function Nubsieve (<syntaxhighlight lang=apl inline>≠</syntaxhighlight>) first appeared in [[A Dictionary of APL]] in 1987, and was eventually added to [[SHARP APL]]. It appears [https://code.jsoftware.com/wiki/Vocabulary/tildeco in J] as <syntaxhighlight lang=j inline>~:</syntaxhighlight> or Nub Sieve. It is also included in [[Dyalog APL 18.0]], released June 2020.


== External links ==
== External links ==
Line 95: Line 97:
=== Documentation ===
=== Documentation ===


* [http://help.dyalog.com/18.0/#Language/Primitive%20Functions/Unique%20Mask.htm Dyalog]
* [https://help.dyalog.com/18.0/#Language/Primitive%20Functions/Unique%20Mask.htm Dyalog]
* J [https://www.jsoftware.com/help/dictionary/d222.htm Dictionary], [https://code.jsoftware.com/wiki/Vocabulary/tildeco NuVoc] (as <source lang=j inline>~:</source>)
* J [https://www.jsoftware.com/help/dictionary/d222.htm Dictionary], [https://code.jsoftware.com/wiki/Vocabulary/tildeco NuVoc] (as <syntaxhighlight lang=j inline>~:</syntaxhighlight>)
* [https://mlochbaum.github.io/BQN/doc/selfcmp.html#mark-firsts BQN] (as <code>∊</code>)


{{APL built-ins}}[[Category:Primitive functions]][[Category:Set functions]]
{{APL built-ins}}[[Category:Primitive functions]][[Category:Set functions]]

Revision as of 22:07, 10 September 2022

Nub Sieve (), Nubsieve, or Unique Mask, is a monadic function that returns a Boolean vector indicating which major cells of its argument would be included in the result of Unique (Nub). More precisely, it indicates all cells which do not match any earlier indicated cell. The Nub Sieve is more informative than Unique because it encodes not only which cells are unique but where they appear in the argument. This means it can be used for tasks such as filtering secondary arrays and working with duplicates that are difficult to do with Unique and slow to compute with Key.

Examples

Nub Sieve returns a 1 for each major cell in the argument that is unique, and a 0 if it's a duplicate:

      ≠ 'Hello, World'
1 1 1 0 1 1 1 1 0 1 0 1

Using Key we can see which elements were labelled unique and duplicate:

      (≠ {⍺⍵}⌸ ⊢) 'Hello, World!'
┌─┬──────────┐
│1│Helo, Wrd!│
├─┼──────────┤
│0│lol       │
└─┴──────────┘
Works in: Dyalog APL

Nub Sieve can be used to filter a matrix by some of its columns, or find its unique rows.

      ⎕← a ← (⍳6) ∘.! 3+⍳3
4  5  6
6 10 15
4 10 20
1  5 15
0  1  6
0  0  1
      (≠1↑⍤1⊢a) ⌿ a           ⍝ Keep only one row for each first column value
4  5  6
6 10 15
1  5 15
0  1  6
      ≠ a                     ⍝ Which entire rows are unique?
1 1 1 1 1 1
      ∧⌿ ≠ a                  ⍝ All of them.
1

Description

While the Nub Sieve satisfies (∪A) ≡ (≠A)⌿A, this criterion is not a full definition because it doesn't specify which cell should be selected from among duplicates. The Nub Sieve should indicate cells by following the same procedure as Unique, that is, by considering all major cells in order and indicating those which do not match any cell already indicated.

Formally, let x be an array of rank at least 1. The Nub Sieve m of x is the array which satisfies the following two axioms (with ⎕IO←0) for all i in ⍳≢x.

notin ← (⍳=≢⍤⊣)⍨               ⍝ Extension of (~∊) to rank >1
(⍴m) ≡ ,≢x                     ⍝ Shape of m
m[i] ≡ (i⌷x) notin m⌿⍥(i∘↑)x   ⍝ Items of m

The search in notin depends on ⎕CT and so the Nub Sieve depends on comparison tolerance. The two comparisons are taken to be independent of ⎕CT; m is exactly Boolean.

When the argument is a scalar, Unique returns its ravel, an instance of scalar rank extension. Correspondingly, Nub Sieve of a scalar is defined to be the singleton vector ,1.

APL models

An implementation based on the above definition follows:

UniqueMask ← {
    ⎕IO←0
    notin ← (⍳=≢⍤⊣)⍨
    x ← 1/⍵                          ⍝ Treat scalar as vector
    m ← ⍬                            ⍝ Initial mask
    m ⊣ {m,←(⍵⌷x) notin m⌿⍵↑x}¨ ⍳≢x
}

The Unique Mask can also be derived from the self-classify or index-in-nub function (∪⍳1/⊢). The following two implementations arise from the fact that 1s in the Unique Mask appear exactly when a new value appears in the self-classify.

(⍳⍤≢=⍳⍨)⍤(∪⍳1/⊢)      ⍝ Pre-correction of "bad meme" (⍳≢⍵)=⍵⍳⍵
(2≠/¯1,⌈\)⍤(∪⍳1/⊢)    ⍝ Optimised self-classify → Nub Sieve conversion

Use cases

One use of Nub Sieve is to remove duplicates from one array and also corresponding arrays, which may contain attributes of cells in that array. The statement a b⌿⍨←⊂≠a filters a and corresponding b in this way. A minor variation is to filter an array based on only one attribute of its major cells: a⌿⍨≠3⌷⍤1⊢a gets the rows of matrix a which introduce new values in column 3. Code like this might be used to compute, for example, the first Nobel prize winner from each country given a list of winners sorted by date. While Key can be used for such computations (for instance {⊣⌿⍵}⌸⍨ in place of ⌿⍨∘≠), the Nub Sieve is slightly simpler and considerably faster in most implementations: Key recomputes uniqueness information for its left argument each time.

The combination with Indices ⍸≠A finds the indices of unique elements of an array, which might be useful to iterate through these elements without extracting them into a separate array (it could even be used to modify them in their original positions). Again, this combination can be computed with Key, using {⊣⌿⍵}⌸A, but the Nub Sieve implementation is more obvious and readable ("Where is A unique?") and much faster (while the particular Key operand {⊣⌿⍵} could be sped up, the function can be written in many ways, and recognising all of them is difficult).

Nub Sieve can be used to find all elements of an array that are duplicates, by inverting the result. This is useful in order to see or manipulate what is being discarded by Unique. A program might print duplicate values before discarding them:

m←≠vals
⎕←'Discarding duplicate elements: ',⍕(~m)⌿vals
vals⌿⍨←m

The same method can be used with a sieve derived from a function of an array rather than the array itself, for instance to keep only one namespace with a given id property but retain the discarded ones for future use.

History

See also Unique#History.

In A Programming Language, the forward set selector is a special notation indicating the nub sieve of , so that unique elements are found with a Compression .

The function Nubsieve () first appeared in A Dictionary of APL in 1987, and was eventually added to SHARP APL. It appears in J as ~: or Nub Sieve. It is also included in Dyalog APL 18.0, released June 2020.

External links

Documentation


APL built-ins [edit]
Primitives (Timeline) Functions
Scalar
Monadic ConjugateNegateSignumReciprocalMagnitudeExponentialNatural LogarithmFloorCeilingFactorialNotPi TimesRollTypeImaginarySquare Root
Dyadic AddSubtractTimesDivideResiduePowerLogarithmMinimumMaximumBinomialComparison functionsBoolean functions (And, Or, Nand, Nor) ∙ GCDLCMCircularComplexRoot
Non-Scalar
Structural ShapeReshapeTallyDepthRavelEnlistTableCatenateReverseRotateTransposeRazeMixSplitEncloseNestCut (K)PairLinkPartitioned EnclosePartition
Selection FirstPickTakeDropUniqueIdentityStopSelectReplicateExpandSet functions (IntersectionUnionWithout) ∙ Bracket indexingIndexCartesian ProductSort
Selector Index generatorGradeIndex OfInterval IndexIndicesDealPrefix and suffix vectors
Computational MatchNot MatchMembershipFindNub SieveEncodeDecodeMatrix InverseMatrix DivideFormatExecuteMaterialiseRange
Operators Monadic EachCommuteConstantReplicateExpandReduceWindowed ReduceScanOuter ProductKeyI-BeamSpawnFunction axis
Dyadic BindCompositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner ProductDeterminantPowerAtUnderRankDepthVariantStencilCutDirect definition (operator)
Quad names Index originComparison toleranceMigration levelAtomic vector