交叉多个数组的最佳方法
Best method to intersect many arrays
我有一个二维数组 ($a)，第一维有 600 个元素，第二维可以有 1k 到 10k 个元素。类似于：
$a[0] = array(4 => true, 10 => true, 18 => true...);
$a[1] = array(6 => true, 10 => true, 73 => true...);
$a[599] = array(106 => true, 293 => true, 297 => true...);
我需要将这 600 个元素中的每一个元素的 $intersection 保存在一个文件中，每个元素彼此相差 5 倍。像这样：
for ($i=0;$i<=599;$i++) {
for ($j=$i+1;$j<=599;$j++) {
for ($k=$j+1;$k<=599;$k++) {
for ($p=$k+1;$p<=599;$p++) {
for ($m=$p+1;$m<=599;$m++) {
$intersection = array_intersect_key($a[$i], $a[$j], $a[$k], $a[$p], $a[$m]);
}
}
}
}
}
我正在使用 array_intersect_key 因为它比 array_intersect 快得多 因为它是 O(n) vs O(n^2).
该代码工作正常，但 运行 非常慢。所以我做了 maaany 其他尝试 运行s 有点快，比如：
for ($i=0;$i<=599;$i++) {
for ($j=$i+1;$j<=599;$j++) {
$b = array_intersect_keys($a[$i], $a[$j]);
for ($k=$j+1;$k<=599;$k++) {
$c = array_intersect_keys($b, $a[$k]);
for ($p=$k+1;$p<=599;$p++) {
$d = array_intersect_keys($c, $a[$p]);
for ($m=$p+1;$m<=599;$m++) {
$intersection = array_intersect_key($d, $a[$m]);
}
}
}
}
}
这个 运行 比第一个代码快 3 倍，但仍然很慢。我还尝试创建像 00000011001110... 这样的长二进制向量（对于每 600 个元素）并进行按位运算 &&，它的工作方式与相交完全相同，但速度并不快，而且使用的内存也更多。
所以我想知道，你有什么突破性的建议吗？我可以使用任何数学运算、矩阵运算……吗？我真的很想重新创建 array_intersect_keys 的 C+ 代码，因为在每次执行时它都会做很多我不需要的事情，比如在执行交集之前对数组进行排序——我不需要那个，因为我已经订购了我所有的东西操作开始之前的数组，因此会产生很大的开销。但我仍然不想走那条路，因为创建一个比本机实现更好的 PHP 扩展并不是那么简单。
注意：我的数组 $a 的所有元素都已排序，第一维中的元素在第二维中的元素较少，因此在数组中排在第一位，因此 array_intersect_keys 工作得更快因为该函数只需要检查直到到达第一个参数的末尾（它的大小较小）。
编辑
@user1597430 再次感谢您对我的关注和进一步的解释。你让我完全明白你说的一切！在那之后，我决定尝试自己实现你的算法，我认为它更简单、更快速，因为我从不需要使用排序，而且我也很好地使用了数组键（而不是值）。如果您需要，请随时使用下面的算法，您已经为我付出了很多时间！
实现下面的算法后，我终于明白了一件事！我只能在所有组合阶段完成后才开始检查 intersections/combinations，之后，我需要 运行 另一种算法来解析结果。对我来说，这是不可能的，因为使用 600x1000 已经花费了很长时间，而且我很可能最终不得不使用 600x20000（是的，600 x 20k），而且我很确定这会花很长时间。只有在“永远”之后，我才能检查 combinations/intersections 结果（解析）。您是否知道一种方式，我可以在每次计算后检查交叉点，或者不必等待生成所有组合？非常可悲的是，在花了将近 6 个小时来理解和实施下面的算法之后，我得出的结论是它不符合我的需要。别担心，如果没有更好的回答，我会接受你的回答，因为你已经帮了我很多，我和你一起学到了很多东西！
<?php
$quantity_first_order_array = 10;
$quantity_second_order_array = 20;
$a = array();
$b = array();
for ($i=0;$i<$quantity_first_order_array;$i++) {
for ($j=0;$j<$quantity_second_order_array;$j++) {
//I just use `$i*2 + $j*3 + $j*$i` as a way to avoid using `rand`, dont try to make sense of this expression, it's just to avoid using `rand`.
$a['group-' . $i][$i*2 + $j*3 + $j*$i] = true;
$b[$i*2 + $j*3 + $j*$i] = true;
}
}
//echo "aaaa\n\n";var_dump($a);exit();
$c = array();
foreach ($b as $chave1 => $valor1) {
$c[$chave1] = array();
foreach ($a as $chave2 => $valor2) {
if (isset($a[$chave2][$chave1])) {
$c[$chave1][] = $chave2;
}
}
}
foreach ($c as $chave1 => $valor1) {
if (count($c[$chave1]) < 5) {
unset($c[$chave1]);
}
}
//echo "cccc\n\n";var_dump($c);exit();
$d = array();
foreach ($c as $chave1 => $valor1) {
$qntd_c_chave1 = count($c[$chave1]);
for ($a1=0;$a1<$qntd_c_chave1;$a1++) {
for ($a2=$a1 + 1;$a2<$qntd_c_chave1;$a2++) {
for ($a3=$a2 + 1;$a3<$qntd_c_chave1;$a3++) {
for ($a4=$a3 + 1;$a4<$qntd_c_chave1;$a4++) {
for ($a5=$a4 + 1;$a5<$qntd_c_chave1;$a5++) {
$d[$c[$chave1][$a1] . '|' . $c[$chave1][$a2] . '|' . $c[$chave1][$a3] . '|' . $c[$chave1][$a4] . '|' . $c[$chave1][$a5]][] = $chave1;
}
}
}
}
}
}
echo "dddd\n\n";var_dump($d);exit();
?>
好吧，我通常不会免费这样做，但是既然你提到了遗传算法......来自 Foldit 社区的你好。
<?php
# a few magic constants
define('SEQUENCE_LENGTH', 600);
define('SEQUENCE_LENGTH_SUBARRAY', 1000);
define('RAND_MIN', 0);
define('RAND_MAX', 100000);
define('MIN_SHARED_VALUES', 5);
define('FILE_OUTPUT', sys_get_temp_dir() . DIRECTORY_SEPARATOR . 'out.csv');
# generates a sample data for processing
$a = [];
for ($i = 0; $i < SEQUENCE_LENGTH; $i++)
{
for ($j = 0; $j < SEQUENCE_LENGTH_SUBARRAY; $j++)
{
$a[$i][] = mt_rand(RAND_MIN, RAND_MAX);
}
$a[$i] = array_unique($a[$i]);
sort($a[$i]);
}
# prepares a map where key indicates the number
# and value is a sequence that contains this number
$map = [];
foreach ($a as $i => $array)
{
foreach ($array as $value)
{
$map[$value][$i] = $i;
}
}
ksort($map);
# extra optimization: drop all values that don't have at least
# MIN_SHARED_VALUES (default = 5) sequences
foreach ($map as $index => $values)
{
if (count($values) < MIN_SHARED_VALUES)
{
unset($map[$index]);
}
else
{
# reindex array keys - we need that later for simple
# "for" loops that should start from "0"
$map[$index] = array_values($map[$index]);
}
}
$file = fopen(FILE_OUTPUT, 'w');
# permutation: generates all sequences that share the same $value
foreach ($map as $value => $array)
{
$array_length = count($array);
for ($i = 0; $i < $array_length; $i++)
{
for ($j = $i + 1; $j < $array_length; $j++)
{
for ($k = $j + 1; $k < $array_length; $k++)
{
for ($l = $k + 1; $l < $array_length; $l++)
{
for ($m = $l + 1; $m < $array_length; $m++)
{
# index indicates a group that share a $value together
$index = implode('-', [$array[$i], $array[$j], $array[$k], $array[$l], $array[$m]]);
# instead of CSV export you can use something like
# "$result[$index][] = $value" here, but you need
# tons of RAM to do that
fputcsv($file, [$index, $value]);
}
}
}
}
}
}
fclose($file);
本地脚本进行约 630 万次排列，总共需要约 15 秒，70% 的时间用于 I/O HDD 操作。
您可以随意使用输出方法（通过在 CSV 文件顶部使用 linux sort out.csv -o sorted-out.csv 或为每个唯一的 $index 序列创建单独的文件指针转储结果 - 由您决定）。
我有一个二维数组 ($a)，第一维有 600 个元素，第二维可以有 1k 到 10k 个元素。类似于：
$a[0] = array(4 => true, 10 => true, 18 => true...);
$a[1] = array(6 => true, 10 => true, 73 => true...);
$a[599] = array(106 => true, 293 => true, 297 => true...);
我需要将这 600 个元素中的每一个元素的 $intersection 保存在一个文件中，每个元素彼此相差 5 倍。像这样：
for ($i=0;$i<=599;$i++) {
for ($j=$i+1;$j<=599;$j++) {
for ($k=$j+1;$k<=599;$k++) {
for ($p=$k+1;$p<=599;$p++) {
for ($m=$p+1;$m<=599;$m++) {
$intersection = array_intersect_key($a[$i], $a[$j], $a[$k], $a[$p], $a[$m]);
}
}
}
}
}
我正在使用 array_intersect_key 因为它比 array_intersect 快得多 因为它是 O(n) vs O(n^2).
该代码工作正常，但 运行 非常慢。所以我做了 maaany 其他尝试 运行s 有点快，比如：
for ($i=0;$i<=599;$i++) {
for ($j=$i+1;$j<=599;$j++) {
$b = array_intersect_keys($a[$i], $a[$j]);
for ($k=$j+1;$k<=599;$k++) {
$c = array_intersect_keys($b, $a[$k]);
for ($p=$k+1;$p<=599;$p++) {
$d = array_intersect_keys($c, $a[$p]);
for ($m=$p+1;$m<=599;$m++) {
$intersection = array_intersect_key($d, $a[$m]);
}
}
}
}
}
这个 运行 比第一个代码快 3 倍，但仍然很慢。我还尝试创建像 00000011001110... 这样的长二进制向量（对于每 600 个元素）并进行按位运算 &&，它的工作方式与相交完全相同，但速度并不快，而且使用的内存也更多。
所以我想知道，你有什么突破性的建议吗？我可以使用任何数学运算、矩阵运算……吗？我真的很想重新创建 array_intersect_keys 的 C+ 代码，因为在每次执行时它都会做很多我不需要的事情，比如在执行交集之前对数组进行排序——我不需要那个，因为我已经订购了我所有的东西操作开始之前的数组，因此会产生很大的开销。但我仍然不想走那条路，因为创建一个比本机实现更好的 PHP 扩展并不是那么简单。
注意：我的数组 $a 的所有元素都已排序，第一维中的元素在第二维中的元素较少，因此在数组中排在第一位，因此 array_intersect_keys 工作得更快因为该函数只需要检查直到到达第一个参数的末尾（它的大小较小）。
编辑
@user1597430 再次感谢您对我的关注和进一步的解释。你让我完全明白你说的一切！在那之后，我决定尝试自己实现你的算法，我认为它更简单、更快速，因为我从不需要使用排序，而且我也很好地使用了数组键（而不是值）。如果您需要，请随时使用下面的算法，您已经为我付出了很多时间！
实现下面的算法后，我终于明白了一件事！我只能在所有组合阶段完成后才开始检查 intersections/combinations，之后，我需要 运行 另一种算法来解析结果。对我来说，这是不可能的，因为使用 600x1000 已经花费了很长时间，而且我很可能最终不得不使用 600x20000（是的，600 x 20k），而且我很确定这会花很长时间。只有在“永远”之后，我才能检查 combinations/intersections 结果（解析）。您是否知道一种方式，我可以在每次计算后检查交叉点，或者不必等待生成所有组合？非常可悲的是，在花了将近 6 个小时来理解和实施下面的算法之后，我得出的结论是它不符合我的需要。别担心，如果没有更好的回答，我会接受你的回答，因为你已经帮了我很多，我和你一起学到了很多东西！
<?php
$quantity_first_order_array = 10;
$quantity_second_order_array = 20;
$a = array();
$b = array();
for ($i=0;$i<$quantity_first_order_array;$i++) {
for ($j=0;$j<$quantity_second_order_array;$j++) {
//I just use `$i*2 + $j*3 + $j*$i` as a way to avoid using `rand`, dont try to make sense of this expression, it's just to avoid using `rand`.
$a['group-' . $i][$i*2 + $j*3 + $j*$i] = true;
$b[$i*2 + $j*3 + $j*$i] = true;
}
}
//echo "aaaa\n\n";var_dump($a);exit();
$c = array();
foreach ($b as $chave1 => $valor1) {
$c[$chave1] = array();
foreach ($a as $chave2 => $valor2) {
if (isset($a[$chave2][$chave1])) {
$c[$chave1][] = $chave2;
}
}
}
foreach ($c as $chave1 => $valor1) {
if (count($c[$chave1]) < 5) {
unset($c[$chave1]);
}
}
//echo "cccc\n\n";var_dump($c);exit();
$d = array();
foreach ($c as $chave1 => $valor1) {
$qntd_c_chave1 = count($c[$chave1]);
for ($a1=0;$a1<$qntd_c_chave1;$a1++) {
for ($a2=$a1 + 1;$a2<$qntd_c_chave1;$a2++) {
for ($a3=$a2 + 1;$a3<$qntd_c_chave1;$a3++) {
for ($a4=$a3 + 1;$a4<$qntd_c_chave1;$a4++) {
for ($a5=$a4 + 1;$a5<$qntd_c_chave1;$a5++) {
$d[$c[$chave1][$a1] . '|' . $c[$chave1][$a2] . '|' . $c[$chave1][$a3] . '|' . $c[$chave1][$a4] . '|' . $c[$chave1][$a5]][] = $chave1;
}
}
}
}
}
}
echo "dddd\n\n";var_dump($d);exit();
?>
好吧，我通常不会免费这样做，但是既然你提到了遗传算法......来自 Foldit 社区的你好。
<?php
# a few magic constants
define('SEQUENCE_LENGTH', 600);
define('SEQUENCE_LENGTH_SUBARRAY', 1000);
define('RAND_MIN', 0);
define('RAND_MAX', 100000);
define('MIN_SHARED_VALUES', 5);
define('FILE_OUTPUT', sys_get_temp_dir() . DIRECTORY_SEPARATOR . 'out.csv');
# generates a sample data for processing
$a = [];
for ($i = 0; $i < SEQUENCE_LENGTH; $i++)
{
for ($j = 0; $j < SEQUENCE_LENGTH_SUBARRAY; $j++)
{
$a[$i][] = mt_rand(RAND_MIN, RAND_MAX);
}
$a[$i] = array_unique($a[$i]);
sort($a[$i]);
}
# prepares a map where key indicates the number
# and value is a sequence that contains this number
$map = [];
foreach ($a as $i => $array)
{
foreach ($array as $value)
{
$map[$value][$i] = $i;
}
}
ksort($map);
# extra optimization: drop all values that don't have at least
# MIN_SHARED_VALUES (default = 5) sequences
foreach ($map as $index => $values)
{
if (count($values) < MIN_SHARED_VALUES)
{
unset($map[$index]);
}
else
{
# reindex array keys - we need that later for simple
# "for" loops that should start from "0"
$map[$index] = array_values($map[$index]);
}
}
$file = fopen(FILE_OUTPUT, 'w');
# permutation: generates all sequences that share the same $value
foreach ($map as $value => $array)
{
$array_length = count($array);
for ($i = 0; $i < $array_length; $i++)
{
for ($j = $i + 1; $j < $array_length; $j++)
{
for ($k = $j + 1; $k < $array_length; $k++)
{
for ($l = $k + 1; $l < $array_length; $l++)
{
for ($m = $l + 1; $m < $array_length; $m++)
{
# index indicates a group that share a $value together
$index = implode('-', [$array[$i], $array[$j], $array[$k], $array[$l], $array[$m]]);
# instead of CSV export you can use something like
# "$result[$index][] = $value" here, but you need
# tons of RAM to do that
fputcsv($file, [$index, $value]);
}
}
}
}
}
}
fclose($file);
本地脚本进行约 630 万次排列，总共需要约 15 秒，70% 的时间用于 I/O HDD 操作。
您可以随意使用输出方法（通过在 CSV 文件顶部使用 linux sort out.csv -o sorted-out.csv 或为每个唯一的 $index 序列创建单独的文件指针转储结果 - 由您决定）。