Как работать с большими массивами?

Question

[codercat]

Как правильно, например, находить общие значения в огромных массивах (100-500к значений) так, чтобы это не занимало много ресурсов?

Если делать это обычным способом, то на выходе получается очень нагруженный процесс. Возможно, следует выбрать другой язык (не знаю, насколько php приспособлен для таких задач) или как-то по-другому спроектировать, например разделить на множество небольших массивов?

$arr1 = [];
$arr2 = [];

for($i = 0; $i <= 400000; ++$i) {
	$arr1[] = rand(1000000, 100000000);
	$arr2[] = rand(1000000, 100000000);
}

$out = array_intersect($arr1, $arr2);

Answer 1

[lyeskin]

Ну для таких случаев подходит хорошо другая структура - множества (sets). Они есть в питоне, например. Работают гораздо быстрее за счет неупорядоченности и уникальности значений.

Comments

[codercat]

Ответил "ответом на вопрос", потому что в комментарии нельзя вставлять код.

[Максим Мосейчук]

codercat: Можно. int a = 3 * 23;

[codercat]

fshp: просто отсутствую кнопочки, буду знать. Спасибо!

Answer 2

[yuras666]

в php есть SplFixedArray - он съест меньше памяти. Имхо ты пытаешься повесить на php то, что ему делать не положено. Я бы реализовал эту логику на стороне того, кто хранит эти данные, например mysql. Если тебе нужно найти пересечения множеств, очень удобно использовать пересечения в redis.

Comments

[codercat]

Да, наверное, не положено. Дело в том, что такие данные мне приходят от API, поэтому сохранять их куда-то, а потом получать и удалять -- как-то нелогично и такое решение отметается. Но спасибо за мнение, буду иметь ввиду!

Answer 3

[Александр Мелеховец]

Значения добавляйте как $arr[$i] = true и делайте пересечение по ключам, array-intersect-key кажется. По сути это реализация множества.

Comments

[codercat]

Работает быстро, но ресурсов хоть и меньше, но всё равно весомо съедает, к сожалению.

Answer 4

[shagguboy]

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

Comments

[Максим Мосейчук]

Что такое поточные операции?

[shagguboy]

fshp: https://ru.wikipedia.org/wiki/SIMD

Answer 5

[codercat]

Попробовал сделать тоже самое на pyton по совету lyeskin , возможно неправильно. Результат получше, конечно, но всё равно не назвал бы его удовлетворительным

import random
set1 = set()
set2 = set()
i = 0

while i < 400000:
        set1.add(random.randint(1000000, 10000000))
        set2.add(random.randint(1000000, 10000000))
        i = i+1;

print set(set1).intersection(set2)

Comments

[lyeskin]

Ну в 2.4 раза уже хорошо :)
Замерьте отдельно отработку цикла и отработку интерсекшна. Есть подозрение, что выделение рандомных чисел работает дольше.

[codercat]

lyeskin: вы правы, отрабатывает почти с такими же затратами даже без вызова set(set1).intersection(set2). Есть идеи, как замерить именно вызов set(set1).intersection(set2)?

[lyeskin]

codercat: поставьте вывод microtime перед и после этой инструкции, вычтете и получите бенчмарк )

[lyeskin]

codercat: и да, я точно питон уже не помню, но вроде не нужно писать set(set1), можно просто set1

[codercat]

lyeskin: отлично! Думаю, это можно считать решением. Спасибо :)

set1 = set()
set2 = set()
mt = time.time();
i = 0
while i < 400000:
        set1.add(random.randint(1000000, 10000000))
        set2.add(random.randint(1000000, 10000000))
        i = i+1;
print time.time() - mt
set3 = set1.intersection(set2)
print time.time() - mt

Вывод

1.29275107384
1.31910300255

Answer 6

[SeptiM]

Отсортируйте и напишите линейный алгоритм для пересечения отсортированных массивов. array_intersect скорее всего работает квадрат и потому все грузит.