Сортировка: альтернатива HashMaps и множествам?

Question

Я пытаюсь создать бесплатный курс в Coursera под названием Algorithms, часть 1. В одном из заданий нас попросили разработать и алгоритм найти все наборы коллинеарных точек на графике. Вот ссылка на дополнительные спецификации:

https://coursera.cs.princeton.edu/algs4/assignments/collinear/specification.php.

В классе FastCollinearPoints нам предлагается реализовать следующий алгоритм:

Думайте о p как о начале координат.

Для каждой другой точки q определите наклон, который она делает с помощью p.

Сортируйте точки по наклонам, которые они делают с помощью p.

Проверьте, имеют ли 3 (или более) смежные точки в отсортированном порядке равные наклоны относительно p. Если это так, то эти точки вместе с p коллинеарны.

Вот часть класса, который я сделал:

    private ArrayList<LineSegment> segments = new ArrayList<>();
        private HashMap<Double, ArrayList<Point>> slopeEndPoints = new HashMap<>();

// finds all line segments containing 4 or more points
    public FastCollinearPoints(Point[] points) {
        if(points == null)
            throw new IllegalArgumentException("Null Argument: points");
        int N = points.length;
        Point[] pointsCopy = Arrays.copyOf(points, points.length);
        Arrays.parallelSort(pointsCopy);
        checkCornerCases(pointsCopy);

        for(int p = 0; p < N-3; p++) {
            Point[] ptsInRange = Arrays.copyOfRange(pointsCopy, p, N);
            Arrays.parallelSort(ptsInRange, ptsInRange[0].slopeOrder());
            int first = 1, last = 2;
            while(last < ptsInRange.length) {
                double slope = ptsInRange[0].slopeTo(ptsInRange[first]);
                while(last < ptsInRange.length 
                        && Double.compare(slope, ptsInRange[0].slopeTo(ptsInRange[last])) == 0)
                    last++;
                if(last - first > 2)
                    if(isSelected(slope, ptsInRange, last-1))
                        segments.add(new LineSegment(ptsInRange[0], ptsInRange[last-1]));
                first = last;
                last++;
            }
        }


    }

    private boolean isSelected(double slope, Point[] points, int end) {
            ArrayList<Point> selection = this.slopeEndPoints.get(slope);
            if(selection == null) {
                selection = new ArrayList<Point>();
                selection.add(points[end]);
                this.slopeEndPoints.put(slope, selection);
                return true;
            }
            else if(selection.contains(points[end]))
                return false;
            else {
                selection.add(selection.size(), points[end]);
                this.slopeEndPoints.put(slope, selection);
                return true;
            }

Когда я отправляю свой ответ, я получаю этот отзыв:

FastCollinearPoints. java: 9: 17: Не используйте тип данных 'HashMap' в этом назначении. Таблицы Ha sh еще не были введены в курс (и не будут соответствовать требованиям производительности в худшем случае). Вместо этого используйте сортировку. [Производительность]

Так что мне было интересно: что они имеют в виду под «сортировкой по использованию»? Могу ли я получить такой же эффект HashMap путем сортировки? Как?

Answer 1

Возможно, кто-то напишет здесь код для вас, и я твердо верю, что он не заставит вас учиться, поэтому давайте попробуем понять, что происходит в алгоритме.

Итак, есть две вещи (которые вы могли бы пояснить в вопросе), но давайте разберем их здесь -

1. Поиск всех наборов коллинеарных точек на графике

2. Для фиксированной точки P, реализующей алгоритм, который вы только что упомянули в вопросе.

Давайте сначала начнем с части 2: * Решение 1043 *, которое вы разместили, является излишним, вам вообще не нужно HashMaps.

Рассмотрим этот фрагмент:

// declare Point P

class Point {
  int x, y;       // 
  double slope;   // slope = y/x
}

double getSlope(Point a) {
  return (double)(a.y - P.y) / (a.x - P.x);
}

// declare list of points as List<Point> ptList

Collections.sort(ptList, new Comparator<Point>() {
  @Override
  public int compare(Point a, Point b) {
    return getSlope(a) < getSlope(b);
  }
});


for(int i = 1; i < ptList.length(); i++) {
    if(getSlope(ptList[i]) == getSlope(ptList[i - 1]) {
       // this means points i, i - 1 have equal slopes
    }
}

Это основано на том факте, что равные числа группируются после сортировки. Например, несортированный массив [0, 2, 1, 2, 0, 3, 1, 1] будет выглядеть так после сортировки [0, 0, 1, 1, 1, 2, 2, 3] и заметит, как равные элементы вместе.

Теперь часть 1: Нам нужно найти все такие наборы. Мы попытаемся сделать каждую точку в данном списке P, а остальные точки, которые еще не обработаны, как установлено Q. Используя описанную выше процедуру, мы можем разделить множества Q на коллинеарные множества.

Когда вы сделали это для всех P, все готово.

---

PS - Пожалуйста, не сравнивайте двойные значения напрямую, используя val1 == val2 из-за точности с плавающей запятой, это не удастся. Используйте пороговое сравнение, например absolute(val1 - val2) < 10^(-9)

Подробнее: https://howtodoinjava.com/java/basics/correctly-compare-float-double/