Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.97/34: Рейтинг темы: голосов - 34, средняя оценка - 4.97
2 / 2 / 0
Регистрация: 15.10.2018
Сообщений: 10
1

Ввод значений из строки или аналог cin >> x в Python

21.11.2019, 23:00. Показов 6142. Ответов 10

Имеется:

Задана последовательность из N целых чисел. Определите, сколько элементов этой последовательности равно первому числу (сам первый элемент не участвует в расчётах!).

Ввод:
Вначале вводится величина N (1 ≤ N ≤ 10^6). Во второй строке записаны N чисел, разделённых единственным пробелом. Эти числа не превосходят 10^9 по модулю.

Вывод:
Выведите единственное число — количество элементов последовательности, совпадающих с первым элементом.

Примеры:

Вход:
6
-5 7 0 -5 3 -5
Выход:
2

Вход:
6
5 7 0 -5 3 -5
Выход:
0

ОГРАНИЧЕНИЯ: 1 s, 32MB

Сама проблема:

При использовании подобных решений, когда считывается вся строка целиком, а не по элементу, как в С++, происходит переполнение памяти и тесты не проходят. Данное решение проходит половину тестов (70/100), но не работает с очень большими данными, выдает Memory Limit Exceeded

Python
1
2
3
input()
arr = list(map(int, input().split()))
print(arr.count(arr[0]) - 1)
Решение на С++, которое проходит все тесты:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include "iostream"
 
using namespace std;
long int a, first_num, ans;
int main() {
    cin >> a;
    for (long int i = 0; i < a; i++) {
        if (i == 0) {
            cin >> first_num;
        }
        else {
            long int k;
            cin >> k;
            if (k == first_num) {
                ans += 1;
            }
        }
    }
    cout << ans;
}
Вопрос:

Как реализовать что-то подобное на питоне, чтобы не выходило за лимит памяти? (Генераторы, которые использую yield тоже выходят за лимиты, поскольку читают строку целиком, ну или я криво их написал )

EDIT1 Для использования доступны только встроенные библиотеки
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.11.2019, 23:00
Ответы с готовыми решениями:

Ввод нескольких значений, поток cin
Привет :) Хотел бы узнать, как можно считать подряд несколько пар значений (например какое то...

Std:cin ввод нескольких значений
Нужно ввести строку с параметром cin &gt;&gt; command; //ввели add_int 5 далее в command у нас...

Бесконечный ввод значений через команду cin
Поставлена задача создать целочисельную матрицу и написать к ней такие ф-ции: будут вводить и...

Cin и ввод строки разными функциями
На одном сайте код cin.read(buff1,3); на другом getline(cin,buff1); нужно считать строку со...

10
Просто Лис
Эксперт Python
4407 / 2804 / 929
Регистрация: 17.05.2012
Сообщений: 8,190
Записей в блоге: 9
22.11.2019, 06:02 2
Хм. Держи генератор:
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
import io
import os
import sys
 
unbuffered_stdin = os.fdopen(sys.stdin.fileno(), 'rb', buffering=0)
 
def myinput_int():
    """Читает числа из потока"""
    buf = io.BytesIO()
    while True:
        ch = unbuffered_stdin.read(1)
        #ch = sys.stdin.read(1)
        #print(ch)
        if ch in b' \n':
            yield int(buf.getvalue())
            buf.truncate(0)
            buf.seek(0)
        elif ch in b'1234567890':
            buf.write(ch)
        else:
            raise NotImplementedError
 
 
for i in myinput_int():
    print(i)
Добавлено через 3 минуты
Всё же так (читает строку):
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
import io
import sys
 
 
def myinput_int():
    """Читает числа из потока"""
    buf = io.StringIO()
    while True:
        ch = sys.stdin.read(1)
        if ch == '\n':
            yield int(buf.getvalue())
            buf.close()
            raise StopIteration
        if ch == ' ':
            yield int(buf.getvalue())
            buf.truncate(0)
            buf.seek(0)
        elif ch in '1234567890':
            buf.write(ch)
        else:
            buf.close()
            raise ValueError(ch)
 
 
for i in myinput_int():
    print(i)
1
3250 / 2052 / 351
Регистрация: 24.11.2012
Сообщений: 4,902
22.11.2019, 06:53 3
Можно попробовать регулярками. Возможно, будет медленно.
Python
1
2
3
4
5
6
7
8
9
10
11
>>> import re
>>> s = "3 14 15 92 65 35"
>>> for match in re.finditer('\d+', s):
        print(int(match.group()))
 
3
14
15
92
65
35
2
Просто Лис
Эксперт Python
4407 / 2804 / 929
Регистрация: 17.05.2012
Сообщений: 8,190
Записей в блоге: 9
22.11.2019, 07:07 4
0x10, можно было бы скормить регулярке поток данных - цены б бы не было! А так вся строка опять хранится в памяти.

Добавлено через 5 минут
Чуть допилил код:
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import io
import sys
 
def myinput_int():
    """Читает числа из потока"""
    with io.StringIO() as buf:
        while True:
            ch = sys.stdin.read(1)
            if ch.isdigit():
                buf.write(ch)
            elif ch == ' ':
                yield int(buf.getvalue())
                buf.truncate(0)
                buf.seek(0)
            elif ch == '\n':
                yield int(buf.getvalue())
                raise StopIteration
            else:
                raise ValueError(ch)
 
 
for i in myinput_int():
    print(i)
3
2 / 2 / 0
Регистрация: 15.10.2018
Сообщений: 10
22.11.2019, 09:33  [ТС] 5
0x10, да, это медленно, теперь выдаёт Time Limit Exceeded, но общий балл за задачу 84/100. Регулярку пришлось немного допилить, чтобы отрицательные значения тоже считала - (\d+|-\d+)

Добавлено через 3 минуты
Рыжий Лис, использовал ваш допиленый код. Выдаёт ошибку питон StopIteration и выводит только первое число 6, когда ввожу любой из примеров. Вы проверяли своё решение на вводном наборе данных (первый пост)?
0
Просто Лис
Эксперт Python
4407 / 2804 / 929
Регистрация: 17.05.2012
Сообщений: 8,190
Записей в блоге: 9
22.11.2019, 10:03 6
Дык первую строку надо отдельно читать:

Python
1
2
3
n = int(input())  # читаем первую строку
for i in myinput_int():  # вторую
    print(i)
1
2 / 2 / 0
Регистрация: 15.10.2018
Сообщений: 10
22.11.2019, 10:30  [ТС] 7
Рыжий Лис, моя ошибка, согласен. Все работает, кроме отрицательных, он их как положительные считывает. Это как-то можно подлатать?

Добавлено через 8 минут
Рыжий Лис, переделал так, но теперь выдаёт ошибку времени, по памяти все прям вообще шик и блеск.
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
import io
import sys
 
 
def myinput_int():
    """Читает числа из потока"""
    k = 0
    with io.StringIO() as buf:
        while True:
            ch = sys.stdin.read(1)
            if ch.isdigit():
                buf.write(ch)
            elif ch == ' ':
                if k:
                    yield -1 * int(buf.getvalue())
                    k = 0
                else:
                    yield int(buf.getvalue())
                buf.truncate(0)
                buf.seek(0)
            elif ch == '-':
                k = 1
            elif ch == '\n':
                if k:
                    yield -1 * int(buf.getvalue())
                    k = 0
                else:
                    yield int(buf.getvalue())
                break
 
 
input()
first, ans = '_', 0
for index, key in enumerate(myinput_int()):
    if index == 0:
        first = key
    elif key == first:
        ans += 1
print(ans)
Ваше решение выше:
[img]https://i.**********/QmzpUQH.png[/img]
Регулярки:
[img]https://i.**********/HGJqnzf.png[/img]
Обычный генератор списков с хранением всех элементов:
[img]https://i.**********/IfM9v35.png[/img]

Звездочки - imgur . com
Миниатюры
Ввод значений из строки или аналог cin >> x в Python   Ввод значений из строки или аналог cin >> x в Python   Ввод значений из строки или аналог cin >> x в Python  

1
2 / 2 / 0
Регистрация: 15.10.2018
Сообщений: 10
22.11.2019, 10:37  [ТС] 8
Касательно времени - программа могла выполняться более, чем 1 секунда, просто компилятор рубит её на 1ой секунде и выдаёт ошибку времени.
0
Просто Лис
Эксперт Python
4407 / 2804 / 929
Регистрация: 17.05.2012
Сообщений: 8,190
Записей в блоге: 9
22.11.2019, 10:55 9
Лучший ответ Сообщение было отмечено VictorMinsky как решение

Решение

Если myinput_int не трогать, то попробуй так:

Python
1
2
3
4
5
6
7
8
input()
gen = myinput_int()
first = next(gen)
ans = 0
for i in gen:
    if i == first:
        ans += 1
print(ans)
Меньше процессора будет тратиться (минус один if внутри цикла).
1
2 / 2 / 0
Регистрация: 15.10.2018
Сообщений: 10
22.11.2019, 11:28  [ТС] 10
Попробовал, все равно выходит за лимиты времени. Стало на пару миллисекунд быстрее в маленьких тестах, в больших по прежнему выходит за пределы.

В любом случае, большое спасибо за помощь. Как я понимаю, для этой задачи нет решения на питоне, в отличие от С++, чтобы получать максимально полный балл (кроме библиотеки numpy, где массивы работают на коде С++, но это нестандартная библиотека ).
0
2 / 2 / 0
Регистрация: 15.10.2018
Сообщений: 10
22.11.2019, 12:03  [ТС] 11
Рыжий Лис, ЭВРИКА!!!
Прикрутил ваше тело к своей регулярке и получилось, еле прошло

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import re
 
 
def split_iter():
    return (x.group(0) for x in re.finditer(r"[-0-9']+", input()))
 
 
input()
gen = split_iter()
first = next(gen)   
ans = 0
for i in gen:
    if i == first:
        ans += 1
print(ans)
Полный балл, 100/100
Миниатюры
Ввод значений из строки или аналог cin >> x в Python  
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.11.2019, 12:03

Есть ли какой-нибудь аналог c# using или python with в c++ ?
В C# (using pattern) и python есть специальные конструкции которые позволяют не следить за...

Аналог декоратора Python или ненормальное програмирование
Всем привет. Часто приходится делать одну и ту же вещь в коде: DWORD time = ::GetTickCount();...

Ввод через пробел. Как остановить ввод. while(cin >> input)
Здравствуйте. Начну с условия задания. Ввести к-во элементов массива. Заполнить массив....

Разработайте программу, осуществляющую ввод 5 значений и нахождение математического ожидания, или среднеквадратического отклонения, или дисперсии при
Разработайте программу, осуществляющую ввод 5 значений и нахождение математического ожидания, или...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.