[Rd] pmatch bug?
Duncan Murdoch
murdoch@dunc@n @end|ng |rom gm@||@com
Tue Jun 16 14:13:52 CEST 2026
On 2026-06-16 7:59 a.m., Duncan Murdoch wrote:
> I believe the problem is that the hash code doesn't allow values to be
> removed. So when x is c(1:n, 1:n) for n > 50, pmatch(x,x) gets exact
> matches to the first half of the values, but not to the second half:
> the hashes point to the removed values and they are rejected.
>
> When it switches to partial matches, for n=51 there are multiple partial
> matches to 1:5, but not to bigger numbers, so those come out as NA. For
> numbers 6:51, the partial match code sees unique partial matches (which
> happen to be exact).
>
> I think the best fix is:
>
> - Fix the hash code to allow for multiple copies in the hash table,
> and record whether values have been used in each of those.
>
> This would be programmed similar to handling hash collisions (which I
> think aren't handled now).
I'm wrong about that part. Hash collisions are currently not a problem.
It's only the duplicates.ok=FALSE case that isn't handled now.
A much simpler fix is to skip hashing if duplicates.ok = FALSE. I don't
know how badly that would affect performance.
Duncan Murdoch
>
>
> Duncan Murdoch
>
>
> On 2026-06-16 7:29 a.m., Peter Dalgaard wrote:
>> OK, so 100 is the cutoff whether to use a hash table or not. It is still odd that it only affects a relatively short block at the beginning of the repeated targets, though.
>>
>>> On 16 Jun 2026, at 11.54, Peter Dalgaard <pdalgd using gmail.com> wrote:
>>>
>>> Something definitely looks odd... I certain can't think of a reason why the behaviour would be keyed to the _size_ of the first argument like this:
>>>
>>>> pmatch(as.character(x)[1:100], as.character(x))
>>> [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
>>> [19] 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
>>> [37] 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
>>> [55] 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
>>> [73] 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
>>> [91] 91 92 93 94 95 96 97 98 99 100
>>>> pmatch(as.character(x)[1:101], as.character(x))
>>> [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
>>> [19] 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
>>> [37] 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 NA NA NA
>>> [55] NA NA 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
>>> [73] 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
>>> [91] 91 92 93 94 95 96 97 98 99 100 101
>>>> pmatch(as.character(x)[2:102], as.character(x))
>>> [1] 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
>>> [19] 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
>>> [37] 38 39 40 41 42 43 44 45 46 47 48 49 50 51 1 NA NA NA
>>> [55] NA 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
>>> [73] 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
>>> [91] 92 93 94 95 96 97 98 99 100 101 102
>>>>> pmatch(as.character(x)[3:102], as.character(x))
>>> [1] 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
>>> [19] 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
>>> [37] 39 40 41 42 43 44 45 46 47 48 49 50 51 1 2 54 55 56
>>> [55] 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
>>> [73] 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
>>> [91] 93 94 95 96 97 98 99 100 101 102
>>>
>>> It's happening in the C code, though, so some poking around is required.
>>>
>>> - pd
>>>
>>>
>>>> On 15 Jun 2026, at 22.14, Duncan Murdoch <murdoch.duncan using gmail.com> wrote:
>>>>
>>>> I think your example is overly complicated. Wouldn't it be enough to show one vector that gives a bad result? For example:
>>>>
>>>> x <- c(1:51, 1:51)
>>>> pmatch(x, x)
>>>>
>>>> which gives
>>>>
>>>> [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
>>>> [30] 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 NA NA NA NA NA 57 58
>>>> [59] 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
>>>> [88] 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
>>>>
>>>> (with the NAs showing up at locations 52 to 56).
>>>>
>>>> I'm not 100% sure that's a bug, since the documentation for pmatch doesn't discuss what should happen if table (the second argument) contains duplicates. I think I'd agree with you that you should get 1:102 as the output, but maybe that was never intended to be supported.
>>>>
>>>> Duncan Murdoch
>>>>
>>>> On 2026-06-15 3:12 p.m., François Rousset via R-devel wrote:
>>>>> Dear R-devel list,
>>>>> the following code shows NA's appearing in the result of pmatch() when
>>>>> comparing a vector to itself when the length of the vector is more than 100.
>>>>> The main specificity of this example is that elements are repeated in
>>>>> the vector which is matched to itself.
>>>>> The results when they do not include any NA (i.e. for argument of length
>>>>> <=100) are exactly as I expect from the documentation.
>>>>> I see that the source C code uses distinct algorithms whether n_input <=
>>>>> 100 || n_target <= 100 or not. Could there by a problem in the source
>>>>> code for larger values ?
>>>>> The NA's correspond to the first positions of the second replicate of
>>>>> the integer sequence, e.g. positions 52 to 56 if n=51 in the example below.
>>>>> But as shown below, the NA's do not appear when the sequence is reversed
>>>>> before being compared to itself.
>>>>> This was first detected with R 4.5.3 and is reproducible with a
>>>>> just-downloaded, virgin R-devel installation.
>>>>> Thanks in advance for any feedback,
>>>>> F.
>>>>> ======================
>>>>> countNAs <- function(n, rev.=FALSE) {
>>>>> seqn <- seq(n)
>>>>> if (rev.) seqn <- rev(seqn)
>>>>> seqn <- rep(seqn,2) # of length 2 n: NA's
>>>>> appear when 2 n > 100
>>>>> chk <- pmatch(seqn, seqn) # I expect the result to be
>>>>> seq(2*n)
>>>>> sum(is.na(chk))
>>>>> }
>>>>> sapply(1:100, countNAs )
>>>>> sapply(1:100, countNAs , rev.=TRUE)
>>>>> =======================
>>>>> Results:
>>>>>> sapply(1:100, countNAs )
>>>>> [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
>>>>> 0 0 0 0 0 0
>>>>> [29] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
>>>>> 5 5 5 5 5 5
>>>>> [57] 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7
>>>>> 7 8 8 8 8 8
>>>>> [85] 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 10
>>>>>> sapply(1:100, countNAs , rev.=TRUE)
>>>>> [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
>>>>> 0 0 0 0 0 0 0 0 0
>>>>> [43] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
>>>>> 0 0 0 0 0 0 0 0 0
>>>>> [85] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
>>>>>> sessionInfo()
>>>>> R Under development (unstable) (2026-06-14 r90150 ucrt)
>>>>> Platform: x86_64-w64-mingw32/x64
>>>>> Running under: Windows 10 x64 (build 19045)
>>>>> Matrix products: default
>>>>> LAPACK version 3.12.1
>>>>> locale:
>>>>> [1] LC_COLLATE=French_France.utf8 LC_CTYPE=French_France.utf8
>>>>> [3] LC_MONETARY=French_France.utf8 LC_NUMERIC=C
>>>>> [5] LC_TIME=French_France.utf8
>>>>> time zone: Europe/Paris
>>>>> tzcode source: internal
>>>>> attached base packages:
>>>>> [1] stats graphics grDevices utils datasets methods base
>>>>> loaded via a namespace (and not attached):
>>>>> [1] compiler_4.7.0 tools_4.7.0
>>>>> ______________________________________________
>>>>> R-devel using r-project.org mailing list
>>>>> https://stat.ethz.ch/mailman/listinfo/r-devel
>>>>
>>>> ______________________________________________
>>>> R-devel using r-project.org mailing list
>>>> https://stat.ethz.ch/mailman/listinfo/r-devel
>>>
>>> --
>>> Peter Dalgaard, Professor,
>>> Center for Statistics, Copenhagen Business School
>>> Solbjerg Plads 3, 2000 Frederiksberg, Denmark
>>> Phone: (+45)38153501
>>> Office: A 4.23
>>> Email: pd.mes using cbs.dk Priv: PDalgd using gmail.com
>>>
>>
>
More information about the R-devel
mailing list