|
5907 / 3359 / 1036
Регистрация: 03.11.2009
Сообщений: 10,008
|
|||||||||||||||||||||||||||||||||
Оптимизация поиска в листе22.05.2015, 17:14. Показов 2930. Ответов 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 На определенном листе при нажатии на кнопку выводить окно поиска Копирование значений ячеек после поиска по массиву на другом листе книги Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Копировать 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 и пр.
Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала.
Ниже прикреплён. . .
|