VPF::php, нестандартная непонятная задача

NewDima

Дата 5.12.2009, 15:33 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 922
Регистрация: 20.2.2006
Где: <?here?>

Репутация: 10
Всего: 12

Мне удалось согнать мой вариант только до 1.60964894295 =(

Добавлено через 28 секунд
при вашем 0.521440029144

--------------------

Начинаем черкать!

Simpliest

Дата 5.12.2009, 15:46 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 625
Регистрация: 1.9.2009

Репутация: 1
Всего: 3

Цитата(sTa1kEr @ 5.12.2009, 14:15

)

Соррь, не большой баг. Не подумал, что array_merege объединяет по ключу

Все это фигня. Там сам подсчет эффективности достаточно замороченный smile

Добавлено через 7 минут и 20 секунд

Цитата(NewDima @ 5.12.2009, 14:33

)

Мне удалось согнать мой вариант только до 1.60964894295 =(

--------------------

sTa1kEr

Дата 5.12.2009, 15:57 (ссылка)

(нет голосов)

Загрузка ...

9/10 программиста

Профиль
Группа: Завсегдатай
Сообщений: 1553
Регистрация: 21.2.2007

Репутация: 56
Всего: 146

Цитата(NewDima @ 5.12.2009, 16:33

)

Мне удалось согнать мой вариант только до 1.60964894295 =(

Раз так, то я тоже оптимизировал слегка smile

1. Убрал статическую переменную
2. Вынес в переменную count($array)
3. Поменял местами if и for, что бы сэкономить на проверке внутри цикла
4. Заменил счетчик мз цикла $total++, на $total += $count вне цикла.. Был не прав. В связи с п.3 - это уже не нужно, заменил на return $count; Почему не на return 1? Можно было бы и так, но в случае return $count PHP не придется создавать дополнительную переменную, что бы вернуть 1.
Я тормоз... Там вообще цикл не нужен... Все, теперь конечный вариант.

Итого:

Код


function bruteforce($array, $result = array()) {
    $total = 0;
    $count = count($array);

    if ($count > 1) {

        for ($i = 0; $i < $count; $i++) {
            $n = array_shift($array);
            $total += bruteforce($array, $result + array($n => $n));
            array_push($array, $n);
        }

    } else {

        //echo implode('', $result).$array[0]."\n";
        return $count;
    }

    return $total;
}

NewDima, если не сложно, проверь какой теперь у тебя результат?

Добавлено @ 15:59

Цитата(Simpliest @ 5.12.2009, 16:46

)

Все это фигня. Там сам подсчет эффективности достаточно замороченный smile

Извини, не понял, что ты этим хотел сказать?

Добавлено @ 16:01

Цитата(Simpliest @ 5.12.2009, 16:46

)

Все это фигня. Там сам подсчет эффективности достаточно замороченный smile

Из-за этого бага, если разкомментировать echo, выводилось только последние 2 цифры.

Это сообщение отредактировал(а) sTa1kEr - 5.12.2009, 16:12

NewDima

Дата 5.12.2009, 16:06 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 922
Регистрация: 20.2.2006
Где: <?here?>

Репутация: 10
Всего: 12

отлично

Completed. 40320 iterations. 0.249315023422 sec

Добавлено через 1 минуту и 50 секунд
В моем варианте время выполнения скрипта растет просто бешеными темпами при увеличении размера массива, так-что какашка у меня=(

--------------------

Начинаем черкать!

sTa1kEr

Дата 5.12.2009, 16:14 (ссылка)

(нет голосов)

Загрузка ...

9/10 программиста

Профиль
Группа: Завсегдатай
Сообщений: 1553
Регистрация: 21.2.2007

Репутация: 56
Всего: 146

Еще одно место оптимизировал, убрал второй цикл smile

Все, больше не знаю, что еще можно оптимизировать... Если увидите, скажите smile

Simpliest

Дата 5.12.2009, 16:20 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 625
Регистрация: 1.9.2009

Репутация: 1
Всего: 3

Цитата(sTa1kEr @ 5.12.2009, 14:57

)

Извини, не понял, что ты этим хотел сказать?

я про рассчет эффективности комбинации согласно задаче ТС smile

Цитата(NewDima @ 5.12.2009, 15:06

)

так-что какашка у меня=(

Я дал профайлинг. посмотри методы которые вызываются по 273к раз
один из них сортировка smile

--------------------

sTa1kEr

Дата 5.12.2009, 16:39 (ссылка)

(нет голосов)

Загрузка ...

9/10 программиста

Профиль
Группа: Завсегдатай
Сообщений: 1553
Регистрация: 21.2.2007

Репутация: 56
Всего: 146

Все... вот последняя экстримальная оптимизация за счет уменьшения рекурсии на 2уровня и ухудшения читабельности smile

:
Так

Код


function bruteforce($array, $result = array()) {
    $total = 0;
    $count = count($array);

    if ($count == 3) {

        $return = implode('', $result);

        //echo $return.$array[0].$array[1].$array[2]."\n";
        //echo $return.$array[0].$array[2].$array[1]."\n";
        //echo $return.$array[1].$array[2].$array[0]."\n";
        //echo $return.$array[1].$array[0].$array[2]."\n";
        //echo $return.$array[2].$array[0].$array[1]."\n";
        //echo $return.$array[2].$array[1].$array[0]."\n";

        return 6;

    } else if ($count > 3) {

        for ($i = 0; $i < $count; $i++) {
            $n = array_shift($array);
            $total += bruteforce($array, $result + array($n => $n));
            array_push($array, $n);
        }
    } else {

        throw new RuntimeException('Array must be have 3 or more elements');

    }

    return $total;
}

Добавлено через 5 минут и 46 секунд
Да... этот метод даже на моем тормазнутом AMD'шнике меньше секунды выполняется...
Но это все равно не true way! smile

NFL

Дата 5.12.2009, 22:01 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 137
Регистрация: 5.5.2009

Репутация: нет
Всего: нет

тааак, с перебором понятно smile

что с эффективностью то делать?
я с ней вообще не пойму... превращать каждое в строку и проверять посимвольно?

Simpliest

Дата 5.12.2009, 22:25 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 625
Регистрация: 1.9.2009

Репутация: 1
Всего: 3

Цитата(NFL @ 5.12.2009, 21:01

)

что с эффективностью то делать?

Бггг, я же говорил smile

--------------------

NFL

Дата 5.12.2009, 22:29 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 137
Регистрация: 5.5.2009

Репутация: нет
Всего: нет

Simpliest, что то тему прочитал видимо невнимательно smile

ща перечитаю smile

sTa1kEr

Дата 5.12.2009, 22:56 (ссылка)

(нет голосов)

Загрузка ...

9/10 программиста

Профиль
Группа: Завсегдатай
Сообщений: 1553
Регистрация: 21.2.2007

Репутация: 56
Всего: 146

В общем, я от нечего делать добил твою задачу smile

Комментировать было лень

Код


class Sub {
    public $id;
    public $time;
    public $bonus;
    public $compatible;
    public $depends;
    public $input;
    public $placed;
    
    public function __construct($input) {
        $this->input = $input;
        $this->id = $this->input[0];
        $this->time = $this->input[1] * Process::RATIO;
    }

    public function reset() {
        $this->bonus = 0;
        $this->compatible = null;
        $this->depends = array();
        $this->placed = false;
    }

    public function compatible($proc) {
        $this->compatible = $proc;
        $this->bonus = $proc->time + $this->time - max($proc->time, $this->time + Process::RATIO);
    }

    public function condition($proc, $left = false) {
        if ($left) {
            $this->depends[] = $proc;
        } else {
            $proc->depends[] = $this;
        }
    }

    public function __toString() {
        return (string)$this->id;
    }
}

class Process {
    const QUALITY = 8;
    const PENALTY = 1.5;
    const RATIO = 0.2;

    protected $processes = array();
    protected $result;
    protected $nominalTime;
    protected $best;

    public function __construct(array $input) {
        foreach ($input as $val) { $this->processes[$val[0]] = new Sub($val); }
    }

    public function run($profile = false) {
        $time = microtime(true);
        $this->prepare();
        $count = $this->bruteforce($this->processes);

        if ($profile) { 
            printf("Iterations: %s; Time: %0.4f\n", $count, microtime(true) - $time);
        }

        return $this->result;
    }

    public function test($string) {
        $processes = array();
        foreach (explode(' ', $string) as $id) {
            $processes[] = $this->processes[(integer)$id];
        }

        $this->prepare();
        $this->calc($processes);
        return $this->result;
    }

    protected function calc($processes) {
        $quality = self::QUALITY;
        $time = $this->nominalTime;
        $prev = null;

        foreach ($processes as $proc) { $proc->placed = false; }
        foreach ($processes as $proc) {
            $proc->placed = true;

            if ($proc->compatible === $prev)  { $time -= $proc->bonus; }

            foreach ($proc->depends as $depend) {
                if (!$depend->placed) { $quality -= self::PENALTY; }
            }

            $prev = $proc;
        }

        $effectiveness = $quality - $time;
        if ($effectiveness >= $this->best) {
            $this->best = $effectiveness;

            array_unshift($this->result, array($effectiveness, $processes));

            if (count($this->result) > 2) {
                array_pop($this->result[2]);
            }
        }
    }

    protected function prepare() {
        $this->nominalTime = 0;
        $this->best = 0;
        $this->result = array();
        
        foreach ($this->processes as $proc) {
            $proc->reset();
            $this->nominalTime += $proc->time;

            if ($proc->input[2] > 0) {
                $proc->compatible($this->processes[$proc->input[2]]);
            }

            if ($proc->input[3] != 0) {
                $proc->condition($this->processes[abs($proc->input[3])], $proc->input[3] < 0);
            }
        }
    }
    
    protected function bruteforce($processes, $result = array()) {
        $total = 0;
        $count = count($processes);

        if ($count == 1) {

            $this->calc($result + array($processes[0]->id => $processes[0]));
            return 1;

        } else {

            for ($i = 0; $i < $count; $i++) {
                $proc = array_shift($processes);
                $total += $this->bruteforce($processes, $result + array($proc->id => $proc));
                array_push($processes, $proc);
            }

        }
        
        return $total;
    }
}

Код


$process = new Process(array(
    array(1, 2, 2, -8),
    array(2, 1, 1, 0),
    array(3, 4, 6, 5),
    array(4, 4, 8, 0),
    array(5, 1, 0, 0),
    array(6, 7, 3, 0),
    array(7, 2, 0, 0),
    array(8, 3, 4, 5)
));

$result = $process->run(true);
echo implode(' ', $result[0][1]).'  '.$result[0][0]."\n";
echo implode(' ', $result[1][1]).'  '.$result[1][0]."\n";

Код


Iterations: 40320; Time: 0.8913
7 6 3 4 8 5 1 2  4.8
7 6 3 4 8 1 2 5  4.8

Если использовать вместо класса Sub массив, то можно увеличить производительность на ~20-30%

Можно будет на досуге решить ее алгоритмом без перебора.

NFL

Дата 5.12.2009, 23:01 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 137
Регистрация: 5.5.2009

Репутация: нет
Всего: нет

sTa1kEr, спс огромное, преподу хватит smile

sTa1kEr

Дата 5.12.2009, 23:04 (ссылка)

(нет голосов)

Загрузка ...

9/10 программиста

Профиль
Группа: Завсегдатай
Сообщений: 1553
Регистрация: 21.2.2007

Репутация: 56
Всего: 146

Пара не очевидных моментов:

Sub::$depends - это процессы, которые по условию должны предшествовать текущему процессу
Sub::$bonus - это время, которое мы экономим, если предшествует совместимый процесс
Process:$nominalTime - это время, затрачиваемое на процесс без учета совместимости процессов

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

Добавлено через 1 минуту и 18 секунд

Цитата(NFL @ 6.12.2009, 00:01

)

sTa1kEr, спс огромное, преподу хватит

Я не для препода ее решал, а для себя smile

Так сказать разминка для мозгов smile

NFL

Дата 5.12.2009, 23:10 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 137
Регистрация: 5.5.2009

Репутация: нет
Всего: нет

sTa1kEr, smile

да ну его, для себя такие задачи решать, никому не нужные smile

sTa1kEr

Дата 5.12.2009, 23:24 (ссылка)

(нет голосов)

Загрузка ...

9/10 программиста

Профиль
Группа: Завсегдатай
Сообщений: 1553
Регистрация: 21.2.2007

Репутация: 56
Всего: 146

Цитата(NFL @ 6.12.2009, 00:10

)

да ну его, для себя такие задачи решать, никому не нужные

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

Кстати, как можно легко доработать этот алгоритм, что-бы сократить перебор, в лучшем случае, до 2х итераций в независимости от количества процессов.
Так как мы знаем "бонусы" для всех процессов и номинальное время, то можем легко высчитать так же минимально возможное время. Т.о. если вычесть из номинального качества минимальное время, мы получим максимально возможную эффективность.
А так как условие задачи - найти последовательности с максимальной эффективностью, то нам достаточно сравнивать полученную эффективность с максимальной и, если они равны, то завершить перебор, т.к. дальнейшей перебор уже не имеет смысла.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| PHP: Общие вопросы \| Следующая тема »