Найти значения K max из списка N

У меня есть требования - 1. Имеются случайные значения в списке/массиве, и мне нужно найти 3 значения max. 2. У меня есть пул значений, и каждый раз, когда этот пул обновляется, может появляться каждые 5 секунд. Теперь каждый раз после обновления мне нужно найти 3 максимальных значения из пула списков.Найти значения K max из списка N

Я думал об использовании Math.max трижды в списке, но я не думаю, что это очень оптимизированный подход. > Не любой механизм сортировки будет дорогостоящим, как я беспокоился только топ 3 максимальных значений, почему сортировать все эти

Пожалуйста, предложите лучший способ сделать это в JAVA

источник

2012-03-30 Abhishek Choudhary

При обновлении значения заменяются и удаляются или добавляются только? –

Возможны оба варианта –

Вы должны понимать, что «дорогостоящий» - относительный термин. Как программист вы всегда торгуете различными расходами. Стоимость сортировки - O (n log n). Это означает, что даже для очень больших коллекций стоимость сортировки списка не растет намного быстрее, чем просто перебирается через список.Некоторое быстрое тестирование показывает, что самый большой массив, который я могу сделать на моем ноутбуке, имеет размер примерно 2^27 и самый большой, который я могу сортировать за пять секунд с помощью 'Arrays.sort (int [] nums)' равно 2^24 (16,7 млн записей). Если вы выбираете 3 лучших из пула менее миллиона, просто сортируйте его. –

Сортируйте список, получите 3 значения max. Если вы не хотите расходов на сортировку, повторите и сохраните n наибольших значений.
Поддержание бассейна - это отсортированная коллекция.

Обновление: FYI Guava имеет класс Ordering с методом greatestOf для получения элементов n max в коллекции. Возможно, вы захотите проверить реализацию.

Ordering.greatestOf

источник

2012-03-30 10:58:43

Если список очень длинный, то или есть ли другой способ сделать это –

Обновлен вопрос для сортировки сценария –

@bunta использовать DoublyLinkedList или просто использовать обратный порядок, а верхние 3 - это первые 3 или последние 3 из хвост. – GriffinHeart

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

источник

2012-03-30 11:01:14 NPE

с формулировкой вопроса, похоже, что он не знает, что было добавлено или сколько. – GriffinHeart

@GriffinHeart: Не уверен, что я понимаю ваше замечание. – NPE

пропустил глагол там, отредактирован. Во всяком случае, это лучше, так как его O (n) и простое и любое время, когда список изменяется, просто перешагивается. – GriffinHeart

A priority queue должен быть структурой данных, в которой вы нуждаетесь.

источник

2012-03-30 11:02:48

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

Во-вторых, самый простой способ сделать то, что вы пытаетесь сделать, - и то, что будет более понятно кому-то позже, если они попытаются выяснить, что делает ваш код, - использовать Collections.sort() и выбрать последний три элемента. Тогда любой, кто увидит код, будет знать: «О, этот код принимает три самых больших элемента». В четком коде есть такая ценность, что он, вероятно, переведет любую оптимизацию, которую вы могли бы сделать. Это также не позволит вам писать ошибки, например, придавать естественный смысл тому, что происходит, когда кто-то дважды вводит один и тот же номер в список или дает полезное сообщение об ошибке, когда в списке всего два элемента.

В-третьих, если вы действительно получаете данные, которые настолько велики, что операции O (n log n) выполняются слишком медленно, вы должны переписать структуру данных, которая содержит данные в первую очередь - java.util.NavigableSet, например, предлагает метод .descendingIterator() которые вы можете исследовать для своих первых трех элементов, это будут три максимальных числа. Если вы действительно хотите, можно использовать структуру данных кучи, и вы можете снять верхние 3 элемента с помощью чего-то вроде одного сравнения за счет добавления процедуры O (log n).

источник

2012-03-30 11:15:41

Найти значения K max из списка N

ответ

Смежные вопросы