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

WBS · 2 Окт 2011

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

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. Интересует наиболее эффективный (быстрый) алгоритм.

rotoZOOM · 2 Окт 2011

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 ));

Вурдалак · 2 Окт 2011

Без рекурсии.)

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-мя.

rotoZOOM · 2 Окт 2011

Вурдалак true с false перепутано, сделано только для значений 0 и 1, и таки да, только для 32 строк максимум

rotoZOOM · 2 Окт 2011

А ну да, автор же сказал, что у него только 0 и 1.

Вурдалак · 2 Окт 2011

rotoZOOM, ~~а у тебя is вместо are~~. Для значений 0 и 1 — согласно ТЗ.

Upd. Ты прав, да.

WBS · 2 Окт 2011

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

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

Этого мне более чем достаточно

.

rotoZOOM написал(а):
true с false перепутано

Тоже заметил. Но это не принципиально.

Продолжаю рассматривать новые идеи по ускорению алгоритма.

rotoZOOM · 2 Окт 2011

WBS тестировалось на матрице какого размера?

WBS · 2 Окт 2011

Тестировал на матрице из темы (размер 10x4). Кстати, она вполне соответствует размерам матриц, которые мне нужно обрабатывать.

rotoZOOM · 2 Окт 2011

ээээ .... экономия на спичках детектед?
Или у тебя таких матриц сто тыщ миллионов?

WBS · 2 Окт 2011

Матриц у меня миллионы. Время обработки 3-4 мин. Сэкономить 1 мин. уже довольно заманчиво.

rotoZOOM · 2 Окт 2011

Если миллионы, то да, согласен! Способ Вурдалака хорош.

Вурдалак · 2 Окт 2011

Если это не разовая задача, то переписал бы на какой-нибудь C++.

rotoZOOM · 2 Окт 2011

Вурдалак +1

WBS · 3 Окт 2011

Отказался от использования класса в коде Вурдалака, что ускорило алгоритм еще в 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);

?>

rotoZOOM · 3 Окт 2011

Подумай, если время сильно критично, может действительно переписать на Си?

WBS · 3 Окт 2011

Вурдалак написал(а):
Если это не разовая задача, то переписал бы на какой-нибудь 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". Код станет чуть медленнее, но это позволит обрабатывать матрицы с произвольными значениями (в т.ч. строки с пробелами).

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

WBS

Новичок

rotoZOOM

ACM maniac

Вурдалак

Продвинутый новичок

rotoZOOM

ACM maniac

rotoZOOM

ACM maniac

Вурдалак

Продвинутый новичок

WBS

Новичок

rotoZOOM

ACM maniac

WBS

Новичок

rotoZOOM

ACM maniac

WBS

Новичок

rotoZOOM

ACM maniac

Вурдалак

Продвинутый новичок

rotoZOOM

ACM maniac

WBS

Новичок

rotoZOOM

ACM maniac

WBS

Новичок