Меню
Что нового?

Проверка уникальности столбцов матрицы (двумерный массив)

  • Автор темы Автор темы WBS
  • Дата начала Дата начала

WBS

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

PHP: 
<?

function mtr_transpose ($arr) {
// транспонирует матрицу $arr (двумерный массив)
	foreach ($arr as $i => $row)
		foreach ($row as $j => $val)
			$arr_tr[$j][$i] = $val;
	return $arr_tr;
}

function mtr_row_unique_check ($arr) {
// проверяет, все ли строки в матрице $arr (двумерный массив) разные
	return sizeof(array_unique(array_map("implode", $arr)))==sizeof($arr) ? TRUE : FALSE;
}

$arr_mtr = array(
	5 => array(0,0,1,1,1,0,0,0,1,0),
	10 => array(1,1,0,0,0,0,1,1,0,0),
	15 => array(1,1,1,1,0,0,0,0,0,1),
	20 => array(1,0,0,1,1,1,0,1,0,0)
);

foreach ($arr_mtr as $row) {
	foreach ($row as $val)
		print("{$val} ");
	print("<br>");
}
print("<p>" . (mtr_row_unique_check(mtr_transpose($arr_mtr)) ? "Все столбцы разные" : "Не все столбцы разные"));

?>

В моем случае матрица состоит только из 1 и 0. Интересует наиболее эффективный (быстрый) алгоритм.
 
PHP: 
function isAllColumnsUniq(&$arr, $c_i, $r_i)
{
    global    $row_idx;
    if ($r_i >= count($arr))
    {
        return count($c_i) < 2;
    }
    if (count($c_i) < 2)
    {
        // столбцов меньше двух
        return true;
    }
    $check = array();
    foreach ($c_i as $idx)
    {
        $check[$arr[$row_idx[$r_i]][$idx]][] = $idx;
    }
    var_dump ($check);
    foreach ($check as $new_c_i)
    {
        if (!isAllColumnsUniq($arr, $new_c_i, $r_i+1))
        {
            return false;
        }
    }
    return true;
}

$arr_mtr = array(
    5 => array(0,0,1,1,1,0,0,0,1,0),
    10 => array(1,1,0,0,0,0,1,1,0,0),
    15 => array(1,1,1,1,0,0,0,0,0,1),
    20 => array(1,0,0,1,1,1,0,1,0,0)
);

$cols = count(reset($arr_mtr));
$col_idx = array();
$row_idx = array(5,10,15,20);
for ($i = 0 ; $i < $cols ; $i++)
{
    $col_idx[] = $i;
}
var_dump (isAllColumnsUniq($arr_mtr, $col_idx, 0 ));
 
Без рекурсии.)
PHP: 
<?php

class Bin_Matrix
{
    protected $cols, $rows, $values;

    public function __construct(array $values)
    {
        $this->rows = count($values);
        $this->cols = count(reset($values));
        $this->values = array_values($values);
    }

    public function hasSameCols()
    {
        $hash = array();
    
        for($j = 0; $j < $this->cols; $j++)
        {
            $v = 0;
    
            for($i = 0; $i < $this->rows; $i++)
            {
                $v |= ($this->values[$i][$j] << $i);
            }
    
            if( isset($hash[$v]) )
            {
                return true;
            }
    
            $hash[$v] = $j;
        }
    
        return false;
    }    
}

$arr_mtr = array(
    5 => array(0,0,1,1,1,0,0,0,1,0),
    10 => array(1,1,0,0,0,0,1,1,0,0),
    15 => array(1,1,1,1,0,0,0,0,0,1),
    20 => array(1,0,0,1,1,1,0,1,0,0)
);

$matrix = new Bin_Matrix($arr_mtr);
var_dump($matrix->hasSameCols());
Но количество строк ограничено 32-мя.
 
  • Like
Реакции: WBS
Вурдалак true с false перепутано, сделано только для значений 0 и 1, и таки да, только для 32 строк максимум :)
 
rotoZOOM, а у тебя is вместо are. Для значений 0 и 1 — согласно ТЗ.

Upd. Ты прав, да.
 
rotoZOOM, спасибо за код, но судя по моим тестам, мой код работает в 1.7 раз быстрее.
Вурдалак, спасибо. Ваш код быстрее моего в 1.46 раза.

Вурдалак написал(а):
Но количество строк ограничено 32-мя
Нажмите для раскрытия...
Этого мне более чем достаточно :).

rotoZOOM написал(а):
true с false перепутано
Нажмите для раскрытия...
Тоже заметил. Но это не принципиально.

Продолжаю рассматривать новые идеи по ускорению алгоритма.
 
Тестировал на матрице из темы (размер 10x4). Кстати, она вполне соответствует размерам матриц, которые мне нужно обрабатывать.
 
ээээ .... экономия на спичках детектед?
Или у тебя таких матриц сто тыщ миллионов?
 
Матриц у меня миллионы. Время обработки 3-4 мин. Сэкономить 1 мин. уже довольно заманчиво.
 
Отказался от использования класса в коде Вурдалака, что ускорило алгоритм еще в 2 раза.

Сейчас по скорости работы распределение такое:
1. Мой алгоритм (1-й пост) - 41 сек.
2. Алгоритм rotoZOOM (2-й пост) - 70 сек.
3. Алгоритм Вурдалака (3-й пост) - 28 сек.
4. Алгоритм Вурдалака без использования классов (код ниже) - 14 сек.

PHP: 
<?

function mtr_col_unique_check ($arr) {
	$rows = count($arr);
	$cols = count(reset($arr));
	$arr_vals = array_values($arr);
	$hash = array();
	for ($j=0; $j<$cols; $j++) {
		$v = 0;
		for ($i=0; $i<$rows; $i++)
			$v |= ($arr_vals[$i][$j] << $i);
		if (isset($hash[$v]))
			return FALSE;
		$hash[$v] = $j;
	}
	return TRUE;
}

$arr_mtr = array(
	5 => array(0,0,1,1,1,0,0,0,1,0),
	10 => array(1,1,0,0,0,0,1,1,0,0),
	15 => array(1,1,1,1,0,0,0,0,0,1),
	20 => array(1,0,0,1,1,1,0,1,0,0)
);

mtr_col_unique_check($arr_mtr);

?>
 
Подумай, если время сильно критично, может действительно переписать на Си?
 
Вурдалак написал(а):
Если это не разовая задача, то переписал бы на какой-нибудь C++.
Нажмите для раскрытия...
Задача не разовая, но достаточно не частая, чтобы не заморачиваться переписыванием на C++.

Может кому пригодится в будущем... поделюсь вариантом, который подходит для мартиц, содержащих произвольные числа (не только 1 и 0):
PHP: 
<?

function mtr_transpose ($arr) {
// транспонирует матрицу $arr (двумерный массив)
    foreach ($arr as $i => $row)
        foreach ($row as $j => $val)
            $arr_tr[$j][$i] = $val;
    return $arr_tr;
}

function mtr_row_unique_check ($arr) {
// проверяет, все ли строки в матрице $arr (двумерный массив) разные
    return sizeof(array_unique(array_map("implode_space", $arr)))==sizeof($arr) ? TRUE : FALSE;
}

function implode_space($arr) {
// Объединяет элементы массива в строку через пробел
	return implode(" ", $arr);
}

$arr_mtr = array(
    5 => array(0,0,1,1,1,0,0,0,1,0),
    10 => array(1,1,0,0,0,0,1,1,0,0),
    15 => array(1,1,1,1,0,0,0,0,0,1),
    20 => array(1,0,0,1,1,1,0,1,0,0)
);

mtr_row_unique_check(mtr_transpose($arr_mtr));

?>

Также вместо функции "implode_space" можно использовать стандартную функцию "serialize". Код станет чуть медленнее, но это позволит обрабатывать матрицы с произвольными значениями (в т.ч. строки с пробелами).
 
Войдите или зарегистрируйтесь для ответа.
Сверху