expressões lambda - Iterar sobre duas Lista de forma otimizada - Otimização de Algoritmo O(n²) C# - Stack Overflow em Português
Preciso iterar sobre duas lista e fazer a comparação dos valores contidos em ambas. Porém a forma que estou fazendo, está consumindo muito tempo, pois a grandeza do meu algoritmo é O(n²), seguem abaixo mais detalhes.
Existe um grande problema nessa abordagem pois, minhas lista são muito grandes, e essa iteração consome muito tempo.
System.ArgumentOutOfRangeException: O índice estava fora do intervalo. Ele deve ser não-negativo e menor que o tamanho da coleção. Nome do parâmetro: index
É uma lista carregara a partir do meu banco, ela conte dois pares de coordenadas (Long1, Lat1) e (Lon2, Lat2). – Mik3i4a5 22/08/17 às 13:54
Tem como mostrar o código? porque você faz o FOREACH de um item e dentro desse faz foreach do primaries – PauloHDSousa 22/08/17 às 13:56
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)).
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.
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]: 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:
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.
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:
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:
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.
Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag c# expressões-lambda complexidade-de-algoritmo ou faça sua própria pergunta.