Сортировка точек на нескольких линиях

Question

Учитывая, что у нас есть две линии на графике (я только заметил, что я перевернутой цифры на оси Y, это была ошибка, она должна идти от 11-1)

И мы заботимся только о целом числе X пересечениях оси

мы должны заказать эти точки из наибольшего значения Y до самого низкого значения Y, независимо от их положений на осях X (Обратите внимание, я сделал этот ПИК вручную, чтобы они не выстроились идеально).

У меня есть несколько вопросов:

1) я должен предположить, что это известная проблема, но у него есть определенное имя?

2) Существует ли известное оптимальное решение при работе с десятками миллиардов (или сотен миллионов) линий? Наш текущий процесс ручного вычисления каждой точки, а затем сравнения ее с гигантским списком требует часов обработки. Несмотря на то, что у нас может быть сто миллионов строк, нам обычно нужны только 100 или 50 000 результатов, некоторые из которых до сих пор «ниже» других строк, которые вычисляют их точки, не нужны.

Answer 1

1. Ваша структура данных является set кортежей

   lines = {(y0, Δy0), (y1, Δy1), ...} 
   

2. Вам нужно только ntop точки, следовательно, построить set содержащий только верхние ntopyi значения, за один проход над данными

   top_points = choose(lines, ntop) 
   

   EDIT --- выбрать ntop мы должны были следить за наименьшему один, и это интересная информация, так что давайте вернемся и это значение из choose, также мы должны инициализировать decremented

   top_points, smallest = choose(lines, ntop) 
   decremented = top_points 
   

   и начать цикл ...

   while True: 
   

3. Генерировать set из значений уменьшенного

   декрементируются = {(у -Δy, Δy) для у, Δy в top_points}

   decremented = {(y-Δy, Δy) for y, Δy in decremented if y>smallest} 
       if decremented == {}: break 
   

4. Генерировать набор кандидатов

   candidates = top_lines.union(decremented) 
   

5. генерировать новый набор верхних точек

   new_top_points, smallest = choose(candidates, ntop) 
   

   ниже не требуется

6. проверить, если new_top_points == top_points

   if new_top_points == top_points: break 
       top_points = new_top_points</strike> 
   

   , конечно, мы находимся в цикле ...

Трудная часть является choose функция, но я думаю, что this answer на вопрос How can I sort 1 million numbers, and only print the top 10 in Python? мог помочь тебе.

Answer 2

1) Это не очень сложная вещь, просто «нормальная» проблема сортировки.

2) Обычно сортировка требует большого вычислительного времени. Но в вашем случае это одно, где вам не нужно использовать сложные методы сортировки.

На обоих графиках растут или падают постоянно, нет «прыжков». Вы можете использовать это в своих интересах. Основной алгоритм:

• определить, растет ли график падения.
• напишите генератор, который генерирует значения; слева направо, если поднимать, формировать справа налево при падении.
• получить первое значение из обоих графиков
• вставить нижнюю дальше в списке результатов
• получить новое значение из графика, который имел низкое значение
• повторите последние два шага, пока один генератор не является «пустым»
• добавьте элементы слева от других генераторов.

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