Преобразование вектора (массива)

[WBS]

Имеется массив чисел размера n. Требуется особым образом преобразовать его в массив размера n2. Объяснить суть преобразования мне сложно, поэтому покажу это на примере.

Исходный массив, n=10:

$arr = array (
	0 => 0.1,
	1 => 5.8,
	2 => 8.5,
	3 => 4.8,
	4 => 3.4,
	5 => 2.7,
	6 => 2.4,
	7 => 2.6,
	8 => 2.8,
	9 => 2
);

В зависимости от значений n2 массив пересчитывается таким образом:


Особый интерес представляет преобразование при n2=3 (когда n не делится на n2 нацело).
Требуется функция для осуществления описанного преобразования.

 

[Breeze]

откуда в n3 взялось 16, т.е. по какому принципу от 4.8 взялась часть?

 

[WBS]

откуда в n3 взялось 16, т.е. по какому принципу от 4.8 взялась часть?

Вот именно это и сложно объяснить словами . Но на примере попробую...
Когда 10 элеменов массива нужно сгруппировать в 3, это означает, что в каждом из трех элементов (при n=3) будет содержаться по ~3.33 элемента из массива при n=10 (10/3 = 3.33).

Для n=10 и n2=3:
16 = 0.1 + 5.8 + 8.5 + 1/3*4.8
10.9 = 2/3*4.8 + 3.4 + 2.7 + 2/3*2.4
8.2 = 1/3*2.4 + 2.6 + 2.8 + 2

 

[Breeze]

я так и подумал =)
тут все просто, делашь в цикле полное присваивание текущей группе пока количество обработанных элементов <=3, дальше разделяешь элемент на 1/3, которую плюсуешь к текущей группе, увеличиваешь номер группы и к ней плюсуешь 2/3, далее так же. можно уже играться с разделением.

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

 

[Breeze]

ну и еще переменная со значением сколько сейчас отрезать.

 

[WBS]

тут все просто, делашь в цикле полное присваивание текущей группе пока количество обработанных элементов <=3, дальше разделяешь элемент на 1/3, которую плюсуешь к текущей группе, увеличиваешь номер группы и к ней плюсуешь 2/3

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

function reduce_arr ($arr, $n) {
	...
	return $arr2;
}

которая принимает в качестве аргументов исходный массив и размер нового массива, а возвращает новый массив.

 

[Вурдалак]

WBS, я могу написать за небольшую сумму.

 

[Breeze]

так покажи то, что получается

 

[fixxxer]

Я, возможно, не понял, но кажется мне, что кагбэ вот

 

[Вурдалак]

fixxxer, ???

 

[fixxxer]

ну типа сначала (если есть необходимость) раздробить на побольше, чтобы делилось на оба n
а потом уже reduce

 

[Вурдалак]

fixxxer, так ты про НОК, а не НОД. Ну, так телодвижений будет даже больше, чем в более «тупом» варианте Breeze'а. Ты так будешь дробить же в общем-то все, включая те, которые и не требуются (плюс погрешность возрастает).

 

[Breeze]

насчет погрешностей: по идее, в случае n=3, если работаем с десятыми и нормальным округлением, то дробление получится по 0.3 и 0.7 -- в итоге имеем 15.8, 11.2, 8.1 вместо того, что у ТС в таблице.
или я чего-то не понимаю =)

 

[WBS]

ну типа сначала (если есть необходимость) раздробить на побольше, чтобы делилось на оба n
а потом уже reduce

Спасибо за идею. Получилось вот так:

<?

function gcd($a, $b) {
// наибольший общий делитель (НОД)
	while ($a*$b != 0)
		($a >= $b) ? ($a = $a % $b) : ($b = $b % $a);
	return ($a + $b);
}

function lcm($a, $b) {
// наименьшее общее кратное (НОК)
	return ($a*$b/gcd($a,$b));
}

function reduce_arr ($arr, $n) {
	$n1 = sizeof($arr);			// размер исходного массива
	$n2 = lcm($n1, $n);			// размер промежуточного массива $arr2
	$block_size1 = $n2/$n1;
	$block_size2 = $n2/$n;
	$arr2 = $arr_result = array();
	foreach ($arr as $val)
		for ($i=0; $i<$block_size1; $i++)
			$arr2[] = $val/$block_size1;
	$cur_block = 0;
	for ($i=0; $i<$n2; $i++) {
		$arr_result[$cur_block] += $arr2[$i];
		if (($i+1)%$block_size2 == 0)
			$cur_block++;
	}
	return $arr_result;
} 



$arr = array (
    0 => 0.1,
    1 => 5.8,
    2 => 8.5,
    3 => 4.8,
    4 => 3.4,
    5 => 2.7,
    6 => 2.4,
    7 => 2.6,
    8 => 2.8,
    9 => 2
);

$n = 3;

$arr2 = reduce_arr($arr, $n);
print("<pre>");
print_r($arr2);
print("</pre>");

?>

Все работает, хотя Вурдалак прав, алгоритм с виду не самый лучший и быстрый.

 

[fixxxer]

fixxxer, так ты про НОК, а не НОД.

Ага

Ну, так телодвижений будет даже больше, чем в более «тупом» варианте Breeze'а. Ты так будешь дробить же в общем-то все, включая те, которые и не требуются (плюс погрешность возрастает).

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

Думать дальше лень =)

 

[rotoZOOM]

function reduce_arr ($arr, $n)
{
    $sz = count($arr);
    $acc = $v = 0;
    $res = array();
    foreach ($arr as $val) {
        $acc+=$n;
        if ($acc<=$sz) $v += $val;
        else {
            $acc%=$sz;
            $res[] = $v + $val * ($n - $acc) / $n;
            $v = $val * $acc / $n;
        }
    }
    $res[] = $v;
    return $res;
}

Без НОК, НОД, один цикл.
Навеяло алгоритмом Брезенхэма для быстрого рисования линий.

 

[WBS]

Без НОК, НОД, один цикл.
Навеяло алгоритмом Брезенхэма для быстрого рисования линий.

Хороший и быстрый алгоритм (раз в 16 быстрее моей реализации из 14 поста). Спасибо.
Хочу отметить, что у моей реализации все-таки есть одно преимущество (которое мне не очень нужно и необходимость которого не оговаривалась в первом посте): он может корректно работать при условии что $n >= размера исходного массива $arr.

 

[rotoZOOM]

Название функции 'reduce' сбило с толку.