r - 在 R 中创建子集数据的二分搜索类似概念

Question

我有以下数据集 w和关键变量 x对于两种情况。

Case 1:
x = 4
w = c(1,2,4,4,4,4,6,7,8,9,10,11,12,14,15)

Case2:
x = 12
w = c(1,2,4,4,4,4,6,7,8,9,10,11,12,14,15)

我想创建一个函数来搜索 x通过数据集w并将根据 x 将原始数据集子集到较小的数据集的位置在 w .输出将是具有与搜索关键字相同的上限值的较小尺寸的数据集。下面是我试图用 R 编写的函数:

create_chunk <- function(val, tab, L=1L, H=length(tab))
{
  if(H >= L)
  {
    mid = L + ((H-L)/2)
    ## If the element is present within middle length
    if(tab[mid] > val)
    {
      ## subset the original data in reduced size and again do mid position value checking
      ## then subset the data
    } else
    {
      mid = mid + (mid/2)
      ## Increase the mid position to go for right side checking
    }
  }
}

在我正在寻找的输出中:

Output for Case 1:
Dataset containing: 1,2,4,4,4,4

Output for Case 2:
Dataset containing: 1,2,4,4,4,4,6,7,8,9,10,11,12


    Please note:
    1. Dataset may contain duplicate values for search key and 
       all the duplicate values are expected in the output dataset.
    2. I have huge size datasets (say around 2M rows) from 
       where I am trying to subset smaller dataset as per my requirement of search key.

新更新:案例 3

输入数据:

                 date    value size     stockName
1 2016-08-12 12:44:43 10093.40    4 HWA IS Equity
2 2016-08-12 12:44:38 10093.35    2 HWA IS Equity
3 2016-08-12 12:44:47 10088.00    2 HWA IS Equity
4 2016-08-12 12:44:52 10089.95    1 HWA IS Equity
5 2016-08-12 12:44:53 10089.95    1 HWA IS Equity
6 2016-08-12 12:44:54 10088.95    1 HWA IS Equity

搜索关键字是:10089.95在值列中。

预期输出为:

                 date    value size     stockName
1 2016-08-12 12:44:47 10088.00    2 HWA IS Equity
2 2016-08-12 12:44:54 10088.95    1 HWA IS Equity
3 2016-08-12 12:44:52 10089.95    1 HWA IS Equity
4 2016-08-12 12:44:53 10089.95    1 HWA IS Equity

Answer 1

您可以执行此操作来处理重复值。如果有重复，将返回其最高位置。请注意 A应该是非递减的。

binSearch <- function(A, value, left=1, right=length(A)){
  if (left > right)
    return(-1)
  middle <- (left + right) %/% 2
  if (A[middle] == value){
    while (A[middle] == value)
        middle<-middle+1
    return(middle-1)
    }
  else {
    if (A[middle] > value)
        return(binSearch(A, value, left, middle - 1))
    else
        return(binSearch(A, value, middle + 1, right))
    }
}

w[1:binSearch(w,x1)]
# [1] 1 2 4 4 4 4
w[1:binSearch(w,x2)]
# [1]  1  2  4  4  4  4  6  7  8  9 10 11 12

但是，正如评论中提到的，您可以简单地使用 findInterval达到同样的目的:

w[1:findInterval(x1,w)]

如您所知，二分查找的顺序为 log(n)但正如 ?findInterval 中所述，它还受益于 log(n)因为第一个参数的长度是一个:

The function findInterval finds the index of one vector x in another, vec, where the latter must be non-decreasing. Where this is trivial, equivalent to apply( outer(x, vec, ">="), 1, sum), as a matter of fact, the internal algorithm uses interval search ensuring O(n * log(N)) complexity where n <- length(x) (and N <- length(vec)). For (almost) sorted x, it will be even faster, basically O(n).

编辑

根据您的编辑和新设置，您可以这样做(假设您的数据在 df 中):

o <- order(df$value)
rows <- o[1:findInterval(key, df$value[o])]
df[rows,]

或者等效地，使用建议的 binSearch功能:

o <- order(df$value)
rows <- o[1:binSearch(df$value[o], key)]
df[rows,]

数据

x1 <- 4
x2 <- 12
w <- c(1,2,4,4,4,4,6,7,8,9,10,11,12,14,15)
key <- 10089.95