@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).' сек.';


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

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

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

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

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

Смысл простой. В input.txt у нас вначале идут продукты, и только за ними запрос. Мы можем сразу же обрабатывать каждый запрос, как только его получим.
Проблемным местом является array_diff, его можно заменить на isset, но в этом случае придётся добавить ещё один цикл
По факту роли не играет никакой.
Можно заменить на str_replace и скормить ему 2 массива, но в этом случае нужно бут считать кол-во элеметов
Так же можно добавить кэширование для поиска в массиве $products, небольшой прирост на повторяющихся запросах будет.

Помимо этого способа в лоб можно заморочится более. Например работать с потоком и "парсить" на ходу. Нам тут же становится известно смещение по продуктам и по запросам.
Но в данном примере мы все входные пиххаем сразу в память.

<?php

// for ($loop = 0; $loop < 10000; ++$loop) { // for benchmark
    $products = [];
    $section = $index = 0;
    $output = fopen(__DIR__.'/output.txt', 'w+');
    foreach (file(__DIR__.'/input.txt', FILE_IGNORE_NEW_LINES) as $line) {
        if (false === strpos($line, '=')) {
            ++$section;
            continue;
        }
        if (1 === $section) {
            $products[$index] = explode(' ', $line);
            ++$index;
            continue;
        }
        $request = explode(' ', $line);
        $total = 0;
        foreach ($products as $product) {
            $total += (int) !array_diff($request, $product);
        }
        fwrite($output, $total.PHP_EOL);
    }
    fclose($output);
// }


Чуток бенчмарков

// for i in {0..10} ; do time php original.php; done
//
// php original.php  0,71s user 0,12s system 99% cpu 0,835 total
// php original.php  0,69s user 0,13s system 99% cpu 0,820 total
// php original.php  0,66s user 0,16s system 99% cpu 0,829 total
// php original.php  0,66s user 0,19s system 99% cpu 0,854 total
// php original.php  0,68s user 0,15s system 99% cpu 0,830 total
// php original.php  0,66s user 0,16s system 99% cpu 0,831 total
// php original.php  0,69s user 0,14s system 99% cpu 0,835 total
// php original.php  0,68s user 0,15s system 99% cpu 0,832 total
// php original.php  0,72s user 0,13s system 99% cpu 0,848 total
// php original.php  0,71s user 0,14s system 99% cpu 0,852 total
// php original.php  0,66s user 0,17s system 99% cpu 0,836 total

// for i in {0..10} ; do time php optimized.php; done
//
// php optimized.php  0,33s user 0,52s system 71% cpu 1,205 total
// php optimized.php  0,38s user 0,43s system 72% cpu 1,112 total
// php optimized.php  0,35s user 0,38s system 70% cpu 1,050 total
// php optimized.php  0,38s user 0,40s system 72% cpu 1,080 total
// php optimized.php  0,35s user 0,41s system 71% cpu 1,055 total
// php optimized.php  0,38s user 0,36s system 74% cpu 0,997 total
// php optimized.php  0,40s user 0,36s system 71% cpu 1,057 total
// php optimized.php  0,40s user 0,37s system 70% cpu 1,087 total
// php optimized.php  0,32s user 0,42s system 74% cpu 0,994 total
// php optimized.php  0,38s user 0,36s system 72% cpu 1,014 total
// php optimized.php  0,36s user 0,36s system 71% cpu 1,025 total
Ответ написан
Ваш ответ на вопрос

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

Войти через TM ID
Похожие вопросы
от 2 000 до 4 000 usd.
Teamlead Краснодар
До 100 000 руб.
ЭЛКОД Москва
от 120 000 руб.
17 авг. 2018, в 17:10
15000 руб./за проект
17 авг. 2018, в 16:58
60000 руб./за проект
17 авг. 2018, в 16:55
10000 руб./за проект