Optimisation de cet algorithme C# (Différence K)

Question

Voici le problème que je suis en train de résoudre (c'est un problème type, pas un problème réel) :

Etant donné N nombres, [N<=10^5] nous devons compter le nombre total de paires de numéros. nombres qui ont une différence de K. [K>0 et K<1e9]

Format d'entrée : La première ligne contient N et K (entiers). La 2ème ligne contient N nombres de l'ensemble. Tous les N nombres sont assurés d'être distincts. Format de sortie : Un nombre entier disant le nombre de paires de nombres qui ont une différence K.

Sample Input #00:
5 2
1 5 3 4 2
Sample Output #00:
3
Sample Input #01:
10 1
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793 
Sample Output #01:
0

J'ai déjà une solution (et je n'ai pas réussi à l'optimiser aussi bien que je l'espérais). Actuellement, ma solution obtient un score de 12/15 lorsqu'il est exécuté, et je me demande pourquoi je n'arrive pas à obtenir 15/15 (ma solution à un autre problème était loin d'être aussi efficace, mais elle a obtenu tous les points). Apparemment, le code est exécuté avec "Mono 2.10.1, C# 4".

Alors, quelqu'un peut-il penser à une meilleure façon d'optimiser cela davantage ? Le profileur VS indique qu'il faut éviter d'appeler String.Split et Int32.Parse. Les appels à Int32.Parse ne peuvent pas être évités, bien que je suppose que je pourrais optimiser la tokenisation du tableau.

Ma solution actuelle :

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace KDifference
{
   class Solution
   {
      static void Main(string[] args)
      {
         char[] space = { ' ' };

         string[] NK = Console.ReadLine().Split(space);
         int N = Int32.Parse(NK[0]), K = Int32.Parse(NK[1]);

         int[] nums = Console.ReadLine().Split(space, N).Select(x => Int32.Parse(x)).OrderBy(x => x).ToArray();

         int KHits = 0;

         for (int i = nums.Length - 1, j, k; i >= 1; i--)
         {
            for (j = 0; j < i; j++)
            {
               k = nums[i] - nums[j];

               if (k == K)
               {
                  KHits++;
               }
               else if (k < K)
               {
                  break;
               }
            }
         }

         Console.Write(KHits);
      }
   }
}

Answer 1

Votre algorithme est toujours O(n^2), même avec le tri et la sortie anticipée. Et même si vous avez éliminé le bit O(n^2), le tri est toujours O(n lg n). Vous pouvez utiliser un algorithme O(n) pour résoudre ce problème. Voici une façon de le faire :

Supposons que l'ensemble que vous avez est S1 = { 1, 7, 4, 6, 3 } et la différence est de 2.

Construisez l'ensemble S2 = { 1 + 2, 7 + 2, 4 + 2, 6 + 2, 3 + 2 } = { 3, 9, 6, 8, 5 } .

La réponse que vous cherchez est la cardinalité de l'intersection de S1 et S2. L'intersection est {6, 3} qui a deux éléments, la réponse est donc 2.

Vous pouvez mettre en œuvre cette solution en une seule ligne de code, à condition d'avoir une séquence d'entiers sequence et entier difference :

int result = sequence.Intersect(from item in sequence select item + difference).Count();

La méthode Intersect construira pour vous une table de hachage efficace qui est O(n) pour déterminer l'intersection.

Answer 2

Essayez ceci (note, non testé) :

1. Trier le tableau
2. Commencez deux index à 0
3. Si la différence entre les nombres à ces deux positions est égale à K, augmenter le nombre, et augmenter l'un des deux index (si les nombres ne sont pas dupliqués, augmenter les deux).
4. Si la différence est supérieure à K, augmenter l'indice #1
5. Si la différence est inférieure à K, augmentez l'indice n°2, si cela le place en dehors du tableau, vous avez terminé.
6. Sinon, retournez au point 3 et continuez

En gros, il faut essayer de séparer les deux indices par une différence de valeur K.

Vous devriez rédiger une série de tests unitaires pour votre algorithme, et essayer de trouver des cas limites.

Answer 3

Cela vous permettrait de le faire en une seule fois. L'utilisation d'ensembles de hachage est avantageuse s'il y a beaucoup de valeurs à analyser/vérifier. Vous pouvez également utiliser un filtre anti-pelliculaire en combinaison avec des ensembles de hachage pour réduire les recherches.

1. Initialiser. Soit A y B sont deux ensembles de hachage vides. Soit c être nul.
2. Analyse de la boucle. Analyser la valeur suivante v . S'il n'y a plus de valeurs, l'algorithme est terminé et le résultat est dans c .
3. Vérification du dos. Si v existe dans A puis incrémenter c et revenir à 2.
4. Correspondance faible. Si v - K > 0 alors :
   • insérer v - K sur A
   • if v - K existe dans B puis incrémenter c (et éventuellement supprimer v - K de B ).
5. Une correspondance élevée. Si v + K < 1e9 alors :
   • insérer v + K sur A
   • if v + K existe dans B puis incrémenter c (et éventuellement supprimer v + K de B ).
6. Rappelez-vous. Insérer v sur B .
7. Retourner à 2.

Answer 4

// solution php pour cette différence k

function getEqualSumSubstring($l,$s) {
$s = str_replace(' ','',$s);
$l = str_replace(' ','',$l);

for($i=0;$i<strlen($s);$i++)
{
   $array1[] = $s[$i];
}
for($i=0;$i<strlen($s);$i++)
{
   $array2[] = $s[$i] + $l[1];
}
return count(array_intersect($array1,$array2));

}

echo getEqualSumSubstring("5 2","1 3 5 4 2");

Answer 5

En fait, c'est trivial de résoudre ce problème avec un hashmap :

Tout d'abord, mettez chaque nombre dans un hashmap : dict((x, x) for x in numbers) en pseudo-code "pythony" ;)

Maintenant, il suffit d'itérer à travers chaque numéro dans le hashmap et de vérifier si le numéro + K est dans le hashmap. Si c'est le cas, on augmente le nombre de numéros d'une unité.

L'amélioration évidente de la solution naïve est de vérifier UNIQUEMENT la limite supérieure (ou inférieure), sinon vous obtenez des résultats doubles et devez ensuite diviser par 2 - inutile.

C'est O(N) pour la création du hashmap lors de la lecture des valeurs et O(N) lors de l'itération, c'est-à-dire O(N) et environ 8loc en python (et c'est correct, je viens de le résoudre ;-) )