Структура данных Java для обработки 2D точек, массивов, списков или других? - PullRequest
Новая
       29

Структура данных Java для обработки 2D точек, массивов, списков или других?

0 голосов
/ 24 апреля 2011

Я разработчик Ruby, благодаря платформе Android я дам Java шанс.

У меня есть набор 2D точек [p1, p2, p3, p4 ... p10], я хочу изменить порядок набора, отсортированный по возрастанию по значениям x точек. В Ruby я бы сделал что-то вроде этого: 

points.sort! {|a,b| a.x <=> b.x}

Я хочу иметь возможность вставлять в набор новые точки, между существующими, в Ruby: 

points.insert(3, point)

Какая лучшая практика Java для этого?

Должны ли точки храниться в массиве, и механизм сортировки и вставки, разработанный мной?

Или уже существует структура для этой цели? (который для упрощения вставки других элементов между существующими и сортировки элементов по их свойствам)

Я знаю, что в Интернете существует множество ресурсов Java, но мне хотелось бы узнать мнение людей, которые занимаются подобными проблемами.

Ответы [ 2 ]

2 голосов
/ 24 апреля 2011

Это зависит от ваших потребностей в производительности. Для вашего использования вы можете перейти к реализации SortedSet, такой как TreeSet , и написать Comparator для своего класса Point (или для существующего, такого как Point2D * 1007). *) сортирует по значению элемента x Это позволит вам вставлять и извлекать элементы в O(log(n)).

Обратите внимание, что если вы делаете много вставок, вы не должны использовать Array, потому что n вставок в середине Array имеет стоимость n^2. Если вы просматриваете данные намного больше, чем обновляете, то может иметь смысл Array.

2 голосов
/ 24 апреля 2011

Есть целые книги, посвященные вашему вопросу (структурам данных), однако я постараюсь сделать это проще. Есть много МНОГИХ вариантов, таких как сортировка кучи, сортировка с сортировкой, сортировка слиянием, двоичные деревья и т. Д., Но вместо изучения этих методов я бы предложил простые встроенные функции.

Arrays.sort (в год) ; Сортирует элементы массива примитивного типа в порядке возрастания, используя их естественный порядок.

Arrays.sort (pa, from, to); Сортирует элементы pa [from] ... pa [to-1] примитивного типа. в порядке возрастания.

Arrays.sort (oa); Сортирует элементы массива типа объекта в порядке возрастания, используя порядок, определенный интерфейсом Comparable, который определяет метод CompareTo. Обратите внимание, что многие классы Java, такие как String (но не StringBuffer), Double, BigInteger и т. Д. Реализуют Comparable.

Arrays.sort (oa, from, to); Сортирует элементы массива в диапазоне от ... до типа объекта в порядке возрастания.

Arrays.sort (oa, comp) ; Сортирует элементы массива типа объекта в порядке возрастания, используя Comparator comp.

Arrays.sort (oa, from, to, comp); Сортирует элементы массива в диапазоне от ... до типа объекта в порядке возрастания с использованием Comparator comp. 

import java.util.Arrays;

public class Dblsrt {
    //========================================================= main
    public static void main(String[] args) {
        //... 1. Sort strings - or any other Comparable objects.
        String[] names = {"Zoe", "Alison", "David"};
        Arrays.sort(names);
        System.out.println(Arrays.toString(names));

        //... 2. Sort doubles or other primitives.
        double[] lengths = {120.0, 0.5, 0.0, 999.0, 77.3};
        Arrays.sort(lengths);
        System.out.println(Arrays.toString(lengths));
    }
}

Выход: 

[Alison, David, Zoe]
[0.0, 0.5, 77.3, 120.0, 999.0]

Комплименты от http://www.leepoint.net/notes-java/data/arrays/70sorting.html

Для более детального просмотра http://www.theparticle.com/javadata2.html

...