Интерполировать массив python, чтобы минимизировать максимальную разницу между элементами

Каков краткий и читабельный способ интерполяции одномерного массива так, чтобы максимальная разница между элементами была минимальной?

Например, если бы у меня был массив [4 9 13 25], и мне было разрешено добавить еще 1 число, чтобы минимизировать максимальную разницу между элементами, я бы вставил 19 между 13 и 25 (максимальная разница теперь равна 6, а не 12).

Конечно, хороший ole 'for loop сделает это, но для потомков есть менее подробный подход, чем приведенный ниже?

# current array
nums = np.array([4.0, 9.0, 13.0, 25.0])
# size of new array
N=10

# recursively find max gap (difference) and fill it with a mid point    
for k in range(N-len(nums)):
    inds = range(len(nums))
    # get the maximum difference between two elements
    max_gap = np.argmax(np.diff(nums))
    # put a new number that's equidistant from the two element values
    new_num = np.interp(np.mean([inds[max_gap],inds[max_gap+1]]), inds, nums)
    nums = np.insert(nums, max_gap+1, new_num)
    print nums

Этот пример интерполирует массив 1D, заполняя области, где наибольшая разница была:

[  4.   9.  13.  19.  25.]
[  4.   9.  13.  16.  19.  25.]
[  4.   9.  13.  16.  19.  22.  25.]
[  4.    6.5   9.   13.   16.   19.   22.   25. ]
[  4.    6.5   9.   11.   13.   16.   19.   22.   25. ]
[  4.    6.5   9.   11.   13.   14.5  16.   19.   22.   25. ]

редактировать 1: Как показывают комментарии, существует компромисс между удобочитаемостью, эффективностью и точностью. Из этих трех атрибутов для меня наиболее важным является удобочитаемость. Я все еще даю +1 за все и все улучшения моего вышеупомянутого алгоритма, хотя, поскольку это общая проблема, и любой ответ, который улучшает любой из этих трех атрибутов, выгоден кому-то, если не мне позже.

Источник

3 ответа

Решение

Если массив маленький и удобочитаемость важнее эффективности, я предлагаю:

  nums = [4., 9., 13., 25]
  N = 10
  while len(nums) < N:
      pos = np.argmax(np.diff(nums))   # where maximum difference is
      nums.insert(pos+1, (nums[pos+1] + nums[pos]) / 2.)  #introduce value

Конечно, это страдает от уже упомянутых проблем, которые, вероятно, это не самый эффективный способ интерполяции с минимальными различиями между точками в конце пробега.

Источник

И, если вам нужна эффективность для длинных массивов, даже если код не такой короткий, я предлагаю:

nums = np.array([4., 9., 13., 25])
diffs = np.diff(nums)
N = 10

# Number of interpolation points proportional to length of gaps
new_points = diffs/sum(diffs) * (N-len(nums))
while sum(np.floor(new_points)) != N -len(nums): # from continuum to discrete 
    pos = np.argmax(new_points - np.floor(new_points))
    new_points[pos] = np.floor(new_points[pos] + 1)
new_points = np.floor(new_points)

# Now we interpolate by inserting linspace values starting from the end to 
# avoid the loop limits being spoiled when introducing values. 
for ii in range(len(new_points))[::-1]:
    #linspace includes borders
    introduce_these = np.linspace(nums[ii], nums[ii+1], new_points[ii] + 2)[1:-1]
    nums = np.insert(nums, ii+1, introduce_these)

Что производит:

In [205]: print nums
[4.   5.66666667   7.33333333   9.   11.   13.   16.   19.   22.   25. ]
Источник

Вполне возможно, что вы можете обновить несколько значений одновременно. Учтите следующее:

for k in xrange(N/count):
    max_gaps = np.argsort(np.diff(nums))
    inds = np.sort(max_gaps[-count:])
    new_num = (nums[inds]+nums[inds+1])/2

    nums = np.insert(nums, inds+1, new_num)
    print nums

Количество будет количество пробелов, одновременно заполненных.

Первый пример, когда count=1 а также N=6:

[  4.   9.  13.  19.  25.]
[  4.   9.  13.  19.  22.  25.]
[  4.   9.  13.  16.  19.  22.  25.]
[  4.    6.5   9.   13.   16.   19.   22.   25. ]
[  4.    6.5   9.   11.   13.   16.   19.   22.   25. ]
[  4.    6.5   9.   11.   13.   16.   19.   22.   23.5  25. ]

Этот пример упрощает линейную интерполяцию и код, но возьмет последний по величине эквивалентный разрыв, а не первый.

Второй пример, когда count=2 а также N=6:

[  4.    6.5   9.   13.   19.   25. ]
[  4.    6.5   9.   13.   16.   19.   22.   25. ]
[  4.    6.5   9.   11.   13.   16.   19.   22.   23.5  25. ]

Увеличение count изменит ваши результаты, но поможет векторизовать код.

Источник
Другие вопросы по тегам