找到像Facebook共同朋友这样的共同关系
我正在构建一个简单的算法来查找两个输入之间的相互连接,但是我无法创建有效且快速的方法来成功找到需要用于循环的结果,但不适用于大数据,请对此提供帮助从上一个月开始工作,但没有成功。谢谢:)
var data_1 = [
{Name:"Jhon",Class:10},
{Name:"Alex",Class:10},
{Name:"Harry",Class:10},
{Name:"Jack",Class:11},
{Name:"Henry",Class:11},
{Name:"Isaac",Class:6},
{Name:"Austin",Class:6},
{Name:"David",Class:6},
{Name:"Alex",Class:6},
{Name:"Ellis",Class:9},
{Name:"Austin",Class:9},
{Name:"Jamie",Class:9}
];
var data_2 = [
{Name:"Jhon",Class:10},
{Name:"Alex",Class:10},
{Name:"Ryan",Class:10},
{Name:"Jack",Class:11},
{Name:"Henry",Class:11},
{Name:"Isaac",Class:6},
{Name:"David",Class:6},
{Name:"Ellis",Class:9},
{Name:"Ryan",Class:9},
{Name:"Jamie",Class:9}
];
Input 1 = Jhon,10
Input 2 = Ellis,9
Step 1: find all students in same class
//case 1 (in this case we use Data_1)
var input_1_child = Jhon,Alex,Harry; (all these names belongs in same class)
var input_2_child = Ellis,Austin,Jamie; (all these names belongs in same class)
Find matches from step 1 childs (match if any name is common in both childs)
Result = False ( in this case there is no common name between "input_1_child" and "input_2_child" so result is false and we move to next step 2)
// case 2 (in this case we use Data_2)
var input_1_child = Jhon,Alex,Ryan;
var input_2_child = Ellis,Ryan,Jamie;
Find matches from step 1 childs (match if any name is common in both childs)
Result = True ( Ryan is common name between "input_1_child" and "input_2_child" so result is true so we return data like below)
return [[0],[2]] - [[7],[8]];
in above result we return two diffrent array , in first array 0 refres to index value of first input and in second array 7 refres to index value of second input so first item in array will always be input index
and 2 and 8 refres to index value of "Ryan" which is common in both childs
//Step 2: this will execute only when step 1 results are false
In step 1 we find all child's of Input 1 now we go one more deep level and find child's of child like below
from Jhon we found 2 other names which is Alex and harray now we find all child's of those two other names
Note in this case we use "data_1"
[0] => index value in data array
Jhone => name
:10 => class
Input 1 => [0]Jhone:10 -> [1]Alex:10 , [2]harray:10
| |
| |
| No Other harray found in data
|
[7]Alex:6-> [5]Isaac:6, [6]David:6
Input 2 => [8]Ellis:9 -> [9]Austin:9 , [10]Jamie:9
| |
| |
| No Other Jamie found in data
|
[6]Austin:6-> [5]Isaac:6, [6]David:6
and again match 2nd level childs of input 1 with input two and return rsults like below
return [[0],[1],[7],[5]] - [[8],[9],[6],[5]];
** NOTE: if results are false in step 2 then repeat this process one more deep level child's until match found**
我的旧解决方案运行得很慢
public function Matrix(Request $request) {
$list_id = $request->input('id');
//user Input
$input_1 = $request->input('name');
$input_1 = explode('|', $input_1);
$input_2 = $request->input('name2');
$input_2 = explode('|', $input_2);
$input_name_1 = $input_1[0];
$input_uuid_1 = $request->input('name_one_class');
$input_id_1 = $input_1[2];
$input_name_2 = $input_2[0];
$input_uuid_2 = $request->input('name_two_class');
$input_id_2 = $input_2[2];
$this->global_input_1_uid = $input_uuid_1;
// case 1
$case1_0 = Sheet::where([['uid', $input_uuid_1], ['name', $input_name_2]])->get();
$case1_1 = Sheet::where([['uid', $input_uuid_2], ['name', $input_name_1]])->get();
if(count($case1_0) > 0) {
//return $case1_0[0]->uid;
$cfi1 = Sheet::whereIn('id',[$input_id_1])->get();
$cfi2 = Sheet::whereIn('id',[$input_id_2])->get();
$Mat_res = [$cfi1,$cfi2];
return view('results')->with('data', $Mat_res)->with('name2', $input_2)->with('name', $input_1)->with('case', 0);
}else if( count($case1_1) > 0) {
$cfi1 = Sheet::whereIn('id',[$input_id_1])->get();
$cfi2 = Sheet::whereIn('id',[$input_id_2])->get();
$Mat_res = [$cfi1,$cfi2];
return view('results')->with('data', $Mat_res)->with('name2', $input_2)->with('name', $input_1)->with('case', 0);
}else {
// case 2
$case_2_1_list = Sheet::where([['uid', $input_uuid_1]])->get();
$case_2_2_list = Sheet::where([['uid', $input_uuid_2]])->get();
$case_2_1_list_name_array = Sheet::where([['uid', $input_uuid_1]])->whereNotIn('id', [$input_id_1])->pluck('name')->toArray();
$case_2_2_list_name_array = Sheet::where([['uid', $input_uuid_2]])->whereNotIn('id', [$input_id_2])->pluck('name')->toArray();
$result_pre = array_intersect($case_2_1_list_name_array, $case_2_2_list_name_array);
$intersection = array_intersect($case_2_1_list_name_array, $case_2_2_list_name_array);
//$intersection = implode(',', $intersection);
//return $case_2_2_list_name_array;
if($result_pre == true) {
$Mat_res = [$input_uuid_1,$input_uuid_2,$intersection];
return view('results')->with('intersection', $intersection)->with('uid1', $input_uuid_1)->with('uid2', $input_uuid_2)->with('name2', $input_2)->with('name', $input_1)->with('case', 1);
}else {
// return $input_uuid_1.' - '.$input_uuid_2;
// return $in_class_two;
// get all first level childs
//$child_1_level_1 = Sheet::where('name', $input_1)->pluck('uid')->toArray();
$child_1_level_1 = Sheet::where([['uid','=', $input_uuid_1],['lid','=', 1]])->whereNotIn('name', [$input_1])->get();
// $child_2_level_1 = Sheet::where('name', $input_2)->pluck('uid')->toArray();
//return $child_1_level_1;
$child_2_level_1 = Sheet::where('uid','=', $input_uuid_2)->whereNotIn('name', [$input_2])->where('lid', $list_id)->get();
return $child_2_level_1;
$nokia = Sheet::where([['name', '=', $input_name_1], ['uid', '=', $input_uuid_1]])->get();
$sony = Sheet::where([['name', '=', $input_name_2], ['uid', '=', $input_uuid_2]])->get();
$child_1_level_1 = $this->setRoute($nokia[0]->id, $child_1_level_1);
$child_2_level_1 = $this->setRoute($sony[0]->id, $child_2_level_1);
//return $child_1_level_1;
array_push($this->final_list_1, $child_1_level_1);
array_push($this->final_list_2, $child_2_level_1);
array_push($this->exclude_list, 0);
$this->matrixLoop(1);
$this->FlaternData(1);
$this->matrixLoop(2);
$this->FlaternData(2);
$matrix_result_1 = $this->theEnd(1);
$matrix_result_2 = $this->theEnd(2);
$a1 = array_keys($matrix_result_1);
$a2 = array_keys($matrix_result_2);
$result=array_intersect($a1,$a2);
$Mat_res = array();
$check = false;
foreach ($matrix_result_1 as $key => $value) {
if($check == true) {break;}
foreach ($matrix_result_2 as $key2 => $value2) {
if($check == true) {break;}
if($key == $key2) {
//return [$value, $value2];
$mk1 = explode("|",$value);
$mk2 = explode("|",$value2);
$mk1str = implode(',', $mk1);
$mk2str = implode(',', $mk2);// ADD ARRAY REVERSE HERE ******************************************IMPOERTANT**************************** $mk2str = implode(',', array_reverse($mk2));
//return [$mk1,$mk2];
$mat1 = $this->removeRepeatedParent($mk1,$mk1str,1);
$mat2 = $this->removeRepeatedParent($mk2,$mk2str,2);
//return [$mat1,'--------------------------------------------',$mat2];
//$mat1 = Sheet::whereIn('id', $mk1)->orderByRaw(DB::raw("FIELD(id, $mk1str)"))->get();
//$mat2 = Sheet::whereIn('id', $mk2)->orderByRaw(DB::raw("FIELD(id, $mk2str)"))->get();
$data = [$mat1, $mat2];
array_push($Mat_res, $data);
//$check = true;
}
}
}
return view('results')->with('data', $Mat_res)->with('name2', $input_2)->with('name', $input_1)->with('case', 5);
}
}
}
回答如下:我认为这种解释将有助于解决您的问题。如果要通过连接实现数据结构,首先必须实现类似图的数据结构来存储数据。
[Graph是具有节点和边的非线性数据结构。例如,如果您使用facebook帐户,则每个人都是一个节点,每个节点都保存该人的信息。边缘是连接节点的链接。
您可以参考graphql(由facebook实现),这是一种实现数据结构和通过模式定义查询的简便方法。您可以轻松地将graphql与nodejs集成。
请参考这些链接以开始使用graphql并了解图形。
Graph theory
Graph Data Structure And Algorithms
Thinking in Graphs
找到像Facebook共同朋友这样的共同关系
我正在构建一个简单的算法来查找两个输入之间的相互连接,但是我无法创建有效且快速的方法来成功找到需要用于循环的结果,但不适用于大数据,请对此提供帮助从上一个月开始工作,但没有成功。谢谢:)
var data_1 = [
{Name:"Jhon",Class:10},
{Name:"Alex",Class:10},
{Name:"Harry",Class:10},
{Name:"Jack",Class:11},
{Name:"Henry",Class:11},
{Name:"Isaac",Class:6},
{Name:"Austin",Class:6},
{Name:"David",Class:6},
{Name:"Alex",Class:6},
{Name:"Ellis",Class:9},
{Name:"Austin",Class:9},
{Name:"Jamie",Class:9}
];
var data_2 = [
{Name:"Jhon",Class:10},
{Name:"Alex",Class:10},
{Name:"Ryan",Class:10},
{Name:"Jack",Class:11},
{Name:"Henry",Class:11},
{Name:"Isaac",Class:6},
{Name:"David",Class:6},
{Name:"Ellis",Class:9},
{Name:"Ryan",Class:9},
{Name:"Jamie",Class:9}
];
Input 1 = Jhon,10
Input 2 = Ellis,9
Step 1: find all students in same class
//case 1 (in this case we use Data_1)
var input_1_child = Jhon,Alex,Harry; (all these names belongs in same class)
var input_2_child = Ellis,Austin,Jamie; (all these names belongs in same class)
Find matches from step 1 childs (match if any name is common in both childs)
Result = False ( in this case there is no common name between "input_1_child" and "input_2_child" so result is false and we move to next step 2)
// case 2 (in this case we use Data_2)
var input_1_child = Jhon,Alex,Ryan;
var input_2_child = Ellis,Ryan,Jamie;
Find matches from step 1 childs (match if any name is common in both childs)
Result = True ( Ryan is common name between "input_1_child" and "input_2_child" so result is true so we return data like below)
return [[0],[2]] - [[7],[8]];
in above result we return two diffrent array , in first array 0 refres to index value of first input and in second array 7 refres to index value of second input so first item in array will always be input index
and 2 and 8 refres to index value of "Ryan" which is common in both childs
//Step 2: this will execute only when step 1 results are false
In step 1 we find all child's of Input 1 now we go one more deep level and find child's of child like below
from Jhon we found 2 other names which is Alex and harray now we find all child's of those two other names
Note in this case we use "data_1"
[0] => index value in data array
Jhone => name
:10 => class
Input 1 => [0]Jhone:10 -> [1]Alex:10 , [2]harray:10
| |
| |
| No Other harray found in data
|
[7]Alex:6-> [5]Isaac:6, [6]David:6
Input 2 => [8]Ellis:9 -> [9]Austin:9 , [10]Jamie:9
| |
| |
| No Other Jamie found in data
|
[6]Austin:6-> [5]Isaac:6, [6]David:6
and again match 2nd level childs of input 1 with input two and return rsults like below
return [[0],[1],[7],[5]] - [[8],[9],[6],[5]];
** NOTE: if results are false in step 2 then repeat this process one more deep level child's until match found**
我的旧解决方案运行得很慢
public function Matrix(Request $request) {
$list_id = $request->input('id');
//user Input
$input_1 = $request->input('name');
$input_1 = explode('|', $input_1);
$input_2 = $request->input('name2');
$input_2 = explode('|', $input_2);
$input_name_1 = $input_1[0];
$input_uuid_1 = $request->input('name_one_class');
$input_id_1 = $input_1[2];
$input_name_2 = $input_2[0];
$input_uuid_2 = $request->input('name_two_class');
$input_id_2 = $input_2[2];
$this->global_input_1_uid = $input_uuid_1;
// case 1
$case1_0 = Sheet::where([['uid', $input_uuid_1], ['name', $input_name_2]])->get();
$case1_1 = Sheet::where([['uid', $input_uuid_2], ['name', $input_name_1]])->get();
if(count($case1_0) > 0) {
//return $case1_0[0]->uid;
$cfi1 = Sheet::whereIn('id',[$input_id_1])->get();
$cfi2 = Sheet::whereIn('id',[$input_id_2])->get();
$Mat_res = [$cfi1,$cfi2];
return view('results')->with('data', $Mat_res)->with('name2', $input_2)->with('name', $input_1)->with('case', 0);
}else if( count($case1_1) > 0) {
$cfi1 = Sheet::whereIn('id',[$input_id_1])->get();
$cfi2 = Sheet::whereIn('id',[$input_id_2])->get();
$Mat_res = [$cfi1,$cfi2];
return view('results')->with('data', $Mat_res)->with('name2', $input_2)->with('name', $input_1)->with('case', 0);
}else {
// case 2
$case_2_1_list = Sheet::where([['uid', $input_uuid_1]])->get();
$case_2_2_list = Sheet::where([['uid', $input_uuid_2]])->get();
$case_2_1_list_name_array = Sheet::where([['uid', $input_uuid_1]])->whereNotIn('id', [$input_id_1])->pluck('name')->toArray();
$case_2_2_list_name_array = Sheet::where([['uid', $input_uuid_2]])->whereNotIn('id', [$input_id_2])->pluck('name')->toArray();
$result_pre = array_intersect($case_2_1_list_name_array, $case_2_2_list_name_array);
$intersection = array_intersect($case_2_1_list_name_array, $case_2_2_list_name_array);
//$intersection = implode(',', $intersection);
//return $case_2_2_list_name_array;
if($result_pre == true) {
$Mat_res = [$input_uuid_1,$input_uuid_2,$intersection];
return view('results')->with('intersection', $intersection)->with('uid1', $input_uuid_1)->with('uid2', $input_uuid_2)->with('name2', $input_2)->with('name', $input_1)->with('case', 1);
}else {
// return $input_uuid_1.' - '.$input_uuid_2;
// return $in_class_two;
// get all first level childs
//$child_1_level_1 = Sheet::where('name', $input_1)->pluck('uid')->toArray();
$child_1_level_1 = Sheet::where([['uid','=', $input_uuid_1],['lid','=', 1]])->whereNotIn('name', [$input_1])->get();
// $child_2_level_1 = Sheet::where('name', $input_2)->pluck('uid')->toArray();
//return $child_1_level_1;
$child_2_level_1 = Sheet::where('uid','=', $input_uuid_2)->whereNotIn('name', [$input_2])->where('lid', $list_id)->get();
return $child_2_level_1;
$nokia = Sheet::where([['name', '=', $input_name_1], ['uid', '=', $input_uuid_1]])->get();
$sony = Sheet::where([['name', '=', $input_name_2], ['uid', '=', $input_uuid_2]])->get();
$child_1_level_1 = $this->setRoute($nokia[0]->id, $child_1_level_1);
$child_2_level_1 = $this->setRoute($sony[0]->id, $child_2_level_1);
//return $child_1_level_1;
array_push($this->final_list_1, $child_1_level_1);
array_push($this->final_list_2, $child_2_level_1);
array_push($this->exclude_list, 0);
$this->matrixLoop(1);
$this->FlaternData(1);
$this->matrixLoop(2);
$this->FlaternData(2);
$matrix_result_1 = $this->theEnd(1);
$matrix_result_2 = $this->theEnd(2);
$a1 = array_keys($matrix_result_1);
$a2 = array_keys($matrix_result_2);
$result=array_intersect($a1,$a2);
$Mat_res = array();
$check = false;
foreach ($matrix_result_1 as $key => $value) {
if($check == true) {break;}
foreach ($matrix_result_2 as $key2 => $value2) {
if($check == true) {break;}
if($key == $key2) {
//return [$value, $value2];
$mk1 = explode("|",$value);
$mk2 = explode("|",$value2);
$mk1str = implode(',', $mk1);
$mk2str = implode(',', $mk2);// ADD ARRAY REVERSE HERE ******************************************IMPOERTANT**************************** $mk2str = implode(',', array_reverse($mk2));
//return [$mk1,$mk2];
$mat1 = $this->removeRepeatedParent($mk1,$mk1str,1);
$mat2 = $this->removeRepeatedParent($mk2,$mk2str,2);
//return [$mat1,'--------------------------------------------',$mat2];
//$mat1 = Sheet::whereIn('id', $mk1)->orderByRaw(DB::raw("FIELD(id, $mk1str)"))->get();
//$mat2 = Sheet::whereIn('id', $mk2)->orderByRaw(DB::raw("FIELD(id, $mk2str)"))->get();
$data = [$mat1, $mat2];
array_push($Mat_res, $data);
//$check = true;
}
}
}
return view('results')->with('data', $Mat_res)->with('name2', $input_2)->with('name', $input_1)->with('case', 5);
}
}
}
回答如下:我认为这种解释将有助于解决您的问题。如果要通过连接实现数据结构,首先必须实现类似图的数据结构来存储数据。
[Graph是具有节点和边的非线性数据结构。例如,如果您使用facebook帐户,则每个人都是一个节点,每个节点都保存该人的信息。边缘是连接节点的链接。
您可以参考graphql(由facebook实现),这是一种实现数据结构和通过模式定义查询的简便方法。您可以轻松地将graphql与nodejs集成。
请参考这些链接以开始使用graphql并了解图形。
Graph theory
Graph Data Structure And Algorithms
Thinking in Graphs