Какой из вариантов перебора массива быстрее?

Question

[maiskiykot]

Скорее хотелось бы посоветоваться, чем я в затруднении. Есть база прокси, которую нужно перебрать (не совсем подходящий формат базы) и сравнить на повторение с существующей. Речь идет о сотнях тысяч записей. Столкнулся с тем, что скрипт отрабатывает это дело часами. Отсюда вопрос: как сделать перебор массива и преобразование строк максимально быстро? Нужно учесть, что база данных правильных прокси пополняется во время проверки новых данных и вариант с array_flip вообще не канает. Кто сталкивался с подобной задачей и как решали? А-то надоедает ждать.

Answer 1

[xmoonlight]

Два варианта:
1. Превращаем массив в тип графа: "дерево" и добавляем "ветки" (новые записи), если их там нет.
2. Делаем 2 списка уникальными (по-отдельности) и выполняем "merge" ("слияние") для этих списков (разные - добавятся, одинаковые - останутся неизменными).

Comments

[maiskiykot]

Что вы имеете в виду под асинхронно? Запускать два скрипта?

[xmoonlight]

maiskiykot, асинхронно - это потоки.
Т.е. разбить весь список на 4-5 групп (столько сколько потоков) и параллельно обработать.

[maiskiykot]

xmoonlight, А разве это возможно в одном скрипте? Параллельно вроде не запускаются процессы? И проверку на совпадения придется в сессии вытаскивать

[xmoonlight]

maiskiykot, задача именно проверять прокси сетевыми запросами или перебрать (сравнить) два списка?
если проверять, то есть multi_curl.

[maiskiykot]

Массивы на локали перебрать

[xmoonlight]

maiskiykot, тогда откуда там динамический список?
"Нужно учесть, что база данных правильных прокси пополняется во время проверки новых данных" - это вот: каким образом происходит?

[maiskiykot]

Так я беру свою базу примерно 250К и проверяю ее на соответствие новым записям - 400К. Если соответствий нет, то запись добавляется в список проверки, т.е. 250К++ иначе возможны совпадения. Новый список вообще безобразный

[xmoonlight]

maiskiykot, а взять php array_unique() - не вариант?!

[maiskiykot]

Проверка ведется параллельно преобразованиям нового списка. Т.е. каждую строку приходится разбирать и пересобирать. Прогонять несколько раз 400К что-то не очень хочется.

[xmoonlight]

maiskiykot, с каким именно преобразованием (сортировкой или добавлением)? Почему не брать порциями (с 1-100, с 101 - 200, и т.д.) ?

[maiskiykot]

Входящий список - каша. Я уже несколько раз это отметил. Вот как вариант:
173.195.185.35.bc.googleusercontent.com;8080;
Какой тут эррэй уникум справится? Не хочется десять раз все преобразовывать. Хочется одним прогоном разобраться. Задача периодическая, поэтому и хочется ее причесать. По поводу дробления - а чего это даст? Перебор массивов с проверкой значения частями - где шанс, что значение не совпадет в последнем? Я и так брейкую цикл после совпадения.

[xmoonlight]

maiskiykot, сделайте готовый список (который накапливайте) графом: "дерево".
1->7->3->'.'->1->9->5->'.'->..... и т.д., '.' - "точка" - это тоже промежуточный и уникальный! узел.
И при проверке из нового списка просто проверяйте достижение "листа" по первым символам по полю хоста.

[maiskiykot]

А как это ускорит процесс? Не врубаюсь. Т.е. появится куча маленьких массивов, по которым буду прогонять монстра в 400К. Нужно будет проверять по первой группе цифр к примеру а их может быть 255. Т.е. бьём на 255 массивов, которые перебираем. Разве потери времени на это не будут большими? И потом, разве поиск в цикле имеет разницу по времени в зависимости от величины массива? Это in_array накапливает время, а isset одинаково ведет себя. Кроме геморроя тут пока ничего не вижу.

[xmoonlight]

maiskiykot, откуда 255? по одному символу вложенные кластеры. И чтобы были записи уникальными - нужно убедиться, что входящий список и результурющий граф содержат уникальные элементы (каждый список по отдельности) и просто сделать merge в результирующий.
Даже проверку ставить никакую не нужно (if-then-else).

[maiskiykot]

Да уж. С графом засада. Даже почитать нечего толком для php

[xmoonlight]

maiskiykot, 2-й вариант - проще. Попробуйте его.

[maiskiykot]

xmoonlight, Т.е. наплевать на повторения и попытаться объединить? А какой шанс, что это ускорит дело? И появляется нюанс при сохранении - вдруг глюк. Придется бэкапить старую базу. Нужно попробовать. Сейчас у меня четвертый час идет проверка. Утомила.

[xmoonlight]

maiskiykot, 400к - это крайне мало. не знаю что там Вы написали в коде.

[maiskiykot]

Сам удивляюсь. Обычные строковые преобразования и проверка на совпадение. Щас вырублю эту хрень и попробую просто преобразовать входящий массив.

[maiskiykot]

Проблема все-таки в проверке уникальности. Преобразования 100К менее чем за 10 минут

[xmoonlight]

maiskiykot, преобразования 100к менее 10 минут?! Это что там такое преобразовывается-то?
КОД - покажите!

[maiskiykot]

Проще показать исходники:

ip148.ip-54-39-138.net;3128;
hotspot.rhitcr.com;8080;
h2830068.stratoserver.net;3128;
free-http1.awesomeproxy.io;3128;
fo211.i10.mi.ru;3128;
filter.maconk12.org;3128;
elearn2-pc2.germanistik.uni-kassel.de;3128;
ec2-52-54-174-211.compute-1.amazonaws.com;8080;
ec2-52-51-155-249.eu-west-1.compute.amazonaws.com;8080;
ec2-52-39-155-119.us-west-2.compute.amazonaws.com;80;
ec2-52-14-238-243.us-east-2.compute.amazonaws.com;3128;
ec2-35-170-71-181.compute-1.amazonaws.com;8080;
ec2-35-164-212-102.us-west-2.compute.amazonaws.com;4000;
ec2-35-158-101-150.eu-central-1.compute.amazonaws.com;80;
ec2-34-221-62-166.us-west-2.compute.amazonaws.com;80;
ec2-34-211-41-52.us-west-2.compute.amazonaws.com;3128;
ec2-34-203-218-129.compute-1.amazonaws.com;3128;
ec2-3-17-23-70.us-east-2.compute.amazonaws.com;3128;
ec2-18-228-14-44.sa-east-1.compute.amazonaws.com;3128;
ec2-18-222-182-77.us-east-2.compute.amazonaws.com;3128;
ec2-18-209-92-6.compute-1.amazonaws.com;8080;
ec2-18-191-242-72.us-east-2.compute.amazonaws.com;3128;
ec2-13-57-253-214.us-west-1.compute.amazonaws.com;8080;
EARTROLY.com;3128;
csiserver.ucd.ie;3128;
cp.sydo.it;80;
cm-84.209.61.144.getinternet.no;3128;
cm-84.209.138.191.getinternet.no;3128;
c738.cloud.wiroos.net;3128;
bikulciute.lt;3128;

[xmoonlight]

maiskiykot, по списку - понятно. И код, который парсит - покажите.
Надеюсь, что там нет функций *str* ?

[maiskiykot]

str_replace есть. Всегда думал, что она быстрее preg_replace. В любом случае время преобразований как раз не критичное. А вот над сравнением нужно поработать.

[maiskiykot]

if (preg_match("![a-z]!",$str[0]))
     {
       $str[0] = str_replace("static.","",$str[0]);
       $proxy = preg_replace("!\.?[a-zA-Z\.-0-9]+$!","",$str[0]);
       $str[0] = str_replace("-",".",$proxy);
     }

[maiskiykot]

Ну и запись сделал каждой строчки в файл. Тоже может притормаживает.

[xmoonlight]

maiskiykot, откуда вообще там replace?! preg_match сразу по строкам и по параметрам!

[maiskiykot]

386000строк за 35 минут

[xmoonlight]

maiskiykot, почему везде антипаттерн?
чтобы разбить данные preg_split

[maiskiykot]

Можно и через preg_match пойти. Я этот код минут пять делал. Он-то как раз не тормозит. Вся проблема в сравнительной части.

[xmoonlight]

maiskiykot, а в сравнительной то что? Давайте тот код, где проблема-то)

[maiskiykot]

Так никакой проблемы. Перебираю foreach и проверка strstr. При совпадении break

[xmoonlight]

maiskiykot, strstr() - ОМГ!
Переделывайте на preg_match()

Делайте всё пакетно: считали 10к записей, обработали, записали в файл, взяли следующие 10к записей (а не каждую строку).

[maiskiykot]

xmoonlight, Да с записью сам понимаю, что ерунда полнейшая. Просто иногда комп стал глючить - жалко работу терять. Я попробую все-таки merge сделать. По ощущениям должно прилично ускорить весь процесс.

[maiskiykot]

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

[xmoonlight]

maiskiykot, Ну ВОТ! Поздравы!

[maiskiykot]

Основное ускорение почему-то именно из-за разбития массива. ХЗ почему.

[xmoonlight]

maiskiykot, а разбитие - на пачки по N-штук, или в граф?

[maiskiykot]

Граф сложно победить - информации ноль. Думаю, что дальше оптимизировать некуда - несколько часов -> менее минуты. Лучшее - враг хорошего.

[xmoonlight]

maiskiykot, т.е., обработкой порциями по N-штук и даже без merge удалось добиться такой скорости, да?

[maiskiykot]

Нет. merge тоже применил. Однако просто прогнал преобразование сначала и уже в 100 раз быстрее получилось - 391000 записей около 10 секунд.

[xmoonlight]

maiskiykot, любой из вариантов из моего ответа - одинаковое время бы занял, т.к. ни там, ни там - проверки не нужны.
Просто теперь все новые подгрузки делаем всегда также пачками: сначала уникализируем новый список, и затем, merge'им.

Answer 2

[SagePtr]

А чем не устраивает вариант воспользоваться любой СУБД, создать таблицу со столбцом, хранящим текстовую запись адреса прокси, уникальный индекс на этот столбец и фигачить туда с игнорированием ошибок вставки (INSERT IGNORE в MySQL, ON CONFLICT DO NOTHING в PostgreSQL)?
А потом просто сделать из этой таблицы выборку и получить уникальные значения. Уж СУБД с индексами, деревьями, хешами и прочими вещами умеют работать хорошо. В виде бонуса - вместе с адресом можно хранить и другую информацию, например, дату добавления, дату последней проверки и т.п.

Comments

[maiskiykot]

Можно и базу подтянуть. Просто времени мало на эксперименты. Да и задача скорее для частного использования. Мне главное время уменьшить.