To solution from @Wictorchaves is sufficient for the question given the size of the data. The solution I propose below is Overkill, with an entry some orders of magnitude above what is being used for the case of the current issue.
Had a question I answered recently that needed performance to judge the intersection between two sets in C#. He used a quadratic algorithm o(n * m)
to determine the intersection. In my answer, I did 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 to calculate the union. Here, a mathematical union of sets is being made itself, so the behavior of eliminate duplications.
In joint union, the following happens:
To make the union operation this way, it is also necessary to remove the identical values.
If the sets are disordered, we need to compare all values of one set with those of the other set. Therefore, quadratic time o(n * m)
.
However, if the sets are ordered, the identification of identical terms requires linear time o(n + m)
. In the my answer, 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 the type E
B
, an ordered set of elements of the type E
cmp : E,E -> S
, a function which, given two elements of E
, defines what the relationship between them; returns -
if the first element is less than the second; +
if the first element is larger than the second or 0
where the elements are identical (S
is the whole signal: {-, 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
All in all, there is a guarantee that the search will take o(n + m)
operations. Linear time, making your problem become tangible now.
On the other hand, in order to make this linear time algorithm, we need to pre-process the data sets A
and B
, as repaired by @Isac. As I explained in the C response#, it is possible to make a total ordering in any set of composite elements, provided that each of the keys of these elements is capable of total ordering.
Then, developing the function cmp
that establishes total ordering relationship between the desired elements in your set of elements, you can make the elements in o(n log n)
and then apply the above algorithm and get the union.
To turn JSON into PHP objects, you can use the function json_decode
. In this case, after decoding the JSON, just sort using the function cmp
total sorting of the field the array within the decoded object $json_decodificado->AdministradorGabrielOliveira
.
Is there a reason you don’t use the value of
user
how element key? A key per user and inside the user element, a key per usertempo
that would have the value ofvis
. That would make your job a lot easier.– Clayderson Ferreira
Following @Claydersonferreira’s suggestion would make it even easier to do the following things like take a user’s all time and do anything. In what you have right now you would have to iterate the entire collection.
– Isac
What parameter to set if it is equal? The three values must be identical?
– Woss
According to the structure and description of the AP I assume they are equal if
user
andtempo
are the same since thevis
indicates only whether or not it has been viewed– Isac
In fact I had thought about it only I did not put in practice because the code I developed was working in the initial model, so I didn’t want to change it so I didn’t lose focus. But had not thought that this could make things both easier... :/ rsrs good! If I understand what you are proposing, the array structure should look like this, shouldn’t it? {"user": [ { "time":"2017-08-24T04:57:13-03:00", "vis":0 }, { "time":"2017-08-24T04:57:13-03:01", "vis":0 } ] }
– GOliveira
I even know how to merge these Json, but I don’t know how to do it without repeating the data.
– Leandro Lima
Your problem is similar to this one: https://answall.com/q/231110/64969; I will try to go up as soon as possible an adaptation of the solution presented to the question Linkei
– Jefferson Quesado
Oops! I’ll look right at the tips when arriving in ksa. But from now, thank you very much!
– GOliveira
And yes. I’m going to use 'user' as the main array, and 'time' as id, so I can only search in the collection I really need. Thanks for the personal tip.
– GOliveira