Форум программистов, компьютерный форум, киберфорум
Python
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.60/48: Рейтинг темы: голосов - 48, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 26.04.2015
Сообщений: 13
1

Оптимизация кода

25.10.2015, 22:06. Показов 9464. Ответов 83
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
kol=0
N=int(input())
teach_list=[]
for i in range(N):
    teach_list.append(input())
teach_list1 = []
for s in teach_list :
    if s not in teach_list1 :
         teach_list1.append(s)
M=int(input())
student_list=[]
for j in range(M):
    student_list.append(input())
for i in range(len(teach_list1)):
    for j in range(M):
        if teach_list1[i]==student_list[j]:
            kol+=1
print(kol)

как можно ускорить?

Условие задачи
Цитата Сообщение от http://acm.timus.ru/problem.aspx?space=1&num=1196
Ограничение времени: 1.5 секунды
Ограничение памяти: 64 МБ
Будем справедливы: сессия ставит задачи не только студентам, но и преподавателям. Любой преподаватель обучает немалое количество студентов, а ведь каждого надо еще и проверить. Поэтому один из преподавателей решил принимать экзамен по истории по такой упрощённой процедуре: студент записывает все известные ему «исторические» даты (достаточно, чтобы он написал только года, но, конечно, мог объяснить, чем замечательна та или иная дата). Преподаватель же держит перед глазами список дат, которые студент должен знать. Для оценки знаний студента преподаватель подсчитывает количество чисел в списке студента, которые также есть в списке преподавателя. В зависимости от полученного числа и выставляется итоговая оценка.
Вы должны оказать посильную помощь в автоматизации этого процесса, разработав программу для подсчёта количества совпадений в списках студента и преподавателя.
Исходные данные
В первой строке содержится число N — количество записей в списке преподавателя. 1 ≤ N ≤ 15000. Затем идет N строк, содержащих список преподавателя, по одной дате в строке. Записаны только года. Каждый год — целое число в пределах от 1 до 109. Даты в этом списке отсортированы по неубыванию. В следующей после списка строке содержится число M — количество записей в списке студента, 1 ≤ M ≤ 106. Затем также M строк с датами (записаны только года, каждый год — целое число в пределах от 1 до 109). Этот список не отсортирован. В списке как студента, так и преподавателя даты могут повторяться.
Результат
Вы должны вывести одно число — количество чисел во втором списке, которые также содержатся в первом.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.10.2015, 22:06
Ответы с готовыми решениями:

Оптимизация кода
Добрый день! Решаю задачу по учебе и вроде код по условию верный, но при тестах выдает ошибку...

Оптимизация кода
Задача G. Условие в .pdf файле. Если нужны тесты, напишите. with open('test\\01', 'r') as inp: ...

Оптимизация кода
Как сделать count для каждого значения? Ниже приведен код, но я хотел бы сделать count каждого...

Оптимизация кода простого калькулятора
Доброго времени. Начал изучать вчера python. Сегодня решил написать простой калькулятор. Написал....

Фрактальное Броуновское движения ( оптимизация кода)
В общем у меня функция генерации фрактального броуновского движения. Делается все очень просто....

83
Эксперт NIX
2795 / 2038 / 682
Регистрация: 02.03.2015
Сообщений: 6,509
25.10.2015, 22:35 2
Что делают строки 7-9? Оставляют только уникальные записи? Это делается через множество: (7-9 убрать).
Python
14
15
for teach in set(teach_list):
    kol += student_list.count(teach)
1
0 / 0 / 0
Регистрация: 26.04.2015
Сообщений: 13
25.10.2015, 23:18  [ТС] 3
Добавлено через 34 минуты
Marinero, спасибо, понял, но всё равно скорость выполнения больше чем надо, можете ещё что либо посоветовать?
0
alex925
25.10.2015, 23:23
  #4

Не по теме:

Цитата Сообщение от svtoroi Посмотреть сообщение
но всё равно скорость выполнения больше чем надо
Сам понял, что сказал?:D

0
0 / 0 / 0
Регистрация: 26.04.2015
Сообщений: 13
25.10.2015, 23:32  [ТС] 5
alex925, нам выполнение этой программы есть ограничение по времени что бы её засчитали выполненной, поэтому да, я понял что сказал.
Python
1
2
3
4
5
6
7
8
9
10
11
12
kol=0
N=int(input())
teach_list=[]
for i in range(N):
    teach_list.append(input())
M=int(input())
student_list=[]
for j in range(M):
    student_list.append(input())
for teach in set(teach_list):
    kol += student_list.count(teach)
print(kol)
программа работает за 1.544 с, а надо что бы было не больше полутора
0
2740 / 2339 / 620
Регистрация: 19.03.2012
Сообщений: 8,830
25.10.2015, 23:52 6
svtoroi, я о том, что если бы скорость выполнения была на столько выской, что была бы даже больше чем надо, то ты бы не спрашивал, что исправить. В данном случае думаю ты хотел сказать, что скорость выполнения недостаточно высокая.
0
0 / 0 / 0
Регистрация: 26.04.2015
Сообщений: 13
26.10.2015, 00:00  [ТС] 7
alex925, понял, осознал)
но всё равно вопрос остаётся
0
Эксперт NIX
2795 / 2038 / 682
Регистрация: 02.03.2015
Сообщений: 6,509
26.10.2015, 00:24 8
Лучший ответ Сообщение было отмечено svtoroi как решение

Решение

Ну раз так ставите вопрос
Python
1
2
teach_list = {input() for _ in range(int(input('Кол-во учителей: ')))}
print(sum(1 for _ in range(int(input('Кол-во студентов: '))) if input() in teach_list))
1
2740 / 2339 / 620
Регистрация: 19.03.2012
Сообщений: 8,830
26.10.2015, 00:25 9
Так попробуй, в тройке точно должно быстрей работать
Python
1
2
3
4
5
6
7
teach_list = [input() for _ in range(int(input('Кол-во учителей: ')))]  
student_list = [input() for _ in range(int(input('Кол-во студентов: ')))]
 
count = 0
for teach in set(teach_list):
    count += student_list.count(teach)
print(count)
1
Marinero
26.10.2015, 00:27
  #10

Не по теме:

Цитата Сообщение от svtoroi Посмотреть сообщение
скорость выполнения больше чем надо
сравните с «время выполнения»

0
0 / 0 / 0
Регистрация: 26.04.2015
Сообщений: 13
26.10.2015, 00:59  [ТС] 11
Цитата Сообщение от Marinero Посмотреть сообщение
Ну раз так ставите вопрос
Код Python
Выделить код
7
print(sum(1 for _ in range(M) if input() in teach_list))
alex925, скорость выполнения увеличилась, но все равно 0.013-0.022 лишние
а можно ли как то это подвязать?
тут если М заменить на len(student_list) то обработка неправильная идет (у меня лишние значения при вводе получаются)
0
Эксперт NIX
2795 / 2038 / 682
Регистрация: 02.03.2015
Сообщений: 6,509
26.10.2015, 01:24 12
svtoroi, Новый вариант попробуйте.
Цитата Сообщение от Marinero Посмотреть сообщение
Python
1
2
teach_list = {input() for _ in range(int(input('Кол-во учителей: ')))}
print(sum(1 for _ in range(int(input('Кол-во студентов: '))) if input() in teach_list))
1
0 / 0 / 0
Регистрация: 26.04.2015
Сообщений: 13
26.10.2015, 01:58  [ТС] 13
Marinero, я даже не представляю как это можно еще лучше написать, но
" svtoroi 1196. Экзамен по истории Python 3.4 Time limit exceeded 8 1.513 716 КБ"
время превышено на 0.013 но это самый лучший вариант
0
Эксперт NIX
2795 / 2038 / 682
Регистрация: 02.03.2015
Сообщений: 6,509
26.10.2015, 09:54 14
Выкладывайте полностью задание/формат вводимых данных — может там где-то ещё ускорение можно найти
1
Эксперт NIX
2795 / 2038 / 682
Регистрация: 02.03.2015
Сообщений: 6,509
26.10.2015, 15:18 15
Надо тут с товарищами советоваться — улучшиться ли поиск если переводить из строки в число. С одной строны — да, но с другой — на сам перевод тоже надо время.
Python
1
2
teach_list = {int(input()) for _ in range(int(input('Кол-во учителей: ')))}
print(sum(1 for _ in range(int(input('Кол-во студентов: '))) if int(input()) in teach_list))
Другой вариант — заморочится с словарями. Но тоже не уверен в прибавке скорости.
Python
1
2
3
4
5
6
7
def c_key(my_dir, key):
    try:
        return my_dir[key]
    except:
        return 0
teach_list = {input():1 for _ in range(int(input('Дат у учителя: ')))}
print(sum(c_key(teach_list, input()) for _ in range(int(input('Дат у студента: '))))
1
Эксперт по компьютерным сетям
5898 / 3355 / 1035
Регистрация: 03.11.2009
Сообщений: 10,003
26.10.2015, 16:25 16
Не уникальные даты тоже нужно же учитывать?
В том плане, что если в списке учителя два раза есть дата 100 и в списке ученика тоже два раза она есть - это считать двумя совпадениями?

Добавлено через 27 минут
вот так понял я (кроме ввода вручную):

Python
1
2
3
4
5
6
7
from random import randint
from collections import Counter
 
teach_list = sorted([randint(1, 20) for _ in range(1, 15)])
stud_list = [randint(1, 20) for _ in range(1, 15)]
tl, sl = Counter(teach_list), Counter(stud_list)
print(sum((tl & sl).values()))
с комментариями и промежуточными выводами
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from random import randint
from collections import Counter
 
# отсортированный лист учителя, вывод
# TODO 1,20 заменить на 1,109   --> диапазон случайных дат
# TODO 1,15 заменить на 1,15001 --> диапазон кол-ва дат
teach_list = sorted([randint(1, 20) for _ in range(1, 15)])
print(teach_list)
 
# лист ученика, вывод
# TODO 1,20 заменить на 1,109   --> диапазон случайных дат
# TODO 1,15 заменить на 1,107   --> диапазон кол-ва дат
stud_list = [randint(1, 20) for _ in range(1, 15)]
print(stud_list)
 
# подсчет кол-ва дат
tl = Counter(teach_list)
sl = Counter(stud_list)
 
# вывод пересечений (по минимальному), вывод суммы пересечений
print(tl & sl)
print(sum((tl & sl).values()))


при 15000 строках в первом и 106 строках во втором листе выполнение занимает:
Код
         78333 function calls (78321 primitive calls) in 0.311 seconds
с импортами:
Код
         79540 function calls (79500 primitive calls) in 0.327 seconds
1
0 / 0 / 0
Регистрация: 26.04.2015
Сообщений: 13
26.10.2015, 22:50  [ТС] 17
Marinero, со словарем вообще не пашет, SyntaxError: bad input ('for')
кстати, советовали как раз это через словарь как то оформить, но я не знаю да и не умею их применять
0
Эксперт NIX
2795 / 2038 / 682
Регистрация: 02.03.2015
Сообщений: 6,509
26.10.2015, 23:30 18
Какой версии питон у Вас?
Python
6
teach_list = dict((int(input()), 1) for _ in range(int(input('Дат у учителя: '))))
0
0 / 0 / 0
Регистрация: 26.04.2015
Сообщений: 13
26.10.2015, 23:55  [ТС] 19
Marinero, сейчас мой компьютер далеко, поэтому я сижу через онлайн среду, в кодскульпторе, там вроде как 3.4 он
0
Эксперт NIX
2795 / 2038 / 682
Регистрация: 02.03.2015
Сообщений: 6,509
27.10.2015, 00:01 20
Python
1
2
import sys
sys.version
0
27.10.2015, 00:01
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.10.2015, 00:01
Помогаю со студенческими работами здесь

Отфильтровать из array только значения, входящие в одну из groups. Оптимизация кода
#!/usr/bin/env python list_in = groups = def check_range(list_in, groups): result = for...

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

Оптимизация кода
Добрый день, прорешивая разные задачки, зачастую мне удавалось добиться результата, чтобы код...

Оптимизация кода
Написал код, работает правильно, но сайт, который проверяет, говорит, что цикломатическая сложность...

Оптимизация кода
Мы будем работать с набором слов. Ваша задача — выписать все слова, которые являются анаграммами...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru