Друзья, передо мной стоит задача исключить из списка словосочетаний те, которые полностью входят в другие. Реализовано с помощью такой функции. Все прекрасно работает, пока массив маленький. 1000 записей обрабатываются за 3 секунды, а вот 3000 за 28 (?!) секунд. Мне нужно пройтись по 100к. Наверняка, есть способ сделать этот код лучше и быстрее. Но какой? з.ы. протестить на 1000 можно тут PHP: function leave_good_tails($array){ $array = explode("\n", $array); $array = array_map('rtrim', $array); foreach($array as $str) { //разбиваем строку на слова $wds = explode(" ", $str); foreach($array as $str2) { $wds2 = explode(" ", $str2); //не будем сопоставлять строку саму с собой if ($str2 != $str){ $intersect = array_intersect($wds2, $wds); $count_needle = count($wds2); $count_intersect = count($intersect); //Если все слова меньшего массива найдены if ($count_intersect == $count_needle){ $all_doubles[] = $str2; } } } } //Теперь отнимем дубли из основного массива echo "<p>Список без вхождений, очищенный от дубликатов:"; $new_array = array_diff($array,$all_doubles); foreach ($new_array as $word){ echo "</br>".$word; } } $start = microtime(true); $array = "ура солнце светит бодро светит солнце "; leave_good_tails($array); echo 'Время выполнения скрипта: '.(microtime(true) - $start).' сек.';
1) Ну дык, там у вас сложность O(n^2), а не O(n); Потому и время растет не линейно. 3000 ровно в 3 раза больше, чем 1000. Три в квадрате - девять. Итого, время выполнения вырастает в 9 раз. Тысяча отрабатывала за 3 секунды, значит, новое время будет 9*3 = 27 секунд. Очень даже похоже на то, что вы описали, если учитывать погрешности и допуски измерений. 2) У вас не по словосочетаниям поиск идет, а по словам. Это несколько разные вещи. 3) Входящий массив точно должен быть просто строкой со словами, разделенными пробелами, а не набором словосочетаний, каждое в своей ячейке? Потому что массив - это массив. А у вас просто строка.
1) похоже 2) Беру первое словосочетание "солнце светит", разбиваю на слова. Беру второе "бодро светит солнце", разбиваю на слова — с тем, чтобы сопоставить каждое слово с каждым. Сопоставляю слова, по их сопоставлению делаю вывод о совпадении словосочетаний : если каждое слово 1 словосочетания нашлось во 2 словосочетании считаю 1 словосочетание дубликатом. Может криворуко написала, но сама желаемая логика выполняется, только медленно. 3) Входящий массив мне дается as is — это просто строка, каждое словосочетания с новой строки. Я его explode по переводу строки — получается массив строк, с которым я дальше и работаю.
А если они в другом порядке даны? Или в этом и есть цель, чтобы идентифицировать "светит солнце" и "солнце светит" как одинаковые? Если нет, то Это лишнее. В таком случае достаточно просто сделать сплит по переводу строки, как у вас, а потом вызвать https://php.net/manual/ru/function.array-unique
Вы совершенно правы, в этом и цель. "светит солнце", "солнце светит бодро": считаем 1 дублем (хоть и порядок разный, и слово "бодро" добавилось), а второе оставляем.
Хм..вечером попробую поковырять интереса академического ради. Но, сходу вопрос, установлен ли какой-нибудь xDebug или еще что-то? Оно может заметно влиять на производительность кода.
Ваш алгоритм, кстати, работает некорректно. Если ему скормить Код (Text): ура солнце светит бодро светит солнце бодро светит солнце бодро светит солнце бодро светит солнце то результатом будет Код (Text): ура бодро светит солнце бодро светит солнце бодро светит солнце бодро светит солнце Дубликатов останется полным полно в итоге.
Попробуйте вот такую функцию: PHP: function leave_good_tails($array) { $array = explode("\n", $array); echo 'Обработано строк: ' . sizeof($array); $array = array_map('rtrim', $array); $array = array_unique($array); foreach ($array as $first_key => $first_operand) { if ($first_operand === '') { unset($array[$first_key]); continue; } $exploded_first_operand = explode(' ', $first_operand); foreach ($array as $second_key => $second_operand) { if ($first_key == $second_key) { continue; } $exploded_second_operand = explode(' ', $second_operand); $intersection = sizeof(array_intersect($exploded_first_operand, $exploded_second_operand)); if ($intersection === sizeof($exploded_first_operand)) { unset($array[$first_key]); break; } } } echo "<p>Список без вхождений, очищенный от дубликатов:<hr>"; foreach ($array as $word) { echo "</br>" . $word; } } Кроме того, что работать будет гарантированно в разы быстрее, она во много раз экономичнее по расходу памяти. Ну и результат выдает корректнее, чем у вас в данный момент. --- Добавлено --- А если подумать...можно сделать иначе. --- Добавлено --- У меня данный вариант отработал 65+ тысяч "типа уникальных значений" за 4 минуты. Ваш исходный алгоритм отрабатывал бы примерно 3.5 часа. Но можно, по идее, сделать еще быстрее.
Вот еще как вариант. PHP: function leave_good_tails($array) { $result = []; $array = explode("\n", $array); echo 'Обработано строк: ' . sizeof($array); $array = array_unique($array); $array_copy = array_map( function ($element) { $element = trim($element); $result = explode(' ', $element); natcasesort($result); return implode(' ', $result); }, $array); $array_copy = array_unique($array_copy); foreach ($array_copy as $first_key => $first_operand) { if ($first_operand === '') { unset($array_copy[$first_key]); continue; } $exploded_first_operand = explode(' ', $first_operand); foreach ($array_copy as $second_key => $second_operand) { if ($first_key == $second_key) { continue; } $exploded_second_operand = explode(' ', $second_operand); $intersection = sizeof(array_intersect($exploded_first_operand, $exploded_second_operand)); if ($intersection === sizeof($exploded_first_operand)) { unset($array_copy[$first_key]); break; } } } foreach (array_keys($array_copy) as $key) { $result[] = $array[$key]; } echo "<p>Список без вхождений, очищенный от дубликатов:<hr>"; foreach ($result as $word) { echo "</br>" . $word; } } В идеальных условиях может быть до 2 раз быстрее предыдущего. И экономичнее. Но надо тестить на реальных данных. Там видно будет.
Насколько изящное и простое решение! Мы просто не будем по сто раз перебирать одно и то же. Этот сервис phpfiddle исполнял мой скрипт за 28 секунд (3000 записей), ваш первый вариант за 17 секунд, а второй — 18 секунд. Протестить большой объем на нем не вышло — у них ограничение на 30 секунд. На простом апаче ваш первый вариант обработал у меня 35 тысяч за 120 минут. Сейчас запустила на fast-cgi, но там тоже крутится уже около 40 минут. Думаю, дело в настройках сервера, вам же удалось за 4 минуты в 2 раза больший объем прогнать. Большое вам спасибо за помощь. Буду думать, что с настройками не так может быть.
Еще, быть может, дело в мощностях. И входные данные входным данным рознь. По-хорошему надо постараться обойтись только лишь встроенными функциями, без велосипедов. Они - это чистый Си. Они работают на порядки быстрее. Тысячи элементов жуют за сотые доли секунды. --- Добавлено --- А какая версия php у вас используется? Это тоже очень важно. Нужна хотя бы 5.6, в идеале - 7.
И да, если у вас стоит задача как можно быстрее обсчитать огромные объемы данных, то, вероятно, проблема в постановке задачи или в выборе инструментария. PHP создан не для таких целей. Ну и да, было бы гораздо легче, если бы выложили сюда архивчиком актуальные входные данные. Хотя бы те же тысяч 30. Уже будет более менее достаточно для тестирований.
Понимаю, что php не самый подходящий инструмент, но это, то чем я хотя бы минимально владею, вот и пытаюсь здесь реализовать. Судя по всему, дело еще и в версии php (5.3), буду в этом направлении двигаться. Так-то без таких задач оно вроде и без разницы, но видно пришла пора А входные данные самые простые — поисковые запросы, загрузила пример на 35К.
Разница есть. На php 5.3 у вас бы строка выдала бы ошибку. Этот синтаксис был введен начиная с 5.4 --- Добавлено --- А теперь это стало похоже на проблему "X-Y". Расскажите, какие цели преследуются? Зачем это нужно, что в конечном счете должно получиться и как должно использоваться? Быть может, вы решаете задачу "не с той стороны".
Взял из вашей выборки на обум пачку строк, оказалось, 2325. Обработал. Получил...2325 строк. Полистал ваш массив. Он состоит из уникальных запросов на 99%. Обработка не имеет смысла. По крайней мере обработка по той схеме, которую вы предложили. Любой из приведенных выше алгоритмов лишь впустую будет тратить время. Из-за этого вопросы по части преследуемых целей становятся еще острее. Потому как путь их достижения был выбран не верный. Вы пытаетесь собрать какую-то аналитику?
Вы правы, $result=[]; и выдала ошибку. Версия php из phpinfo. Этот файл на 35 тысяч мне удалось обработать за 7170 секунд (2 часа) с помощью вашего 1 скрипта. 26 тысяч осталось, около 9 отсеялось. Результат проверили вручную частично — все отлично работает, то, что нужно осталось, что не нужно отфильтровалось. Боюсь, по целям рассказать особенно нечего, кроме того, что уже было. Запрос, полностью входящий в другой запрос, нужно удалить, чтобы избежать дублирования. "солнце светит ярко" удаляем, если есть запрос "солнце светит ярко нам". Удалим "солнце светит ярко нам", если найдется запрос "солнце светит ярко нам всем". Оставим только самый длинный.
Коллеги, вы зациклились на классическом алгоритме "сравнение массивов". Откажитесь от этой идеи и сделайте 2-х/3-х проходной алгоритм - скоростя вырастут на порядки. Думаю, цель/задача позволяет.
А зачем? Куда эти запросы идут? Что это даст? Это 0.02% от проверенной массы. Неужели оно стоит таких затрат? Да, была такая мысль, но я стопорнулся, увидев, что входящий контент и без того уникален и в фильтре нужды и нет по сути. Тут хоть сколько проходов делай, эффекта не будет. На финальном проходе все равно придется обработать почти полный объем данных. Хотя, смотря что ты имел ввиду. Я сейчас про деление на равные части, независимую их проверку, потом слияние результатов, деление на n-1 частей, проверку и так далее, пока в конце не окажется пласт финальный. Если ты просто про нарезку на равные части и их независимый прогон, то это не зайдет - совпадение из первого фрагмента может лежать только в последнем. Тогда фильтр не отработает.
>> ... деление на n-1 частей, проверку и так далее, пока в конце не окажется пласт финальный. Это нелинейный алгоритм, а я про линейный. Ну, или "почти линейный".
про солнце я не вкурил 1. есть "солнце светит". мы ищем. 2. находим "солце светит нам", херим первый, который короче, т.е. "солце светит" 3. натыкаемся на "солнце светит всем". Возникает вопросы: кто главнее? нафига удаляли? и почему именно его?..
Потому что пункт два не правильный у тебя. "солнце светит нам" - это расширенная версия "солнце светит". Значит, "солнце светит" не нужно.
я написал именно это, как мне кажется. Именно по этому, не понятно, что делать в случае нахождения фразы, которая совпадает с изначальной. Короче мне насрать конечно, но я вижу как минимум два взаимоисключающих подхода, которые зависят от задачи. А задачу я не понимаю толком.
Странно, что здесь не упомянули про diff С помощью данных алгоритмов и следовало решать задачу, упростив алгоритм для сравнения слов
Я был неправ, у этой задачи нет линейного алгоритма. Я так думаю... Но можно заметно ускорить, если использовать индексацию. Например, так: PHP: function f0($text) { $source = explode("\n", mb_strtolower($text)); $b = $bb = $idx = []; foreach($source as $k=>$v) { if(!$v) continue; $b[$k] = explode(' ', $v); foreach($b[$k] as $kk=>$w) { if($w == '') { unset($b[$k][$kk]); continue; }; $idx[$w][$k] = 1; } } foreach($b as $k=>$v) { // (самый медленный кусок) $c = []; foreach($v as $kk=>$w) { $c = $kk == 0 ? $idx[$w] : array_intersect_key($c, $idx[$w]); } $bb[$k] = $c; } foreach($bb as $k=>$v) { foreach($v as $kk=>$vv) { if($kk != $k and isset($bb[$kk])) { unset($bb[$k]); } } } // Восстановить массив исходных данных (строк) и отфильтровать return array_intersect_key(explode("\n", $text), $bb); } У меня те 35933 строки от ТС отрабатывает за 6.5 секунд, оставляя 26386 строк. (php-5.6.18, Win7, 3Ггц). Для обработки требуется ~60 Мб RAM. Зависимость времени от числа строк квадратичное (примерно). п.с. Вообще, задачка оказалась интересной, не тривиальной.