N 個の要素を持つ配列が与えられた場合、長さが等しいか、長さがほぼ 1 異なる M (M < N) 個の連続するサブ配列を探しています。たとえば、N = 12 で M = 4 の場合、すべてのサブ配列は次のようになります。 N/M = 3 の長さが等しい。N = 100 で M = 12 の場合、長さ 8 と 9 のサブ配列が必要であり、両方のサイズが元の配列内で均一に分散されている必要があります。この単純なタスクは、実装するのが少し難しいものになりました。Bresenham のライン アルゴリズムを適応させたものを思いつきました。これは、C++ でコーディングすると次のようになります。
/// The function suggests how an array with num_data-items can be
/// subdivided into successively arranged groups (intervals) with
/// equal or "similar" length. The number of intervals is specified
/// by the parameter num_intervals. The result is stored into an array
/// with (num_data + 1) items, each of which indicates the start-index of
/// an interval, the last additional index being a sentinel item which
/// contains the value num_data.
///
/// Example:
///
/// Input: num_data ........... 14,
/// num_intervals ...... 4
///
/// Result: result_start_idx ... [ 0, 3, 7, 10, 14 ]
///
void create_uniform_intervals( const size_t num_data,
const size_t num_intervals,
std::vector<size_t>& result_start_idx )
{
const size_t avg_interval_len = num_data / num_intervals;
const size_t last_interval_len = num_data % num_intervals;
// establish the new size of the result vector
result_start_idx.resize( num_intervals + 1L );
// write the pivot value at the end:
result_start_idx[ num_intervals ] = num_data;
size_t offset = 0L; // current offset
// use Bresenham's line algorithm to distribute
// last_interval_len over num_intervals:
intptr_t error = num_intervals / 2;
for( size_t i = 0L; i < num_intervals; i++ )
{
result_start_idx[ i ] = offset;
offset += avg_interval_len;
error -= last_interval_len;
if( error < 0 )
{
offset++;
error += num_intervals;
} // if
} // for
}
このコードは、N = 100、M=12 の間隔の長さを計算します: 8 9 8 8 9 8 8 9 8 8 9 8
実際の問題は、自分の問題を正確に呼び出す方法がわからないため、検索に苦労しました。
- そのようなタスクを達成するための他のアルゴリズムはありますか?
- 彼らはどのように呼ばれていますか？他のアプリケーションの分野を知っていれば、名前が付けられるかもしれません。
データをクラスタリングするためのより大きなアルゴリズムの一部として、このアルゴリズムが必要でした。並列ソート（？）の実装にも役立つと思います。