Как ускорить код

@gajason · Регистрация: 26.01.2023

Студворк — интернет-сервис помощи студентам

Добрый день!

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import sys
import time
 
for i in range(int(sys.stdin.readline())):
 
    sys.stdin.readline()
    lst = [int(i) for i in sys.stdin.readline().split()]
 
    summa = 0
    for item in set(lst):
      cnt = lst.count(item)
      summa += (cnt // 3 * 2 + cnt % 3) * item
    
    print(summa)

@Gdez · 26.01.2023, 11:17

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

Без полного условия задачи - никак…

@eaa · 26.01.2023, 11:23

Сообщение от gajason

lst.count(item)

здесь твоя проблема.

Добавлено через 1 минуту
используй

Python
1
from collections import Counter

@gajason · 26.01.2023, 11:54 **[ТС]**

Спасибо за ответ.

Допустим, в одной строке 10000 повторений одного и того же числа, я не хотел 10000 раз бессмысленно по циклу пробежаться. Поэтому и засунул все в SET, чтобы исключить повторения.
Беру из SET значение, проверяю сколько повторений в LIST.

как это "from collections import Counter" поможет - я не понимаю

Добавлено через 4 минуты

Сообщение от Gdez

Без полного условия задачи - никак…

Есть строка из (допустим) 20000 чисел, разделенных пробелом.
Надо среди них найти число, количество его повторений, и сделать определенное действие над ними (допустим число * к-во повторений).

@eaa · 26.01.2023, 11:55

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collections import Counter
 
import sys
import time
 
for i in range(int(sys.stdin.readline())):
 
    sys.stdin.readline()
    lst = [int(i) for i in sys.stdin.readline().split()]
 
    summa = 0
    for item, cnt in Counter(lst).items():
        summa += (cnt // 3 * 2 + cnt % 3) * item
 
    print(summa)

@gajason · 26.01.2023, 11:58 **[ТС]**

Сообщение от eaa

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collections import Counter
 
import sys
import time
 
for i in range(int(sys.stdin.readline())):
 
    sys.stdin.readline()
    lst = [int(i) for i in sys.stdin.readline().split()]
 
    summa = 0
    for item, cnt in Counter(lst).items():
        summa += (cnt // 3 * 2 + cnt % 3) * item
 
    print(summa)

Спасибо огромное!

Пока не очень хорошо понимаю логику Python!

@eaa · 26.01.2023, 12:15

Сообщение от gajason

lst.count(item)

count работает за O(n). в set тоже n элементов может быть.
в итоге O(n^2) действий - в худшем случае.
т.е для 10000 элементов, программа в худшем случае выполнит порядка 10^10 операций.
а Counter работает за O(n) - примерно (чуть больше на самом деле, но не суть).

Добавлено через 9 минут
gajason, учитывая что python выполняет в 1 секунду около от 10^6 до 10^7 операций.
для выполнения вашей программы понадобится от 10^3 до 10^4 секунд (от 17 до 167 минут).
Если грубо оценить.

Добавлено через 1 минуту
Дело тут не в python. Просто написан неправильный алгоритм для программы.

@gajason · 26.01.2023, 12:19 **[ТС]**

Сообщение от eaa

count работает за O(n). в set тоже n элементов может быть.
в итоге O(n^2) действий - в худшем случае.
т.е для 10000 элементов, программа в худшем случае выполнит порядка 10^10 операций.
а Counter работает за O(n) - примерно (чуть больше на самом деле, но не суть).

Добавлено через 9 минут
gajason, учитывая что python выполняет в 1 секунду около от 10^6 до 10^7 операций.
для выполнения вашей программы понадобится от 10^3 до 10^4 секунд (от 17 до 167 минут).
Если грубо оценить.

Добавлено через 1 минуту
Дело тут не в python. Просто написан неправильный алгоритм для программы.

Благодарю!

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

Как ускорить код

Решение

Решение