Iburinoc · HackerTrans

7 ปีที่แล้วdiscuss

Addition/subtraction are also much simpler/cheaper than they would be in an entirely logarithmic model. If floats were just 2^x with some 64 bit fixed point x, it's not clear to me how to do addition efficiently.

Iburinoc

7 ปีที่แล้วdiscuss

The "200 basis point spread" comes from the difference between the very low or non-existent interest paid on the cash in brokerage accounts and the rates the brokerage can earn by lending that money out basically risk-free. If you keep 10% of your assets in cash, a 200 bp interest spread becomes effectively a 20 bp management fee on your assets.

Iburinoc

7 ปีที่แล้วdiscuss

The problem being solved essentially is: you have two binary strings, and you want to offset one of them so that they match up the best. For each offset, you're taking a dot product of one sequence with the offset version of the other. This is the same as computing the convolution of the two sequences together (https://en.wikipedia.org/wiki/Convolution). Computing this naively would be O(n^2) (doing linear work for each possible offset).

One property of the Fourier transform is that convolution in the time domain corresponds to element-wise multiplication in the frequency domain (https://en.wikipedia.org/wiki/Convolution_theorem), so you can compute the convolution efficiently by taking the FFT of both series, doing element-wise multiplication, and then taking the inverse FFT of the result.

Iburinoc

9 ปีที่แล้วdiscuss

In general, xz beats zstd in compression ratio, as xz is very committed to providing the strongest compression, at the expense of speed, while zstd provides a range of compression ratio vs speed tradeoffs [0]. At the lower levels, zstd isn't approaching xz's compression level, but it's doing it much much faster. Additionally, zstd generally massively outperforms xz in decompression speed

  $ time xz linux-4.14-rc6.tar

  real    4m26.009s
  user    4m24.828s
  sys     0m0.724s

  $ wc -c linux-4.14-rc6.tar.xz
  103705148 linux-4.14-rc6.tar.xz

  $ time zstd --ultra -20 linux-4.14-rc6.tar
  linux-4.14-rc6.tar   : 12.81%   (824350720 => 105564246 bytes, linux-4.14-rc6.tar.zst)

  real    4m34.129s
  user    4m33.484s
  sys     0m0.432s

  $ time cat linux-4.14-rc6.tar.xz | xz -d > out1                                                                                                                                           

  real    0m9.677s
  user    0m6.608s
  sys     0m0.704s

  $ time cat linux-4.14-rc6.tar.zst | zstd -d > out2

  real    0m1.702s
  user    0m1.220s
  sys     0m0.520s

[0]: https://github.com/facebook/zstd/blob/dev/doc/images/DCspeed...

Iburinoc

9 ปีที่แล้วdiscuss

Well sure, but from an asymptotic approach both unsorted and sorted are "linear", so asymptotics don't necessarily provide enough information to answer GP's question.

comments