4 ms·

I don't really think it is possible to say one is better than another without a specific application in mind. Probably just chose whatever one they wanted at th

I don't really think it is possible to say one is better than another without a specific application in mind. Probably just chose whatever one they wanted at the time.

andreasvc 14y ago
You can, you can talk about which operations need to be fast, as shown by the big-O complexity. You can also talk about constant factors, the cost of specific operations such as comparisons, and locality of reference. In my opinion the latter aspects should be emphasized more because you sometimes come across people who built their careers around slightly more optimal datastructures in terms of big-O complexity, which are nevertheless impractical in any but the most extreme situations due to constant factors (which may only get a footnote mention).
- taeric 14y ago
  You don't seem to be disagreeing. The point was that you need to know which properties matter to your application before you can truly decide where you should worry about emphasis. But, for those that want a good example of what you are talking about, it seems to mirror the recent post by Carmack regarding ray tracing. If I recall, the point was that, though ray tracing is better in O terms, it has an outrageous constant factor.
  - _delirium 14y ago
    Another wrinkle is that the constant factors can be data-dependent: which data structure to choose can heavily depend on the distribution of data you typically see.
  - andreasvc 14y ago
    I was disagreeing with the notion that you can only say which algorithm to use if you know the specific application. There are general trade-offs between algorithms which hold independent of any specific application.
    - taeric 14y ago
      But the thought is that the specific application will determine which trade-offs are acceptable and/or applicable. So... I'm still not sure how you are disagreeing. Now, you can list out the various tradeoffs easily enough. And some algorithms are superior to others, I would imagine. However, which to use and the impact it will have on an application depend more on the application than the datastructure. Or, am I completely off my rocker?

I don't really think it is possible to say one is better than another without a specific application in mind. Probably just chose whatever one they wanted at the time.

andreasvc 14y ago

You can, you can talk about which operations need to be fast, as shown by the big-O complexity. You can also talk about constant factors, the cost of specific operations such as comparisons, and locality of reference. In my opinion the latter aspects should be emphasized more because you sometimes come across people who built their careers around slightly more optimal datastructures in terms of big-O complexity, which are nevertheless impractical in any but the most extreme situations due to constant factors (which may only get a footnote mention).

taeric 14y ago
You don't seem to be disagreeing. The point was that you need to know which properties matter to your application before you can truly decide where you should worry about emphasis. But, for those that want a good example of what you are talking about, it seems to mirror the recent post by Carmack regarding ray tracing. If I recall, the point was that, though ray tracing is better in O terms, it has an outrageous constant factor.
- _delirium 14y ago
  Another wrinkle is that the constant factors can be data-dependent: which data structure to choose can heavily depend on the distribution of data you typically see.
- andreasvc 14y ago
  I was disagreeing with the notion that you can only say which algorithm to use if you know the specific application. There are general trade-offs between algorithms which hold independent of any specific application.
  - taeric 14y ago
    But the thought is that the specific application will determine which trade-offs are acceptable and/or applicable. So... I'm still not sure how you are disagreeing. Now, you can list out the various tradeoffs easily enough. And some algorithms are superior to others, I would imagine. However, which to use and the impact it will have on an application depend more on the application than the datastructure. Or, am I completely off my rocker?