Distinct is slow

[chedkowski-leonsoftware]

This code takes about 3 minutes to execute:

$collection1 = Collection::range(start: 1, end: 1001); // [1,2,3,...,1_000] (count: 1_000)
$collection2 = Collection::range(start: 1, end: (30 * 1000) + 1); // [1,2,3,...,,30_000] (count 30_000)

$result = $collection1->merge($collection2)->distinct()->all();

self::assertCount(30000, $result);

similar code written in pure PHP executes in less than a second:

$collection1 = range(start: 1, end: 1000); // [1,2,3,...,1_000] (count: 1_000)
$collection2 = range(start: 1, end: 30 * 1000); // [1,2,3,...,30_000] (count: 30_000)

$result = array_unique(array_merge($collection1, $collection2));

self::assertCount(30000, $result);

Version

"php": ">=8.3", "loophp/collection": "^7.0",

Is there any way to speed up these operations?

[drupol]

I rewrote your script for making very simple benchmarks, I post the script here in case we need it later:

```php merge($collection2)->distinct()->all(); assert($count === count($result)); }; $bench2 = function (int $end, int $count) { $collection1 = range(start: 1, end: $end); $collection2 = range(start: 1, end: 5 * $end); $result = array_unique(array_merge($collection1, $collection2)); assert($count === count($result)); }; $benchmark = function (array $benchmarks, mixed ...$arguments): void { $bench = function (Closure $closure, mixed ...$arguments): void { $start = microtime(true); $memoryStart = memory_get_usage(); $closure(...$arguments); $memory = memory_get_usage() - $memoryStart; $total = microtime(true) - $start; echo 'Time: ' . $total . PHP_EOL; echo 'Memory: ' . ($memory) . PHP_EOL; }; foreach ($benchmarks as $benchmark) { $bench($benchmark, ...$arguments); } }; $benchmark([$bench1, $bench2], 5000, 25000); ```

And yes, the Distinct operation is slow, and there are several reasons for this.

Firstly, implementing the distinct operation in userland requires maintaining a history of all the items processed, which inherently adds overhead. Secondly, since the Collection library works with both keys and values, the data storage requirement is effectively doubled.

Moreover, the Collection library itself is inherently slow. My primary goal was not to optimize for performance but to create a functional library that meets my needs. I aimed for a lazy evaluation library with well-defined functions in their respective files to facilitate algorithm improvements and encourage easy collaboration from contributors.

A significant reason for the slowness is that Collection can handle any type of iterables (arrays, iterators, objects) with any type of keys (objects, booleans, arrays) and any type of values. This flexibility incurs a performance cost because every operation must account for both the keys and the values.

Comparing Collection (a PHP implementation) to array_* (a C implementation) is somewhat nonsensical. array_* will always be faster, but it is limited to handling only arrays.

The project is open-source, and you're free to improve the algorithm if you think there is room for improvements, contributions are very welcome.

[github-actions[bot]]

Since this issue has not had any activity within the last 5 days, I have marked it as stale. I will close it if no further activity occurs within the next 5 days.