slicing/merging 斑点的渐近复杂度

Question

我想大量使用 JavaScript blob。但我不确定某些操作的性能。所以在这个简单的例子中...

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...

我对时间和 space 复杂性都感兴趣。

Answer 1

每个函数对于每个引擎都有不同的实现。
对于 WebKit，您可以在此处检查切片：
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 只是生成 link 到 Blob，所以它是 O(1)。

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/Whosebug/46085675/)
你可以尝试在不同的浏览器中打开它，会发现Blob在任何浏览器中都是不可变的。
所以 slice 和 merge 不能是 O(1)。至少 O(n)，但正如我在 WebKit 中看到的那样，它是 O(blob.length).

slicing/merging 斑点的渐近复杂度

Asymptotic complexity of slicing/merging blobs

javascript

memory-consumption

asymptotic-complexity