LINUX.ORG.RU

Готовая библиотека на подсчет количества пересечений оси графиком.

 ,


0

2

Есть ось Х со сдвигом по Y = 1.1, есть график плавающий между Y = 0.9 и Y = 1.2. График состоит из большого массива соединенных между собой последовательно координат.

Есть готовая библиотека, выполняющая подсчеты пересечений графиком оси X?

PS: Да я знаю что можно использовать цикл+условие, но интересует именно готовое решение.

Вот тебе готовое решение:

>>> def steemandlinux_is_too_lazy_to_write_two_fucking_lines_of_code(s):
...   return sum((x >= 0) != (y >= 0) for x, y in zip(s[:-1], s[1:]))
... 
>>> steemandlinux_is_too_lazy_to_write_two_fucking_lines_of_code(
... [1, 2, 3, -1, -3, 1, -1, 1])
4
>>> 

Библиотека, блин… Жесть вообще. Скоро люди вообще кодить разучатся.

i-rinat ★★★★★ ()
Последнее исправление: i-rinat (всего исправлений: 1)
Ответ на: комментарий от beresk_let

Вроде норм. Только в питоне мантра: «явное лучше неявного». Фильтровать нули с помощью None это слишком хитро. В три часа ночи можно и не сообразить, что это, как и зачем.

i-rinat ★★★★★ ()
Ответ на: комментарий от i-rinat

А это будет работать медленнее включений из-за лямбд. Да-да, преждевременная оптимизация и всё такое, но зачем заводить вредные привычки.

beresk_let ★★★★★ ()
Последнее исправление: beresk_let (всего исправлений: 1)

Предлагаю взамен неинтересной задачи её не настолько слабоумного старшего брата.

Пусть есть длинный исходный массив чисел. Надо построить алгоритм нахождения количества пересечений нуля за время O(ln(n)) для любого не заданного наперёд подмассива длины n.

Это аналог RMQ-задач. Сперва надо подумать, как бы правильно определить, что такое «количество пересечений нуля» и какую операцию над какой группой выбрать, чтобы правильно считать эти количества пересечений.

А ещё можно в конец оборзеть и попросить O(1) :)

anonymous ()
Ответ на: комментарий от knovich

Лол, мемы про метапрог упоминаются даже теми, кто не принимал участия в этой мыльной опере.

Ну а библиотека ради одной формулы - это перебор, автору потенциальной либы лучше запилить все основные вычисления из предметной области. Усилий по сопровождению каждой функции меньше + больше шансов, что либа кому-то понадобится.

Это я про гипотетическую «либу из одной функции» vs «либу для всей предметной области».

arturianec100 ()
Ответ на: комментарий от anonymous

Особо быстрые алгоритмы часто требуют специфических структур данных, а не просто «массив или список». И вообще - разработка принципиально нового алгоритма не входит в компетенцию многих прикладных разработчиков.

arturianec100 ()
Ответ на: комментарий от anonymous

Пусть есть длинный исходный массив чисел. Надо построить алгоритм нахождения количества пересечений нуля за время O(ln(n)) для любого не заданного наперёд подмассива длины n.

Закэщировать в массиве все ответы?

monk ★★★★★ ()
Ответ на: комментарий от monk

Когда исходный массив и так «длинный» (пусть N), что тогда делать с массивом длиной N^2? Не, в таких вещах надо память кушать не более, чем линеарифмично. Время на предобработку тоже.

anonymous ()
Ответ на: комментарий от anonymous

Пусть есть длинный исходный массив чисел. Надо построить алгоритм нахождения количества пересечений нуля за время O(ln(n)) для любого не заданного наперёд подмассива длины n.

Сводится к подсчёту суммы элементов подмассива.

Допустим, у тебя элементы a₁, a₂, a₃, …, aₙ. Пусть будет a₁ + a₂ + a₃ + … + aₙ = S. Допустим, хотим посчитать сумму aₖ + aₖ₊₁ + … + aₚ₋₁ + aₚ. Представляем сумму всех элементов массива как (a₁ + a₂ + … + aₖ₋₁) + (aₖ + aₖ₊₁ + … + aₚ₋₁ + aₚ) + (aₚ₊₁ + … + aₙ) = S. Считаем всевозможные суммы (a₁ + a₂ + … + aₖ), их N+1 штук. Считаем всевозможные суммы (aₚ + … + aₙ), их тоже N+1 штук. Сумму подмассива k~p вычисляем разницей между S и двумя запросами к вспомогательным массивам. Скорость работы — O(1), вспомогательное место — O(N).

i-rinat ★★★★★ ()
Ответ на: комментарий от i-rinat

Кстати, соглашусь, мысль правильная, на фиг все эти RMQ. Только хочу добавить два момента. 1. Чешется упростить предобработку до подсчёта всех Sₖ = a₁ + a₂ + … + aₖ. Тогда aₖ + aₖ₊₁ + … + aₚ₋₁ + aₚ = Sₚ - Sₖ₋₁.

2. Аддитивной величины aₖ пока нет, которую суммировать будем. Мы там ещё не договорились, что делать с «касаниями».

anonymous ()
Ответ на: комментарий от anonymous

Чешется упростить предобработку до подсчёта всех Sₖ

А, ну да. Что-то я ступил.

Аддитивной величины aₖ пока нет, которую суммировать будем.

Это же число пересечений на отрезке. Во время предобработки определяем.

Мы там ещё не договорились, что делать с «касаниями».

Забить. Вообще на задачу забить. Совсем.

К реальности она отношения не имеет, это не решение какой-то конкретной проблемы. Для учебной задачи она слишком мутная.

i-rinat ★★★★★ ()