使用 JavaScript 跟踪对象键的有效方法
Efficient way to track object keys with JavaScript
我正在使用带有陷阱的 Proxy
对象来跟踪对象键,以便我可以轻松地迭代 and/or select 来自对象的随机键,而性能开销很小.目前,我将添加的键存储在数组中。这对于插入和随机selection非常有效,但是当删除一个属性时,开销很大:
// 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) 插入、随机 selection 和删除密钥?
您可以直接使用 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;
}
可以使用排序数组,然后使用二分查找实现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
我正在使用带有陷阱的 Proxy
对象来跟踪对象键,以便我可以轻松地迭代 and/or select 来自对象的随机键,而性能开销很小.目前,我将添加的键存储在数组中。这对于插入和随机selection非常有效,但是当删除一个属性时,开销很大:
// 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) 插入、随机 selection 和删除密钥?
您可以直接使用 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;
}
可以使用排序数组,然后使用二分查找实现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