4,494
edits
Interval Index: Difference between revisions
Jump to navigation
Jump to search
m
Text replacement - " ⊢( *[^∘])" to " ⎕←$1"
(Created page with "{{Built-in|Interval Index|⍸}}, or '''Bins''' (<source lang=apl inline>⍋</source>) in A+, is a primitive search function which locates cell...") |
m (Text replacement - " ⊢( *[^∘])" to " ⎕←$1") |
||
| (4 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{Built-in|Interval Index|⍸}}, or '''Bins''' (<source lang=apl inline>⍋</source>) in [[A+]], is a [[primitive function|primitive]] [[search function]] which locates [[cell]]s of its right [[argument]] relative to cells of a [[sorted]] left argument. Like searching for the right page for a word in a dictionary, knowing the first word on each page, Interval Index finds for each cell (word to search for) an [[index]] (page number) in the left argument (dictionary) so that the target cell is between the [[major cell]] at that index (first word on the page) and the major cell at the following index (first word on the next page). In general computer science, this problem is known as a '''predecessor search''' (see [[wikipedia:predecessor problem|predecessor problem]]), since it searches for the predecessor—entry immediately | {{Built-in|Interval Index|⍸}}, or '''Bins''' (<source lang=apl inline>⍋</source>) in [[A+]], is a [[primitive function|primitive]] [[search function]] which locates [[cell]]s of its right [[argument]] relative to cells of a [[sorted]] left argument. Like searching for the right page for a word in a dictionary, knowing the first word on each page, Interval Index finds for each cell (word to search for) an [[index]] (page number) in the left argument (dictionary) so that the target cell is between the [[major cell]] at that index (first word on the page) and the major cell at the following index (first word on the next page). In general computer science, this problem is known as a '''predecessor search''' (see [[wikipedia:predecessor problem|predecessor problem]]), since it searches for the predecessor—entry immediately preceding—of an array, but may be referred to by the name of a common technique used to solve it, the [[wikipedia:binary search|binary search]]. Interval Index may also be considered a way to perform [[wikipedia:data binning|data binning]]. | ||
Like [[Grade]], Interval Index relies on [[array ordering]], but is not subject to [[comparison tolerance]]. Its result depends on [[index origin]] when present. | Like [[Grade]], Interval Index relies on [[array ordering]], but is not subject to [[comparison tolerance]]. Its result depends on [[index origin]] when present. | ||
| Line 31: | Line 31: | ||
You can use Interval Index with [[Matrix|matrices]] and other high-[[rank]] arrays as well, in order to compare cells of those array. For example, if you took several pictures at a programming conference, and have the conference schedule as well as image timestamps, then you can find which talk each picture is of. Use the start time for each talk as the left argument, and the timestamp for each picture in the right argument. | You can use Interval Index with [[Matrix|matrices]] and other high-[[rank]] arrays as well, in order to compare cells of those array. For example, if you took several pictures at a programming conference, and have the conference schedule as well as image timestamps, then you can find which talk each picture is of. Use the start time for each talk as the left argument, and the timestamp for each picture in the right argument. | ||
<source lang=apl> | <source lang=apl> | ||
⎕←schedule ← 4 2 ⍴ 1 00 1 45 2 15 2 30 | |||
1 0 | 1 0 | ||
1 45 | 1 45 | ||
2 15 | 2 15 | ||
2 30 | 2 30 | ||
⎕←timestamps ← 3 2 ⍴ 1 16 2 02 1 50 | |||
1 16 | 1 16 | ||
2 2 | 2 2 | ||
| Line 48: | Line 48: | ||
Like [[Index Of]], Interval Index splits its right argument into [[cell]]s with the same rank as the [[major cell]]s of the left argument (in [[Dyalog APL]], a [[scalar]] left argument is not allowed; in other languages it is treated as a list of a single scalar major cell). One scalar value is returned for each cell. In all current implementations, the cell shapes of left and right arguments must match; otherwise, a [[LENGTH ERROR]] is given. In [[A+]] and [[J]], arguments are also required to have the same type ([[character]], [[numeric]], or [[box]]ed). | Like [[Index Of]], Interval Index splits its right argument into [[cell]]s with the same rank as the [[major cell]]s of the left argument (in [[Dyalog APL]], a [[scalar]] left argument is not allowed; in other languages it is treated as a list of a single scalar major cell). One scalar value is returned for each cell. In all current implementations, the cell shapes of left and right arguments must match; otherwise, a [[LENGTH ERROR]] is given. In [[A+]] and [[J]], arguments are also required to have the same type ([[character]], [[numeric]], or [[box]]ed). | ||
Interval Index uses [[array ordering]] to order cells. Note that array ordering is always defined in terms of intolerant comparison, so that Interval Index does not depend on [[comparison tolerance]]. | Interval Index uses [[array ordering]] to order cells. Note that array ordering is always defined in terms of intolerant comparison, so that Interval Index does not depend on [[comparison tolerance]]. Any cell which comes before another cell in this ordering is said to precede it. If the cells do not intolerantly [[match]] then the first strictly precedes the second. | ||
There are two major ways to define the value corresponding to a single cell: | There are two major ways to define the value corresponding to a single cell: | ||
| Line 89: | Line 89: | ||
<references /> | <references /> | ||
{{APL built-ins}} | {{APL built-ins}}[[Category:Primitive functions]][[Category:Search functions]] | ||