3

Are there any good methods for doing this? I can find papers with algorithms, but they usually do not show their computational results with the same problem sets and the publishing year of two papers is usually different so they will most likely use different equipment for solving the problems.

Edit: By problem, I am referring also to the specific size of the problem, memory usage and other characteristics of the problem.

4
7
  1. I generally go through review papers in the field and try to cite them as well if they have any sentence in the paper "claiming that the previous method is SOTA".
  2. There are also benchmark sites.
  3. Famous datasets even have their personal benchmarks linked to their sites.
  4. You could use research gate or any other forum and ask a question there.
  5. You could try a keyword search on google scholar and see if any paper claims to do so.

Regarding the difference in setting, generally the "well-acclaimed" SOTA papers don't have these issues. At least that's what I've noticed majorly in my field.

If that is the case, then I suggest making a small study within the paper covering all the results in the different settings. (Please do correct me if I'm wrong here).

3

I think you have a misunderstanding about algorithm efficiency and its study. A good course in algorithms and data structures should correct that.

I'll assume here that you actually mean algorithm and not just a useful computer program. They are not the same thing. Some useful programs, while they may contain algorithms, have their performance dominated by other non-algorithmic concerns. The performance there might, indeed, be tied to a particular kind of dataset for which small deviations result in wildly different performance.

Algorithms are judged good or bad based on theoretical concerns, not by running them on sample data. The theoretical measures make them independent of hardware within certain bounds. A fast algorithm will run faster than a slow algorithm on different computers that have a similar architecture (see caveats below). Some algorithms (bubble sort) are always bad. Others are always better (selection sort). Still others are "always" good (merge sort, but see caveats).

So, the "different equipment" idea is a red herring, provided that the equipment has a similar architecture.

Caveats, and there are quite a few.

Some algorithms require a lot of memory (quick sort on a large set) because they are highly recursive. If a machine has insufficient fast memory then quick sort on a large data set will be limited by the, independent, efficiency of the memory system.

Some "slowish" algorithms work well on small data sets and can be preferred over "fastish" algorithms if the data set is expected to be small. But these things are known and are normally incorporated into working software. For example, in quick sort once a "split" results in a segment of size 10 or so, a quadratic algorithm will take over to complete the sort. But that is just good software design, and it uses known, theoretical, results for the various options.

However, if the architecture of a machine changes drastically (as a GPU differs from a CPU), then the game changes and some algorithms that are fast on one will be slower on the other. For example, still sorting things, if an architecture makes comparisons "free" then an algorithm that uses lots of comparisons, rather than rearrangements, will be preferred on that architecture. But, again, this is based on the theoretical considerations that measures the various kinds of operations required by an algorithm.

So, to answer your question, you need to look at the theoretical measures, and these are normally provided by authors.

Another caveat. There are some applied problems that are fairly ill structured and haven't (as yet) yielded to the theoretical analysis assumed above. Perhaps a bit of chaos is involved. For these, some empirical measures might be required at the moment. But some of those sorts of problems can also drive people to invent new architectures that can efficiently handle the problems. But, the same sort of problem also drives the theoreticians to invent new algorithms that are amenable to a general analysis of efficiency. But, the results will, most likely, be reported in theoretical terms, not timings on specific hardware. This is probably what you are seeing. And, hopefully, part of their analysis includes limits on when the algorithm can be expected to behave well.

17
  • 3
    I guess this answer applies to comparing a bunch of kinds of sort, but good luck on your "theoretical" evaluation of any machine or statistical learning approach.
    – user133933
    Mar 23 at 12:50
  • 2
    @Libor, actually, any algorithm (provided it actually is an algorithm) can be analyzed and its efficiency predicted. Randomness, for example, is not an obstacle. Some things are harder than others of course. But algorithmics isn't a dead art.
    – Buffy
    Mar 23 at 12:54
  • 3
    I think this answer is either plain wrong, or you are using more the word "algorithm" differently from what many people are used to. Mar 23 at 14:08
  • 3
    @Aymous, I realize that people outside CS and math might use terms informally. But I also depended on the question's specific tags. And in Math and CS, algorithm has a specific meaning that has been stable for over half a century. A statement about algorithms may not apply to a non-algorithm. I suspect, now that the OP actually meant something else than what is literally stated. In part, I was trying to jumpstart the education of the OP who has some confusions somewhere. But they asked about why algorithm papers have a certain structure and I wrote about that. Not about other things.
    – Buffy
    Mar 23 at 15:24
  • 4
    @Buffy I actually meant that within CS itself, the term algorithm is used differently! Many places in CS, they call "useful computer programs" as "algorithms". I think that's where the confusion arose. I completely agree with what you have said regarding algorithms but the word has a taken a different meaning in a few fields within CS itself.
    – Aymuos
    Mar 23 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.