The WictorChaves solution is sufficient for the question, given the size of the data. The solution I propose below is overkill , with an input some orders of magnitude higher than what is being used for the case of the current issue.
Had a question I recently answered that needed performance to judge the intersection between two sets in C #. It used a quadratic algorithm o(n * m) to determine the intersection. In the my answer , I made a theoretical preamble showing that it is possible to solve the problem in linear time (approximately o(n log n) ) .
Well, the question there was to calculate the intersection, but this one is about calculating the union. Here, a mathematical union of sets is actually being done, so the behavior eliminates duplications .
In joining sets, the following happens:
Todothejoinoperationthisway,youalsoneedtoremovetheidenticalvalues.
Ifthesetsarecluttered,weneedtocompareallthevaluesofonesetwiththoseoftheotherset.Therefore,quadratictimeo(n*m).
However,ifthesetsareordered,theidentificationoftheidenticaltermsrequireslineartimeo(n+m).Inthe my answer , I suggested an algorithm to identify the elements of the intersection. I will present a slightly modified version of it.
-
A , an ordered set of elements of type E
-
B , an ordered set of elements of type E
-
cmp : E,E -> S , a function that, given two elements of E , defines the relationship between them; returns - if the first element is less than the second; + if the first element is greater than the second or 0 if the elements are identical ( S is the set sign: {-, 0, +} )
entrada:
A, conjunto ordenado de elementos do tipo E
B, conjunto ordenado de elementos do tipo E
cmp, função sinal que compara dois elementos de E
retorno:
C, conjunto de elementos do tipo E oriundo da união de A e B
começo
i <- 0 # índice para iterar em A
j <- 0 # índice para iterar em B
C <- []
ultimo_elemento_adicionado <- null
enquanto i < A.tamanho && j < B.tamanho:
s = cmp(A[i], B[j])
se s == '0':
# elementos são iguais, um deles como elemento candidato
candidato <- A[i]
i <- i + 1
j <- j + 1
senão, se s == '-':
# A[i] < B[j], então próxima comparação será com A[i + 1] e B[j]; A[i] agora é candidato
candidato <- A[i]
i <- i + 1
senão # caso trivial onde s == '+':
# A[i] > B[j], então próxima comparação será com A[i] e B[j + 1]; B[j] agora é candidato
candidato <- B[j]
j <- j + 1
# agora vamos ver se o candidato deve ser inserido em C: precisa ser distinto do último elemento adicionado, ou ser o primeiro elemento adicionado
se ultimo_elemento_adicionado != null && cmp(candidato, ultimo_elemento_adicionado) != '0':
ultimo_elemento_adicionado = candidato
C.push(candidato)
# caso i ou j extrapolem o tamanho de A ou B, respectivamente, não há mais comparações a se fazer
retorna C
fim
In all, there is a guarantee that the search will take% of% operations. Linear time, making your problem become tangible now.
In order to make this linear time algorithm, we need to preprocess the data sets o(n + m) and A , as repaired by @Isac . As I explained in the C # response , you can do a full sort on any set of compound elements, as long as each of the keys of these elements is amenable to total ordering.
So by developing the B function that establishes the total ordering relationship between the desired elements in your element set, you can rearrange the elements in cmp and then apply the algorithm above and get the join.
To turn JSON into PHP objects, you can use the o(n log n) function. In case, after decoding the JSON, just order using the json_decode function of total field ordering the array inside the decoded object cmp .
