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

gnuplot ?

А он разве считает? Или только чертит?

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

>>> 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
>>> 

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

Мне кажется, для последовательности (-1, 0, -1) функция выдаст два пересечения графика, тогда как на самом деле там ни одного.

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

Я бы предложил так:

def there_are_three_lines_but_steemandlinux_is_still_too_lazy(s):
    s = tuple(filter(None, s))
    return sum(s[i] * s[i-1] < 0 for i in range(1, len(s)))

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

Видимо, кто какие конструкции чаще использует, тому они и кажутся более очевидными. Мне от

tuple(item for item in s if item != 0)

Ну можно же тот же filter, но с lambda x: x != 0.

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

Фильтровать нули с помощью None это слишком хитро

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

При чём тут функциональное программирование в тегах?

ТС-у нужна функция, считающая пересечения - значит функциональное.

Да, но ведь пересечение оси графиком, значит, графическое программирование. Кто сказал «Метапрог»?

ТС-у нужна библиотека, так что программирование — библиотечное.

На самом деле там 1/2.

А, нет, извините. На самом деле там 1. 1/2 будет при (1, 1, 1, 0), например.

Касание графиком нуля — это в любом случае не пересечение графиком оси абсцисс.

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

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

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

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

Ню-ню :)

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

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

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

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

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

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

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

Пусть есть длинный исходный массив чисел. Надо построить алгоритм нахождения количества пересечений нуля за время 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).

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

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

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

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

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

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

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

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

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