Considerando que graph.Connections
tenha tamanho n
e primaries
tenha tamanho k
, tem uma abordagem que roda em tempo o(n log(n) + m log(m) + (n + m))
.
Essa abordagem é dividida em duas etapas:
- preparação dos dados (
o(n log(n) + m log(m))
)
- percorrer os dados (
o(n + m)
)
Como acontece essa mágica? Bem, vamos à ideia geral e, depois, entramos nos detalhes.
Se você tem um conjunto não ordenado de cardinalidade n
, para detectar se temos elementos repetidos sem fazer ordenação é necessário fazer o(n^2 - n)
operações. Se o conjunto for indexado, podemos reduzir esse número pela metade. Isso dá um alívio temporário, enquanto os dados não aumentam em ordem de grandeza... Imagina que você tem agora o dobro de elementos agora no conjunto (ou seja, 2n
); a quantidade de operações de busca agora é de o( ((2n)^2 - 2n)/2) = o((4 n^2 - 2 n)/2) = o(2 n^2 - n)
. Bastou aumentar a ordem de grandeza para que toda a otimização fosse perdida.
Agora, e se o conjunto fosse ordenável? Bem, ele sendo ordenável, o custo para ordená-lo é o(n log n)
(se ele não estiver previamente ordenado). Agora, dado um conjunto indexado ordenado, quantas operações são necessárias fazer para detectar eventual repetição? Apenas o(n)
. Explico-me melhor.
Quando o conjunto é indexado, posso acessar seus membros pelo índice. Por exemplo, C[i]
pega o i
-ésimo elemento do conjunto C
, já C[i + 1]
pega o elemento seguinte ao i
-ésimo. Pegar um elemento de um índice do conjunto é equivalente a determinar uma função f: N -> E
que mapeia um número natural (conjunto N
é o conjunto dos naturais) para um elemento de um conjunto arbitrário E
. Se os elementos em E
são ordenáveis e C
está ordenado de modo crescente, f
então será uma função monotonamente crescente. O que isso quer dizer? Bem, basicamente garante que f(i) <= f(i+1)
para qualquer i
dentro do domínio da função. Através da indução, também podemos demonstrar que f(i) <= f(i + k), k >= 0
.
Um dos impactos da função ser monotonamente crescente é que, se f(i) < f(i + 1)
, isso garante que f(i) < f(i + k), K >= 1
. Então, se dois elementos de índices consecutivos (i
e i + 1
) não forem idênticos, isso garante que não é necessário comparar nenhum elemento de índice j < i
com outro elemento qualquer de índice k >= i + 1
. Em outras palavras, as únicas comparações necessárias são entre elementos consecutivos.
Mas estamos falando de dois conjuntos, não de apenas um. Como isso se aplica?
Porque o princípio é o mesmo. Imagine que estamos trabalhando com dois conjuntos, A
e B
. Imagina que os conjuntos estão ordenados e que são do mesmo tipo de dados. Agora, escolha i
um índice válido em A
e j
um índice válido em B
. Com esses conjuntos e esses índices, obtemos os elementos A[i]
e B[j]
. Existem três possibilidades de comparação entre A[i]
e B[j]
:
A[i] == B[j]
: nesse caso, achamos elementos de mesmo valor, o que nós desejávamos;
A[i] > B[j]
: como estamos lidando com conjuntos ordenados, sabemos que, para k < j
, temos que B[k] <= B[j]
, portanto não faz sentido comparar A[i]
com qualquer elemento de B
com índice menor do que j
;
A[i] < B[j]
: como estamos lidando com conjuntos ordenados, sabemos que, para k < i
, temos que A[k] <= A[i]
, portanto não faz sentido comparar B[j]
com qualquer elemento de A
com índice menor do que i
.
Isso nos fornece uma base para um algoritmo de busca. De modo semelhante, só interessam aqui elementos (de certo modo) consecutivos, como no caso de procurar elementos repetidos em um conjunto ordenado. Foi definir aqui um pequeno pseudo-código para escrever uma função que detecte elementos iguais nos conjuntos A
e B
. Os argumentos para essa função são:
A
, um conjunto ordenado de elementos do tipo E
B
, um conjunto ordenado de elementos do tipo E
cmp : E,E -> S
, uma função que, dados dois elementos de E
, define qual a relação entre eles; retorna -
caso o primeiro elemento seja menor do que o segundo; +
se o primeiro elemento for maior do que o segundo ou 0
caso os elementos sejam idênticos (S
é o conjunto sinal: {-, 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
começo
i <- 0 # índice para iterar em A
j <- 0 # índice para iterar em B
enquanto i < A.tamanho && j < B.tamanho:
s = cmp(A[i], B[j])
se s == '0':
# elementos são iguais, faça alguma coisa
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]
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]
j <- j + 1
# caso i ou j extrapolem o tamanho de A ou B, respectivamente, não há mais comparações a se fazer
fim
Ao todo, há a garantia que a busca demore o(n + m)
operações. Tempo linear, fazendo com que seu problema torne-se tangível agora.
Só por curiosidade, perguntaram semana passada sobre o desempenho comparado do mergesort com o do insertionsort, pois o mergesort estava demorando aproximadamente 2x o tempo do insertionsort. Após fazer um tunning da ordenação aproveitando ao máximo a memória alocada, o desempenho obtido foi ridiculamente melhor (tipo, entre 3 mil e 7 mil vezes menor). Então, reduzir a complexidade do problema nesse nível traz grandes mudanças.
Até então, tudo foi discorrido de maneira abstrata. Como podemos tornar isso um pouco mais factível?
O primeiro passo é definir o conjunto E
e as propriedades de seus elementos, para então poder definir uma ordenação. Se E
consistir de apenas uma única chave ordenável, basta ordenar por essa chave. Por exemplo, podemos ter E
o conjunto de verbetes do dicionário; um verbete é constituído pela palavra do verbete e pelo seu significado, sendo a chave a palavra do verbete, e essa chave é passível de ordenação lexicográfica/ordenação alfabética. Por exemplo, sabemos que análise
vem lexicograficamente antes de complexidade
. Assim, é possível ordenar um dicionário usando a ordem lexicográfica.
E para o caso de chaves múltiplas? Bem, escolhemos uma chave arbitrária inicialmente. Ela será a, digamos assim, chave dominante. Se ordenarmos apenas pela chave dominante, teremos listas parcialmente ordenadas. Nesse caso, se escolhe uma outra chave para dominar sobre os outros elementos, sendo assim essa seria a segunda chave dominante. Repetimos esse passo até que todas as chaves sejam usadas, definindo uma hierarquia de dominância entre chaves. O mais interessante aqui é que, para o algoritmo de busca acima, não importa qual seja a hierarquia de dominância escolhida, contanto que ela seja consistente. (Talvez a escolha dessa hierarquia de dominância afete a quantidade de trabalho feito na ordenação dos dados, entretanto).
No nosso caso, o conjunto que temos de comparar é o de duas coordenadas. Elementos desse conjunto contém quatro valores: lat1 , long1 , lat2 , long2
. Como para o algoritmo de busca a hierarquia de dominância de chaves não importa, vou ordenar inicialmente por lat1
, usando lat2
como primeiro critério de desempate, seguido de long1
e, então long2
. De grosso modo, a função de comparação seria algo mais ou menos assim:
int cmp_coords(Connection c, Primary p) {
double delta = c.Initial.Coordinate.CoordY - p.LatitudeOne;
if (delta != 0) {
// caso em qua a chave dominante prevalece
return delta < 0? -1: +1;
}
// caso em que a chave dominante empatou
// primeiro critério de desempate: Lat2
delta = c.End.Coordinate.CoordY - p.LatitudeTwo;
if (delta != 0) {
// desempatou!!
return delta < 0? -1: +1;
}
// segundo critério de desempate: Long1
delta = c.Initial.Coordinate.CoordX - p.LongitudeOne;
if (delta != 0) {
// desempatou!!
return delta < 0? -1: +1;
}
// último critério de desempate/última chave: Long2
delta = c.End.Coordinate.CoordX - p.LongitudeTwo;
if (delta != 0) {
// desempatou!!
return delta < 0? -1: +1;
}
// ok, realmente empatou em tudo!
return 0;
}
Assim, se tivermos as variáveis graphConnectionsOrdered
criadas a partir de graph.Connections
aplicando a função de comparação análoga à função acima, e também a primariesOrdered
do mesmo jeito em relação à primaries
, podemos fazer o seguinte:
int i = 0; // índice de iteração sobre graphConnectionsOrdered
int j = 0; // índice de iteração sobre primariesOrdered
while (i < graphConnectionsOrdered.Length && j < primariesOrdered.Length) {
int s = cmp_coords(graphConnectionsOrdered[i], primariesOrdered[j]);
if (s == 0) {
// elementos são iguais, faz algo?
i++;
j++;
} else if (s < 0) {
// elemento em graphConnectionsOrdered menor do que o primariesOrdered; incrementa índice do graphConnectionsOrdered
i++;
} else {
// elemento em graphConnectionsOrdered maior do que o primariesOrdered; incrementa índice do primariesOrdered
j++;
}
}
Isso executa em tempo garantido o(n + m)
. O tempo necessário para ordenar cada conjunto é o(n log(n))
e o(m log(m))
. Portanto, o tempo total é o(n log(n) + m log(m) + (n + m))
.
Certo, mas você sempre falou para trabalhar com um tipo homogeneizado, mas a comparação usa dois tipos distintos. Por quê? E como isso é possível?
Bem, certo, realmente eu pulei essa parte de propósito. Apesar de ambos Connection
e Primary
representarem duas coordenadas, eles não são do mesmo tipo. Em compensação, eles são trivialmente convertidos um tipo no outro: existe uma bijeção entre Connection
e Primary
. Devido a essa bijeção, se respeitarmos o modo como ela é feita (e nós a respeitamos ali em cima), então temos que os tipos são equivalentes. Como eles são equivalentes, usei algumas conversões implícitas entre eles dois, economizando criação de variáveis temporárias que só existiriam para fazer essa homogeneização.