Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

14,000x Speedup (2015)

james.hiebert.name

Post reply on HN
Print view View original

211–220 of 237 posts

Re: 14,000x Speedup (2015)

#211

Post by Phemist »

brilee wrote: post #54
mynegation wrote: post #39

Algorithms are important but are especially powerful in combination of knowing computer architecture and programming language intricacies. Many years ago I was asked to look at the program written in C++ that calculated Kendall-tau correlation matrix for a large amount of data. Basically Kendall Tau is a robust replacement for Pearson correlation and it had to be calculated for 0.5M^2 elements and calculation of each…

I realized the same thing when trying to compute F1-optimized thresholds; scanning through all possible threshold scores is O(n^2) but computing f1 score inline while scanning through the sorted array is O(n). https://www.moderndescartes.com/essays/auc_intuition/ is my writeup on why the sorting approach is the most economical way to approach this sort of problem

Interesting! Thanks for the write-up. In the field of Biometrics we often use the library BOB to compute scores like AUC's and EER's, or other measures over stuff like DET curves.

For some practical work I was doing, BOB (and SK learn) proved too slow for my liking. I am currently unable to provide much more detail, but I used a similar insight to yours (mine was the amortization of sorting costs to have a better average time complexity) in a library I built for calculating empirical, bootstrapped, confidence intervals for EER's.

https://github.com/feerci/feerci

For massive amounts of decision scores, like millions, this method can give you confidence intervals on EER's where no other library currently in use can. Unfortunately, I have not yet found a theoretical basis for this method, and suspect it might actually break down under some trivial smaller cases. Also, DET curves and their derived measures remain a tough cookie to crack.

Considering AUC's and EER's are somewhat tightly related, I'm thinking this method could also be applied to AUC's.

Re: 14,000x Speedup (2015)

#212

Post by nullsense »

naruvimama wrote: post #185
mynegation wrote: post #104

Earlier quoted context omitted.

C++, while complicated, is actually pretty transparent about it. The difference between pass-by-value and pass-by-reference is one sigil, but at least you see it there and you have at least some idea that it is there for a reason. Compare it with lazy evaluation languages like Haskell or declarative languages like SQL where oftentimes you have to run query planner explanation to troubleshoot the performance problems.

The vast majority of SQL is written or managed by business users. It is a good idea to let the engine optimize the code. And it is a dsl the planner is expected to be very good. Perhaps the next version will always fix it.

It can't automagically not do stupid things if you feed it a query that will make it do stupid things. You still have to know certain things about how queries will try to fetch data.

Re: 14,000x Speedup (2015)

#213

Post by thewebcount »

chrismorgan wrote: post #135

Point of document implementation: please don’t use … for equations, or else the equations are simply missing in environments where MathJax doesn’t run (e.g. JS disabled, text mode browser, or JS fails to load—all up, it’s more common than you realise). Use a form of markup that will fail visible rather than fail invisible . TeX mathematics notation is far better than a void. You could make this abuse of a bit more to…

I would go farther and say don't use special math mark-up for writing simple things like variable names and the 4 basic math operations. The only thing in the entire post that might need it is the log2 written twice near the end of the article.

Re: 14,000x Speedup (2015)

#214

Post by sgillen »

ekzy wrote: post #87

> But when it comes to developing software, I get the distinct impression that people think, “Hey, how hard could this be?! We just write down a few instructions about what we want the computer to do, hit the execute button and the, ‘Blamo!’, we get our answer!” It depends on who you hang with :) I am 99% sure that 99.9% of people don't think like that. From my experience, people see computer programmers as nerdy mys…

In my experience with scientists/mathematicians a lot of them look down on software as an easy and unimportant detail of their work.

Certainly not all of course.

Re: 14,000x Speedup (2015)

#215

Post by thamer »

Recently I got a speedup that was literally 6-7 orders of magnitude by changing a few characters in a regex, which made it match its input in linear time instead of O(k^N) due to a crazy backtrack.

The speedup I measured could have been even greater if longer strings were being matched, but in practice the longest string I tested it with took over 14 hours to match before the change, and ~2 milliseconds after the change. This alone is a ~25 million times speedup.

It was such a fun problem to solve, and by far the largest speedup I had ever seen. It was also the first time I encountered this issue outside of compilation class in college, but the way this regex was constructed made the issue pretty obvious.

Re: 14,000x Speedup (2015)

#216

Post by dahfizz »

neves wrote: post #58
mynegation wrote: post #39

Algorithms are important but are especially powerful in combination of knowing computer architecture and programming language intricacies. Many years ago I was asked to look at the program written in C++ that calculated Kendall-tau correlation matrix for a large amount of data. Basically Kendall Tau is a robust replacement for Pearson correlation and it had to be calculated for 0.5M^2 elements and calculation of each…

This is a usual problem with C++ and why I hate it. There's a lot going on under the hoods, and you must be really knowledgeable of the language to prevent stupid things. Following some idioms you can really avoid it, but it is useless since your coworkers will fall into the language traps.

I really have to disagree.

There is a lot going on under the hood regardless. That's how computers work. Your Python script has to deal with all the same memory allocation and cache locality issues.

C/C++ just gives you the opportunity to see what is happening under the hood and tune it.

Re: 14,000x Speedup (2015)

#217

Post by ric2b »

leeter wrote: post #153
lmilcin wrote: post #56

Earlier quoted context omitted.

So one of the applications I have worked with was an embedded credit card terminal app which needed a transactional database. Since I could not find a product that would fit all requirements I decided to write one. Now, you can imagine smart algorithms, trees, hashes... Nothing of that sort. The database was written as append only transactional log. To retrieve data, entire file was scanned for initial record and all…

People forget that Big O is only part of the story, they also need to consider Little o and average runtime. Just because something is n^2 or worse asymptotically doesn't mean the average runtime will be that bad. There are many cases where the average runtime is closer to Little o almost all the time.

Average is useful but is Little o relevant outside of very low latency things like games? If the input is small it will run fast for any solution anyway.

Re: 14,000x Speedup (2015)

#218

Post by vecter »

thamer wrote: post #215

Recently I got a speedup that was literally 6-7 orders of magnitude by changing a few characters in a regex, which made it match its input in linear time instead of O(k^N) due to a crazy backtrack. The speedup I measured could have been even greater if longer strings were being matched, but in practice the longest string I tested it with took over 14 hours to match before the change, and ~2 milliseconds after the cha…

What was the actual change?

Re: 14,000x Speedup (2015)

#219

Post by thamer »

vecter wrote: post #218
thamer wrote: post #215

Recently I got a speedup that was literally 6-7 orders of magnitude by changing a few characters in a regex, which made it match its input in linear time instead of O(k^N) due to a crazy backtrack. The speedup I measured could have been even greater if longer strings were being matched, but in practice the longest string I tested it with took over 14 hours to match before the change, and ~2 milliseconds after the cha…

What was the actual change?

It was a long regex, made of multiple parts with two OR'd together that looked very similar except for the last few characters. These two parts were trying to match a structured format, think of something like a domain name for example; it's not just [a-z0-9.-]+ since you can't have the - or . at the start or at the end, and maybe the end part has a limited length (say you want to match only short TLDs). I can't really say what these strings were but they had these sorts of restrictions and a range that was a bit larger than what domains can use (like capital letters).

So they had something like this for this structured part:

    [a-zA-Z]+[a-zA-Z0-9-.]*[a-zA-Z0-9]?(\.[a-zA-Z]{2,3})?
Actually kind of like that, but with multiple ()? and (){N} wrapping the different layers.

Let's call the regex above STRUCTURED. Now how do you match either one of these structured strings followed by either `.foo` or `.bar`? They had it as:

    STRUCTURED\.foo|STRUCTURED\.bar
(again, where STRUCTURED is replaced with the whole long regex from above). Meaning that the regex engine, as it consumes the first characters that potentially match the structured string, can't tell whether it's in the left or right branch of this OR until it reaches either the `.foo` or `.bar` suffix.

The change I made was simply to match it with:

    STRUCTURED(\.foo|\.bar)
In this case the engine can consume each character of the input and make its way through STRUCTURED without having to maintain k branches per character (given as k=2 in the example above but it was much more than that).

I hope the general idea still comes through despite the simplification and required obfuscation.

Re: 14,000x Speedup (2015)

#220

Post by rladd »

We can easily reduce this to effectively time=0 which is an infinite speedup.

Since the membership of any of the local cells in the global cells is static, we only have to compute this once. Then we add a globalCell parameter to each local cell to specify which global cell it's contained in.

If this uses up too much memory, we could go to a slower but still much, much faster than the blog post's method of something like:

- Create 2d array where the 1st dimension is a sorted list of local row values, one per global row value, that represent the maximum X value within any global cell. Then the the 2nd dimension are local column values, one per global column value that similarly correspond to the maximum Y value of any local cell per global cell. (mapping the coordinates to an array)

- Find the entry that the current local row value fits into (for example the entry with a value higher than the local row value, which is higher than the next list entry).

- This selects a second dimension array for that global row that has similar properties: it's only necessary to then find which value the local row fits into to determine the global cell (which would be the array's value at that index).

Post reply on HN