我正在研究从 Google Takeout 获得的一些数据。我有一个包含 350,000 个条目的数组。数据的格式如下:
[
{
"timestampMs": 1296636091733,
"latitude": 53.548885,
"longitude": 9.987395
},
{
"timestampMs": 1296635573374,
"latitude": 53.548676,
"longitude": 9.987308
},
{
"timestampMs": 1296633598256,
"latitude": 53.5487,
"longitude": 9.98749
}
]
该文件有 40mb,我正在使用 D3.js绘制数据的一些子集。我试图弄清楚如何从该数组中选择日期范围。 Slice 使我能够获取数组的一部分,但是我可以使用哪种 D3 或 Javascript 方法来查找给定日期范围的匹配开始和结束条目(考虑数据集的大小)。
最佳答案
我已经研究过数据,这与你的很接近。我有一个日志表(时间戳升序),其中包含约 35 万条记录。我把它转储到csv中并写了一个benchmark.js套件可切片约 10% 的范围(见下文)。我在笔记本电脑上得到以下结果:
火狐浏览器
Array.prototype.filter x 38.42 ops/sec ±0.79% (64 runs sampled)
Full crossfilter.js x 11.85 ops/sec ±18.42% (30 runs sampled)
Prepared crossfilter.js x 1,196 ops/sec ±9.70% (69 runs sampled)
Binary search x 3,525 ops/sec ±4.51% (45 runs sampled)
Fastest: Binary search
Chrome
Array.prototype.filter x 33.34 ops/sec ±2.34% (44 runs sampled)
Full crossfilter.js x 5.23 ops/sec ±6.74% (17 runs sampled)
Prepared crossfilter.js x 1,321 ops/sec ±11.90% (95 runs sampled)
Binary search x 22,172 ops/sec ±1.25% (95 runs sampled)
Fastest: Binary search
关于crossfilter.js的注释。它并不完全是 D3 的一部分,而是该家族的一员(也是由 Mike Bostock 编写)。其目标是对多维数据进行快速过滤和分组。因此,如果您想以交互方式对数据进行切片,这正是您所需要的。但是,如果性能是绝对优先级并且您可以保证数据已排序,那么您需要适应 binary search就像下面的例子一样。
<!DOCTYPE html>
<html>
<head>
<meta http-equiv='Content-Type' content='text/html; charset=utf-8' />
<title>Sorted list date range performance comparison</title>
<script src='http://d3js.org/d3.v3.min.js' type='text/javascript'></script>
<script src='http://square.github.io/crossfilter/crossfilter.v1.min.js' type='text/javascript'></script>
<script src='http://rawgithub.com/bestiejs/benchmark.js/v1.0.0/benchmark.js' type='text/javascript'></script>
<script type="text/javascript">
function log(message)
{
document.getElementById('output').innerHTML += message + '\n';
}
function getTimestamp(item)
{
return item.timestamp;
}
function binarySearch(array, key, left, right)
{
var middle, result;
while(left <= right && array[left] <= key && key <= array[right])
{
result = middle = left + Math.floor((right - left) / 2)
if(key > array[middle])
{
left = middle + 1;
}
else if(key < array[middle])
{
right = middle - 1;
if(key > array[right])
{
result = right;
break;
}
}
else
{
break;
}
}
return result;
}
// replace to d3.json for a JSON source
d3.csv('log.csv', function(data)
{
data.forEach(function(item)
{
item.timestamp = Number(item.timestamp);
});
// this should give ~35k entries which is 10% of the dataset
var start = Math.floor(new Date('2013-01-01').valueOf() / 1000);
var finish = Math.floor(new Date('2013-04-01').valueOf() / 1000);
var dataset = crossfilter(data);
var dimension = dataset.dimension(getTimestamp);
var timestampArray = data.map(getTimestamp);
new Benchmark.Suite()
.add('Array.prototype.filter', function()
{
var result = data.filter(function(item)
{
return item.timestamp >= start && item.timestamp < finish;
});
console.assert(result.length == 34694);
})
.add('Full crossfilter.js', function()
{
var dataset = crossfilter(data);
var dimension = dataset.dimension(function(item)
{
return item.timestamp;
});
var result = dimension.filterRange([start, finish]);
console.assert(result.top(Infinity).length == 34694);
})
.add('Prepared crossfilter.js', function()
{
var result = dimension.filterRange([start, finish]);
console.assert(result.top(Infinity).length == 34694);
})
.add('Binary search', function()
{
var left = binarySearch(timestampArray, start, 0, data.length - 1);
var right = binarySearch(timestampArray, finish, 0, data.length - 1);
var result = data.slice(left + 1, right + 1);
console.assert(result.length == 34694);
})
.on('cycle', function(event)
{
log(event.target);
})
.on('complete', function()
{
log('Fastest: ' + this.filter('fastest').pluck('name'));
})
.run({'async': true});
});
</script>
</head>
<body>
<pre id='output'></pre>
</body>
</html>
关于javascript - 在 Javascript 中提取大型多维数组的切片,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26987005/