найти N наибольших элементов в массиве

[makc]

без полной сортировки, какие есть способы? кто подскажет?

[Michael Antipin]

Что-то известно про состав и способ наполнения массива?

--
Michael Antipin

[Michael Antipin]

Вообще вполне можно сортировать каким-то аолгоритмом, прервав
сортировку после N элементов. Пузырьком сортируй N раз -- вот и
результат. :)

--
Michael Antipin

[Daniil Tutubalin]

Вроде такую задачу тут в рассылке уже решали.

Увы, не помню, что у Дональда Кнута было по этому поводу.

[Yuri Zhloba]

Задача академическая или есть практическая надобность такое сделать?

Если академическая, то читать источники по алгоритмам и структурам данных.

Если практическая -- то не париться, а отсортировать массив и взять N
первых элементов. Если важно сохранить изначальную позицию элементов в
массиве, то клонировать массив и сортировать клон.

[Daniil Tutubalin]

О, Михаил хорошую идею подсказывает.

Если мой сонный мозг не врёт, то пирамидальная сортировка хорошо подойдёт. 

С одной стороны трудоёмкость эн-логарифм-эн, с другой стороны выдёргивает элементы один за другим именно в порядке увеличения/уменьшения.

Так что просто прекратить на нужном этапе - и вуаля.

Правда, определённый оверхед будет всё равно.

http://ru.wikipedia.org/wiki/Пирамидальная_сортировка

[kutu]

1. создаем новый массив
2. начинаем проходить исходный массив
3. если длина нового массива меньше чем нужно, то добавляем текущий
элемент в такое место, чтобы новый массив был по возрастанию
4. если длина массива нужная и первый элемент из массива меньше
текущего элемента, то первый элемент удаляем, а текущий элемент
вставляем как в пункте 3.

[Moonlight]

Где-то так:
var a:Array = [14, 8, 7, 7, 3, 0, 13, 2, 9];
var n:int = 3;

// sorted array of max n elements
var max:Array = [];

for (var i:int = 0; i < a.length; i++) {
if (max.length < n || a[i] > max[0]) {
// look for index to insert
var j:int = max.length < n ? 0 : 1;
while (j < max.length && max[j] < a[i]) {
j++;
}

// adding element into sorted array
if (j == max.length && j < n) {
max[j] = a[i];
} else {
max.splice(j, 0, a[i]);
if (max.length > n) {
max.splice(0, 1);
}
}
}
}

Если коротко: создаем структуру "сортированный список", в которой
будем хранить текущий список N максимальных элементов. Проходимся по
нашему масиву и добавляем элемент в сортированый список, если длинна
списка < n или если текущий элемент больше минимального в списке.

[Vadim Nikolaev]

Можно вообще без сортировок, если не пугает что промежуточный массив будет длиной с максимальное количество элементов

private function getMaxElementsLength($arr : Array) : Array

{

var maxArr : Array = [];

for (var i : int = 0; i < $arr.length; i++) {

var elementsArr : Array = maxArr[$arr[i]];

if(elementsArr == null) {

elementsArr = [];

}

elementsArr.push($arr[i]);

maxArr[$arr[i]] = elementsArr;

}

trace(" maxElementsArray = "+ maxArr[maxArr.length-1]);

                        //maxElementsArray = 100500,100500,100500,100500

return maxArr[maxArr.length-1];

}

var arr : Array = [1,2,3,4,9,5,1,100500,5,100500,5,4,1,9,100500,8,6,5,1,7,1,3,1,2,1,9,100500];

trace( getMaxElementsLength(arr).length); // 4

 

--
Vadim Nikolaev
Flash Developer

Company: Alawar
Gmail: Cema...@gmail.com
Skype: CemaprJl
Cell Phone: +7 923 186 6633

[Daniil Tutubalin]

> добавляем текущий элемент в такое место

> первый элемент удаляем, а текущий элемент вставляем 

Вы тоже считаете, что операции "вставить элемент" и "удалить элемент" имеют константную трудоёмкость, которая никак не зависит от длины массива?

[makc]

> способ наполнения массива?
увы, при наполнении массива элементы часто переписываются

> Если академическая, то читать источники по алгоритмам и структурам данных.

ближайшее, что нашёл - http://en.wikipedia.org/wiki/Selection_algorithm
- но оно не совсем то

> Если практическая -- то не париться, а отсортировать массив

не очень удобно, т.к. массив как бы пул, в конце м.б. куча элементов,
которые не нужно учитывать

остальные ответы ещё почитаю, спасибо

[Daniil Tutubalin]

@Moonlight

> Где-то так:

При полностью отсортированном массиве ( var a:Array = [1, 2, 3, 4, 5, 6, 7, 8, 9]; ) работает очень неоптимально.

[Flop Serg]

Кто нить знает что такое max-heap???
я думаю куча идеально для нахождения этих самых N элементов
кучу эту ограничить N Элементами а все что не влазит

>> Если практическая -- то не париться, а отсортировать массив
> не очень удобно, т.к. массив как бы пул, в конце м.б. куча элементов,
> которые не нужно учитывать

А если у тебя массив - пул
то сразу же переписывай и ввесто массива юзай кучу
и сортировать не придется берешь себе с верху кучи N нужных элементов

[Moonlight]

Для сохранения сортированого списка можно использовать вместо обычного
масива - двусвязный список (аналог list в библиотеке STL С++). Тогда
добавление\удаление из него элементов будет очень быстрым, но займет
больше памяти.
Когда писал пример - лень было его описывать :)

[Moonlight]

Ещё решение - N раз пройтись по масиву в поисках i-го по величине
элемента.

[Michael Antipin]

> Ещё решение - N раз пройтись по масиву в поисках i-го по величине
> элемента.

Я там сверху, в третьем сообщении, об этом написал, назвав это пузырьком. :)
А вообще сортировать никто не просил, так что все сводится к пробегам
со сравнениями _без перестановок_. Просили же только _найти_, зачем
сортировать?

N раз пробежатся по массиву, отыскивая наибольший элемент.
Это можно реализовать за полторы минуты.
Если под пивом -- то за десять (дебаг затягивается).
Что тут еще обсуждать? :)

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

--
Michael Antipin

[makc]

> >> Если практическая -- то не париться, а отсортировать массив
> > не очень удобно, т.к. массив как бы пул, в конце м.б. куча элементов,
> > которые не нужно учитывать
>
> А если у тебя массив - пул
> то сразу же переписывай и ввесто массива юзай кучу
> и сортировать не придется берешь себе с верху кучи N нужных элементов

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

если интересно, вообще речь идёт о нахождении N длиннейших сторон в
выпуклой оболочке (ух ты ж термин, не знал что оно так на русском)

[makc]

> N раз пробежатся по массиву, отыскивая наибольший элемент.
> Это можно реализовать за полторы минуты.
> Если под пивом -- то за десять (дебаг затягивается).
> Что тут еще обсуждать? :)

ну так и сделал сначала, но мало ли, вдруг магическим образом можно
сделать за один проход, "а пацаны-то и не знают"... решил спросить.

[Daniil Tutubalin]

Чудесная картинка на которой один за другим появляются элементы в порядке убывания начиная с максимального:

http://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif

Трудоёмкость нахождения одного такого элемента пропорционально логарифму N по основанию 2, что очень быстро.

[makc]

> Чудесная картинка на которой один за другим появляются элементы в порядке
> убывания начиная с максимального:

я помню, это из твоей ссылки про пирамидальную сортировку, но там ещё
подготовительный этап ;) и в статье прямо пишут:

> Недостатки: Сложен в реализации.

[Daniil Tutubalin]

Подготовительный этап n*log n, то есть почти однопроходный.

Сложность в реализации сильно преувеличена. Самая сложная часть - разобраться с индексами, потому что бинарное дерево довольно хитро размазывается по массиву.

Во всём остальном не намного сложнее пузырька.

[Flop Serg]

> мне немножко стыдно, но я не знаю, что такое куча :( судя по тексту,
> имеется ввиду изначально вставлять в порядке убывания/возрастания, но
> я уже отписался что это не хороший вариант, т.к. при заполнении
> элементы часто перезаписываются (т.е. используется их первоначальный
> порядок).

Ну да куча это такой _сортированный_ особо упорядоченный массив

Ну если уж тебе так надо сохранить этот исходный массив то юзай
паралельно и массив и кучу
потеряешь немного памяти и пару миллисекунд на вставке/удалении/изменении
зато всегда есть Н наибольших элементов
а если у тебя всетаки во много раз чаще происходят изменения в этом
массиве чем возникает необходимость поиска
то оставляй как сделал

[Flop Serg]

> я помню, это из твоей ссылки про пирамидальную сортировку, но там ещё
> подготовительный этап ;) и в статье прямо пишут:

Подготовительный этап это и есть построение кучи из массива
Если не будешь сбрасывать/удалять кучу, то нинидо никаких тебе
подготовительных операций
куча(массив/биннарное дерево) всегда есть и всегда упорядоченное (сортированное)

потери только на вставке/удалении/изменении но это быстро и не затратно