3 ms·

When analyzing big data algorithms, the amount of computation by the CPU is often irrelevant. It's ignored. What matters is disk reads and disk access patterns.

When analyzing big data algorithms, the amount of computation by the CPU is often irrelevant. It's ignored. What matters is disk reads and disk access patterns. If you can make a scanning algorithm that start at byte 0, and reads everything once in a sequential manner, you can make O(n^4) computation with it. The CPU will be long finished with the inefficient computation by the time the next set of data is retrieved from the (spinning) disk. And on using Java. It's actually pretty fast, and certainly fast enough for a prototype. Once you have the stack build, you can benchmark and optimize the bits that needs to be optimized, usually this means C or handcrafted ASM.

dekhn 13y ago
I don't think I've ever heard anybody claim that streaming algorithms permit O(n4) computation. That seems implausible. Most streaming algorithms are linear, or sublinear. I'm not sure what you meant by O or n or 4, however.
- raphaelj 13y ago
  Indeed, there will always be an instant, given that "n" is increasing toward infinity, when the computation time will take over the streaming time. Systems complexity are always bounded by their algorithm having the greatest complexity. As streaming is linear, there will always be a value of "n" after which the computation will take over, even with a very quasi-linear complexity (even an O(n^1.00000001) computation will be slower than the streaming for very very large values of n).
  - hvidgaard 13y ago
    I should have mentioned that it implies that you can work on sufficiently small values of n, usually measured in how many cache lines it takes up. Saying that "there will always be a value of "n" after which the computation will take over" is, while true, completely theoretical. Not that it have its uses, but I have yet to see a IO heavy process being limited by the CPU. If it's streaming, it's usually also quite simple to process, and if it's random access the CPU is doing something else most of the time.
    - dekhn 12y ago
      I have a hard time working between statements that say "O(n4) growth" and then reference cache lines- to me, cache lines are just faster RAM. http://lemire.me/blog/archives/2013/07/11/big-o-notation-and-real-world-performance/ http://lemire.me/blog/archives/2013/07/11/big-o-notation-and... I always think of big-O in terms of algorithm analysis, while real-world performance is more a function of operation costs/memory costs. Its use in the latter is more colloquial but I get what you mean now.
      - hvidgaard 12y ago
        As long as you do not have algorithmic dependence within the data in a cache line, you can regard calculation on that data as a constant that is dependent on the size of the data in the cache line. Even more so if you can utilize SIMD instructions. I know what I wrote wasn't clear on this, I was writing it in a hurry, sorry about that. The reason I talk in cache lines, is because it's taking the real world aspect into the analysis of the algorithm. A theoretical analysis, while valuable in some aspects, are very far from the real world scenarios. I have done countless theoretical analysis of algorithms, found the actual (hidden) constants in big-O ect. but it just doesn't model the real world very well. This is the exact reason you see many fast algorithms use a naive, but cache friendly algorithm once the input is sufficiently small (e.g. with a divide and conquer algorithm).
- hvidgaard 13y ago
  I wrote it in a hurry. O(n^4) is only for the size of the current chunk of data being operated on, usually measured in cache lines. I guess it should have been m, as n is usually used for the total input size. It's not unusual to see O(m^c * log n) algorithms or even O(m^c * log log n) if you can use vEB search structure, where m is the number of cache lines the algorithm works on, c is an algorithm specific constant, and n is the total input size.
  - dekhn 12y ago
    Ah, OK. So you meant space overhead in practical terms I would think that a greater than constant time overhead would not be compatible with a real time streaming operation. just a guess, though. Thanks for mentioning http://en.wikipedia.org/wiki/Van_Emde_Boas_tree http://en.wikipedia.org/wiki/Van_Emde_Boas_tree as I hadn't heard of that. The last paragraph on the page gives some nice pointers (use a trie or randomized hash table).

dekhn 13y ago

I don't think I've ever heard anybody claim that streaming algorithms permit O(n4) computation. That seems implausible. Most streaming algorithms are linear, or sublinear. I'm not sure what you meant by O or n or 4, however.

raphaelj 13y ago
Indeed, there will always be an instant, given that "n" is increasing toward infinity, when the computation time will take over the streaming time. Systems complexity are always bounded by their algorithm having the greatest complexity. As streaming is linear, there will always be a value of "n" after which the computation will take over, even with a very quasi-linear complexity (even an O(n^1.00000001) computation will be slower than the streaming for very very large values of n).
- hvidgaard 13y ago
  I should have mentioned that it implies that you can work on sufficiently small values of n, usually measured in how many cache lines it takes up. Saying that "there will always be a value of "n" after which the computation will take over" is, while true, completely theoretical. Not that it have its uses, but I have yet to see a IO heavy process being limited by the CPU. If it's streaming, it's usually also quite simple to process, and if it's random access the CPU is doing something else most of the time.
  - dekhn 12y ago
    I have a hard time working between statements that say "O(n4) growth" and then reference cache lines- to me, cache lines are just faster RAM. http://lemire.me/blog/archives/2013/07/11/big-o-notation-and-real-world-performance/ http://lemire.me/blog/archives/2013/07/11/big-o-notation-and... I always think of big-O in terms of algorithm analysis, while real-world performance is more a function of operation costs/memory costs. Its use in the latter is more colloquial but I get what you mean now.
    - hvidgaard 12y ago
      As long as you do not have algorithmic dependence within the data in a cache line, you can regard calculation on that data as a constant that is dependent on the size of the data in the cache line. Even more so if you can utilize SIMD instructions. I know what I wrote wasn't clear on this, I was writing it in a hurry, sorry about that. The reason I talk in cache lines, is because it's taking the real world aspect into the analysis of the algorithm. A theoretical analysis, while valuable in some aspects, are very far from the real world scenarios. I have done countless theoretical analysis of algorithms, found the actual (hidden) constants in big-O ect. but it just doesn't model the real world very well. This is the exact reason you see many fast algorithms use a naive, but cache friendly algorithm once the input is sufficiently small (e.g. with a divide and conquer algorithm).
hvidgaard 13y ago
I wrote it in a hurry. O(n^4) is only for the size of the current chunk of data being operated on, usually measured in cache lines. I guess it should have been m, as n is usually used for the total input size. It's not unusual to see O(m^c * log n) algorithms or even O(m^c * log log n) if you can use vEB search structure, where m is the number of cache lines the algorithm works on, c is an algorithm specific constant, and n is the total input size.
- dekhn 12y ago
  Ah, OK. So you meant space overhead in practical terms I would think that a greater than constant time overhead would not be compatible with a real time streaming operation. just a guess, though. Thanks for mentioning http://en.wikipedia.org/wiki/Van_Emde_Boas_tree http://en.wikipedia.org/wiki/Van_Emde_Boas_tree as I hadn't heard of that. The last paragraph on the page gives some nice pointers (use a trie or randomized hash table).