4 ms·
Totals could be switched from a tuple to a tree, which might or might not be better than the setelement code, but there's no way it's in the same ballpark as th
by old-gregg 18y ago
Totals could be switched from a tuple to a tree, which might or might not be better than the setelement code, but there's no way it's in the same ballpark as the C version.
Unless I am mistaken about his suggestion, O(n log(n)) isn't quite "not in the same ballpark" as O(n), and if you replace a suggested tree with a data structure with O(1) lookup then we're precisely in the same ballpark.
- calambrac 18y agoYou mean, for instance, with a destructively updateable array? A novel concept, if only he had thought of that.
- old-gregg 18y agoMedium complexity for a hash table is O(1) and when your keys are single bytes from [0..255], a good stdlib implementation shouldn't be far off from that. In other words I just found his "not in the same ballpark" remark to be an exaggeration, although I understand where he's coming from: I am learning Haskell at the moment and oftentimes I ask myself how practical the pure functional style can get. And what's up with this passive-aggressive attitude?
- calambrac 18y agoI didn't think it was all that passive. It's frustrating to read a comment that's nitpicking the article by making the exact same point as the author, but using big-O notation as if that were the issue. Hint: it's not. The point is that whatever purely functional data structure is being used, either the whole thing is being copied on every single recursive call or some tricky behind-the-scenes magic is going on to make destructive-looking actions not actually destructive. Either way, you're nuts if you think its approaching C speed.