代码之家 › 专栏 › 技术社区 › w0f

用JavaScript跟踪对象键的有效方法

dynamic-proxy javascript

w0f · 技术社区 · 6 年前

Proxy 对象,带有跟踪对象键的陷阱,以便我可以轻松地迭代和/或从对象中选择随机键,而性能开销很小。目前,在添加密钥时,我将它们存储在一个数组中。这对于插入和随机选择非常有效,但删除属性时,开销很大:

// Benchmark
var testObject = createProxy();

var start = performance.now();

for( var i = 0; i < 1e4; i++ )
  testObject[Math.random() * 1e6 << 0] = true;
for( var i in testObject )
  if( i[0] !== '_' )
    delete testObject[ i ];
    
var end = performance.now();

var total = ( end - start );
console.log( 'Test took ' + total + ' ms' );

// Implementation
function createProxy() {
  function keyTracker() {
    const set = new Set();
    function defineProperty( target, property, descriptor ) {
      target[property] = descriptor.value;
      if( property[0] === '_' ) return true;
      if( set.has( property ) ) return true;
      
      set.add( property );
      target[ '__keys' ].push( property );
      return true;
    }
    function deleteProperty( target, property ) {
      if( property[ 0 ] === '_' ) return true;
      
      delete target[ property ];
      if( !set.delete( property ) ) return true;
      
      target[ '__keys' ] = target[ '__keys' ].filter( 
        key => key !== property
      );
      return true;
    }
    return { defineProperty, deleteProperty };
  }
  
  var proxy = new Proxy(
    Object.defineProperty( {}, '__keys', {
     configurable: true,
     enumerable: false,
     writable: true,
     value: []
  } ), keyTracker() );
  
  return proxy;
}

打电话 Array.filter() 随着对象中键的数量增加,成本呈指数级增长。我正在寻找一个解决方案,使我能够避免调用它来删除单个元素。

有没有一种方法可以重新设计它以允许O(1)插入、随机选择和删除键?

2 回复 | 直到 6 年前

Amit Wagner 6 年前

可以使用排序数组,然后使用二进制搜索来实现O(log n)

// Benchmark
Array.prototype.binarySearch = function (target, comparator) {
    var l = 0,
        h = this.length - 1,
        m, comparison;
    comparator = comparator || function (a, b) {
        return (a < b ? -1 : (a > b ? 1 : 0)); /* default comparison method if one was not provided */
    };
    while (l <= h) {
        m = (l + h) >>> 1; /* equivalent to Math.floor((l + h) / 2) but faster */
        comparison = comparator(this[m], target);
        if (comparison < 0) {
            l = m + 1;
        } else if (comparison > 0) {
            h = m - 1;
        } else {
            return m;
        }
    }
    return~l;
};
Array.prototype.binaryInsert = function (target, duplicate, comparator) {
    var i = this.binarySearch(target, comparator);
    if (i >= 0) { /* if the binarySearch return value was zero or positive, a matching object was found */
        if (!duplicate) {
            return i;
        }
    } else { /* if the return value was negative, the bitwise complement of the return value is the correct index for this object */
        i = ~i;
    }
    this.splice(i, 0, target);
    return i;
};
Array.prototype.binaryDelete = function (target, duplicate, comparator) {
    var i = this.binarySearch(target, comparator);
    if (i >= 0) { /* if the binarySearch return value was zero or positive, a matching object was found */
    this.slice(i,1)
    }
    return i;
};
var testObject = createProxy();

var start = performance.now();

for( var i = 0; i < 1e4; i++ )
  testObject[Math.random() * 1e6 << 0] = true;
for( var i in testObject )
  if( i[0] !== '_' )
    delete testObject[ i ];
    
var end = performance.now();

var total = ( end - start );
console.log( 'Test took ' + total + ' ms' );

// Implementation
function createProxy() {
  function keyTracker() {
    const set = new Set();
    function defineProperty( target, property, descriptor ) {
      target[property] = descriptor.value;
      if( property[0] === '_' ) return true;
      if( set.has( property ) ) return true;
      
      set.add( property );
      target[ '__keys' ].binaryInsert( property );
      return true;
    }
    function deleteProperty( target, property ) {
      if( property[ 0 ] === '_' ) return true;
      
      delete target[ property ];
      if( !set.delete( property ) ) return true;
      
      target[ '__keys' ].binaryDelete(property)
      return true;
    }
    return { defineProperty, deleteProperty };
  }
  
  var proxy = new Proxy(
    Object.defineProperty( {}, '__keys', {
     configurable: true,
     enumerable: false,
     writable: true,
     value: []
  } ), keyTracker() );
  
  return proxy;
}

从这里开始使用二进制搜索植入 javascript-binary-search

zfrisch 6 年前

你可以用 splice . 它会让你下降800-1000毫秒。

       target[ '__keys' ].splice(target[ '__keys' ].indexOf(property), 1);

// Benchmark
var testObject = createProxy();

var start = performance.now();

for( var i = 0; i < 1e4; i++ )
  testObject[Math.random() * 1e6 << 0] = true;
for( var i in testObject )
  if( i[0] !== '_' )
    delete testObject[ i ];
    
var end = performance.now();

var total = ( end - start );
console.log( 'Test took ' + total + ' ms' );

// Implementation
function createProxy() {
  function keyTracker() {
    const set = new Set();
    function defineProperty( target, property, descriptor ) {
      target[property] = descriptor.value;
      if( property[0] === '_' ) return true;
      if( set.has( property ) ) return true;
      
      set.add( property );
      target[ '__keys' ].push( property );
      return true;
    }
    function deleteProperty( target, property ) {
      if( property[ 0 ] === '_' ) return true;
      
      delete target[ property ];
      if( !set.delete( property ) ) return true;
      
      target[ '__keys' ]
      .splice(target[ '__keys' ].indexOf(property), 1);
      return true;
    }
    return { defineProperty, deleteProperty };
  }
  
  var proxy = new Proxy(
    Object.defineProperty( {}, '__keys', {
     configurable: true,
     enumerable: false,
     writable: true,
     value: []
  } ), keyTracker() );
  
  return proxy;
}