Модераторы: skyboy, MoLeX, Aliance, ksnk

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> php, нестандартная непонятная задача, "эффективный процесс" 
:(
    Опции темы
NewDima
Дата 5.12.2009, 13:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 10
Всего: 12
Если задача все-таки в переборе всех перестановок, то вот класс, реализующий интерфейс Iterator
Код

class Replacement implements  Iterator {
    protected $key = 0;
    protected $value = null;
    public function __construct($n) {
        $this->length = ((int)$n < 1)?1:(int)$n;
        $this->value = range(1, $this->length);
    }
    public function current() {
        return $this->value;
    }
    public function key() {
        return $this->key;
    }
    protected function __bur($el, $arr) {
        $got = max($arr);
        foreach ($arr as $value) {
            if (ord($value) > ord($el) &&
                ord($value) < ord($got)) {
                $got = $value;
            }
        }
        return array_merge(array($got), self::sort(array_merge(array_diff($arr, array($got)), array($el))));
    }
    public function sort($arr) {
        sort($arr);
        return $arr;
    }
    public function rsort($arr) {
        rsort($arr);
        return $arr;
    }
    public function nextFor($arr) {
        if (self::rsort($arr) === $arr) {
            return false;
        } else {
            if (count($arr) == 2) {
                return array_reverse($arr);
            }
            $first = array_shift($arr);
            if (false !== ($subnext = self::nextFor($arr))) {
                return array_merge(array($first), $subnext);
            } else {
                return self::__bur($first, $arr);
            }
        }
    }
    public function next() {
        $this->value = self::nextFor($this->value);
        ++$this->key;
    }
    public function rewind() {
        $this->value = range(1, $this->length);
        $this->key = 0;
    }
    public function valid() {
        return $this->value !== false;
    }
}

Использование:
Код

$rep = new Replacement(8);
$i = 0;
foreach ($rep as $value) {
    echo implode('', $value) . '<br />';
    $i++;
}
echo $i;


Добавлено через 8 минут и 52 секунды
Плюс класса в том, что никакого массива реально не создается, но значения можно получить по порядку.
Если увидите косяки, сделайте замечания, писал, чтобы размяться


--------------------
Начинаем черкать!
PM ICQ   Вверх
sTa1kEr
Дата 5.12.2009, 14:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

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

$rep = new Replacement(8);
$i = 0;
$time = microtime(true);
fwrite(STDOUT, "\n");
foreach ($rep as $value) {
    //echo implode('', $value) . '<br />';
    if ($i % 100 == 0) {
        fwrite(STDOUT, "\r".$i);
    }
    $i++;
}
fwrite(STDOUT, "\nOK. ".(microtime(true) - $time)."\n");

Цитата

40300
OK. 70.312089920044  smile 


Добавлено через 5 минут и 5 секунд
Нет, класс грамотно написан. Просто метод полного перебора тут ну никак не подходит.

Добавлено через 8 минут и 13 секунд
Хотя операций с массивами что-то многовато...
PM MAIL   Вверх
Simpliest
Дата 5.12.2009, 14:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 1
Всего: 3
Цитата(sTa1kEr @  5.12.2009,  13:05 Найти цитируемый пост)
40300
OK. 70.312089920044

да вы гоните.


--------------------
user posted image
PM   Вверх
sTa1kEr
Дата 5.12.2009, 14:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

Репутация: 56
Всего: 146
Нет, тут однозначно проще при помощи рекурсии перебор делать.

Добавлено через 1 минуту и 12 секунд
Цитата(Simpliest @  5.12.2009,  15:13 Найти цитируемый пост)
да вы гоните. 

Это результат, который получился на моем компе. Класс NewDima я скопировал один в один.
PM MAIL   Вверх
Simpliest
Дата 5.12.2009, 14:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 1
Всего: 3
Цитата(sTa1kEr @  5.12.2009,  13:14 Найти цитируемый пост)
Это результат, который получился на моем компе. Класс NewDima я скопировал один в один. 

Да я вроде как не возражаю. 
Но такие результаты - значит конкретная реализация не годится.
Блин, сейчас сяду посмотрю


--------------------
user posted image
PM   Вверх
NewDima
Дата 5.12.2009, 14:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 10
Всего: 12
Не понял, почему 40300
результат
40320:2.52513289452 
Вполне сносный результат


--------------------
Начинаем черкать!
PM ICQ   Вверх
Simpliest
Дата 5.12.2009, 14:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 1
Всего: 3
Так, ну во-первых, этот же код у меня выполнился за  
40300
OK.  2.217719078064

sTa1kEr, что у тебя за машина?

Во-вторых, буду смотреть дальше.


--------------------
user posted image
PM   Вверх
NewDima
Дата 5.12.2009, 14:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 10
Всего: 12
Core 2 Duo E8500 3,16Ghz 3,25 ОЗУ


--------------------
Начинаем черкать!
PM ICQ   Вверх
Simpliest
Дата 5.12.2009, 14:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 1
Всего: 3
Цитата(NewDima @  5.12.2009,  13:29 Найти цитируемый пост)
почему 40300

потому что у него данные выводятся каждые 100 тактов цикла


--------------------
user posted image
PM   Вверх
NewDima
Дата 5.12.2009, 14:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 10
Всего: 12
Полагаю, какие-то методы ведут себя по-разному в разных версиях php?
У меня правильное количество результатов и я их посматривал smile

Добавлено через 14 секунд
Понял, не заметил


--------------------
Начинаем черкать!
PM ICQ   Вверх
sTa1kEr
Дата 5.12.2009, 14:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

Репутация: 56
Всего: 146
Вот мой вариант на скорую руку:
Код

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

    for ($i = 0; $i < count($array); $i++) {
        $n = array_shift($array);
        
        if (count($array) > 0) {
            bruteforce($array, $result + array($n => $n));
        } else {
            //echo implode('', $result).$n."\n";
            $count++;
        }
        
        array_push($array, $n);
    }

    return $count;
}

$time = microtime(true);
$count = bruteforce(range(1, 8));
echo "Completed. ".$count." iterations. ".(microtime(true) - $time)." sec\n";
// Completed. 40320 iterations. 12.601891994476 sec



Это сообщение отредактировал(а) sTa1kEr - 5.12.2009, 15:16
PM MAIL   Вверх
NewDima
Дата 5.12.2009, 14:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 10
Всего: 12
Completed. 40320 iterations. 0.307599067688 sec


--------------------
Начинаем черкать!
PM ICQ   Вверх
sTa1kEr
Дата 5.12.2009, 14:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

Репутация: 56
Всего: 146
Цитата(Simpliest @  5.12.2009,  15:31 Найти цитируемый пост)
sTa1kEr, что у тебя за машина?

AMD Athlon™ X2 Dual Core Processor BE-2400 Вообще-то у меня netbeans компилиться smile 

Но это все не имеет значения, т.к.
1. Мы не знам на каком компе будет выполнятся программа, вполне вероятно, что задача составлялась когда еще БК'шки были
2. Преподаватель всегда может сказать: "ну ок, а теперь сделай то же самое для 12 процессов"

Добавлено через 9 минут и 43 секунды
Блин, AMD - ### =\
PM MAIL   Вверх
NewDima
Дата 5.12.2009, 15:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 10
Всего: 12
sTa1kEr, сижу и не могу сообразить, как вашим скриптом вывести генерируемые значения по порядку?


--------------------
Начинаем черкать!
PM ICQ   Вверх
sTa1kEr
Дата 5.12.2009, 15:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

Репутация: 56
Всего: 146
Соррь, не большой баг. Не подумал, что array_merege объединяет по ключу

Добавлено через 2 минуты и 46 секунд
Исправил 
bruteforce($array, $result + (array)$n);
на 
bruteforce($array, $result + array($n => $n));
PM MAIL   Вверх
Страницы: (3) Все 1 [2] 3 
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "PHP"
Aliance
IZ@TOP
skyboy
SamDark
MoLeX

Новичкам:

  • PHP редакторы собираются и обсуждаются здесь
  • Электронные книги по PHP, документацию можно найти здесь
  • Интерпретатор PHP, полную документацию можно скачать на PHP.NET

Важно:

  • Не брезгуйте пользоваться тегами [code=php]КОД[/code] для повышения читабельности текста/кода.
  • Перед созданием новой темы воспользуйтесь поиском и загляните в FAQ
  • Действия модераторов можно обсудить здесь

Внимание:

  • Темы "ищу скрипт", "подскажите скрипт" и т.п. будут переноситься в форум "Web-технологии"
  • Темы с именами: "Срочно", "помогите", "не знаю как делать" будут УДАЛЯТЬСЯ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, IZ@TOP, skyboy, SamDark, MoLeX, awers.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | PHP: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0688 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.