N-грамма поколения


У меня есть следующий код, но это слишком медленно. Как я могу сделать это быстрее?

<?php
class Ngram {

const SAMPLE_DIRECTORY = "samples/";
const GENERATED_DIRECTORY = "languages/";
const SOURCE_EXTENSION = ".txt";
const GENERATED_EXTENSION = ".lng";
const N_GRAM_MIN_LENGTH = "1";
const N_GRAM_MAX_LENGTH = "6";

public function __construct() {
    mb_internal_encoding( 'UTF-8' );
    $this->generateNGram();
}

private function getFilePath() {
    $files = array();
    $excludes = array('.', '..');
    $path = rtrim(self::SAMPLE_DIRECTORY, DIRECTORY_SEPARATOR . '/');
    $files = scandir($path);
    $files = array_diff($files, $excludes);
    foreach ($files as $file) {

        if (is_dir($path . DIRECTORY_SEPARATOR . $file))
            fetchdir($path . DIRECTORY_SEPARATOR . $file, $callback);
        else if (!preg_match('/^.*\\' . self::SOURCE_EXTENSION . '$/', $file))
            continue;
        else
            $filesPath[] = $path . DIRECTORY_SEPARATOR . $file; 
    }
    unset($file);
    return $filesPath;
}
protected function removeUniCharCategories($string){
    //Replace punctuation(' " # % & ! . : , ? ¿) become space " "
    //Example : 'You&me', become 'You Me'.
    $string = preg_replace( "/\p{Po}/u", " ", $string );
    //--------------------------------------------------
    $string = preg_replace( "/[^\p{Ll}|\p{Lm}|\p{Lo}|\p{Lt}|\p{Lu}|\p{Zs}]/u", "", $string );
    $string = trim($string);
    $string = mb_strtolower($string,'UTF-8');
    return $string;
}
private function generateNGram() {
    $files = $this->getFilePath();
    foreach($files as $file) {
        $file_content = file_get_contents($file, FILE_TEXT);
        $file_content = $this->removeUniCharCategories($file_content);
        $words = explode(" ", $file_content);
        $tokens = array();
        foreach ($words as $word) {
            $word = "_" . $word . "_";
            $length = mb_strlen($word, 'UTF-8');
            for ($i = self::N_GRAM_MIN_LENGTH, $min =  min(self::N_GRAM_MAX_LENGTH, $length); $i <= $min; $i++) {
                for ($j = 0, $li = $length - $i; $j <= $li; $j++) {
                    $token = mb_substr($word, $j, $i, 'UTF-8');
                    if (trim($token, "_")) {
                        $tokens[] = $token;
                    }   
                }
            }
        }
        unset($word);
        $tokens = array_count_values($tokens);
        arsort($tokens);
        $ngrams = array_slice(array_keys($tokens), 0);
        file_put_contents(self::GENERATED_DIRECTORY . str_replace(self::SOURCE_EXTENSION, self::GENERATED_EXTENSION, basename($file)), implode(PHP_EOL, $ngrams));
    }
    unset($file);
}
}
$ii = new Ngram();
?>


Комментарии
2 ответа

Этот код, кажется, очень хорошо, что касается производительности. Я не вижу способа улучшить его.

Я использовал отладчик xdebug и cachegrind, чтобы увидеть, что мои пробы были привязаны к производительности цикла, который создает маркеры. Я исследовал переключения $I и $J в петельку, но производительность была не лучше.

Я не вижу каких-либо способ улучшить код, так что я бы посмотрел на более быстрый процессор или компилируемых языках, таких как С. Есть также большие улучшения в работе с PHP 5.4, так трогательно, что может быть очень хороший вариант.

Ответ на другой ответ

Теперь у нас есть два ответа, оба претендующие разных узких мест. Это делает вещи интересными! Я перечислю доказательства, что заставляет меня верить, что это ЦП. Первое доказательство я буду расследовать будет анкетная информация. Вторая будет простое доказательство снятия ввода/вывода и наблюдения за время работы. Пропустить на второе место в "удален раздел ввода/вывода", Если вы просто хотите быстрый ответ.

Профайлинг

Инструменты я использую отладчик xdebug и программа.

Сначала я создал четыре некоторые образцы файлов. Мои первые 3 файлы были Лорем Ипсум тип текстов на греческий, китайский и латынь. Моя четвертая была конкатенация этих трех файлов и показано ниже:

遺健問使物済表績象全問前禎。画更予服的負要前行年語断。肉購会際以面長力攻以野所。治条育録療常強門守更校尊無場審言団。早患社支科視徐取告性表変全意主場。度坂信神暮明死載高深典導昇話。無稿乳横面祝揚倉厘積卒食当正使。食考割闘出護空樫京速地間作夜半文性新局。前馬報惑般供筋子真車東生然歌論略形。政図警情調並浜校素先間後善経完。

Lorem ipsum dolor sit amet, eu ius nisl impedit. Tritani denique ut nam, brute aliquid iudicabit eos ei. Ad vix hinc numquam, unum utamur vix cu. Natum ubique vocibus ei duo.

Quo te eius propriae voluptatibus, id nostro forensibus signiferumque est, graecis senserit gloriatur per et. Eu munere facete scripserit vel, cu vim laudem noster. His cu dictas prodesset, aliquando constituto reprimique sed ex. Mazim decore imperdiet ut vel. Scripta delicatissimi an pro, quo ex porro nominati.

Δε τις έργων κανείς γραμμή, κι χρόνου φακέλους γειτονιάς ήδη. Σε πακέτων επενδυτής λες, που κρατήσουν επεξεργασία δε, μια ακούσει ξεχειλίζει παρατηρούμενη τα. Νέων πετάνε συνηθίζουν δε για', στη να σωστά ευκολότερο βαθμολόγησε. Απλό τέτοιο διοίκηση στα μη, δε νέο τότε περιβάλλον, οι δώσε απαρατήρητο των.

Βαθμολόγησε επιδιόρθωση επιχειρηματίες αν ματ, σου δεδομένη αγοράζοντας δωροδοκηθούν με, τα ένα αναφορά βουτήξουν. Αν καρέκλα υποψήφιο εξαρτάται όσο, και δε τεράστιο προκύπτουν σημαντικός, αν ναι καθώς διορθώσει. Υόρκη ιδιαίτερα τη άρα, τα λοιπόν παράγοντες μας. Πόρτες γραμμές σκεφτείς λες με. Σου βγήκε αρχεία δε. Και εφαμοργής κακόκεφος δε.

Тогда я побежал код, с небольшой модификацией, чтобы помочь бенчмаркинг:

$startTime = microtime(true);

for ($i = 1; $i <= 10; $i++)
{
$ii = new Ngram();
}

$finishTime = microtime(true);
echo 'Took: ' . ($finishTime - $startTime) . 'seconds';

Потребовалось около 0.61 секунд без отладчика xdebug включен и 29,1 секунды с ним. Обратите внимание, насколько медленнее он с дебаггером xdebug (это занимает много времени, чтобы отслеживать выполнение профилирования)! Затем я заметил, что отладчик xdebug информации с помощью программа:

kcachegrind table

Вы можете увидеть, что время от функции file_put_contents (которая выделена на скрине очень мало. Из 29,1 секунд он тратит только .01 секунд записи файлов (4 из них). Это было на моей памяти с файловой системой ext4. Вы можете видеть, что есть 40 вызовов функции file_put_contents 4 файлов, 10 раз каждое. На самом деле, больше времени тратится на getFilePath , который имеет более дорогостоящим файл stat операций.

Более интересная часть-это как 29 секунд уходит в generateNGram. У меня есть картина того, что я верю, чтобы быть "горячей" части кода:

kcachegrind hot

Мы получаем в 4 уровнях зацикливание здесь, где есть 121280 звонки на внутренние функции петли. Нет времени числится за цикл структурах или в дополнение к маркерам массив ($жетонов[] = $знак;). Я точно не знаю, где 29 секунд привык, но я предполагаю, что это было в эти петли.

Удален Ввода/Вывода

Простой способ определить, является ли это ввода/вывода заключается в удалении я закомментировал функции file_put_contents линии и побежала тест снова. Я обнаружил, что нет никакой разницы во времени с 0.63 секунды без xdebug и 29.2 секунды с ним (по сравнению с 0,61 и 29.1). Это было на самом деле медленнее (из-за колебаний времени), но это только показывает незначительное влияние I/О.

Резюме

Я до сих пор считаю, что это ЦП и поддерживать мои рекомендации для ускорения процессора, PHP 5.4 или компилируемом языке. Другого ответа поднимает хорошие моменты в "оптимизация, зачем?" разделе.

6
ответ дан 31 марта 2012 в 06:03 Источник Поделиться

После некоторого тестирования, это ЦП. Я также попал в PHP максимальный размер памяти при работе с большими файлами: он ест больше, чем 3G памяти при загрузке файла 4М. Попробуйте уменьшить использование памяти. :)

Я оставлю мой ответ ниже, так как Павел ответил на это.

Ввода/вывода

Вполне очевидно, что вы собираетесь создать много данных. В Гугле N-грамм корпус, например, использует 1и дискового пространства. Вы, вероятно, иметь меньше данных, но ты все равно будешь генерировать много байт, что говорит о том, что ваша программа не ЦП, но ИО-связаны. Это также означает, что использование более быстрого процессора или другой язык не поможет.

Нижняя граница

Давайте попробуем отработать нижнюю границу, чтобы увидеть, какие улучшения могут быть сделаны. Поскольку вы не можете идти быстрее, чем программа просто писать ngrams без всякого расчета, вы должны попробовать копирование ваших данных ngrams в другую папку, чтобы увидеть, как долго он будет принимать. Используя "СР" было бы опасно, поскольку там могут быть сумасшедшие оптимизации, такие как копирование при записи на вашей конкретной файловой системы.

time cat ngrams/* > all_my_ngrams
time cat corpus/* > all_my_corpus

Вы можете сравнить это, чтобы время, необходимое для вашей программы, чтобы закончить, и увидеть, где вы теряете свое время. Другой вариант-использовать микровремени с эталоном времени вы принимаете, чтобы на самом деле делать вычисления, и времени для функции file_get_contents и функции file_put_contents.

Оптимизация, для чего?

Ведь это, наверное, один сценарий, почему вы хотите сделать это быстро? Если у вас есть ngrams, вы можете использовать их и забыть об этом скрипте. Есть ли хорошая причина, чтобы улучшить этот скрипт? Если проблема является более конкретным, чем "слишком долго", чем мы можем помочь: слишком много оперативной памяти? занимает месяцы? Конкретные стратегии могут помочь в решении конкретных проблем.

2
ответ дан 30 апреля 2012 в 09:04 Источник Поделиться