#java #arraylist
#java #массивный список
Вопрос:
Ребята, у меня есть массивный список, который содержит около 3000 двойных значений.
Мне в основном нужны упорядоченные индексы 100 лучших двойников в массив-списке. Меня интересуют не фактические значения 100 лучших, а только их индексы в порядке от максимума к минимуму.
Например, если наибольшими значениями (от max до min) в списке массивов являются index50, index27 и index96, то я сопоставляю только с 50, 27, 96 в этом точном порядке.
Код для массива-списка:
ArrayList<Double> ids = new ArrayList<Double>();
Результирующий набор или список индексов может содержаться в ЛЮБОЙ структуре данных, которая поддерживает порядок 50, 27, 96, такой как ArrayList или любой другой тип коллекции.
В итоге:
Как мне вернуть номера индексов с наибольшими 100 значениями (double) в ArrayList?
Любая помощь приветствуется, ребята,
Комментарии:
1. Уникальны ли двойные значения? Если нет, то как вы можете указать, какой индекс имеет большее значение для двух одинаковых чисел?
2. Да, он содержит повторяющиеся значения. Повторения должны быть возвращены в любом порядке. Например, если ВСЕ элементы содержат 1.0, то они возвращаются в любом порядке. Приветствия….
3. Вау, пока что три ответа полностью игнорируют часть о необходимости использования индексов вместо значений. : (
Ответ №1:
import java.util.*;
После всех этих разговоров об O (thing) для сортировки я подумал, что должен показать, что на самом деле сортировка по вставке является лучшей в этом случае. Приведенный ниже код показывает различные предложения с этой страницы и мои собственные идеи. Относительные характеристики:
Сортировка вставки: 61 480n
Сортировка объектов: 1 147 538 узлов
Отсортированное множество: 671 007ns
Ограниченный набор: 435 130ns
public class DoubleIndexSort {
static class DI implements Comparable<DI> {
final int index;
final double val;
DI(double v, int i) {
val = v;
index = i;
}
public int compareTo(DI other) {
if (val < other.val) {
return 1;
} else if (val == other.val) {
return 0;
}
return -1;
}
}
public static void checkResult(double[] test, int[] indexes) {
for(int i = 0;i < indexes.length;i ) {
int ii = indexes[i];
double iv = test[ii];
// System.out.println("Checking " i " -> " ii " = " iv);
for(int j = 0;j < test.length;j ) {
// System.out.println(j " -> " test[j]);
if (j != ii amp;amp; test[j] > iv) throw new RuntimeException();
}
test[ii] = -1;
}
}
public static int[] getHighestIndexes(double[] data, int topN) {
if (data.length <= topN) {
return sequence(topN);
}
int[] bestIndex = new int[topN];
double[] bestVals = new double[topN];
bestIndex[0] = 0;
bestVals[0] = data[0];
for(int i = 1;i < topN;i ) {
int j = i;
while( (j > 0) amp;amp; (bestVals[j - 1] < data[i]) ) {
bestIndex[j] = bestIndex[j - 1];
bestVals[j] = bestVals[j - 1];
j--;
}
bestVals[j] = data[i];
bestIndex[j] = i;
}
for(int i = topN;i < data.length;i ) {
if (bestVals[topN - 1] < data[i]) {
int j = topN - 1;
while( (j > 0) amp;amp; (bestVals[j - 1] < data[i]) ) {
bestIndex[j] = bestIndex[j - 1];
bestVals[j] = bestVals[j - 1];
j--;
}
bestVals[j] = data[i];
bestIndex[j] = i;
}
}
return bestIndex;
}
public static int[] getHighestIndexes2(double[] data, int topN) {
if (data.length <= topN) {
return sequence(topN);
}
DI[] di = new DI[data.length];
for(int i = 0;i < data.length;i ) {
di[i] = new DI(data[i], i);
}
Arrays.sort(di);
int[] res = new int[topN];
for(int i = 0;i < topN;i ) {
res[i] = di[i].index;
}
return res;
}
public static int[] getHighestIndexes3(double[] data, int topN) {
if (data.length <= topN) {
return sequence(topN);
}
SortedSet<DI> set = new TreeSet<DI>();
for(int i=0;i<data.length;i ) {
set.add(new DI(data[i],i));
}
Iterator<DI> iter = set.iterator();
int[] res = new int[topN];
for(int i = 0;i < topN;i ) {
res[i] = iter.next().index;
}
return res;
}
public static int[] getHighestIndexes4(double[] data, int topN) {
if (data.length <= topN) {
return sequence(topN);
}
SortedSet<DI> set = new TreeSet<DI>();
for(int i=0;i<data.length;i ) {
set.add(new DI(data[i],i));
if( set.size() > topN ) {
set.remove(set.last());
}
}
Iterator<DI> iter = set.iterator();
int[] res = new int[topN];
for(int i = 0;i < topN;i ) {
res[i] = iter.next().index;
}
return res;
}
/**
* @param args
*/
public static void main(String[] args) {
long elap1 = 0;
long elap2 = 0;
long elap3 = 0;
long elap4 = 0;
for(int i = 1;i <= 1000;i ) {
double[] data = testData();
long now = System.nanoTime();
int[] inds = getHighestIndexes(data, 100);
elap1 = System.nanoTime() - now;
checkResult(data, inds);
System.out.println("nInsert sort: " (elap1 / i));
now = System.nanoTime();
inds = getHighestIndexes2(data, 100);
elap2 = System.nanoTime() - now;
checkResult(data, inds);
System.out.println("Object sort: " (elap2 / i));
now = System.nanoTime();
inds = getHighestIndexes3(data, 100);
elap3 = System.nanoTime() - now;
checkResult(data, inds);
System.out.println("Sorted set: " (elap3 / i));
now = System.nanoTime();
inds = getHighestIndexes4(data, 100);
elap4 = System.nanoTime() - now;
checkResult(data, inds);
System.out.println("Limited set: " (elap4 / i));
}
}
private static int[] sequence(int n) {
int[] indexes = new int[n];
for(int i = 0;i < n;i ) {
indexes[i] = i;
}
return indexes;
}
public static double[] testData() {
double[] test = new double[3000];
for(int i = 0;i < test.length;i ) {
test[i] = Math.random();
}
return test;
}
}
Комментарии:
1. Порядок выполнения является только одним фактором при принятии решения.
getHighestIndexes()намного сложнее, чем некоторые из более медленных решений, требующие больше времени для написания и тестирования. А поскольку время разработчика дороже процессорного, это огромная часть. Кстати,getHighestIndexes()сбой для списков из 100 или менее значений.
Ответ №2:
Я предполагаю, что сортировка вставки выполняется за O (n ^ 2) времени. Используйте сортировку кучи, которая выполняется за O (nlog (n)) время. Используйте минимальную кучу из 100 узлов. Когда вы выполняете итерацию по вашему списку, сравните значение с корнем. Если он больше, замените корневой каталог и запустите алгоритм heapify.
После того, как вы закончите со всеми элементами, ваша куча будет содержать 100 лучших элементов.
Использование правильной структуры данных для кучи позволит вам сохранить индексы вместе со значением.
Примером может быть
class MinHeapNode
{
public int value;
public int index;
public MinHeapNode left;
public MinHeapNode right;
}
Ответ №3:
Я бы сказал, что если вам нужны только 100 лучших значений, почему бы не использовать инвертированную сортировку выборки, которая отсекается после 100 итераций? Сортировка выбора гарантирует, что одно значение будет помещено в правильную позицию при каждом проходе, поэтому после 100 прохождений по списку верхними значениями должно быть то, которое вы хотите. Я уверен, что существует более элегантное решение, но оно должно быть простым в реализации.
Комментарии:
1. О, я пропустил индексную часть вопроса.
2. по-видимому, OP также сделал это 😉
Ответ №4:
Вы можете добавить все пары значение (как ключ) индекс (как значение) в TreeMap (или другие SortedMap карты) SortedMap.values , возвращающие значения (т. Е. индексы) в отсортированном порядке.
Редактировать: это не сработает, если в вашем списке есть дубликаты, так как второй put перезапишет ранее сохраненное значение (индекс). Итак, следующее кажется лучше:
Создайте пары index и value, добавьте их в SortedSet (как предложено StKiller ниже), используя компаратор, который сортирует по значению, а затем по индексу (чтобы быть совместимым с equals, как указано в документе API-doc). Затем просто возьмите первые 100 пар, или, скорее, индексы, хранящиеся в них.
Правка 2: На самом деле, вам действительно не нужны пары, вы можете использовать компаратор для индексов для поиска значений…
Комментарии:
1. Не лучше ли использовать TreeSet ? Он использует одно и то же дерево для сортировки и хранит только уникальные значения.
2. Я почти уверен, что DJDonna хочет сохранить повторяющиеся значения.
3. Набор будет содержать только значения, но DJDonaL3000 ищет значения … но, вы напомнили мне, что TreeMap не помогает, если некоторые значения совпадают.
Ответ №5:
Используйте сортировку по вставке. Это можно сделать в O (n ^ 2). Поддерживайте список, содержащий 100 лучших значений из имеющегося у вас массива. Просмотрите имеющийся у вас массив-список и используйте сортировку по вставке, чтобы поместить верхние элементы в новый массив-список.
Комментарии:
1. Сортировка по вставке выполняется O (n) только тогда, когда список уже отсортирован в правильном порядке. В общем случае это O (n ^ 2), хотя вы могли бы использовать двоичный поиск при выполнении вставки, чтобы сделать это O (n log n). В любом случае, это приведет только к 100 наибольшим значениям, а не к индексам, которые нужны DJDonaL3000.
2. @David Harkness, я понял это и внес изменения. Спасибо, что указали на это.
Ответ №6:
На языке, подобном scala, вы могли бы просто использовать zipWithIndex , sortWith , take (n) и map :
val ids = List (2.0, 2.5, 1.5, 0.5, 7.5, 7.0, 1.0, 8.0, 4.0, 1.0);
ids.zipWithIndex.sortWith ((x, y) => (x._1 > y._1)).take (3).map (vi => vi._2)
res65: List[Int] = List(7, 4, 5)
Однако в Java вам придется выполнять больше шаблонного кода, если вызов scala (который на 100% совместим с java) невозможен.
Однако почти такое же простое решение могло бы быть возможно с функциональной java (см. API, список).