Ускорить программу на Python

@jvf · Регистрация: 27.05.2017

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

Есть простенькая задачка. Я её решил на C++, но на Python не получается, потому что язык более медленный, и не удаётся уложиться в 1 секунду. Но я знаю, что на Python также можно решить эту задачу. Но как?

1. Задача

Кликните здесь для просмотра всего текста

Простые числа
(Время: 1 сек. Память: 16 Мб Сложность: 25%)

Необходимо вывести все простые числа от M до N включительно.
Входные данные

Входной файл INPUT.TXT содержит два натуральных числа M и N, разделенных пробелом (2 ≤ M ≤ N ≤ 300 000)
Выходные данные

В выходной файл OUTPUT.TXT выведите все простые числа от M до N в порядке возрастания, по одному в строке. Если таковых чисел нет, то следует вывести «Absent».

Пример:
INPUT.TXT
2 5
OUTPUT.TXT
2
3
5

INPUT.TXT
4 4
OUTPUT.TXT
Absent

2. Решение на C++ (решение правильное)

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <fstream>
#include <iostream>
#include <math.h>
 
#include <stdio.h>
#include <stdlib.h>
 
using namespace std;
 
 
int find_prost(int a)
 
{
 
    if (a==2) 
        {return 1;};
 
    for (int i=2;i<sqrt(a)+1;i++){
 
 
        if ((a%i)==0){
 
            return 0;
        }
 
    }
 
    return 1;
 
 
}
 
int main(int argc, char* argv[])
{
    setlocale(LC_ALL, "rus"); // êîððåêòíîå îòîáðàæåíèå Êèðèëëèöû
    
    int m,n;
    
    ifstream fin("INPUT.TXT"); // îòêðûëè ôàéë äëÿ ÷òåíèÿ
 
    fin >> m;
    fin >> n;
 
    fin.close(); 
    //cout <<"m="<<m<<" n="<<n;
        
    ofstream fout("OUTPUT.TXT");
   
 
    //fout<< "Hello";
    //fout.close();
    
    bool find = false;
    int answer;
 
    
    for (int i=m;i<=n;i++){
 
        answer = find_prost(i);
        //cout<<"i="<<i<<"answer="<<answer<<endl;
 
        if (answer == 1) {
            find = true;
            fout << i<<endl;
        } 
 
    }
 
    if (find == false){
 
        fout << "Absent";
    }
 
    fout.close();
    //cout << a%2;
    //system("pause");
    
    return 0;
}

3. Решение на Python (не укладываюсь в 1 секунду)

Кликните здесь для просмотра всего текста

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import math
 
f = open("INPUT.TXT")
g = open("OUTPUT.TXT", "w")
 
s = f.readline().split(" ")
m = int(s[0])
n = int(s[1])
 
def sum(x):
 
    sum = 0
 
    for n in range(1,x-1):
        sum += n*math.pow(2, x-2-n)
 
    return sum 
        
 
def find_prost(a):
 
    for i in range(2, int(math.sqrt(a))+1):
        #print("i=",i)
        if (a % i) == 0:
            #print("Наша ситуация")
            return 0
 
    return 1
 
"""
answer = find_prost(17)
 
found = False
 
for i in range(m,n+1):
    if sum(i)%i == 1 or i==2:
        found = True
        g.write(str(i)+" ")
 
if found == False:
    g.write("Absent")
"""
found = False
for i in range(m, n+1):
 
    if find_prost(i) == 1:
        found = True
        g.write(str(i)+" ")
 
if found == False:
    g.write("Absent")

vic5710 · 18.11.2017, 22:54

ну это закон сохранения энергии чем больше скорость, тем больше расход памяти
попробуй так

Python
1
2
3
4
5
6
def primes(n):
    a = [1]*n
    for i in range(2, math.ceil(math.sqrt(n))):
        if a[i]:
            for j in range(i*2 , n, i): a[j] = 0
    return [i for i in range(2,n) if a[i]]

@Vigi · 19.11.2017, 08:24

jvf, Ваш вариант можно и так сократить.
На этом сервисе можно обойтись и без работы с файлами.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import math
 
m, n = map(int, input().split())
n += 1
a = [True] * n
 
for i in range(2, int(math.sqrt(n)) + 1):
    if a[i] == False:
        continue
    for j in range(i * 2, n, i):
        a[j] = False
 
b = [i for i in range(m, n) if a[i]]
 
if len(b) == 0:
    print("Absent")
else:
    for p in b:
        print(p)

@jvf · 19.11.2017, 12:55 **[ТС]**

Там на сервере я решил новую задачу. Но только на C++, на Python решение не проходит. Задача:

Кликните здесь для просмотра всего текста

Простые числа
(Время: 0,5 сек. Память: 16 Мб Сложность: 28%)

Необходимо вывести все простые числа от M до N включительно.
Входные данные

Входной файл INPUT.TXT содержит два натуральных числа M и N, разделенных пробелом (2 ≤ M ≤ N ≤ (10 в 6 степени))
Выходные данные

В выходной файл OUTPUT.TXT выведите все простые числа от M до N в порядке возрастания, по одному в строке. Если таковых чисел нет, то следует вывести «Absent».

Пример первый:
INPUT.TXT
2 5

OUTPUT.TXT
2 3 5

Пример второй:
INPUT.TXT
4 4

OUTPUT.TXT
Absent

Вот решение на C++, оно прошло, мне его засчитали, но мне интересно, а можно ли решить то же самое на Python.

Кликните здесь для просмотра всего текста

#include <fstream>
#include <iostream>
#include <math.h>

#include <stdio.h>
#include <stdlib.h>

using namespace std;

int main(int argc, char* argv[])
{
setlocale(LC_ALL, "rus");

int m,n;

ifstream fin("INPUT.TXT");
fin >> m;
fin >> n;

fin.close();
cout <<"m="<<m<<" n="<<n<<endl;

ofstream fout("OUTPUT.TXT");

n+=1;
bool a[n];

for(int i = 0; i < n; i++){
a[i]=true;
}

for ( int i=2;i<sqrt(n)+1;i++){

if (a[i] == true){

for (int j=i*2;j<n;j+=i){

a[j] = false;
}
}
}

bool found = false;
for (int i=m;i<n;i++){

if (a[i] == 1){
found = true;
fout << i<<endl;
//cout<<i<<" ";
}
}

if (found == false){

fout<<"Absent";

}

fout.close();

return 0;
}

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

Это решение уже не подходит к новой задаче, потому что там лимит в 0,5 секунды, а чисел стало до 1 000 000

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import math
 
f = open("INPUT.TXT")
g = open("OUTPUT.TXT", "w")
 
s = f.readline().split(" ")
m = int(s[0])
n = int(s[1])
 
n += 1
a = [True] * n
#print(a)
 
for i in range(2, int(math.sqrt(n))+1):
    if a[i] == False:
        continue
 
    for j in range(i * 2, n, i):
            a[j] = False
 
#print(a)
b = [i for i in range(m, n) if a[i]]
#print(b)
#t2= time()
 
if len(b) == 0:
    g.write("Absent")
else:
    for p in b:
        g.write(str(p)+" ")

vic5710 · 19.11.2017, 13:20

ну можно так:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def primes2(n):
    a = bytearray(n)
    a[0] = True
    a[1] = True
    for i in range(2, math.ceil(math.sqrt(n))):
        if not a[i]:
            for j in range(i*2 , n, i): a[j] = True
    return [i for i in range(2,n) if not a[i]]
    
while True:
    n = int(input('?')) + 1
    t1 = time()
    a = primes2(n)
    print (time() -t1)

Python
1
2
3
4
5
6
7
>>> 
?100000
0.027171850204467773
?1000000
0.26625776290893555
?2000000
0.5441009998321533

дальше уже cython

@jvf · 19.11.2017, 13:32 **[ТС]**

Вот улучшенный алгоритм, который проходит и более сложную проверку:

время -- 0,47 секунды на 1 000 000 чисел.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#import math
 
def primes(n):
    sieve = [True] * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]
 
f = open("INPUT.TXT")
g = open("OUTPUT.TXT", "w")
 
s = f.readline().split(" ")
m = int(s[0])
n = int(s[1])
 
n+= 1
 
s = primes(n)
 
found = False
 
for p in s:
  if p>=m:
    found = True
    g.write(str(p)+" ")
    #print(str(p)+" ")
 
if found == False:
    g.write("Absent")
 
g.close()
f.close()

Добавлено через 3 минуты
Ранее мы обсуждали более простую задачу. Там рекород составил 0,312 секунды.

Новый алгоритм ускоряют задачу в три раза без большого лимита памяти!

Итог -- трёхкратное ускорение.

Результат -- 0,187 секунды!!!

Это трёхкратное ускорение по сравнению с прошлым лучшим результатам (если укладываемся в ограничение по памяти)

vic5710 · 19.11.2017, 14:38

это вариант решета Сундарама
я бы написал на Си и сделал обертку для питона
http://vscode.ru/prog-lessons/... na-si.html

@Semen-Semenich · 19.11.2017, 18:53

что покажет на вашем тесте этот код?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def searh(n):
    if n % 2 == 0:
        return n == 2
    d = 3
    while d * d <= n and n % d != 0:
        d += 2
    return d * d > n 
        
s,e = list(map(int,input().split()))
list_number =[i for i in list(range(s,e+1)) if searh(i)]
if list_number:
    print(*list_number,sep = '\n')
else:
 print('Absent')

@jvf · 19.11.2017, 19:02 **[ТС]**

Есть два теста: более простой (n<=300000 и время ограничено 1 секундой) и более сложный (n<=1000000 и время ограничено 0,5 секундами).

Ваше решение не проходит более простой тест на сервере, заваливается с результатом в 1,875 секунды. То есть для прохождения первого теста вам нужно ускорить вашу программу на 0,875 секунды.

@Semen-Semenich · 19.11.2017, 19:06

понятно хотя на другом сайте выдало такие результаты

@jvf · 19.11.2017, 19:10 **[ТС]**

Вот скриншота вашего результата на более простом тесте на другом сервере:

Ваш результат самый верхний. Он выделен красным, потому что не прошёл проверку по времени.

Там написано Time limit exceeded, тест 15, время 1,1875

@jvf · 19.11.2017, 19:14 **[ТС]**

На скриншоте видно, что пока лучший результат из моих тестируемых -- 0,171 секунда.

Новые блоги и статьи Все статьи Все блоги /
Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .

vic5710 963 / 718 / 276 Регистрация: 10.12.2016 Сообщений: 1,764
	19.11.2017, 14:38
	это вариант решета Сундарама я бы написал на Си и сделал обертку для питона http://vscode.ru/prog-lessons/... na-si.html 1

@jvf 7 / 7 / 3 Регистрация: 27.05.2017 Сообщений: 89 Записей в блоге: 10
	19.11.2017, 19:02 [ТС]
	Есть два теста: более простой (n<=300000 и время ограничено 1 секундой) и более сложный (n<=1000000 и время ограничено 0,5 секундами). Ваше решение не проходит более простой тест на сервере, заваливается с результатом в 1,875 секунды. То есть для прохождения первого теста вам нужно ускорить вашу программу на 0,875 секунды. 0

@Semen-Semenich 5237 / 3481 / 1176 Регистрация: 21.03.2016 Сообщений: 8,310
	19.11.2017, 19:06
	понятно хотя на другом сайте выдало такие результаты Миниатюры 0

@jvf 7 / 7 / 3 Регистрация: 27.05.2017 Сообщений: 89 Записей в блоге: 10
	19.11.2017, 19:10 [ТС]
	Вот скриншота вашего результата на более простом тесте на другом сервере: Ваш результат самый верхний. Он выделен красным, потому что не прошёл проверку по времени. Там написано Time limit exceeded, тест 15, время 1,1875 0

@jvf 7 / 7 / 3 Регистрация: 27.05.2017 Сообщений: 89 Записей в блоге: 10
	19.11.2017, 19:14 [ТС]
	На скриншоте видно, что пока лучший результат из моих тестируемых -- 0,171 секунда. 0