|
5907 / 3359 / 1036
Регистрация: 03.11.2009
Сообщений: 10,008
|
|||||||||||||||||||||||||||||||||
Оптимизация поиска в листе22.05.2015, 17:14. Показов 2939. Ответов 34
Метки нет (Все метки)
Есть задача
Дан лист целых числе и число, написать функцию, возвращающую лист из двух значений в листе (проверять слева направо), дающих в сумме второй параметр. Например:
Также в функцию будут передаваться листы размером до 10млн элементов. Удостовериться, что код не таймаутится.
код с комментариями
На этот момент, код, который я написал, задачу решает, нерешенной осталась одна проблема - с листом в 10млн элементов. При выполнении этого теста задача прерывается с ошибкой превышения объема памяти:
Данные для проверки:
Сразу оговорюсь, что питон 2.7, functools.lru_cache не подходит.
0
|
|||||||||||||||||||||||||||||||||
| 22.05.2015, 17:14 | |
|
Ответы с готовыми решениями:
34
Кнопка поиска в конкретном листе Макрос для поиска значений на листе |
|
5907 / 3359 / 1036
Регистрация: 03.11.2009
Сообщений: 10,008
|
|
| 22.05.2015, 20:20 [ТС] | |
|
0
|
|
|
2796 / 2039 / 682
Регистрация: 02.03.2015
Сообщений: 6,509
|
||||||
| 23.05.2015, 11:32 | ||||||
|
Ещё одна реализация через index (может будет быстрее).
Вот только не уверен правильно ли описал try/except:
0
|
||||||
|
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
|
|||
| 23.05.2015, 11:42 | |||
|
Добавлено через 3 минуты
0
|
|||
|
5907 / 3359 / 1036
Регистрация: 03.11.2009
Сообщений: 10,008
|
|
| 23.05.2015, 11:43 [ТС] | |
|
6 секундный порог для 10млн листа не берется)
0
|
|
|
2796 / 2039 / 682
Регистрация: 02.03.2015
Сообщений: 6,509
|
|
| 23.05.2015, 12:05 | |
|
Jabbson, Новый код или старый? Быстрее нового вряд ли что-то придумаешь, разве что из модулей более быстрый поиск можно поискать (в numpy, например)
0
|
|
|
5907 / 3359 / 1036
Регистрация: 03.11.2009
Сообщений: 10,008
|
|
| 23.05.2015, 12:09 [ТС] | |
|
Новый.
В комментариях к заданию идет речь об использовании memoization, кешировании и декораторах. Полагаю, именно проблема в обработке больших объемов данных.
0
|
|
|
|
||
| 23.05.2015, 22:29 | ||
|
А такой вопрос, а сортировать список, а потом применять бинарный поиск не даст выигрыш во времени?
Т.е сортирует список, делаем обход по списку берем значение элемента x и ищем двоичным поиском элемент y= сумма- x; Добавлено через 11 минут Только я не особо понимаю как это поможет ведь сложение это не такая уж и затратная операция как по мне.
0
|
||
|
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
|
||
| 23.05.2015, 23:18 | ||
|
Добавлено через 8 минут Плюс ещё в варианте с сортировкой надо к элементам прицеплять индекс их первого вхождения, чтобы правильную пару выбрать.
0
|
||
|
|
||||
| 23.05.2015, 23:40 | ||||
|
Добавлено через 46 секунд Добавлено через 14 минут
0
|
||||
|
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
|
|
| 23.05.2015, 23:46 | |
|
Да, хеш-таблица. Конечно, в худшем случае сортировка будет лучше, но тест с худшим случаем подгонять под конкретную реализацию придётся.
0
|
|
|
|
||||||
| 25.05.2015, 08:36 | ||||||
|
Такие вещи просто обязательно надо делать с numpy. Иначе питоновские циклы будут крутиться вечно.
Учитывая, что у нас ограничения по памяти, двумерные массивы делать не нужно - памяти может не хватить на таких масштабах. Поэтому делаем цикл с кешированием. Примерно так:
0
|
||||||
|
|
|
| 25.05.2015, 10:21 | |
|
А, ясно.
Там для каждого el1 находится первый, дающий в сумме n, а я думал, нужно все.
0
|
|
| 25.05.2015, 10:21 | |
|
Правильная организация поиска на листе Excel Функция поиска макс прогресии в листе Организация быстрого поиска данных на листе Excel На определенном листе при нажатии на кнопку выводить окно поиска Копирование значений ячеек после поиска по массиву на другом листе книги Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
| Опции темы | |
|
|
Новые блоги и статьи
|
|||
|
Baragoz - DPS/HPS бот для WoW 3.3.5a, многоязычный
AmbA 26.10.2026
Хотите ещё ботов? У меня есть один! А я пока отдохну от него.
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=12062&stc=1&d=1793007952
Инструкция внутри.
Сразу отвечу: А в PvP с ним. . .
|
Особенности gif сгенерированных в Си
russiannick 21.10.2026
Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности.
Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .
|
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3)
8Observer8 18.10.2026
Содержание блога | English Version
Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .
|
Локальный http сервер
Argus19 17.10.2026
Локальный http сервер
На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .
|
|
Копировать 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.
В помощники взял Яндекс-Алису.
Было создано три зала на разные интересы.
исторические и ретро
сериал Хичкок. . .
|