循环二进制索引

Circular binary index

本文关键字：索引 二进制 循环      更新时间：2023-09-26

我正在构建一个工具，通过最近的时间戳连接多个流。流可能不同步，所以我将最后的n(可能>=500)项存储在固定大小的循环缓冲区中。我想使用sortedIndex (而不是search )来查找缓冲区中放置项目的位置。我需要这个索引来查找恰好在时间戳之前和之后的流项。

处理拐角问题的边缘情况并不重要，我不在乎您是否在数组或0之外返回一个索引以获得最大值。我昨晚在玩这个实现，不能找出一个工作的实现。

函数契约如下，基于_.sortedIndex(实现)

/**
 * Binary search for finding the closest computed (by iterator) value
 * in some sorted circular array
 *
 * @param {Array} array a circular array-like
 * @param {Object} value to search for an index
 * @param {Function} iterator to compute the compare value of an item
 */
function sortedIndex(array, value, iterator) {
    var low = 0,
        high = array.length;
    while (low != high && iterator(array[low]) > iterator(array[high])) {
        // The binary search I failed to implement
    }
    return low;
}

一些测试用例(同样可以自由地以不同的方式处理转角用例):http://jsbin.com/yusilaba/1/edit

function identity(x) {
    return x;
}
function property(prop) {
    return function(x) {
        return x[prop];
    };
}
test('sortedIndex should work on simple case', function(t) {
    var array = [1, 2, 3, 4];
    equal(sortedIndex(array, 2, identity), 1, 'equal case sorts towards left');
    equal(sortedIndex(array, 2.5, identity), 2);
    equal(sortedIndex(array, 10, identity), 0);
    equal(sortedIndex(array, -10, identity), 3);
    array = [{a: 1}, {a: 2}, {a: 3}, {a: 4}];
    equal(sortedIndex(array, {a: 2}, property('a')), 1);
    equal(sortedIndex(array, {a: 2.5}, property('a')), 2);
    equal(sortedIndex(array, {a: 10}, property('a')), 0);
    equal(sortedIndex(array, {a: -10}, property('a')), 3);
});
test('sortedIndex should work on circular collections', function() {
    var array = [2, 3, 4, 1, 1.5];
    equal(sortedIndex(array, 2, identity), 0, 'equal case sorts towards left');
    equal(sortedIndex(array, 2.5, identity), 1);
    equal(sortedIndex(array, 10, identity), 3);
    equal(sortedIndex(array, -10, identity), 2);
    equal(sortedIndex(array, 5, identity), 4);
    equal(sortedIndex(array, 3.5, identity), 3);
    array = [{a: 2}, {a: 3}, {a: 4}, {a: 1}, {a: 1.5}];
    equal(sortedIndex(array, {a: 2}, property('a')), 0, 'equal case sorts towards left');
    equal(sortedIndex(array, {a: 2.5}, property('a')), 1);
    equal(sortedIndex(array, {a: 10}, property('a')), 3);
    equal(sortedIndex(array, {a: -10}, property('a')), 2);
});

编辑—这是我完成的版本https://github.com/trevnorris/cbuffer/pull/14

sortedIndex : function(value, comparitor, context) {
    var low = this.start,
        high = this.size - 1;
     // Tricky part is finding if its before or after the pivot
     // we can get this info by checking if the target is less than
     // the last item. After that it's just a typical binary search.
     if (low && comparitor.call(context, value, this.data[high]) > 0) {
        low = 0, high = this.end;
     }
     while (low < high) {
       var mid = (low + high) >>> 1;
       if (comparitor.call(context, value, this.data[mid]) > 0) low = mid + 1;
       else high = mid;
     }
     // http://stackoverflow.com/a/18618273/1517919
     return (((low - this.start) % this.size) + this.size) % this.size;
}

这是我想到的(它通过了您的测试用例)。基本上，当数组被排序时，它会进行正常的二分查找。当它是圆的(例如:[2,3,4,1])，它找到枢轴(这是圆开始的索引，所以在这个例子中，索引3，对应于数组中的4，将是枢轴)，然后二进制搜索枢轴所在的数组部分。

 function findPivot(arr, low, high, iterable){
    // base cases
    if (high < low)  return -1;
    if (high == low) return low;
    var mid = Math.floor((low + high)/2);
    if (mid < high && iterable(arr[mid]) > iterable(arr[mid + 1]))
      return mid;
    if (mid > low && iterable(arr[mid]) < iterable(arr[mid - 1]))
      return (mid-1);
    if (iterable(arr[low]) >= iterable(arr[mid]))
      return findPivot(arr, low, mid-1, iterable);
    else
      return findPivot(arr, mid + 1, high, iterable);
 }
 function binarySearch(arr, low, high, val, iterable)
 {
    if (high < low)
        return low;
    var mid = Math.floor((low + high)/2);
    if (iterable(val) == iterable(arr[mid]))
      return mid;
    if (iterable(val) > iterable(arr[mid]))
      return binarySearch(arr, (mid + 1), high, val, iterable);
    else
      return binarySearch(arr, low, (mid -1), val, iterable);
 }

 function sortedIndex(array, value, iterable) {
     var arr_size = array.length;
    var pivot = findPivot(array, 0, arr_size-1, iterable);
    if (pivot == -1) {
      if(iterable(array[arr_size-1]) < iterable(value)){
        return 0;
      } else if(iterable(array[0]) > iterable(value)){
        return arr_size-1;
      }
      return binarySearch(array, 0, arr_size-1, value, iterable);
    }
   if(iterable(array[pivot]) < iterable(value)){
     return pivot+1;
   } else if(iterable(array[pivot+1]) > iterable(value)){
      return pivot;
   }
    if (iterable(array[pivot]) == iterable(value))
      return pivot;
    if (iterable(array[0]) <= iterable(value))
      return binarySearch(array, 0, pivot-1, value, iterable);
    else
      return binarySearch(array, pivot+1, arr_size-1, value, iterable);
    }
以下是测试用例:http://jsbin.com/ratufewa/1/edit

希望这是正确的方向。

迭代解http://jsbin.com/ratufewa/3/edit:

 function findPivot(arr, low, high, iterable)
 {
   while(true){
      // base cases
      if (high < low)  return -1;
      if (high == low) return low;
      var mid = (low + high) >>> 1;
      if (mid < high && iterable(arr[mid]) > iterable(arr[mid + 1]))
        return mid;
      if (mid > low && iterable(arr[mid]) < iterable(arr[mid - 1]))
        return (mid-1);
      if (iterable(arr[low]) >= iterable(arr[mid]))
        high = mid-1;
      else
        low = mid + 1;
   }
 }
 function binarySearch(arr, low, high, val, iterable)
 {
   while(true){
      if (high < low)
     return low;
      var mid = (low + high) >>> 1;
      if (iterable(val) == iterable(arr[mid]))
        return mid;
      if (iterable(val) > iterable(arr[mid]))
        low = mid + 1;
      else
        high = mid -1;
   }
 }

 function sortedIndex(array, value, iterable) {
    var arr_size = array.length;
    var pivot = findPivot(array, 0, arr_size-1, iterable);
    if (pivot == -1) {
      if(iterable(array[arr_size-1]) < iterable(value)){
        return 0;
      } else if(iterable(array[0]) > iterable(value)){
        return arr_size-1;
      }
      return binarySearch(array, 0, arr_size-1, value, iterable);
    }
   if(iterable(array[pivot]) < iterable(value)){
     return pivot+1;
   } else if(iterable(array[pivot+1]) > iterable(value)){
      return pivot;
   }
    if (iterable(array[pivot]) == iterable(value))
      return pivot;
    if (iterable(array[0]) <= iterable(value))
      return binarySearch(array, 0, pivot-1, value, iterable);
    else
      return binarySearch(array, pivot+1, arr_size-1, value, iterable);
 }

通常，在循环缓冲区中存储实际占用位置的开始和结束。有了这些信息，我们可以区分三种情况:

function sortedIndex(buffer, item, getValue) {
    if (buffer.start < buffer.end)
        // do standard binary search between start and end indices
    else if (getValue(buffer[0]) <= getValue(item))
        // do standard binary search between 0 and end index
    else // getValue(buffer[0] > getValue(item)
        // do standard binary search between start and buffer.length
}
相关文章：