vitaly_74
@vitaly_74

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

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

5a89d4b8eda95349161698.png
входные данные: 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).' сек.';


?>
  • Вопрос задан
  • 309 просмотров
Решения вопроса 2
vitaly_74
@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;
           }
Ответ написан
Комментировать
Rsa97
@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]
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
customtema
@customtema
arint.ru
Или я не понял задачу, или загнать входные данные в ассоциативный массив, и простым перебором формировать результирующий массив для вывода.

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

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

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

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

Войдите, чтобы написать ответ

Похожие вопросы