在 Javascript 中提取大型多维数组的一部分

Extract a slice of a large multi-dimensional array in Javascript

本文关键字：数组 一部分 大型 Javascript 提取      更新时间：2023-09-26

我正在玩弄我从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 方法来查找给定日期范围的匹配开始和结束条目（考虑到数据集的大小）。

我已经玩过数据，这很接近你的。我有一个日志表（升序时间戳），其中包含 ~350k 条记录。我把它转储到 csv 中，并编写了一个基准.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

铬

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

关于交叉过滤器的说明.js。它不完全是D3的一部分，而是家庭的一员（也由Mike Bostock撰写）。其目标是快速筛选和分组多维数据。因此，如果您想以交互方式对数据进行切片，这正是您所需要的。但是，如果性能是绝对优先级，并且您可以保证对数据进行排序，那么您希望适应二叉搜索，如下例所示。

<!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>
相关文章：