UPD
Проверка через replace
Для PHP есть решения "в оба конца", нечувствительные к повторам цифр в массиве цифр $digits и в числе $number, которые используют функции preg_replace()
и str_replace()
.
Если:
- число
$number
использовать как шаблон (строка "/[$number]/");
- в качестве строки замены взять пустую строку;
- массив цифр склеить в обрабатываемую строку (функция implode($digits)),
то функция preg_replace()
удалит в обрабатываемой строке все символы шаблона,
т.е. при наличии всех цифр из массива цифр в числе на выходе будет пустая строка.
Если же
- использовать массив
$digit
в качестве массива поиска;
- в качестве строки замены использовать пустую строку;
- вместо обрабатываемой строки использовать число $number,
то функция str_replace()
удалит все цифры массива поиска из обрабатываемой строки,
т.е. при наличии в массиве цифр всех цифр числа на выходе будет пустая строка.
Такой подход приводит к короткому и эффективному коду.
Проверка с переводом числа в массив цифр
Поскольку количество цифр ограничено, то разница в программной сложности алгоритмов сводится к коэффициенту 10.
За этот коэффициент можно побороться так:
- с помощью функции str_split() или sscanf() преобразовать число в массив цифр;
- упорядочить массивы и выбросить повторы;
- сравнить массивы в параллельном проходе (если в одном из массивов нашлась меньшая цифра, то он точно не подмножество другого).
Однако тесты показали проигрыш в производительности.
Программа:
define("N", 100000);
define("M", 11);
define("PR", 1);
function print_digits($text, $digits){
print "$text [ ";
foreach($digits as $dig){
print"$dig ";
}
print "]";
}
function array_sort_unique($arr){
sort($arr);
$prev = null;
foreach($arr as $key => $item){
if($item === $prev){
unset($arr[$key]);
}
$prev = $item;
}
return array_values($arr);
}
function check_by_replace($number, $digits){
$result1 = preg_replace("/[$number]/", "", implode($digits));
$res1 = (empty($result1)) ? "⊂" : "⊄";
$result2 = str_replace($digits, "", $number);
$res2 = (empty($result2)) ? "⊂" : "⊄";
return[$res1, $res2];
}
function check_by_arrays($number, $digits){
$arr_dig = array_sort_unique($digits);
$str_num = (string)$number;
$format = str_repeat("%1d", count($str_num));
$arr_num = array_sort_unique(sscanf($str_num, $format));
$res1 = "⊂";
$res2 = "⊂";
if($arr_dig !== $arr_num){
$key_num = 0;
$key_dig = 0;
while(($key_num < count($arr_num)) && ($key_dig < count($arr_dig))){
if($arr_num[$key_num] > $arr_dig[$key_dig]){
$res1 = "⊄";
$key_dig++;
}elseif($arr_num[$key_num] < $arr_dig[$key_dig]){
$res2 = "⊄";
$key_num++;
}else{
$key_dig++;
$key_num++;
}
}
}
return[$res1, $res2];
};
function comparison($number, $digits, $pr = 0){
$replace_res = check_by_replace($number, $digits);
$arrays_res = check_by_arrays($number, $digits);
if($pr > 0){
print_digits("<br><br>* check_by_replace: *", $digits);
print_digits(" $replace_res[0] $number, $number $replace_res[1]", $digits);
print_digits("<br>* check_by_array: *", $digits);
print_digits(" $arrays_res[0] $number, $number $arrays_res[1]", $digits);
}
}
print"ПРОВЕРКА";
comparison(13579, [1, 9, 5], PR);
comparison(13579, [1, 9, 5, 2], PR);
comparison(13579, [9, 1, 7, 5, 3, 2], PR);
comparison(13579, [1, 9, 5, 9, 1], PR);
comparison(13579391, [1, 9, 5, 3, 2, 7], PR);
printf("<br><br>ТЕСТ БЫСТРОДЕЙСТВИЯ<br>%d сравнений по %d цифр<br>", (int)N, (int)M);
$test_dig = [];
$test_num = [];
for($i = 0; $i < N; $i++){
$dig = [];
$num = [];
for($j = 0; $j < M; $j++){
$dig[] = mt_rand(0,9);
$num[] = mt_rand(0,9);
}
$test_dig[] = $dig;
$test_num[] = implode($num);
}
$time0 = microtime(true);
for($i = 0; $i < N; $i++){
check_by_replace($test_num[$i], $test_dig[$i]);
}
$time1 = microtime(true);
for($i = 0; $i < N; $i++){
check_by_arrays($test_num[$i], $test_dig[$i]);
}
$time2 = microtime(true);
printf("<br>check_by_replace: %.03f c", $time1 - $time0);
printf("<br>check_by_arrays: %.03f" c, $time2 - $time1);
Результаты:
ПРОВЕРКА
* check_by_replace: * [ 1 9 5 ] ⊂ 13579, 13579 ⊄ [ 1 9 5 ]
* check_by_array: * [ 1 9 5 ] ⊂ 13579, 13579 ⊂ [ 1 9 5 ]
* check_by_replace: * [ 1 9 5 2 ] ⊄ 13579, 13579 ⊄ [ 1 9 5 2 ]
* check_by_array: * [ 1 9 5 2 ] ⊂ 13579, 13579 ⊂ [ 1 9 5 2 ]
* check_by_replace: * [ 9 1 7 5 3 2 ] ⊄ 13579, 13579 ⊂ [ 9 1 7 5 3 2 ]
* check_by_array: * [ 9 1 7 5 3 2 ] ⊂ 13579, 13579 ⊂ [ 9 1 7 5 3 2 ]
* check_by_replace: * [ 1 9 5 9 1 ] ⊂ 13579, 13579 ⊄ [ 1 9 5 9 1 ]
* check_by_array: * [ 1 9 5 9 1 ] ⊂ 13579, 13579 ⊂ [ 1 9 5 9 1 ]
* check_by_replace: * [ 1 9 5 3 2 7 ] ⊄ 13579391, 13579391 ⊂ [ 1 9 5 3 2 7 ]
* check_by_array: * [ 1 9 5 3 2 7 ] ⊂ 13579391, 13579391 ⊂ [ 1 9 5 3 2 7 ]
ТЕСТ БЫСТРОДЕЙСТВИЯ
100000 сравнений по 11 цифр
check_by_replace: 3.922 с
check_by_arrays: 10.482 с