希尔排序–js代码实现

希尔排序

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
  • 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;

希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

1. 算法步骤

  1. 选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;
  2. 按增量序列个数 k,对序列进行 k 趟排序;
  3. 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

2. JavaScript 代码实现

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //动态定义间隔序列
        gap =gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

插入排序–js实现

插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。

1. 算法步骤

  1. 将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
  2. 从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

2. 动图演示

动图演示

3. JavaScript 代码实现

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

选择排序–js实现算法

选择排序

选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1. 算法步骤

  1. 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
  2. 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
  3. 重复第二步,直到所有元素均排序完毕。

2. 动图演示

动图演示

3. JavaScript 代码实现

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

冒泡算法 — js之实现

冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

作为最简单的排序算法之一,冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样,每次都在第一页第一位,所以最熟悉。冒泡排序还有一种优化算法,就是立一个 flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

1. 算法步骤

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

    2. 动图演示

    动图演示

    3. 什么时候最快

    当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊)。

    4. 什么时候最慢

    当输入的数据是反序时(写一个 for 循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吗)。

    5. JavaScript 代码实现

    function bubbleSort(arr) {
        var len = arr.length;
        for (var i = 0; i < len - 1; i++) {
            for (var j = 0; j < len - 1 - i; j++) {
                if (arr[j] > arr[j+1]) {        // 相邻元素两两对比
                    var temp = arr[j+1];        // 元素交换
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

转:JavaScript instanceof 运算符深入剖析

原文地址:https://www.ibm.com/developerworks/cn/web/1306_jiangjj_jsinstanceof/

instanceof 运算符简介

在 JavaScript 中,判断一个变量的类型尝尝会用 typeof 运算符,在使用 typeof 运算符时采用引用类型存储值会出现一个问题,无论引用的是什么类型的对象,它都返回 “object”。ECMAScript 引入了另一个 Java 运算符 instanceof 来解决这个问题。instanceof 运算符与 typeof 运算符相似,用于识别正在处理的对象的类型。与 typeof 方法不同的是,instanceof 方法要求开发者明确地确认对象为某特定类型。例如:

清单 1. instanceof 示例
var oStringObject = new String("hello world");
console.log(oStringObject instanceof String);   // 输出 "true"

这段代码问的是“变量 oStringObject 是否为 String 对象的实例?”oStringObject 的确是 String 对象的实例,因此结果是”true”。尽管不像 typeof 方法那样灵活,但是在 typeof 方法返回 “object” 的情况下,instanceof 方法还是很有用的。

instanceof 运算符的常规用法

通常来讲,使用 instanceof 就是判断一个实例是否属于某种类型。例如:

清单 2. instanceof 常规用法
1
2
3
4
// 判断 foo 是否是 Foo 类的实例
function Foo(){}
var foo = new Foo();
console.log(foo instanceof Foo)//true

另外,更重的一点是 instanceof 可以在继承关系中用来判断一个实例是否属于它的父类型。例如:

清单 3. instanceof 在继承中关系中的用法
1
2
3
4
5
6
7
8
// 判断 foo 是否是 Foo 类的实例 , 并且是否是其父类型的实例
function Aoo(){}
function Foo(){}
Foo.prototype = new Aoo();//JavaScript 原型继承
var foo = new Foo();
console.log(foo instanceof Foo)//true
console.log(foo instanceof Aoo)//true

上面的代码中是判断了一层继承关系中的父类,在多层继承关系中,instanceof 运算符同样适用。

你真的了解 instanceof 操作符吗?

看了上面的代码示例,是不是觉得 instanceof 操作符很简单,下面来看点复杂的用法。

清单 4. instanceof 复杂用法
1
2
3
4
5
6
7
8
9
console.log(Object instanceof Object);//true
console.log(Function instanceof Function);//true
console.log(Number instanceof Number);//false
console.log(String instanceof String);//false
console.log(Function instanceof Object);//true
console.log(Foo instanceof Function);//true
console.log(Foo instanceof Foo);//false

看了上面的代码是不是又晕头转向了?为什么 Object 和 Function instanceof 自己等于 true,而其他类 instanceof 自己却又不等于 true 呢?如何解释?要想从根本上了解 instanceof 的奥秘,需要从两个方面着手:1,语言规范中是如何定义这个运算符的。2,JavaScript 原型继承机制。

详细剖析 ECMAScript-262 edition 3 中 instanceof 运算符的定义

语言规范对中 instanceof 运算符的定义如下:

清单 5. 规范中 instanceof 运算符定义
11.8.6 The instanceof operator
 The production RelationalExpression:
     RelationalExpression instanceof ShiftExpression is evaluated as follows:
 1. Evaluate RelationalExpression.
 2. Call GetValue(Result(1)).// 调用 GetValue 方法得到 Result(1) 的值,设为 Result(2)
 3. Evaluate ShiftExpression.
 4. Call GetValue(Result(3)).// 同理,这里设为 Result(4)
 5. If Result(4) is not an object, throw a TypeError exception.// 如果 Result(4) 不是 object,
                                                                //抛出异常
 /* 如果 Result(4) 没有 [[HasInstance]] 方法,抛出异常。规范中的所有 [[...]] 方法或者属性都是内部的,
在 JavaScript 中不能直接使用。并且规范中说明,只有 Function 对象实现了 [[HasInstance]] 方法。
所以这里可以简单的理解为:如果 Result(4) 不是 Function 对象,抛出异常 */
 6. If Result(4) does not have a [[HasInstance]] method,
   throw a TypeError exception.
 // 相当于这样调用:Result(4).[[HasInstance]](Result(2))
 7. Call the [[HasInstance]] method of Result(4) with parameter Result(2).
 8. Return Result(7).
 // 相关的 HasInstance 方法定义
 15.3.5.3 [[HasInstance]] (V)
 Assume F is a Function object.// 这里 F 就是上面的 Result(4),V 是 Result(2)
 When the [[HasInstance]] method of F is called with value V,
     the following steps are taken:
 1. If V is not an object, return false.// 如果 V 不是 object,直接返回 false
 2. Call the [[Get]] method of F with property name "prototype".// 用 [[Get]] 方法取
                                                                // F 的 prototype 属性
 3. Let O be Result(2).//O = F.[[Get]]("prototype")
 4. If O is not an object, throw a TypeError exception.
 5. Let V be the value of the [[Prototype]] property of V.//V = V.[[Prototype]]
 6. If V is null, return false.
 // 这里是关键,如果 O 和 V 引用的是同一个对象,则返回 true;否则,到 Step 8 返回 Step 5 继续循环
 7. If O and V refer to the same object or if they refer to objects
   joined to each other (section 13.1.2), return true.
 8. Go to step 5.

上面的规范定义很晦涩,而且看起来比较复杂,涉及到很多概念,但把这段规范翻译成 JavaScript 代码却很简单,如下:

清单 6. JavaScript instanceof 运算符代码
1
2
3
4
5
6
7
8
9
10
11
function instance_of(L, R) {//L 表示左表达式,R 表示右表达式
 var O = R.prototype;// 取 R 的显示原型
 L = L.__proto__;// 取 L 的隐式原型
 while (true) {
   if (L === null)
     return false;
   if (O === L)// 这里重点:当 O 严格等于 L 时,返回 true
     return true;
   L = L.__proto__;
 }
}

JavaScript 原型继承机制

由于本文主要集中在剖析 JavaScript instanceof 运算符,所以对于 JavaScript 的原型继承机制不再做详细的讲解,下面参考来自 http://www.mollypages.org/misc/js.mp 的一张图片,此图片详细的描述了 JavaScript 各种对象的显示和隐式原型链结构。

由其本文涉及显示原型和隐式原型,所以下面对这两个概念作一下简单说明。在 JavaScript 原型继承结构里面,规范中用 [[Prototype]] 表示对象隐式的原型,在 JavaScript 中用 __proto__ 表示,并且在 Firefox 和 Chrome 浏览器中是可以访问得到这个属性的,但是 IE 下不行。所有 JavaScript 对象都有 __proto__ 属性,但只有 Object.prototype.__proto__ 为 null,前提是没有在 Firefox 或者 Chrome 下修改过这个属性。这个属性指向它的原型对象。 至于显示的原型,在 JavaScript 里用 prototype 属性表示,这个是 JavaScript 原型继承的基础知识,在这里就不在叙述了。

图 1. JavaScript 原型链

JavaScript 原型链

讲解 instanceof 复杂用法

有了上面 instanceof 运算符的 JavaScript 代码和原型继承图,再来理解 instanceof 运算符将易如反掌。下面将详细讲解 Object instanceof Object,Function instanceof Function 和 Foo instanceof Foo 三个示例,其它示例读者可自行推演。

清单 7. Object instanceof Object
1
2
3
4
5
6
7
8
9
10
11
12
// 为了方便表述,首先区分左侧表达式和右侧表达式
ObjectL = Object, ObjectR = Object;
// 下面根据规范逐步推演
O = ObjectR.prototype = Object.prototype
L = ObjectL.__proto__ = Function.prototype
// 第一次判断
O != L
// 循环查找 L 是否还有 __proto__
L = Function.prototype.__proto__ = Object.prototype
// 第二次判断
O == L
// 返回 true
清单 8. Function instanceof Function
1
2
3
4
5
6
7
8
// 为了方便表述,首先区分左侧表达式和右侧表达式
FunctionL = Function, FunctionR = Function;
// 下面根据规范逐步推演
O = FunctionR.prototype = Function.prototype
L = FunctionL.__proto__ = Function.prototype
// 第一次判断
O == L
// 返回 true
清单 9. Foo instanceof Foo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 为了方便表述,首先区分左侧表达式和右侧表达式
FooL = Foo, FooR = Foo;
// 下面根据规范逐步推演
O = FooR.prototype = Foo.prototype
L = FooL.__proto__ = Function.prototype
// 第一次判断
O != L
// 循环再次查找 L 是否还有 __proto__
L = Function.prototype.__proto__ = Object.prototype
// 第二次判断
O != L
// 再次循环查找 L 是否还有 __proto__
L = Object.prototype.__proto__ = null
// 第三次判断
L == null
// 返回 false

简析 instanceof 在 Dojo 继承机制中的应用

在 JavaScript 中,是没有多重继承这个概念的,就像 Java 一样。但在 Dojo 中使用 declare 声明类时,是允许继承自多个类的。下面以 Dojo 1.6.1 为例。

清单 10. Dojo 中多重继承
1
2
3
4
5
6
7
8
9
10
dojo.declare("Aoo",null,{});
dojo.declare("Boo",null,{});
dojo.declare("Foo",[Aoo,Boo],{});
var foo = new Foo();
console.log(foo instanceof Aoo);//true
console.log(foo instanceof Boo);//false
console.log(foo.isInstanceOf(Aoo));//true
console.log(foo.isInstanceOf(Boo));//true

上面的示例中,Foo 同时继承自 Aoo 和 Boo,但当使用 instanceof 运算符来检查 foo 是否是 Boo 的实例时,返回的是 false。实际上,在 Dojo 的内部,Foo 仍然只继承自 Aoo,而通过 mixin 机制把 Boo 类中的方法和属性拷贝到 Foo 中,所以当用 instanceof 运算符来检查是否是 Boo 的实例时,会返回 false。所以 Dojo 为每个类的实例添加了一个新的方法叫 isInstanceOf,用这个方法来检查多重继承。

结束语

本文详细介绍了 JavaScript 语言中 instanceof 运算符,并且结合语言规范深入剖析了此操作符的算法。对读者使用 JavaScript 编写复杂的面向对象程序会有很大的帮助。本文所有代码在 Firefox 15 下通过测试。

相关主题

移动端触摸数字转盘无限滚动实现思路

先看下效果,这个转盘的数字是从0-105,可以设置起始数字,那么之前的数字就变灰,不可选取,点击 加减号,会自动转动4个数字间隔,同时也可以手动触摸拖动,拖到终端105,自动回弹不可再拖动下去,同时选中的数字自动变黄···

好啦看下gif实现效果,或者点击查看,请滑动到第三屏

 

难点分析:

1、因为一个圆是360度,数字按照一定间隔排列比较合理的是18度排一个数字,那么一个圆形只能排列20个数字,其他数字如何生成?

2、如何判断当前选中并且加黄?

3、手指触摸拖动和圆盘转动的换算关系?

4、转动如何更加平滑有一定弹性

5、如何控制相应的数字显示隐藏来达到转盘数字一直增加或者减少的效果?

继续阅读移动端触摸数字转盘无限滚动实现思路

JavaScript反调试技巧

写在前面的话

在此之前,我一直都在研究JavaScript相关的反调试技巧。但是当我在网上搜索相关资料时,我发现网上并没有多少关于这方面的文章,而且就算有也是非常不完整的那种。所以在这篇文章中,我打算跟大家总结一下关于JavaScript反调试技巧方面的内容。值得一提的是,其中有些方法已经被网络犯罪分子广泛应用到恶意软件之中了。

对于JavaScript来说,你只需要花一点时间进行调试和分析,你就能够了解到JavaScript代码段的功能逻辑。而我们所要讨论的内容,可以给那些想要分析你JavaScript代码的人增加一定的难度。不过我们的技术跟代码混淆无关,我们主要针对的是如何给代码主动调试增加困难。

本文所要介绍的技术方法大致如下:

1.   检测未知的执行环境(我们的代码只想在浏览器中被执行);

2.   检测调试工具(例如DevTools);

3.   代码完整性控制;

4.   流完整性控制;

5.   反模拟;

简而言之,如果我们检测到了“不正常”的情况,程序的运行流程将会改变,并跳转到伪造的代码块,并“隐藏”真正的功能代码。

一、函数重定义

这是一种最基本也是最常用的代码反调试技术了。在JavaScript中,我们可以对用于收集信息的函数进行重定义。比如说,console.log()函数可以用来收集函数和变量等信息,并将其显示在控制台中。如果我们重新定义了这个函数,我们就可以修改它的行为,并隐藏特定信息或显示伪造的信息。

我们可以直接在DevTools中运行这个函数来了解其功能:

console.log("HelloWorld");
var fake = function() {};
window['console']['log']= fake;
console.log("Youcan't see me!");

运行后我们将会看到:

VM48:1 Hello World

你会发现第二条信息并没有显示,因为我们重新定义了这个函数,即“禁用”了它原本的功能。但是我们也可以让它显示伪造的信息。比如说这样:

console.log("Normalfunction");
//First we save a reference to the original console.log function
var original = window['console']['log'];
//Next we create our fake function
//Basicly we check the argument and if match we call original function with otherparam.
// If there is no match pass the argument to the original function
var fake = function(argument) {
    if (argument === "Ka0labs") {
        original("Spoofed!");
    } else {
        original(argument);
    }
}
// We redefine now console.log as our fake function
window['console']['log']= fake;
//Then we call console.log with any argument
console.log("Thisis unaltered");
//Now we should see other text in console different to "Ka0labs"
console.log("Ka0labs");
//Aaaand everything still OK
console.log("Byebye!");

如果一切正常的话:

Normal function
VM117:11 This is unaltered
VM117:9 Spoofed!
VM117:11 Bye bye!

实际上,为了控制代码的执行方式,我们还能够以更加聪明的方式来修改函数的功能。比如说,我们可以基于上述代码来构建一个代码段,并重定义eval函数。我们可以把JavaScript代码传递给eval函数,接下来代码将会被计算并执行。如果我们重定义了这个函数,我们就可以运行不同的代码了:

//Just a normal eval

eval("console.log('1337')");

//Now we repat the process...

var original = eval;

var fake = function(argument) {

    // If the code to be evaluated contains1337...

    if (argument.indexOf("1337") !==-1) {

        // ... we just execute a different code

        original("for (i = 0; i < 10;i++) { console.log(i);}");

    }

    else {

        original(argument);

    }

}

eval= fake;

eval("console.log('Weshould see this...')");

//Now we should see the execution of a for loop instead of what is expected

eval("console.log('Too1337 for you!')");

运行结果如下:

1337
VM146:1We should see thisVM147:10
VM147:11
VM147:12
VM147:13
VM147:14
VM147:15
VM147:16
VM147:17
VM147:18
VM147:19

正如之前所说的那样,虽然这种方法非常巧妙,但这也是一种非常基础和常见的方法,所以比较容易被检测到。

二、断点

为了帮助我们了解代码的功能,JavaScript调试工具(例如DevTools)都可以通过设置断点的方式阻止脚本代码执行,而断点也是代码调试中最基本的了。

如果你研究过调试器或者x86架构,你可能会比较熟悉0xCC指令。在JavaScript中,我们有一个名叫debugger的类似指令。当我们在代码中声明了debugger函数后,脚本代码将会在debugger指令这里停止运行。比如说:

console.log("Seeme!");
debugger;
console.log("Seeme!");

很多商业产品会在代码中定义一个无限循环的debugger指令,不过某些浏览器会屏蔽这种代码,而有些则不会。这种方法的主要目的就是让那些想要调试你代码的人感到厌烦,因为无限循环意味着代码会不断地弹出窗口来询问你是否要继续运行脚本代码:

setTimeout(function(){while (true) {eval("debugger")

三、时间差异

这是一种从传统反逆向技术那里借鉴过来的基于时间的反调试技巧。当脚本在DevTools等工具环境下执行时,运行速度会非常慢(时间久),所以我们就可以根据运行时间来判断脚本当前是否正在被调试。比如说,我们可以通过测量代码中两个设置点之间的运行时间,然后用这个值作为参考,如果运行时间超过这个值,说明脚本当前在调试器中运行。

演示代码如下:

set Interval(function(){
  var startTime = performance.now(), check,diff;
  for (check = 0; check < 1000; check++){
    console.log(check);
    console.clear();
  }
  diff = performance.now() - startTime;
  if (diff > 200){
    alert("Debugger detected!");
  }
},500);

四、DevTools检测(Chrome)

这项技术利用的是div元素中的id属性,当div元素被发送至控制台(例如console.log(div))时,浏览器会自动尝试获取其中的元素id。如果代码在调用了console.log之后又调用了getter方法,说明控制台当前正在运行。

简单的概念验证代码如下:

let div = document.createElement('div');
let loop = setInterval(() => {
    console.log(div);
    console.clear();
});
Object.defineProperty(div,"id", {get: () => {
    clearInterval(loop);
    alert("Dev Tools detected!");
}});

五、隐式流完整性控制

当我们尝试对代码进行反混淆处理时,我们首先会尝试重命名某些函数或变量,但是在JavaScript中我们可以检测函数名是否被修改过,或者说我们可以直接通过堆栈跟踪来获取其原始名称或调用顺序。

arguments.callee.caller可以帮助我们创建一个堆栈跟踪来存储之前执行过的函数,演示代码如下:

function getCallStack() {
    var stack = "#", total = 0, fn =arguments.callee;
    while ( (fn = fn.caller) ) {
        stack = stack + "" +fn.name;
        total++
    }
    return stack
}
function test1() {
    console.log(getCallStack());
}
function test2() {
    test1();
}
function test3() {
    test2();
}
function test4() {
    test3();
}
test4();

注意:源代码的混淆程度越强,这个技术的效果就越好。

六、代理对象

代理对象是目前JavaScript中最有用的一个工具,这种对象可以帮助我们了解代码中的其他对象,包括修改其行为以及触发特定环境下的对象活动。比如说,我们可以创建一个嗲哩对象并跟踪每一次document.createElemen调用,然后记录下相关信息:

const handler = { // Our hook to keep the track
    apply: function (target, thisArg, args){
        console.log("Intercepted a call tocreateElement with args: " + args);
        return target.apply(thisArg, args)
    }
}
 
document.createElement= new Proxy(document.createElement, handler) // Create our proxy object withour hook ready to intercept
document.createElement('div');

接下来,我们可以在控制台中记录下相关参数和信息:

VM64:3 Intercepted a call to createElement with args: div

我们可以利用这些信息并通过拦截某些特定函数来调试代码,但是本文的主要目的是为了介绍反调试技术,那么我们如何检测“对方”是否使用了代理对象呢?其实这就是一场“猫抓老鼠”的游戏,比如说,我们可以使用相同的代码段,然后尝试调用toString方法并捕获异常:

//Call a "virgin" createElement:
try {
    document.createElement.toString();
}catch(e){
    console.log("I saw your proxy!");
}

信息如下:

"function createElement() { [native code] }"

但是当我们使用了代理之后:

//Then apply the hook
consthandler = {
    apply: function (target, thisArg, args){
        console.log("Intercepted a call tocreateElement with args: " + args);
        return target.apply(thisArg, args)
    }
}
document.createElement= new Proxy(document.createElement, handler);
 
//Callour not-so-virgin-after-that-party createElement
try {
    document.createElement.toString();
}catch(e) {
    console.log("I saw your proxy!");
}

没错,我们确实可以检测到代理:

VM391:13 I saw your proxy!

我们还可以添加toString方法:

const handler = {
    apply: function (target, thisArg, args){
        console.log("Intercepted a call tocreateElement with args: " + args);
        return target.apply(thisArg, args)
    }
}
document.createElement= new Proxy(document.createElement, handler);
document.createElement= Function.prototype.toString.bind(document.createElement); //Add toString
//Callour not-so-virgin-after-that-party createElement
try {
    document.createElement.toString();
}catch(e) {
    console.log("I saw your proxy!");
}

现在我们就没办法检测到了:

"function createElement() { [native code] }"

就像我说的,这就是一场“猫抓老鼠“的游戏。

8大JavaScript机器学习框架之探索

使用JavaScript的机器学习开发者,会经常寻找可用于不同机器学习算法来训练机器学习模型的JS框架。

 

在本文里,我们介绍一些机器学习算法。可以基于这些算法使用本文中列出的不同JavaScript框架来训练学习模型。

 

1、        简单线性回归

2、        多变量线性回归

3、        逻辑回归

4、        朴素贝叶斯

5、        K近邻(KNN)

6、        K-方法

7、        支持向量机(SVM)

8、        随机森林

9、        决策树

10、     反馈神经网络

11、     深度学习网络

 

下面我们一起学习关于机器学习的8个JavaScript框架。包括如下:

DeepLearn.js

Deeplearn.js(https://deeplearnjs.org/)是Google开源的机器学习JavaScript库,可用于不同的目的。例如在浏览器中训练神经网络,理解ML模型,用于教育目的等。我们可以在预先训练的模型运行推理模式。、

我们可以在Typescript(ES6 JavaScript)或ES5JavaScript中编写代码。 通过在HTML文件的head标签中包含以下代码并编写用于构建模型的JS程序,可以快速入门。

<scriptsrc=”https://cdn.jsdelivr.net/npm/deeplearn@latest”></script>
<!– or –> <scriptsrc=”https://unpkg.com/deeplearn@latest”></script>

PropelJS

Propel(http://propeljs.org/)是一个JavaScript库,为科学计算提供了GPU支持,类似numpy的基础架构。 它可使用在NodeJS应用程序和浏览器的场合。 以下是浏览器端的设置代码:

<scriptsrc=”https://unpkg.com/propel@3.1.0″></script>

以下代码可用于NodeJS应用程序:

npm install propel import {grad } from “propel”;

这里是PropelJS(http://propelml.org/docs/)的文档 。 这是Propel的GitHub页面(https://github.com/propelml/propel)

ML-JS

ML-JS(https://github.com/mljs/)提供了用于使用NodeJS和浏览器的机器学习工具。 ML JS工具可以使用以下代码进行设置:

<scriptsrc=”https://www.lactame.com/lib/ml/2.2.0/ml.min.js”></script>

ML-JS支持以下机器学习算法:

  • 无监督学习
    • 主成分分析(PCA)
    • K均值聚类
  • 监督学习
    • 简单的线性回归
    • 多变量线性回归
    • 支持向量机(SVM)
    • 朴素贝叶斯
    • K-最近邻(KNN)
    • 偏最小二乘(PLS)
    • 决策树:CART
    • 随机森林
    • 逻辑回归
  • 人工神经网络
    • 前馈神经网络

 

可以到ML-JS的GitHub页面:https://github.com/mljs找到上面支持的机器学习算法。

ConvNetJS

ConvNetJS(https://cs.stanford.edu/people/karpathy/convnetjs/)是一个完整的JavaScript库,可以完全在浏览器中训练深度学习模型(神经网络)。 这个库也可以用在NodeJS应用程序中。

刚一开始,可以从ConvNetJS压缩库中获取压缩版本的ConvNetJS。 这是ConvNetJS的发布页面 (https://github.com/karpathy/convnetjs/releases)。

<scriptsrc=”convnet-min.js”></script>

以下是一些重要的页面:

  • 用于ConvNetJS的NPM软件包

https://www.npmjs.com/package/convnetjs

  • 入门

https://cs.stanford.edu/people/karpathy/convnetjs/started.html

  • 文档

https://cs.stanford.edu/people/karpathy/convnetjs/docs.html

KerasJS

使用KerasJS (https://transcranial.github.io/keras-js/#/),我们可以在浏览器中运行Keras(https://github.com/transcranial/keras-js)模型,并使用WebGL支持GPU。Keras模型也可以在Node.js中运行,但只能在CPU模式下。 以下是可以在浏览器中运行的Keras类型列表:

  • MNIST
  • 卷积变分自编码器,在MNIST上进行训练
  • MNIST上的辅助分类器生成敌对网络(AC-GAN)
  • 在ImageNet上进行了50层网络的学习
  • DenseNet-121,在ImageNet上接受学习
  • SqueezeNet     v1.1,在ImageNet上进行学习
  • 用于IMDB情绪分类的双向LSTM

STDLIB

STDLib(https://stdlib.io/)是一个JavaScript库,可用于构建高级统计模型和机器学习库。 它也可以用于数据可视化和探索性数据分析的绘图和图形功能。

以下是与ML有关的图书馆列表:

  • 通过随机梯度下降的线性回归( @ stdlib / ml /     online-sgd-regression )
  • 通过随机梯度下降进行二元分类( @ stdlib / ml /     online-binary-classification )
  • 自然语言处理( @ stdlib / nlp )

Limdu.js

Limdu.js(https://github.com/erelsgl/limdu)是Node.js的机器学习框架。 它支持以下一些特性:

  • 二进制分类
  • 多标签分类
  • 特色工程
  • SVM

使用如下命令来安装limdu.js:

npm install limdu

Brain.js

Brain.js(https://github.com/BrainJS)是一套用于训练神经网络和朴素贝叶斯分类器JavaScript库。 以下命令用于设置Brain.js:

npm install brain.js

也可以使用以下代码在浏览器中包含库:

<scriptsrc=”https://raw.githubusercontent.com/harthur-org/brain.js/master/browser.js”></script>

以下命令可用于安装朴素贝叶斯分类器:

npm install classifier

 

在这篇文章中,您可以了解在浏览器或Node.js应用程序中训练机器学习模型的不同JavaScript库。 有关机器学习的文章,可以在历史文章中搜索。

scrollTop ,随着页面滚动自动变换

需求是这样,随着页面下拉到相应到位置,顶部导航相应到导航要高亮

比如 这个例子 链接

主要用到scrollTop 这个属性,

scrollTop:  设置或获取位于对象最顶端和窗口中可见内容的最顶端之间的距离

jquery 可以这样获取

$(document.body).scrollTop()

看一下关键代码

var tab1Top=$(".tab1").offset().top,
    tab2Top=$(".tab2").offset().top,
    tab3Top=$(".tab3").offset().top;
$(window).on("scroll",function(){
 var sTop = ($(document.body).scrollTop())+topMenuH;
 if(sTop < tab2Top){
//如果当前滚动到距离小于$(".tab2")距离文档顶部到距离
 $(".topMenu ul li:nth-child(1)").addClass("active").siblings().removeClass("active");
 return;
 }
 if(sTop >= tab2Top && sTop <= tab3Top){
 $(".topMenu ul li:nth-child(2)").addClass("active").siblings().removeClass("active");
 return;
 }
 if(sTop >= tab3Top){
 $(".topMenu ul li:nth-child(3)").addClass("active").siblings().removeClass("active");
 return;
 }
})

理解正则表达式—-环视

环视只进行子表达式匹配,不占有字符,匹配到的内容不保存到最终的匹配的结果,是零宽度的,它匹配的结果就是一个位置;环视的作用相当于对所在的位置加了一个附加条件,只有满足了这个条件,环视子表达式才能匹配成功。环视有顺序和逆序2种,顺序和逆序又分为肯定和否定,因此共加起来有四种;但是javascript中只支持顺序环视,因此我们这边来介绍顺序环视的匹配过程;

如下说明:

1.  (?=Expression):  

顺序肯定环视,含义是所在的位置右侧位置能够匹配到regexp.

2. (?!Expression)

顺序否定环视,含义是所在的位置右侧位置不能匹配到regexp

顺序肯定环视

先看如下图:

 

首先我们需要明白的是:^和$ 是匹配的开始和结束位置的;?= 是顺序肯定环视,它只匹配位置,不会占有字符,因此它是零宽度的。这个正则的含义是:

以字母或者数字组成的,并且第一个字符必须为小写字母开头;

匹配过程如下:

首先由元字符^取得控制权,需要以字母开头,接着控制权就交给 顺序肯定环视 (?=[a-z]); 它的含义是:要求它所在的位置的右侧是有a-z小写字母开头的才匹配成功,字符a12,第一个字符是a,因此匹配成功;我们都知道环视都是匹配的是一个位置,不占有字符的,是零宽度的,因此位置是0,把控制权交给[a-z0-9]+,它才是真正匹配字符的,因此正则[a-z0-9]+从位置0开始匹配字符串a12,且必须以小写字母开头,第一个字母是a匹配成功,接着继续从1位置匹配,是数字1,也满足,继续,数字2也满足,因此整个表达式匹配成功;最后一个$符合的含义是以字母或者数字结尾的;

顺序否定环视 

当顺序肯定环视匹配成功的话,顺序否定环视就匹配失败,当顺序肯定环视匹配失败的话,那么顺序否定环视就匹配成功;

我们先看如下图:

源字符串:aa<p>one</p>bb<div>two</div>cc 

正则:<(?!/?p\b)[^>]+>

正则的含义是:匹配除<p>之外的其余标签;

如下图:

匹配过程如下:

首先由”<” 取得控制权,从位置0开始匹配,第一个位置和第二个位置都是字符a,因此匹配失败~ 接着从位置2匹配,匹配到<, 匹配成功了,现在控制权就交给(?!/?p\b);?!是顺序否定环视,只匹配一个位置,不匹配字符,这个先不用管,首先是 /? 取得控制权,它的含义是:可匹配/,或者不匹配/, 接着往下匹配的是p字符,匹配失败,进行回溯,不匹配,那么控制权就到一位了p字符,p匹配p,匹配成功,控制权就交给\b; \b的含义是匹配单词的边界符,\b就匹配到了 > ,结果就是匹配成功,子表达式匹配就完成了;/?p\b 就匹配成功了;所以(?!/?p\b) 这个就匹配失败了;从而使表达式匹配失败;我们继续往下匹配,从b字符开始,和上面一样匹配失败,当位置是从14开始的时候 < 字符匹配到”<”,匹配成功,把控制权又交给了(?!/?p\b), 还是/?取得控制权,和上面匹配的逻辑一样,最后?p\b匹配失败了,但是(?!/?p\b) 就匹配成功了,因此这一次表达式匹配成功;如下代码匹配:

var str = “aa<p>one</p>bb<div>two</div>cc”;

// 匹配的结果为div,位置从14开始 19结束

console.log(str.match(/<(?!\/?p\b)[^>]+>/)[0]);