4

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.

  • Possuo um lista por nome Conexões e uma de Primários.
  • Preciso iterar sobre ambas conforme código abaixo.

    for (int i = 0; i < graph.Connections.Count; i++)
    {
         foreach (var primare in primaries)
         {
             if (graph.Connections[i].Initial.Coordinate.CoordX == primare.LongitudeOne && graph.Connections[i].Initial.Coordinate.CoordY == primare.LatidudeOne && graph.Connections[i].End.Coordinate.CoordX == primare.LongitudeTwo && graph.Connections[i].End.Coordinate.CoordY == primare.LatitudeTwo)
             { 
                   graph.Connections[i].PrimaryConnectionData.Source = graph.Connections[i].Initial.Id;
    
                   //Código aqui......
             }       
         }
    }
    
  • Existe um grande problema nessa abordagem pois, minhas lista são muito grandes, e essa iteração consome muito tempo.

Tentei uma abordagem diferente, usando um dicionário, conforme exemplo abaixo.

OBS: O meu pPointOne.Id é um long

foreach (var primary in primaries)
{
    var coordOne = new CoordinateGraph() { CoordX = primary.LongitudeOne, CoordY = primary.LatidudeOne };
    var coordTwo = new CoordinateGraph() { CoordX = primary.LongitudeTwo, CoordY = primary.LatitudeTwo };

    var pPointOne = new PrimaryPoint();
    var pPointTwo = new PrimaryPoint();

    int position;
    if (graph.PointsMap.TryGetValue(coordOne, out pPointOne) && graph.PointsMap.TryGetValue(coordTwo, out pPointTwo))
    {
        position = Convert.ToInt32(pPointOne.Id);
        graph.Connections[position].PrimaryConnectionData.Source = graph.Connections[position].Initial.Id; 

        //Código aqui...
     }
}

Porém nessa segunda abordagem eu tenho um erro em tempo de execução, que está abaixo.

Result Message:

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

  • Minha questão é, como posso fazer esse processo de forma mais otimizada?

  • Tem como fazer isso usando Lambda?

7
  • O que é esse primaries? De onde vem? Commented 22/08/2017 às 13:50
  • É uma lista carregara a partir do meu banco, ela conte dois pares de coordenadas (Long1, Lat1) e (Lon2, Lat2).
    – Mik3i4a5
    Commented 22/08/2017 às 13:54
  • Tem como mostrar o código? porque você faz o FOREACH de um item e dentro desse faz foreach do primaries Commented 22/08/2017 às 13:56
  • Sim, eu preciso iterar sobre as duas lista, para verificar se: primare.Long1 == graph.connection.long1 && primare.Lat1 == graph.connection.Lat1 && primare.Long2 == graph.connection.long2 && primare.Lat2 == graph.connection.Lat2
    – Mik3i4a5
    Commented 22/08/2017 às 13:59
  • Então coloca o código de onde vem o primaries Commented 22/08/2017 às 14:00

1 Resposta 1

2

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:

  1. preparação dos dados (o(n log(n) + m log(m)))
  2. 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.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .