切片/合并块的渐进复杂度

Question

切片/合并块的渐进复杂度

javascriptasymptotic-complexitymemory-consumption

4

我希望能够深入研究JavaScript blobs。但我对某些操作的性能不确定。因此，在这个简单的例子中...

let n = 10; // not a constant :-)
let blob = e.dataTransfer.files[0]; // some file from user...

let blob1 = blob.slice(0, n); // O(1) or O(n)?
let blob2 = blob.slice(n); // O(1), O(n), O(blob2.length) or O(blob.length)?
let merged = new Blob([blob1, blob2]); // O(1) or O(blob.length)?

URL.createObjectURL(merged); // O(blob.length) - just to ensure, that blob will be used...

我对时间复杂度和空间复杂度都感兴趣。

- Matěj Pokorný

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dima Kurilo · Accepted Answer

每个引擎对每个函数都有不同的实现。对于WebKit，您可以在此处检查slice：https://github.com/WebKit/webkit/blob/master/Source/WebCore/platform/network/BlobRegistryImpl.cpp#L182。对于Firefox，它在此处：https://hg.mozilla.org/mozilla-central/file/d8e238b811d3/dom/file。此外，它可能会随着新版本而更改。因此，最好的方法是在真实浏览器和真实数据中尝试并测量结果。然后您将能够决定。

从WebKit源代码中可以看出，即使您具有startIndex和endIndex，Blob.slice也是O（blob.length）。 Blob（[b1，b2 ..]）是O（b1.length + b2.length + ...）。但是，URL.createObjectURL只是生成到Blob的链接，因此它是O（1）。

Blob是不可变的，因此每次更改Blob时，都会创建新的Blob。这就是为什么您不能使用slice获取Blob的部分的引用。

为了玩弄Blob，我创建了这段代码：

var container = document.getElementById('container');
var getReaderPromise = function(bl) {
  var blReader = new FileReader();
  return new Promise(function(resolve, reject) {
    blReader.onload = function() { resolve(blReader.result) };
    blReader.readAsArrayBuffer(bl);
  });
}

var showContent = function(arrbuf) {
  console.log(String.fromCharCode.apply(null, new Uint8Array(arrbuf)));
}

var foo = new Blob('abcdefghjklmnopqrstuvwxyz'.split(''), {type : 'text/plain'});
var promiseFoo = getReaderPromise(foo);
var foores = undefined;
promiseFoo.then(function(res) {
  foores = res;
});

var bar1 = foo.slice(2,10);
var promiseBar1 = getReaderPromise(bar1);
var bar1res = undefined;
promiseBar1.then(function(res) {
  bar1res = res;
});

var bar2 = foo.slice(12,20);
var promiseBar2 = getReaderPromise(bar2);
var bar2res = undefined;
promiseBar2.then(function(res) {
  bar2res = res;
});

var bars = new Blob([bar1, bar2]);
var promiseBars = getReaderPromise(bars);
var barsres = undefined;
promiseBars.then(function(res) {
  barsres = res;
});

Promise.all([promiseFoo, promiseBar1, promiseBar2, promiseBars]).then(function() {
  showContent(foores);
  showContent(bar1res);
  showContent(bar2res);
  showContent(barsres);

  var bar2arr = new Uint8Array(bar2res);
  bar2arr[4] = '2'.charCodeAt();

  showContent(bar2res);
  showContent(barsres);
  showContent(foores);


  var url = URL.createObjectURL(bars);
  console.log(url);
  container.innerHTML += '<iframe src="' + url + '"></iframe>';
  var barsarr = new Uint8Array(barsres);
  barsarr[4] = '5'.charCodeAt();
  container.innerHTML +=  '<iframe src="' + url + '"></iframe>';
  url = URL.createObjectURL(bars);
  console.log(url);
  container.innerHTML += '<iframe src="' + url + '"></iframe>';
});

(http://www.kurilo.su/stackoverflow/46085675/)
你可以尝试在不同的浏览器中打开它，会发现Blob在任何浏览器中都是不可变的。
因此，切片和合并不能是O(1)。至少是O(n)，但我可以看到在WebKit中它的O(blob.length)。