Форум программистов, компьютерный форум, киберфорум
Python
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.85/13: Рейтинг темы: голосов - 13, средняя оценка - 4.85
Эксперт по компьютерным сетям
 Аватар для Jabbson
5907 / 3359 / 1036
Регистрация: 03.11.2009
Сообщений: 10,008

Оптимизация поиска в листе

22.05.2015, 17:14. Показов 2930. Ответов 34
Метки нет (Все метки)

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

Дан лист целых числе и число, написать функцию, возвращающую лист из двух значений в листе (проверять слева направо), дающих в сумме второй параметр. Например:

Code
1
2
3
sum_pairs([11, 3, 7, 5],         10)
#              ^--^      3 + 7 = 10
== [3, 7]
Code
1
2
3
4
5
6
sum_pairs([4, 3, 2, 3, 4],         6)
#          ^-----^         4 + 2 = 6, индексы: 0, 2 *
#             ^-----^      3 + 3 = 6, индексы: 1, 3
#                ^-----^   2 + 4 = 6, индексы: 2, 4
#  * пара находится раньше, поэтому это ответ
== [4, 2]
Code
1
2
3
sum_pairs([0, 0, -2, 3], 2)
#  нет пар, дающих в результате 2.
== None
Code
1
2
3
4
5
sum_pairs([10, 5, 2, 3, 7, 5],         10)
#              ^-----------^   5 + 5 = 10, индексы: 1, 5
#                    ^--^      3 + 7 = 10, индексы: 3, 4 *
#  * пара находится раньше, поэтому это ответ
== [3, 7]
Отрицательные числа и дубликаты могут и будут появляться.
Также в функцию будут передаваться листы размером до 10млн элементов. Удостовериться, что код не таймаутится.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def sum_pairs(l, n):
    res = []
    pos = []
    for el in range(len(l)):
        if n-l[el] in l[el+1:]:
            res.append([l[el], n-l[el]])
    for x in res:
        if x[0] != x[1]:
            pos.append([l.index(x[0]), l.index(x[1])])
        else:
            pos.append([[y for y in enumerate(l) if y[1] == x[0]][0][0],
                        [y for y in enumerate(l) if y[1] == x[1]][1][0]])
    if pos:
        return res[[i for i, z in enumerate(pos) if pos[i][1] == min([z[1] for z in pos])][0]]
    else:
        return None
код с комментариями
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
def sum_pairs(l, n):
    res = []
    pos = []
 
    for el in range(len(l)):
        """ тут я обхожу все элементы листа l и добавляю их в лист res в том случае,
            если в оставшейся справа части листа l есть элемент, который в сумме с
            выбранным элементом дают n"""
        if n-l[el] in l[el+1:]:
            res.append([l[el], n-l[el]])
 
    for x in res:
        """ тут я обхожу все элементы (тоже листы) листа res и проверяю не одинаковы ли
            элементы в каждом из листов (case [5, 5]), и возвращаю позиции этих элементов
            в листе l, если они не одинаковы, а обратном случае - 1 вхождение первого
            элемента и второе вхождение второго элемента"""
        if x[0] != x[1]:
            pos.append([l.index(x[0]), l.index(x[1])])
        else:
            pos.append([[y for y in enumerate(l) if y[1] == x[0]][0][0],
                        [y for y in enumerate(l) if y[1] == x[1]][1][0]])
    if pos:
        """ тут я возвращаю элементы листа l по позициям из pos, если таких позиций неколько
            возвращаю те, второй [1] элемент которых наименьший (условие с нахождение пары 
            раньше)"""
        return res[[i for i, z in enumerate(pos) if pos[i][1] == min([z[1] for z in pos])][0]]
    else:
        return None

На этот момент, код, который я написал, задачу решает, нерешенной осталась одна проблема - с листом в 10млн элементов. При выполнении этого теста задача прерывается с ошибкой превышения объема памяти:
Traceback:
in
in sum_pairs
MemoryError
Полагаю, надо использовать memoization. Прошу помощи с тем, как это сделать. Если я верно понимаю, memoization - это своего рода кеширование запросов для быстрого доступа к уже совершенным запросам, вместо выполнения их заново. Представлен функцией, декорирующей данную функцию.

Данные для проверки:

l1 = [1, 4, 8, 7, 3, 15] # [1, 7]
l2 = [1, -2, 3, 0, -6, 1] # [0, -6]
l3 = [20, -13, 40] # None
l4 = [1, 2, 3, 4, 1, 0] # [1, 1]
l5 = [10, 5, 2, 3, 7, 5] # [3, 7]
l6 = [4, -2, 3, 3, 4] # [4, 4]
l7 = [0, 2, 0] --> [0, 0]
l8 = [5, 9, 13, -3] # [13, -3]

print sum_pairs(l1, 8)
print sum_pairs(l2, -6)
print sum_pairs(l3, -7)
print sum_pairs(l4, 2)
print sum_pairs(l5, 10)
print sum_pairs(l6, 8)
print sum_pairs(l7, 0)
print sum_pairs(l8, 10)
Тут можно пошагово посмотреть выполнение первого вызова:


Сразу оговорюсь, что питон 2.7, functools.lru_cache не подходит.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
22.05.2015, 17:14
Ответы с готовыми решениями:

Оптимизация поиска анаграмм
Помогите, пожалуйста, оптимизировать программу (память и время), она работает крайне медленно. Задача программы: Анагра́мма —...

Кнопка поиска в конкретном листе
День добрый! Проблема такая- создал большую таблицу с расчетами (склад - приход, расход). Каждый лист это новый месяц. Последний лист...

Макрос для поиска значений на листе
Помогите написать макрос в Excel Смысл макроса примерно такой. В книги есть листы где каждый лист это определнный месяц. В листах...

34
Эксперт по компьютерным сетям
 Аватар для Jabbson
5907 / 3359 / 1036
Регистрация: 03.11.2009
Сообщений: 10,008
22.05.2015, 20:20  [ТС]
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от Marinero Посмотреть сообщение
found=False
я сделал found = 0

PS. теперь каждый раз думаю - 0 или 1 после баша
0
Эксперт NIX
 Аватар для Marinero
2796 / 2039 / 682
Регистрация: 02.03.2015
Сообщений: 6,509
23.05.2015, 11:32
Ещё одна реализация через index (может будет быстрее).
Вот только не уверен правильно ли описал try/except:
  1. правильно next или pass
  2. pos1 = el1 на своем месте или его после next надо?
  3. и может except(ValueError)?
Python
1
2
3
4
5
6
7
8
9
10
11
12
def sum_pairs(l, n):
        pos1 = -1
        pos2 = len(l)
        for el1 in range(pos2):
                if el1 >= pos2:
                        break
                try:
                        pos2 = l.index(n - l[el1], el1 + 1, pos2)
                        pos1 = el1     
                except:                
                        next
        return (l[pos1], l[pos2]) if pos1 >= 0 else None
0
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
23.05.2015, 11:42
Цитата Сообщение от Marinero Посмотреть сообщение
Python
except:                
    next
Странное выражение. Что ты этим хочешь сделать?

Добавлено через 3 минуты
Цитата Сообщение от Marinero Посмотреть сообщение
правильно next или pass
А, только заметил. В общем, формально и то и другое, но логично pass.
0
Эксперт по компьютерным сетям
 Аватар для Jabbson
5907 / 3359 / 1036
Регистрация: 03.11.2009
Сообщений: 10,008
23.05.2015, 11:43  [ТС]
6 секундный порог для 10млн листа не берется)
0
Эксперт NIX
 Аватар для Marinero
2796 / 2039 / 682
Регистрация: 02.03.2015
Сообщений: 6,509
23.05.2015, 12:05
Jabbson, Новый код или старый? Быстрее нового вряд ли что-то придумаешь, разве что из модулей более быстрый поиск можно поискать (в numpy, например)
0
Эксперт по компьютерным сетям
 Аватар для Jabbson
5907 / 3359 / 1036
Регистрация: 03.11.2009
Сообщений: 10,008
23.05.2015, 12:09  [ТС]
Новый.
В комментариях к заданию идет речь об использовании memoization, кешировании и декораторах.
Полагаю, именно проблема в обработке больших объемов данных.
0
Эксперт С++
 Аватар для Avazart
8489 / 6156 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
23.05.2015, 22:29
А такой вопрос, а сортировать список, а потом применять бинарный поиск не даст выигрыш во времени?
Т.е сортирует список, делаем обход по списку берем значение элемента x и ищем двоичным поиском элемент y= сумма- x;

Добавлено через 11 минут
Цитата Сообщение от Jabbson Посмотреть сообщение
В комментариях к заданию идет речь об использовании memoization, кешировании и декораторах.
Memoization в Python

Только я не особо понимаю как это поможет ведь сложение это не такая уж и затратная операция как по мне.
0
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
23.05.2015, 23:18
Цитата Сообщение от Avazart Посмотреть сообщение
А такой вопрос, а сортировать список, а потом применять бинарный поиск не даст выигрыш во времени?
Обращение к set - O(1), бинпоиск - O(log(n)).

Добавлено через 8 минут
Плюс ещё в варианте с сортировкой надо к элементам прицеплять индекс их первого вхождения, чтобы правильную пару выбрать.
0
Эксперт С++
 Аватар для Avazart
8489 / 6156 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
23.05.2015, 23:40
Цитата Сообщение от Somebody Посмотреть сообщение
Обращение к set - O(1),
Разве? А что же там в основе реализации? Хеш-таблица?

Добавлено через 46 секунд
Цитата Сообщение от Somebody Посмотреть сообщение
люс ещё в варианте с сортировкой надо к элементам прицеплять индекс их первого вхождения, чтобы правильную пару выбрать.
Ну это да недочет, если важен порядок, но не такой уж значимый думаю.

Добавлено через 14 минут
Цитата Сообщение от Avazart Посмотреть сообщение
Разве? А что же там в основе реализации? Хеш-таблица?
А уже сам нашел https://wiki.python.org/moin/TimeComplexity
0
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
23.05.2015, 23:46
Да, хеш-таблица. Конечно, в худшем случае сортировка будет лучше, но тест с худшим случаем подгонять под конкретную реализацию придётся.
0
Эксперт Python
 Аватар для dondublon
4663 / 2082 / 367
Регистрация: 17.03.2012
Сообщений: 10,203
Записей в блоге: 6
25.05.2015, 08:36
Такие вещи просто обязательно надо делать с numpy. Иначе питоновские циклы будут крутиться вечно.
Учитывая, что у нас ограничения по памяти, двумерные массивы делать не нужно - памяти может не хватить на таких масштабах.
Поэтому делаем цикл с кешированием. Примерно так:
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def get_where_sums_is(arr, s):
    """s = sum"""
    r = np.arange(len(arr))
    cache = {}
    for i in xrange(len(arr)):
        a = arr[i]
        if a > s:
            pass  # skip values greater then s
        else:
            indices = cache.get(a)
            if indices is None:
                indices = r[arr == s - a]
                cache[a] = indices
            print i, ":", indices  # what to do with it?
Остаётся вопрос - что делать с найденными индексами, но тут уж возможно варианты. Если на быстродействие закладываемся, то просто сляпать из них корежи - не есть хорошо.
0
Эксперт NIX
 Аватар для Marinero
2796 / 2039 / 682
Регистрация: 02.03.2015
Сообщений: 6,509
25.05.2015, 08:58
dondublon, Мы тут изначальный вариант сильно подсократили, может опираясь на него что-то посоветуешь?
0
Эксперт Python
 Аватар для dondublon
4663 / 2082 / 367
Регистрация: 17.03.2012
Сообщений: 10,203
Записей в блоге: 6
25.05.2015, 09:49
Marinero, там хитрый алгоритм, я не очень понял.
Главное - имея цикл по pos2, мы меняем pos2 внутри цикла.
0
Эксперт NIX
 Аватар для Marinero
2796 / 2039 / 682
Регистрация: 02.03.2015
Сообщений: 6,509
25.05.2015, 10:03
dondublon, Основная идея алгоритма тут. Цикл вообще по len(l) == pos2 в начале цикла. А потом уже его изменение на границу цикла не влияет (так что пришлось добавить if el1 >= pos2: break)
0
Эксперт Python
 Аватар для dondublon
4663 / 2082 / 367
Регистрация: 17.03.2012
Сообщений: 10,203
Записей в блоге: 6
25.05.2015, 10:21
А, ясно.
Там для каждого el1 находится первый, дающий в сумме n, а я думал, нужно все.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
25.05.2015, 10:21

Правильная организация поиска на листе Excel
Добрый день! Бьюсь с проблемой второй день. Суть в чем: Макрос сканирует лист входящей книги (inputbook) построчно, находит необходимую...

Функция поиска макс прогресии в листе
Доброго времени суток, есть вот такая функция int max(node *ptr){ if(ptr == 0) return 0; int count, tmp; tmp = count=...

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

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

Копирование значений ячеек после поиска по массиву на другом листе книги
Добрый день! Помогите, пожалуйста, разобраться с задачей. Необходимо автоматически заполнять лист "вышли". На листе...


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

Или воспользуйтесь поиском по форуму:
35
Ответ Создать тему
Новые блоги и статьи
Копировать Windows на новый диск на UEFI
damix 17.10.2026
https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .
ИИ не может найти нужный язык в списке
Supersumestria 05.10.2026
Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO
zorxor 05.10.2026
Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .
Программный домашний кинотеатр
russiannick 27.09.2026
Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
Мобильное приложение ColorStep
pavlinmavlin 17.09.2026
Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части
Maks 13.09.2026
Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru