Эффективный способ сравнить ОЧЕНЬ БОЛЬШОЕ ЧИСЛО ЗНАЧЕНИЙ php - PullRequest
Новая
       8

Эффективный способ сравнить ОЧЕНЬ БОЛЬШОЕ ЧИСЛО ЗНАЧЕНИЙ php

1 голос
/ 08 апреля 2011

привет Я должен сравнить очень большое количество значений, я использовал массивы, но не хватает памяти. значения в массивах составляют около 5000000, и для каждого значения снова будет выполняться цикл 5000000. вкратце будет выполнено 5000000 x 5000000 циклов.

я просто запускаю два цикла. пожалуйста, дайте мне знать какой-нибудь эффективный способ сделать это, так как эта программа останавливается из-за памяти. 

for($k=0;$k<sizeof($pid);$k++) // size of $pid = 5000000
{
$out =0;
        for ($m=0;$m<sizeof($outid);$m++) // size of $out 5000000
        {
                    if ($pid[$k] == $out[$m])
                    {
                            $out ++;
                    }

        }
}

Ответы [ 3 ]

3 голосов
/ 08 апреля 2011

Если бы вы могли отсортировать оба списка, вам нужно было бы просмотреть каждый список только один раз, потому что у вас мог бы быть индекс для первого списка и индекс для второго списка. Если элемент в первом индексе меньше, чем элемент во втором индексе, увеличьте первый индекс, в противном случае увеличьте второй индекс. Затем вы просто отслеживаете, сколько элементов равны, когда проходите над ними.

1 голос
/ 08 апреля 2011

Сложность алгоритма может быть сложным предметом для большинства программистов на VB и PHP - это не тривиально.

Подход 1

Допустим, вы нашли способ использовать ваш O(n^2) подходи предположим, что ваш компьютер может выполнить 1000000 сравнений за 1 секунду, и вы запускаете цикл сейчас 2:04:45 pm EEST | Wednesday, June 23, 2010, тогда цикл завершится 6:58:05 am EET | Monday, January 23, 2012.

Я не эксперт в PHP, но я уверен, что у страницы есть ограничение по времени, в соответствии с которым она должна обслуживаться, или исключение тайм-аута страницы - throw.Этот предел может быть 30 с, 90 с или как вы его определили, но требуемый лимит времени для этого цикла глупый.

Подход 2

Если вы решите отсортировать массив, это действие займет O(n log n) для обоих массивов и O(n log n) для сравнения.Это сделает общее время около 3 * O(n log n), это просто 100.5 seconds.Или 33.49 seconds, если предварительно отсортированы массивы.

Я бы выбрал Подход 2 , если бы я был вами.

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

0 голосов
/ 08 апреля 2011

вы можете попробовать функцию пересечения массива http://ua.php.net/manual/en/function.array-intersect.php, она основана на C и должна работать более оптимизированно

...