类似二进制搜索的概念在 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)

我想创建一个函数，它将通过数据集 w 搜索 x，并将原始数据集根据 x 在 [=15] 中的位置子集化为较小的数据集=].输出将是一个较小的数据集，其上限值与搜索键相同。下面是我试图在 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

这是一个非常简单的解决方案，您可以使用此命令构建您的函数。当然，您必须检查 x 是否在 w 中，但这是您的工作:-)

x <- 12
w <- c(1,2,4,4,4,4,6,7,8,9,10,11,12,14,15)

index <- which(x == w)

w_new <- w[1:index[length(index)]]
print(w_new)
#[1]  1  2  4  4  4  4  6  7  8  9 10 11 12

Answer 2

您可以这样做来处理重复值。如果重复，将返回最高位置。请注意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

类似二进制搜索的概念在 R 中创建子集数据

Binary Search like concept to create subset data in R

r

dataset

binary-search