Сортировка огромного списка массивов (ArrayList <Class>) на основе значений членов класса в Java - PullRequest
Новая
       11

Сортировка огромного списка массивов (ArrayList <Class>) на основе значений членов класса в Java

0 голосов
/ 05 декабря 2011

Есть две подзадачи.

1- Сравнение двух огромных массивов

2- Сортировка элементов массива по значениям его объекта для достижения (1).

У меня есть ArrayList объектов класса. т.е. 

Class X
{
    double x;
    double y;
    int sortVal;
}

ArrayList<X> alX = new ArrayList<X>(); //size = 10,000
ArrayList<Integer> myValue = new ArrayList<Integer>(); //size = 15

Я хочу проверить, присутствует ли myValue в sortVal. 

X ob = new X();
for(i=0;i<myValue.size();i++)
{
   for(j=0;j<alX.size();j++)
   {  
      ob = alX.get(j)
      **if (myValues.get(i) == ob.sortVal)**
   }
}

Поскольку размер массива 'alX' огромен, он занимает много времени на вычисления.

Я думал, что лучшим способом будет сортировка элементов ArrayList alX на основе значений sortVal класса X. С помощью сортировки, когда sortVal больше myValue, я могу выйти из цикла.

1) как можно отсортировать элементы массива alX на основе значения sortVal.

2) Есть ли лучший подход, чем сортировка массива, для сравнения двух значений. т.е. (myValues.get (i) == alX.ob.sortVal)

[править] Учитывайте значения, 

ArrayList<X>:
x      : 1,1,1,2,3,5,4,5
y      : 2,4,6,4,4,6,2,1
sortVal: 10,20,30,10,10,20,30

ArrayList<Integer>:
myValue: 10,20,30

Ответы [ 4 ]

3 голосов
/ 05 декабря 2011

Вы можете создать Map<Integer, X>, если значения sortVal являются уникальными, или Map<Integer, Lists<X>>, если они не являются.Это имеет временную сложность O (n) или O (n * log n), что является стоимостью выполнения сортировки.

РЕДАКТИРОВАТЬ: Это создает MultiMap ключей и набор объектовдля этого ключа за один проход. 

List<X> xs = ...
Map<Integer, Set<X>> mapBySortVal = new LinkedHashMap<>();
for(X x: xs) {
   Set<X> set = mapBySortVal.get(x.sortVal);
   if (set == null)
      mapBySortVal.put(x.sortVal, set = new LinkedHashSet<>());
   set.add(x);
}

for(Integer value: myValues) {
   Set<X> xs = mapBySortVal.get(value);
   if (xs != null) 
       // found some.
}
2 голосов
/ 05 декабря 2011

По первому вопросу вы можете отсортировать коллекцию по любому поводу, указав Comparator, которую следует использовать (см. Collections#sort)

Поскольку вы назвали свое поле sortVal, я думаю, что экземпляры этого класса могут быть отсортированы по этому значению, и вы можете захотеть реализовать интерфейс Comparable для этого класса. Таким образом, вы можете использовать Collections#sort без указания Comparator

0 голосов
/ 05 декабря 2011

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

ИЛИ

Сортировка с использованием компаратора.Это займет больше времени.

Просто посмотрите на их документы для объяснения.

0 голосов
/ 05 декабря 2011

Google гуава получает очень полезные функции.Для заказа массивов предусмотрено com.google.common.collect.Ordering<T>.

Например: 

Ordering<String> byLengthOrdering = new Ordering<String>() {
 public int compare(String left, String right) {
   return Ints.compare(left.length(), right.length());
 }
};
List<String> sorted = byLengthOrdering.reverse().sortedCopy(sourceList);
...