Как ускорить программу

@Антон Ф · Регистрация: 17.07.2019

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

Вот задача:
Требуется определить в заданном массиве количество элементов, равных искомому числу.

Входные данные
В первой строке вводится одно натуральное число N, не превосходящее 10^5: количество чисел в массиве.

Во второй строке вводятся N натуральных чисел, не превосходящих 10^9, каждое следующее не меньше предыдущего.

В третьей строке вводится количество искомых чисел M - натуральное число, не превосходящее 10^6.

В четвертой строке вводится M натуральных чисел, не превосходящих 10^9.

Выходные данные
Для каждого запроса выведите в отдельной строке одно число: количество элементов массива, равных числу-запросу. Элементы массива нумеруются с единицы.

Если в массиве нет такого числа, выведите 0.
Время: 6 сек
Память: 256 мегабайт
Я сделал так:

Python
1
2
3
4
5
6
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
for i in range(m):
    print(a.count(b[i]))

Но последний тест не зашёл по времени(6.068 сек)

@Alli_Lupin · 21.08.2019, 17:07

Антон Ф, Можно попробовать стандартные способы ускорения, например, PyPy.

@Semen-Semenich · 21.08.2019, 20:12

Антон Фмне кажется не зря в задании сказано

Сообщение от Антон Ф

каждое следующее не меньше предыдущего.

то есть если после искомого стоит число больше то дальнейший поиск не имеет смысла то есть сократится время на итерации по остальным числам ну и все таки первая N для того и дана чтоб её использовать в коде

Python
1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
for i in range(m):
    count_ = 0
    for j in range(n):
        if a[j] > b[i]:
            break
        elif a[j] == b[i]:
            count_ += 1
    print(count_)

@Catstail · 23.08.2019, 11:25

Нужно применять двоичный поиск

Рыжий Лис · 23.08.2019, 13:56

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

Нужно применять двоичный поиск

Для каждого запроса? Думаю, будет долго.

Можно попробовать так:

Python
1
2
3
4
5
6
7
8
9
10
from collections import Counter
 
n = input()
arr = input().split(' ')  # не будем тратить время на конвертацию
m = input()
ls = input().split(' ')
 
c = Counter(arr)
for i in ls:
    print(c[i])

@dondublon · 23.08.2019, 17:24

Если тупой перебор через count - вычислительная сложность O(N).
Если бинарный поиск - то M*O(log(N)).

Отсюда вывод - берём N и M, считаем, что меньше, и делаем так

Добавлено через 1 минуту
Хотя есть и третий способ. Упорядочить массив-запрос, и идти по нему. Одновременно будет двигаться указатель по a.

@Catstail · 24.08.2019, 11:19

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
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
for bb in b:
    print(binSearch(a,bb)
 
def binSearch(arr,v):
    n=len(arr)
    left=0
    right=n-1
    count=0
    if v > arr[n-1]:
        return 0
    if v < arr[0]:
        return 0
    while(True):
        middle=(left+right)//2
        if arr[middle]==v:
            count+=1
            i=middle-1
            while (i >= 0) and (arr[i]==v):
                count+=1
                i-=1
            i=middle+1
            while (i < n) and (arr[i]==v):
                count+=1
                i+=1
            return count
        elif middle==left | middle==right:
            return count
        elif arr[middle] > v:
            right=middle
        else:
            left=middle

https://ideone.com/JQoWuj

@ksyrx · 26.08.2019, 00:14

Во-первых, кинь все в def (если пользуешься сишной реализацией), ибо локальные переменные эффективнее глобальных.

Юзай xrange вместо range, если питон 2.x

@hacthies · 27.08.2019, 16:56

Catstail, зачем так усложнять себе жизнь? bisect работает идеально в питоне.

Нашел левую границу, правую границу, а дальше все легко - вычел из правой левую и готово.

@Catstail · 27.08.2019, 18:34

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

@dondublon · 27.08.2019, 18:39

Catstail, позвольте не согласиться. Использовать готовые библиотеки - это гуд, а писать то, что уже написано ранее - это переизобретать велосипед.

Другой вопрос, что в данной задаче bisect не поможет. (hacthies)

@Catstail · 27.08.2019, 18:46

Про велосипеды я слышу регулярно. Но совершенно очевидно, что тот, кто боится изобрести велосипед, вообще ничего не изобретет. Умение программировать - это знание алгоритмов и умение их реализовать. А этот навык достигается только изобретением велосипедов

@dondublon · 27.08.2019, 19:18

Catstail, не думаю.
Это, скорее, относится, к олимпиадному программированию, то есть из спортивного интереса. В продакшне же каждый велосипед - потеря рабочего времени, и это также очевидно. Поэтому и ценится умение использовать готовое, то есть знание библиотек. "Умение программировать" в продакшне также включает в себя другие навыки, относящиеся к работе в команде.
Очевидно, что личный велописед будет хуже стыковаться с другими модулями, написаными другими людьми, плюс это всё ещё и надо будет читать.
Вот представьте себе, сидит такой "наследник", втыкает в легаси и вдруг его осеняет - "!"№;;%:?, это ж бинарный поиск!" А время уже потеряно.

@Catstail · 27.08.2019, 20:47

dondublon, да пожалуйста. Все зависит от целей подготовки специалиста. Если готовится аккуратный исполнитель, то он, разумеется, должен быть в меру туп. Но если человек хочет решать самостоятельные творческие задачи, то ему нужна не столько аккуратность, сколько знание алгоритмов и структур данных. А познается все это, извините, на "велосипедах".

@dondublon · 28.08.2019, 12:26

Хех... Сам себя не похвалишь - никто не похвалит

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

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

Аккуратный человек не может быть тупым.
Я говорил про человека, который умеет работать в команде, с другими людьми. Сюда входит не только отказ от велосипедов, но и, к примеру, знание ООП и умение его применять. Это как частный случай задачи по организации кода вообще. Хорошо разбить код на объекты - с этой задачей тупой не справится, тут думать надо. Тоже творческая задача.
По теме: https://en.wikipedia.org/wiki/... _the_small
Работать с людьми вообще сложнее, чем с техникой и программами. Эта область куда хуже формализуется. Так что тут простор для творчества - ого-го.

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

Но если человек хочет решать самостоятельные творческие задачи, то ему нужна не столько аккуратность, сколько знание алгоритмов и структур данных.

Если человек хочет решать творческие задачи - ему нужно развивать творческое мышление. Отдельная большая задача.
Знание алгоритмов, тут, безусловно, в плюс - но знание, а не переписывание их при каждом удобном случае.
Архитекторы не занимаются технологией изготовления кирпичей и бетонных плит (в массе своей).

@Catstail · 28.08.2019, 18:02

dondublon, "в меру туп" - это метафора. В промышленной разработке (тем более - при командной работе) безусловно нужно использовать библиотеки.

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

Знание алгоритмов, тут, безусловно, в плюс - но знание, а не переписывание их при каждом удобном случае.

- а как их узнаешь, не реализовывая? Чисто теоретически, "всухую"? Неэффективно. Нужны тренировки. (Сколько раз переписывать - ну, пока не отложится в сознании! Это индивидуально.) И по-моему, Форум - это и есть место для тренировки. Кстати, ТС просит помощи не в промышленной разработке, а в типичной учебной задаче.

Посмотрим теперь на ситуацию глазами преподавателя:

При моем подходе тот, кто учится, не только решит задачу, но и поймет, почему примененный алгоритм позволяет ускорить решение. И реализацию свою слепит худо-бедно.

При подходе моих оппонентов, тот, кто учится, поймет, что binsearch работает быстрее. Почему? На этот вопрос он ответить не сумеет.

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

Архитекторы не занимаются технологией изготовления кирпичей и бетонных плит (в массе своей).

- верно. У реальной архитектуры есть специфика, отличающая ее от разработки ПО. Вот создается, к примеру, новый язык программирования. Творческая задача? Безусловно! Допустим, в качестве языка реализации выбран некий язык X. У этого языка есть набор библиотек. И вот разработчику нового языка понадобилась сортировка. Выясняется, что стандартная сортировка языка X неудобна или вообще не подходит. Для того могут быть тысячи причин. Что делать в этой ситуации "архитектору", который о сортировке знает только то, что вызывается она посредством "sort"? Ну, хорошо. Худо-бедно он справился. Язык создан. А теперь на нем нужно реализовывать библиотеку стандартных алгоритмов. И опять вопрос - что будет делать "архитектор", не знающий реализаций алгоритмов, а знающий лишь их названия? Вот реальная ситуация для "творческой задачи".

Новые блоги и статьи Все статьи Все блоги /
Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .

@Alli_Lupin 5037 / 1064 / 149 Регистрация: 29.01.2013 Сообщений: 6,214
	21.08.2019, 17:07
	Антон Ф, Можно попробовать стандартные способы ускорения, например, PyPy. 0

@Catstail Супер-модератор 38171 / 21106 / 4307 Регистрация: 12.02.2012 Сообщений: 34,697 Записей в блоге: 14
	23.08.2019, 11:25
	Нужно применять двоичный поиск 0

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	23.08.2019, 17:24
	Если тупой перебор через count - вычислительная сложность O(N). Если бинарный поиск - то MO(log(N)). Отсюда вывод - берём N и M, считаем, что меньше, и делаем так Добавлено через 1 минуту* Хотя есть и третий способ. Упорядочить массив-запрос, и идти по нему. Одновременно будет двигаться указатель по a. 1

@ksyrx 207 / 58 / 19 Регистрация: 18.02.2018 Сообщений: 256
	26.08.2019, 00:14
	Во-первых, кинь все в def (если пользуешься сишной реализацией), ибо локальные переменные эффективнее глобальных. Юзай xrange вместо range, если питон 2.x 0

@hacthies 8 / 12 / 2 Регистрация: 08.08.2019 Сообщений: 63
	27.08.2019, 16:56
	Catstail, зачем так усложнять себе жизнь? bisect работает идеально в питоне. Нашел левую границу, правую границу, а дальше все легко - вычел из правой левую и готово. 0

@Catstail Супер-модератор 38171 / 21106 / 4307 Регистрация: 12.02.2012 Сообщений: 34,697 Записей в блоге: 14
	27.08.2019, 18:34
	Пользоваться библиотечной программой - это подмена умения программировать знанием библиотек. Для этого много ума не требуется. 0

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	27.08.2019, 18:39
	Catstail, позвольте не согласиться. Использовать готовые библиотеки - это гуд, а писать то, что уже написано ранее - это переизобретать велосипед. Другой вопрос, что в данной задаче bisect не поможет. (hacthies) 0

@Catstail Супер-модератор 38171 / 21106 / 4307 Регистрация: 12.02.2012 Сообщений: 34,697 Записей в блоге: 14
	27.08.2019, 18:46
	Про велосипеды я слышу регулярно. Но совершенно очевидно, что тот, кто боится изобрести велосипед, вообще ничего не изобретет. Умение программировать - это знание алгоритмов и умение их реализовать. А этот навык достигается только изобретением велосипедов 1

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	27.08.2019, 19:18
	Catstail, не думаю. Это, скорее, относится, к олимпиадному программированию, то есть из спортивного интереса. В продакшне же каждый велосипед - потеря рабочего времени, и это также очевидно. Поэтому и ценится умение использовать готовое, то есть знание библиотек. "Умение программировать" в продакшне также включает в себя другие навыки, относящиеся к работе в команде. Очевидно, что личный велописед будет хуже стыковаться с другими модулями, написаными другими людьми, плюс это всё ещё и надо будет читать. Вот представьте себе, сидит такой "наследник", втыкает в легаси и вдруг его осеняет - "!"№;;%:?, это ж бинарный поиск!" А время уже потеряно. 0

@Catstail Супер-модератор 38171 / 21106 / 4307 Регистрация: 12.02.2012 Сообщений: 34,697 Записей в блоге: 14
	27.08.2019, 20:47
	dondublon, да пожалуйста. Все зависит от целей подготовки специалиста. Если готовится аккуратный исполнитель, то он, разумеется, должен быть в меру туп. Но если человек хочет решать самостоятельные творческие задачи, то ему нужна не столько аккуратность, сколько знание алгоритмов и структур данных. А познается все это, извините, на "велосипедах". 1