Ищу хорошую бонусную викторину для проверки эффективности (в частности, эффективность, связанная со временем) [закрыто
-
23-10-2019 - |
Вопрос
Я делаю вступительный в лаборатории компьютерных наук раз в неделю. Я надеялся провести быстрый конкурс в конце моей следующей лаборатории. Я хочу дать им блок кода, как это:
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
Я думаю, что для того, чтобы иметь измеримую разницу в производительности между методами, вы должны сделать что -то много раз.
Решение
Поскольку это вводной класс, и ваши ученики не освещали сортировку, но я думаю, что будет очень трудно придумать что -то достаточно простое, достаточно интересное, чтобы иметь несколько разных способов сделать это, и достаточно сложный, что там там является заметной разницей в скорости между различными реализациями на современном компьютере. Ваша настоящая проблема, однако, заключается в том, что что -то достаточно простое, чтобы они могли попробовать, уже имеет каноническую реализацию, только короткий поиск в Google.
Мое предложение - инвертировать задачу. Попросите ваших учеников соревноваться, чтобы придумать самое чудесное, самое медленное, большинство моментов, о котором они могут подумать. Я полагаю, что это так же ценно думать обо всех неправильных способах сделать что -то, как и в том, чтобы думать о правильном, и так же сложно быть худшим, как и лучшим. Проще увидеть результаты субъективно, так как плохой код будет В самом деле медленный. Нет гуглей для ответа. Наконец, по моему (неуместному) мнению, это дополнительный бонус за то, чтобы сделать вызов более увлекательным.
Что -то вроде поиска строки в другой строке легче сделать плохим, чем хорошо. Возможно, попросите их извлечь все основные числа из строки 2 КБ случайных буквенно -цифровых символов. Много способов сделать ухо свиньи этой проблемы.
Другие советы
Согласился с «много раз» для коротких операций, но для более длинных, когда -то может быть достаточно самостоятельно.
Я предлагаю посмотреть Проект Эйлер, отличная коллекция вопросов программирования. Самое приятное то, что проблемы разработаны с учетом «правила одной минуты», что большинство проблем должны занимать умеренный компьютер менее чем на одну минуту, чтобы выполнить эффективный Алгоритм, чтобы найти ответы. Так что отличное место для начала. :)
Две вещи.
Во -первых, эффективность - это больше, чем время исполнения. Это также касается использования памяти, доступа к памяти, файловой системы/доступа к ресурсам и т. Д. Есть множество вещей, которые входят в эффективность. Поэтому, пожалуйста, будьте явными, что вы ищете рутину с самым коротким временем выполнения. В противном случае вы отправляете смешанное сообщение ...
Во -вторых, я услышал эту проблему около 15 лет назад, и я не могу ее забыть:
Создать список всех 5-значных пар, которые суммируют 121212
. Анкет Однако ни одно из 2 чисел не может повторить десятичную цифру. Так 1
может появиться только один раз в любом номере. Итак, пример пары результатов 98167 + 23045
. Анкет Существует немало, и его легко создать решение для грубой силы, но для эффективного решения требуется некоторая мысль. Есть 192 уникальных пары ...
Это хорошие идеи. Как насчет вопроса о сортировке?
Сортировка множества чисел также может быть хорошей идеей, поскольку для него есть целая куча алгоритмов (вставка, выбор, быстрый, куча и т. Д.), Которые имеют разные характеристики производительности. Это также дало бы студентам возможность узнать о нотации Big-O и т. Д.