peut améliorer cet algorithme pour optimiser le temps de fonctionnement (trouver des points dans les segments)

Question

on me donne 2 Intégrales, le premier est le nombre de segments (Xi, Xj) et le second est le nombre de points qui peuvent ou ne peux pas être à l'intérieur de ces segments.

A titre d'exemple, l'entrée peut être:

2 3 
0 5 
8 10 
1 6 11 

Lorsque, dans la première ligne, 2 signifie "2 segments" et 3 signifie "3 points". Les 2 segments sont "0 à 5" et "8 à 10", et les points à rechercher sont 1, 6, 11. Le signal de sortie est

1 0 0 

Lorsque le point 1 se trouve dans le segment « 0 à 5 ", et les points 6 et 11 ne sont dans aucun segment. Si un point apparaît dans plus d'un segment, comme un 3, la sortie serait 2.

Le code d'origine, était juste une double boucle pour rechercher des points entre les segments. Je le Java Arrays tri rapide (modifié de façon quand il trie les points d'extrémité de segments, trie également startpoints commencent alors [i] et à la fin [i] appartiennent au même segment i) pour améliorer la vitesse de la double boucle mais il nest pas assez important.

Le code suivant fonctionne très bien, mais quand il y a trop de segments qui est très lent:

public class PointsAndSegments { 

    private static int[] fastCountSegments(int[] starts, int[] ends, int[] points) { 
     sort(starts, ends); 
     int[] cnt2 = CountSegments(starts,ends,points); 
     return cnt2; 
    } 

    private static void dualPivotQuicksort(int[] a, int[] b, int left,int right, int div) { 
    int len = right - left; 
    if (len < 27) { // insertion sort for tiny array 
     for (int i = left + 1; i <= right; i++) { 
      for (int j = i; j > left && b[j] < b[j - 1]; j--) { 
       swap(a, b, j, j - 1); 
      } 
     } 
     return; 
    } 
    int third = len/div; 
    // "medians" 
    int m1 = left + third; 
    int m2 = right - third; 
    if (m1 <= left) { 
     m1 = left + 1; 
    } 
    if (m2 >= right) { 
     m2 = right - 1; 
    } 
    if (a[m1] < a[m2]) { 
     swap(a, b, m1, left); 
     swap(a, b, m2, right); 
    } 
    else { 
     swap(a, b, m1, right); 
     swap(a, b, m2, left); 
    } 
    // pivots 
    int pivot1 = b[left]; 
    int pivot2 = b[right]; 
    // pointers 
    int less = left + 1; 
    int great = right - 1; 
    // sorting 
    for (int k = less; k <= great; k++) { 
     if (b[k] < pivot1) { 
      swap(a, b, k, less++); 
     } 
     else if (b[k] > pivot2) { 
      while (k < great && b[great] > pivot2) { 
       great--; 
      } 
      swap(a, b, k, great--); 
      if (b[k] < pivot1) { 
       swap(a, b, k, less++); 
      } 
     } 
    } 
    // swaps 
    int dist = great - less; 
    if (dist < 13) { 
     div++; 
    } 
    swap(a, b, less - 1, left); 
    swap(a, b, great + 1, right); 
    // subarrays 
    dualPivotQuicksort(a, b, left, less - 2, div); 
    dualPivotQuicksort(a, b, great + 2, right, div); 

    // equal elements 
    if (dist > len - 13 && pivot1 != pivot2) { 
     for (int k = less; k <= great; k++) { 
      if (b[k] == pivot1) { 
       swap(a, b, k, less++); 
      } 
      else if (b[k] == pivot2) { 
       swap(a, b, k, great--); 
       if (b[k] == pivot1) { 
        swap(a, b, k, less++); 
       } 
      } 
     } 
    } 
    // subarray 
    if (pivot1 < pivot2) { 
     dualPivotQuicksort(a, b, less, great, div); 
    } 
    } 

    public static void sort(int[] a, int[] b) { 
     sort(a, b, 0, b.length); 
    } 

    public static void sort(int[] a, int[] b, int fromIndex, int toIndex) { 
     rangeCheck(a.length, fromIndex, toIndex); 
     dualPivotQuicksort(a, b, fromIndex, toIndex - 1, 3); 
    } 

    private static void rangeCheck(int length, int fromIndex, int toIndex) { 
     if (fromIndex > toIndex) { 
      throw new IllegalArgumentException("fromIndex > toIndex"); 
     } 
     if (fromIndex < 0) { 
      throw new ArrayIndexOutOfBoundsException(fromIndex); 
     } 
     if (toIndex > length) { 
      throw new ArrayIndexOutOfBoundsException(toIndex); 
     } 
    } 

    private static void swap(int[] a, int[] b, int i, int j) { 
     int swap1 = a[i]; 
     int swap2 = b[i]; 
     a[i] = a[j]; 
     b[i] = b[j]; 
     a[j] = swap1; 
     b[j] = swap2; 
    } 

    private static int[] naiveCountSegments(int[] starts, int[] ends, int[] points) { 
     int[] cnt = new int[points.length]; 
     for (int i = 0; i < points.length; i++) { 
      for (int j = 0; j < starts.length; j++) { 
       if (starts[j] <= points[i] && points[i] <= ends[j]) { 
        cnt[i]++; 
       } 
      } 
     } 
     return cnt; 
    } 

    public static void main(String[] args) { 
     Scanner scanner = new Scanner(System.in); 
     int n, m; 
     n = scanner.nextInt(); 
     m = scanner.nextInt(); 
     int[] starts = new int[n]; 
     int[] ends = new int[n]; 
     int[] points = new int[m]; 
     for (int i = 0; i < n; i++) { 
      starts[i] = scanner.nextInt(); 
      ends[i] = scanner.nextInt(); 
     } 
     for (int i = 0; i < m; i++) { 
      points[i] = scanner.nextInt(); 
     } 
     //use fastCountSegments 
     int[] cnt = fastCountSegments(starts, ends, points); 
     for (int x : cnt) { 
      System.out.print(x + " "); 
     } 
    } 

Je crois que le problème est dans la méthode CountSegments() mais je ne suis pas sûr d'une autre façon de le résoudre . Supposément, je devrais utiliser un algorithme de division et de conquête, mais après 4 jours, je suis à la hauteur de n'importe quelle solution. J'ai trouvé a similar problem in CodeForces mais la sortie est différente et la plupart des solutions sont en C++. Depuis que j'ai 3 mois que j'ai commencé à apprendre Java, je pense que j'ai atteint ma limite de connaissances.

Answer 1

Cet article est une implémentation similaire à @ l'idée de Shole:

public class SegmentsAlgorithm { 

    private PriorityQueue<int[]> remainSegments = new PriorityQueue<>((o0, o1) -> Integer.compare(o0[0], o1[0])); 
    private SegmentWeight[] arraySegments; 

    public void addSegment(int begin, int end) { 
     remainSegments.add(new int[]{begin, end}); 
    } 

    public void prepareArrayCache() { 
     List<SegmentWeight> preCalculate = new ArrayList<>(); 
     PriorityQueue<int[]> currentSegmentsByEnds = new PriorityQueue<>((o0, o1) -> Integer.compare(o0[1], o1[1])); 
     int begin = remainSegments.peek()[0]; 
     while (!remainSegments.isEmpty() && remainSegments.peek()[0] == begin) { 
      currentSegmentsByEnds.add(remainSegments.poll()); 
     } 
     preCalculate.add(new SegmentWeight(begin, currentSegmentsByEnds.size())); 
     int next; 
     while (!remainSegments.isEmpty()) { 
      if (currentSegmentsByEnds.isEmpty()) { 
       next = remainSegments.peek()[0]; 
      } else { 
       next = Math.min(currentSegmentsByEnds.peek()[1], remainSegments.peek()[0]); 
      } 
      while (!currentSegmentsByEnds.isEmpty() && currentSegmentsByEnds.peek()[1] == next) { 
       currentSegmentsByEnds.poll(); 
      } 
      while (!remainSegments.isEmpty() && remainSegments.peek()[0] == next) { 
       currentSegmentsByEnds.add(remainSegments.poll()); 
      } 
      preCalculate.add(new SegmentWeight(next, currentSegmentsByEnds.size())); 
     } 
     while (!currentSegmentsByEnds.isEmpty()) { 
      next = currentSegmentsByEnds.peek()[1]; 
      while (!currentSegmentsByEnds.isEmpty() && currentSegmentsByEnds.peek()[1] == next) { 
       currentSegmentsByEnds.poll(); 
      } 
      preCalculate.add(new SegmentWeight(next, currentSegmentsByEnds.size())); 
     } 
     SegmentWeight[] arraySearch = new SegmentWeight[preCalculate.size()]; 
     int i = 0; 
     for (SegmentWeight l : preCalculate) { 
      arraySearch[i++] = l; 
     } 
     this.arraySegments = arraySearch; 
    } 

    public int searchPoint(int p) { 
     int result = 0; 
     if (arraySegments != null && arraySegments.length > 0 && arraySegments[0].begin <= p) { 
      int index = Arrays.binarySearch(arraySegments, new SegmentWeight(p, 0), (o0, o1) -> Integer.compare(o0.begin, o1.begin)); 
      if (index < 0){ // Bug fixed 
       index = - 2 - index; 
      } 
      if (index >= 0 && index < arraySegments.length) { // Protection added 
       result = arraySegments[index].weight; 
      } 
     } 
     return result; 
    } 

    public static void main(String[] args) { 
     SegmentsAlgorithm algorithm = new SegmentsAlgorithm(); 
     int[][] segments = {{0, 5},{3, 10},{8, 9},{14, 20},{12, 28}}; 
     for (int[] segment : segments) { 
      algorithm.addSegment(segment[0], segment[1]); 
     } 
     algorithm.prepareArrayCache(); 

     int[] points = {-1, 2, 4, 6, 11, 28}; 

     for (int point: points) { 
      System.out.println(point + ": " + algorithm.searchPoint(point)); 
     } 
    } 

    public static class SegmentWeight { 

     int begin; 
     int weight; 

     public SegmentWeight(int begin, int weight) { 
      this.begin = begin; 
      this.weight = weight; 
     } 
    } 
} 

Il imprime:

-1: 0 
2: 1 
4: 2 
6: 1 
11: 2 
28: 0 

ÉDITÉE:

public static void main(String[] args) { 
    SegmentsAlgorithm algorithm = new SegmentsAlgorithm(); 
    Scanner scanner = new Scanner(System.in); 
    int n = scanner.nextInt(); 
    int m = scanner.nextInt(); 
    for (int i = 0; i < n; i++) { 
     algorithm.addSegment(scanner.nextInt(), scanner.nextInt()); 
    } 
    algorithm.prepareArrayCache(); 
    for (int i = 0; i < m; i++) { 
     System.out.print(algorithm.searchPoint(scanner.nextInt())+ " "); 
    } 
    System.out.println(); 
} 

Answer 2

Compte tenu des contraintes de l'OP, nous allons n être le nombre de segments, m le nombre de points à la requête, où n,m < = 5 * 10^4, je peux trouver une solution O(nlg(n) + mlg(n)) (qui devrait être assez pour passer le plus juge en ligne)

Comme chaque requête est un problème de vérification: le point peut être couvert par certains intervalles, oui ou non, on n'a pas besoin pour trouver/combien de intervalles le point a été couvert.

Aperçu de l'algorithme:

1. Trier tous les premiers intervalles par le point de départ, si égalité, par la longueur (point de fin extrême droite)
2. Essayez de fusionner les intervalles pour obtenir des disjoints intervalles qui se chevauchent. Par exemple (0,5), (2,9), (3,7), (3,5), (12,15), vous obtiendrez (0,9), (12,15). Comme les intervalles sont classés, cela peut être fait avec avidité O(n)
3. sont au-dessus du précalcul, maintenant chaque point, nous nous interrogeons sur l'aide des intervalles disjoints.Il suffit de recherche binaire si un intervalle contient tel point, chaque requête est O(lg(n)) et nous avons obtenu m points, donc au total O(m lg(n))

Combiner l'algorithme entier, nous obtenons un algorithme O(nlg(n) + mlg(n))