Как решить данную задачу (Олимпиадная)?

Question

[vitaly_74]

Добрый день, решаю олимпидную задачу, решение получаю. но время затрачиваемое на получение результата слишком велико. подскажите пожалуйста какими еще способами можно решить эту задачу? пока что пробовал с помощью regex и 3-х вложенных циклов (задачу с regex удалил) версия php 5.6.
Я не прошу скидывать решений, я прошу подсказать как с помощью чего можно решить?


входные данные: 4 width=5 ht=3 len=10 name=circ rad=5 name=circ rad=5 name=sqr width=5 ht=3 4 ht=3 width=5 name=circ name=sqr width=5 len=10

<?
$start = microtime(true);
$handle = @fopen("input.txt", "r");
$products = array();
$properties = array ();
if ($handle) {
    $i=0;
    while (($buffer = fgets($handle, 4096)) !== false) {
        if ($i==0){
            $count_products = trim($buffer);
        }
        if ($i>0 and $i<$count_products+1){
            $arrayString = explode(' ',trim($buffer));
            $arr = array();
            foreach ($arrayString as $string){
                $keyValArr= explode('=', $string);
                $arr[$keyValArr[0]]=$keyValArr[1];
            }
            array_push($products, $arr);
        }
        if ($i==$count_products+1){
            $count_properties = trim($buffer);
        }
        if ($i>$count_products+1){
            //array_push($properties, explode(" ", trim($buffer)));
            $arrayString = explode(' ',trim($buffer));
            $arr = array();
            foreach ($arrayString as $string){
                $keyValArr= explode('=', $string);
                $arr[$keyValArr[0]]=$keyValArr[1];
            }
            array_push($properties, $arr);

        }

        $i=$i+1;

    }
    if (!feof($handle)) {
        echo "Ошибка: fgets() неожиданно потерпел неудачу\r\n";
    }
    fclose($handle);
}
//echo 'Время выполнения скрипта: '.(microtime(true) - $start).' сек.';
$response="";
foreach ($properties as $propertyString=>$arrayInProperty){
    $numberProperty = count ($arrayInProperty);
//    echo json_encode($arrayInProperty).'<br \>';
    $numberProduct = 0;
    foreach ($products as $productString=>$arrayInProduct){
        $string="";
        $index = 0;

       foreach ($arrayInProperty as $property=>$value){
           if(array_key_exists($property, $arrayInProduct)){

              if (trim($arrayInProduct[$property])==$value){
                  $string = $string.$property.' = '. $arrayInProduct[$property]."<br \ >";
                  $index = $index+1;
              }
              else {
                  break;
              }
           }else {
//               echo '/ not'.'<br \>';
               break;
           }
       }

        if ($numberProperty == $index){
            $numberProduct = $numberProduct+1;
        }

//       echo $string;
//       echo '<br \>';
    }
    $response = $response.$numberProduct.PHP_EOL;
}
$fp = fopen("output.txt", "w+");
fwrite($fp,$response);
//echo json_encode($arrayInProperty).'<br \>';
//echo json_encode($properties);
echo 'Время выполнения скрипта: '.(microtime(true) - $start).' сек.';


?>

Comments

[vitaly_74]

время выполнения при больших данных 10 сек. с 3-ми циклами и 27 сек с 2-мя циклами + regex

[vitaly_74]

нужно время выполнения меньше 6 сек

Answer 1

[vitaly_74]

по 1 пункту я не много не понял, а чем это поможет?
2 пункт я так и сделал (о чем свидетельствует break. )

if(array_key_exists($property, $arrayInProduct)){ //Если существует свойство у продукта

              if (trim($arrayInProduct[$property])==$value){ // если данное свойство равно свойству продукта.
                  $string = $string.$property.' = '. $arrayInProduct[$property]."<br \ >";
                  $index = $index+1;
              }
              else {
                  break;
              }
           }else {
//               echo '/ not'.'<br \>';
               break;
           }

Answer 2

[Rsa97]

Поскольку в запросах используется только равенство, то изначально не разделять свойства товаров по символу =.
Подготовить массив, где каждой паре 'свойство=значение' будет соответствовать массив со списком товаров.

[
  'width=5' => [0, 3],
  'ht=3' => [0, 3],
  'len=10' => [0],
  'name=circ' => [1, 2],
  'rad=5' => [1, 2].
  'name=sqr' => [3]
]

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

array_intersect([0, 3], [0, 3]) = [0, 3]
[1, 2]
[3]
array_intersect([0, 3], [0]) = [0]

Comments

[vitaly_74]

благодарю за ответ!

[longclaps]

Хорошая попытка, но - нет. Вот набор данных, который наглухо тебя застопорит:
Для всех товаров один и тот же набор свойств (обозначим key00,key01,..key99)
Всем свойствам присвоены одно из двух значений из {0, 1}, причем почти все свойства единички, кроме 1го или 2 нулей. Если все товары разные - это даст как раз 10^4 возможных товаров.
Наши 1000 запросов - в них по 98-99 ключей с единицами.
итак, 1000 запросов, почти 100 слияний, и в каждом откидывается всего пара товаров - это порядка 1000*100*(10^4)^2/(константа типа от 2 до 8, могу и аккуратно посчитать) элементарых операций.
Шах и мат.

[vitaly_74]

longclaps, ну это хотябы что то.

[longclaps]

vitaly_74, ну идея не расщеплять пару ключ-значение, а рассматривать её как единый ключ - совершенно верная. Дальше-то что?

[vitaly_74]

#Затем по списку свойств в запросе выбирать массивы, если их больше одного, то находить их пересечение через array_intersect# а вы не подскажите как динамически добавить в array_intersect от 2 до 20 значений? там же значения на строку принимаются от 1-20

[Rsa97]

vitaly_74, Не надо динамически, пересечение можно считать для каждого массива, начиная со второго.
A ∩ B ∩ C = (A ∩ B) ∩ C
Ну и, если на каком-то шаге получен пустой массив, то можно завершить поиск.
ø ∩ A = ø

Answer 3

[Артем Спиридонов]

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

Я бы абстрагировал в несколько функций, для простоты:
- загрузка данных
- обход запросов
- обход свойств товаров
- проверка позиции
- добавление результата (если нет ветки - добавляет, если есть - инкрементирует)
- вывод результатов

Количество итераций - произведение запросов и количества товаров.
Пути снижения количества итераций, навскидку:
- сделать индекс свойств товаров
- (вне зависимости от индекса) при исследовании свойств пропускать (continue) позиции с отсутствующим искомым свойством

На этом идеи заканчиваются.

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

Comments

[Максим Федоров]

если надо просто сделать так, чтобы просто работало, надо просто делать так, чтобы просто работало

Иногда задачи решают, чтобы себя потренировать, потму дополнительная сложность в таком случае — довольно хорошая практика

А так согласен

[vitaly_74]

да про преждевеменную оптимизацию только прочитал, но в условии (выше на скрин не попало, стоит "ограничение по времени 6с." )

[Артем Спиридонов]

vitaly_74, 6с? Что за бред.... какая машина, какое окружение - масса влияющих факторов.