Ищу хорошую бонусную викторину для проверки эффективности (в частности, эффективность, связанная со временем) [закрыто

Question

Я делаю вступительный в лаборатории компьютерных наук раз в неделю. Я надеялся провести быстрый конкурс в конце моей следующей лаборатории. Я хочу дать им блок кода, как это:

public class EfficientCode{

    public static void main(){
        long startTime, endTime, executionTime;
        startTime = System.currentTimeMillis();

        yourEfficientMethod():
        endTime = System.currentTimeMillis();
        executionTime = endTime – startTime;

    }

    public static void doSomething(){
        // you do this part.  
    }

}

Они будут реализовать этот метод DOSOMENT, и человек с самым быстрым кодом получит несколько бонусных знаков.

Проблема в том, что вопрос должен быть несколько прост. Студенты хорошо понимают: петли, если/иначе, струны, добавление, массивы и т. Д.

Вот мои идеи о том, каким может быть вопрос:

• Найдите все идеальные цифры от 1 до 1 000 000. (Идеальное число - это число, где все факторы числа составляют число. IE: 6 = 3 + 2 + 1)
• Найдите все основные цифры от 1 до 1 000 000

Я думаю, что для того, чтобы иметь измеримую разницу в производительности между методами, вы должны сделать что -то много раз.

Answer 1

Поскольку это вводной класс, и ваши ученики не освещали сортировку, но я думаю, что будет очень трудно придумать что -то достаточно простое, достаточно интересное, чтобы иметь несколько разных способов сделать это, и достаточно сложный, что там там является заметной разницей в скорости между различными реализациями на современном компьютере. Ваша настоящая проблема, однако, заключается в том, что что -то достаточно простое, чтобы они могли попробовать, уже имеет каноническую реализацию, только короткий поиск в Google.

Мое предложение - инвертировать задачу. Попросите ваших учеников соревноваться, чтобы придумать самое чудесное, самое медленное, большинство моментов, о котором они могут подумать. Я полагаю, что это так же ценно думать обо всех неправильных способах сделать что -то, как и в том, чтобы думать о правильном, и так же сложно быть худшим, как и лучшим. Проще увидеть результаты субъективно, так как плохой код будет В самом деле медленный. Нет гуглей для ответа. Наконец, по моему (неуместному) мнению, это дополнительный бонус за то, чтобы сделать вызов более увлекательным.

Что -то вроде поиска строки в другой строке легче сделать плохим, чем хорошо. Возможно, попросите их извлечь все основные числа из строки 2 КБ случайных буквенно -цифровых символов. Много способов сделать ухо свиньи этой проблемы.

Answer 2

Согласился с «много раз» для коротких операций, но для более длинных, когда -то может быть достаточно самостоятельно.

Я предлагаю посмотреть Проект Эйлер, отличная коллекция вопросов программирования. Самое приятное то, что проблемы разработаны с учетом «правила одной минуты», что большинство проблем должны занимать умеренный компьютер менее чем на одну минуту, чтобы выполнить эффективный Алгоритм, чтобы найти ответы. Так что отличное место для начала. :)

Answer 3

Две вещи.

Во -первых, эффективность - это больше, чем время исполнения. Это также касается использования памяти, доступа к памяти, файловой системы/доступа к ресурсам и т. Д. Есть множество вещей, которые входят в эффективность. Поэтому, пожалуйста, будьте явными, что вы ищете рутину с самым коротким временем выполнения. В противном случае вы отправляете смешанное сообщение ...

Во -вторых, я услышал эту проблему около 15 лет назад, и я не могу ее забыть:

Создать список всех 5-значных пар, которые суммируют 121212. Анкет Однако ни одно из 2 чисел не может повторить десятичную цифру. Так 1 может появиться только один раз в любом номере. Итак, пример пары результатов 98167 + 23045. Анкет Существует немало, и его легко создать решение для грубой силы, но для эффективного решения требуется некоторая мысль. Есть 192 уникальных пары ...

Answer 4

Это хорошие идеи. Как насчет вопроса о сортировке?

Answer 5

Сортировка множества чисел также может быть хорошей идеей, поскольку для него есть целая куча алгоритмов (вставка, выбор, быстрый, куча и т. Д.), Которые имеют разные характеристики производительности. Это также дало бы студентам возможность узнать о нотации Big-O и т. Д.