首页 / JAVASCRIPT / javascript-循环二进制索引

javascript-循环二进制索引

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了javascript-循环二进制索引，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6104字，纯文字阅读大概需要9分钟。

内容图文

我正在构建一个工具,可以在最近的时间戳之前加入多个流.这些流可能不同步,因此我将最后n个(可能> == 500)项目存储在固定大小的循环缓冲区中.我想使用sortedIndex(而不是搜索)来查找项目在缓冲区中的放置位置.我需要此索引来在时间戳之前和之后找到流项目.

处理即将来临的问题的极端情况并不重要,我不在乎是否在数组之外返回索引,或者对于最大值返回0.昨晚我一直在执行此实现,无法找到可行的实现.

以下是功能合同,其基于_.sortedIndex(implementation)

/**
 * 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;
     }
     // https://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);
 }

内容总结

以上是互联网集市为您收集整理的javascript-循环二进制索引全部内容，希望文章能够帮你解决javascript-循环二进制索引所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/678975.html

来源：【匿名】

【上一篇】javascript-HTML中的交互式画布vs渲染表.哪种方法更快？【下一篇】javascript 怎么调用php方法

更多 ►

【javascript-循环二进制索引】教程文章相关的互联网学习教程文章

JavaScript二进制数据序列化和反序列化【代码】

最近业余时间在搞h5小游戏，由于同步协议过于频繁，和服务器之间的同步直接用json就显得太浪费了，于是我们商讨之下决定改用二进制。学习过程中并没有遇到一篇就解决问题的文章，遂再总结一发。 1.二进制数据的存储ArrayBuffer对象、TypedArray对象、DataView对象是JavaScript操作二进制数据的一个接口。　（1）ArrayBuffer对象：代表内存之中的一段二进制数据，它不能直接读写，只能通过视图（TypedArray视图和DataView视图)来读写...

javascript-使用rabbitmq stomp发送protobuf(二进制)数据【代码】

我已经在客户端使用protobuf.js创建了Rabbitmq踩踏的一个示例.protobuf示例链接：https://github.com/dcodeIO/ProtoBuf.js 发送消息文件内容：var Game = builder.build("Game"); var Car = Game.Cars.Car; var car = new Car("Rusty", "mayur"); var buffer = car.encode(); var mq_username = "guest", mq_password = "guest", mq_vhost = "/", mq_url = 'http://192.168.0.14:15674/stomp', mq_queue1 = '/queue/A...

JavaScript使用IEEE标准进行二进制浮点运算产生莫名错误的解决方法_javascript技巧

javascript做带小数的计算时，会出现9的循环，以下方法帮助解决。第一个参数是需要处理的数值，第二个参数是需要保留的小数位数。自家项目里面就这么用了~ 代码如下: function round(v,e){ var t=1; for(;e>0;t*=10,e--); for(;e<0;t/=10,e++); return Math.round(v*t)/t; }

javascript – 如何使用HTML5 File API加密二进制文件并上传到服务器【代码】

我需要使用HTML5 FileReader API和CryptoJS加密并上传文件到Apache / PHP服务器我成功完成了以下工作 >使用FileReader API读取文件>使用readAsDataURL()函数将文件转换为base64>使用以下内容加密它 CryptoJS.AES.encrypt(e.target.result,密码); 但我无法将其作为File对象发送到服务器,因为我已经将其转换为文本对象,我无法将其转换回文件.以下是我的javascript文件和服务器端代码段. app.jsvar reader = new FileReader();// Rea...

Node.js中使用Buffer编码、解码二进制数据详解

JavaScript很擅长处理字符串，但是因为它最初的设计是用来处理HTML文档，因此它并不太擅长处理二进制数据。JavaScript没有byte类型，没有结构化的类型（structured types），甚至没有字节数组，只有数字和字符串。（原文：JavaScript doesnt have a byte type — it just has numbers — or structured types, or http://skylitecellars.com/ even byte arrays: It just has strings.）因为Node基于JavaScript，它自然可以处理类似...

Node.js中使用Buffer编码和解码二进制数据的方法

这篇文章主要介绍了Node.js中使用Buffer编码、解码二进制数据详解,Buffer支持ascii、utf8、ucs2、base64等编码格式,需要的朋友可以参考下JavaScript很擅长处理字符串，但是因为它最初的设计是用来处理HTML文档，因此它并不太擅长处理二进制数据。JavaScript没有byte类型，没有结构化的类型（structured types），甚至没有字节数组，只有数字和字符串。（原文：JavaScript doesnt have a byte type — it just has numbers — or st...

js实现操作二进制数据方法

下面我就为大家分享一篇js操作二进制数据方法，具有很好的参考价值，希望对的大家有所帮助。最近做了几个项目，用js操作二进制数据，通过socket与后台进行传输。在此用博客做个记录首先是新建一个socket：var socket=new WebSocket("ws://192.168.0.147");接着定义socket打开，连接之后执行的函数：websocket有个属性binaryType，可将其设置为“blob”或者“arraybuffer”，默认格式为“blob”，做项目的时候忘记设置为“arraybuff...

js操作二进制数据方法总结

这次给大家带来js操作二进制数据方法总结，js操作二进制数据的注意事项有哪些，下面就是实战案例，一起来看一下。最近做了几个项目，用js操作二进制数据，通过socket与后台进行传输。在此用博客做个记录首先是新建一个socket：var socket=new WebSocket("ws://192.168.0.147");接着定义socket打开，连接之后执行的函数：websocket有个属性binaryType，可将其设置为“blob”或者“arraybuffer”，默认格式为“blob”，做项目的时候忘...

js如何操作二进制数据

最近做了几个项目，用js操作二进制数据，通过socket与后台进行传输。本文主要和大家分享，js如何操作二进制数据，希望能帮助到大家。首先是新建一个socket：var socket=new WebSocket("ws://192.168.0.147");接着定义socket打开，连接之后执行的函数：websocket有个属性binaryType，可将其设置为“blob”或者“arraybuffer”，默认格式为“blob”，做项目的时候忘记设置为“arraybuffer”了，结果在下面接收数据的时候就需要用Blob...

nodeJS中二进制buffer对象实例详解

前面的话　　在ES6引入TypedArray之前，JavaScript语言没有读取或操作二进制数据流的机制。Buffer类被引入作为Nodejs的API的一部分，使其可以在TCP流和文件系统操作等场景中处理二进制数据流。现在TypedArray已经被添加进ES6中，Buffer类以一种更优与更适合Node.js用例的方式实现了Uint8Array。本文将详细介绍buffer对象概述　　由于应用场景不同，在Node中，应用需要处理网络协议、操作数据库、处理图片、接收上传文件等，在网络...

nodeJS之关于二进制buffer对象的详细介绍

本篇文章主要介绍了nodeJS之二进制buffer对象，小编觉得挺不错的，现在分享给大家，也给大家做个参考。一起跟随小编过来看看吧前面的话在ES6引入TypedArray之前，JavaScript语言没有读取或操作二进制数据流的机制。Buffer类被引入作为Nodejs的API的一部分，使其可以在TCP流和文件系统操作等场景中处理二进制数据流。现在TypedArray已经被添加进ES6中，Buffer类以一种更优与更适合Node.js用例的方式实现了Uint8Array。本文将详细介绍...

JavaScript趣题：统计二进制

咋们搞前端的，想必很少有机会接触二进制吧，那些位运算啥的，不是底层应该考虑的问题嘛？昨天看到一个题目，它和二进制相关，但用不用位运算都没关系，借助JS的语言特性，也能轻易地解决。描述如下：写一个函数，接收一个十进制的正整数作参数，用二进制表示它，并返回那些数位等于1的数目。来个例子：1234表示为二进制是10011010010，这里面有5个1，所以返回5。看了这个描述，我的脑海中首先想到的是，以前老师上课教的，怎么从十...

使用node.js中的Buffer类处理二进制数据的方法【图】

前言在Node.js中，定义了一个Buffer类，该类用来创建一个专门存放二进制数据的缓存区。这篇文章就详细介绍了node.js中的Buffer类处理二进制数据的方法，下面话不多说，来看看详细的介绍。创建Buffer对象第一种：直接使用一个数组来初始化缓存区var arr = [0,1,2] var buf = new Buffer(arr) console.log(buf) 执行效果：第二种：直接使用一个字符串来初始化缓存区var str = hello var buf = new Buffer(str) console.log(buf) 执行...

使用jscript实现二进制读写脚本代码_javascript技巧

因此，这里是一个很好的方式访问的二进制文件从JScript的。如果您要访问的这个对象从VBScript中，然后把它放在一个SWF文件。此对象已经被用于在愤怒将文件上载到Web服务，并已被证明是好的和快速的文件，在0-10 MB的地区。/** This is a fairly well optimized object which alows 访问的二进制文件从JScript的在Windows *作业系统。 *该文件的末尾是小的一套测试，以显示它如何 *用。您将需要adodb 2.5或更高版本。 ...

JS中字符问题(二进制/十进制/十六进制及ASCII码之间的转换)

JS中字符问题(二进制/十进制/十六进制及ASCII码之间的转换)var a=11160; alert(parseInt(a,2)); //将111做为2进制来转换,忽略60(不符合二进制),从左至右只将符合二进制数的进行转换 alert(parseInt(a,16)); //将所有的都进行转换依照此方法,其实可以转换成任何进制 var a=1110; alert(parseInt(a,10).toString(16)); //将A转换为10进制,然后再转换成16进制同样也可以是其它进制下面说下ASCII 码: function test(){ var a=ab; ...

首页 / JAVASCRIPT / javascript-循环二进制索引

javascript-循环二进制索引

内容导读

内容图文

内容总结

内容备注

内容手机端

【javascript-循环二进制索引】教程文章相关的互联网学习教程文章

JAVASCRIPT - 相关标签

循环 - 相关标签

JAVASCRIPT - 技术教程分类

JAVASCRIPT - 最新教程

JAVASCRIPT - 最热教程