How to evaluate efficiency...

[DieterPi]

A question about setting up exercises on efficiency...

Say I want to make a exercise on binary search, how could I make a test plan that checks if a binary search has been used? Like testing for the number of comparisons.

I know I can set a time limit combined with a 'bit' test case to force efficient solutions. But setting that up feels like trail-and-error.. (what time limit do I need, what size of test case do I need ...)

It would be great if I could construct a (custom) testcase that checks for the number of comparisons. How should I handle this idea?

[DieterPi]

Even deze vraag terug oprakelen omdat ik terug met oefeningen bezig ben over efficiëntie.

Gewoon ter informatie: is er nu al een mogelijk om 'efficiëntie' te controleren? Of staat zoiets op de roadmap? (waarschijnlijk wel niet echt evident, ik ben me daar ten volle bewust van 😉)

[TomNaessens]

Hi @DieterPi,

Measuring efficiency based on time is pretty hard to implement since all our processes run on shared resources, so evaluating efficiency based on runtime for example won't be accurate. This is not something we're looking at implementing.

As you say in your original message, there is some merit in the idea of counting comparisons, but it won't be very easy 😅

As a start, you could ask students to implement a compare function that increases some amount_of_comparisons value, and another get_amount_of_comparisons that returns that amount. You could then write a custom oracle function that calls get_amount_of_comparisons and checks if that's "within expected bounds".

Additionally, to hide that bit of code from the students and not require them to implement it, you could serve those functions in a "before" part of the context, but you'll have to use the JSON-test plan instead of yaml then, as @chvp illustrated here.