Поддержание 5 лучших значений в PHP эффективно - PullRequest
Новая
       23

Поддержание 5 лучших значений в PHP эффективно

1 голос
/ 21 марта 2009

Я пишу небольшой алгоритм на PHP, который проходит через n количество фильмов с оценками и сохраняет 5 лучших. Я не читаю из файла данных, но из потока, поэтому я нельзя просто заказать фильмы по рейтингу.

Мой вопрос: какой самый эффективный способ отслеживать лучшие 5 фильмов с оценками, когда я читаю поток? В настоящее время я делаю следующее:

  1. Чтение в 5 фильмах (в массив, называемый фильмами []), с двумя ключами фильмов [] [имя] и фильмов [] [рейтинг]
  2. Упорядочить массив по фильмам [рейтинг] с помощью array_multisort () (самый высокий рейтинг теперь у фильмов [4])
  3. Читать в следующем фильме
  4. Если этот новый рейтинг фильма> фильмы [0] [рейтинг], то заменить фильмы [0] на этот новый фильм
  5. Переупорядочить список
  6. Повторите 3-5 до конца

Мой метод работает, но требует сортировки в списке после каждого чтения. Я считаю, что это дорогой метод, в основном из-за того, что каждый раз, когда я использую array_multisort (), я должен делать цикл for для 5 фильмов, просто чтобы построить индекс для сортировки. Кто-нибудь может предложить лучший способ подойти к этому?

Ответы [ 8 ]

4 голосов
/ 21 марта 2009

Связанные списки будут работать здесь.

Создайте связанный список, который объединяет первые 5 фильмов в правильном порядке. Для каждого нового фильма просто начните с конца цепочки и продолжайте, пока ваш фильм не окажется между одним с более высоким рейтингом и другим с более низким рейтингом. Затем вставьте свою ссылку в список здесь. Если фильм был лучше худшего (и, следовательно, ваш список теперь 6 длинных), просто удалите последнюю ссылку в цепочке, и вы вернетесь к 5.

Нет сортировки, нет индексации.

3 голосов
/ 21 марта 2009

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

set movies[0..4].rating to -1.
while more movies in stream:
    read in next movie.
    if movie.rating < movies[0].rating:
        next while
    if movie.rating < movies[1].rating:
        movies[0] = movie
        next while
    if movie.rating < movies[2].rating:
        movies[0] = movies[1]
        movies[1] = movie
        next while
    if movie.rating < movies[3].rating:
        movies[0] = movies[1]
        movies[1] = movies[2]
        movies[2] = movie
        next while
    if movie.rating < movies[4].rating:
        movies[0] = movies[1]
        movies[1] = movies[2]
        movies[2] = movies[3]
        movies[3] = movie
        next while
    movies[0] = movies[1]
    movies[1] = movies[2]
    movies[2] = movies[3]
    movies[3] = movies[4]
    movies[4] = movie

В конце у вас есть отсортированный список фильмов. Если их меньше 5, у других будет рейтинг -1, поэтому вы будете знать, что они недействительны. Предполагается, что рейтинг реального фильма равен нулю или больше, но вы можете изменить значения, если они не указаны.

Если вам нужно настроить его для более чем 5 фильмов, вы можете. Лучше всего было бы снова свернуть петлю. Однако в какой-то момент сортировка будет более эффективной, чем использование этого метода. Этот метод действительно хорош только для небольшого набора данных.

3 голосов
/ 21 марта 2009

Ваш алгоритм выглядит хорошо. Я не уверен, как массивы реализованы в PHP. С точки зрения алгоритма: используйте кучу вместо массива.

1 голос
/ 21 марта 2009

Мой метод работает, но требует сортировки в списке после каждого чтения.

Нет, это не так, требуется только сортировка после того, как вы найдете новый фильм, рейтинг которого:> movies [0] [rating].

Этот метод мне кажется эффективным. Вы сортируете только изредка, когда есть новая запись для топ-5, что будет тем меньше, чем больше фильмов вы обрабатываете.

0 голосов
/ 21 марта 2009

Может быть, это может помочь. 

class TopList {
    private $items = array();
    private $indexes = array();
    private $count = 0;
    private $total = 5;
    private $lowest;
    private $sorted = false;

    public function __construct($total = null) {
        if (is_int($total))
            $this->total = $total;

        $this->lowest = -1 * (PHP_INT_MAX - 1);
    }

    public function addItem($index, $item) {
        if ($index <= $this->lowest)
            return;

        $setLowest = $this->count === $this->total;
        if ($setLowest) {
            /* //remove first added
            $lowestIndex = array_search($this->lowest, $this->indexes);
            /*/ //remove last added
            $lowestIndex = end(array_keys($this->indexes, $this->lowest));
            //*/
            unset($this->indexes[$lowestIndex], $this->items[$lowestIndex]);
        } else {
            ++$this->count;
            $setLowest = $this->count === $this->total;
        }

        $this->indexes[] = $index;
        $this->items[] = $item;
        $this->sorted = false;

        if ($setLowest)
            $this->lowest = min($this->indexes);
    }

    public function getItems() {
        if (!$this->sorted) {
            array_multisort($this->indexes, SORT_DESC, $this->items);
            $this->sorted = true;
        }
        return $this->items;
    }
}

$top5 = new TopList(5);
foreach ($movies as $movie) {
    $top5->addItem($movie['rating'], $movie);
}
var_dump($top5->getItems());
0 голосов
/ 21 марта 2009

Вот что я бы сделал: 

// let’s say get_next_movie () returns array with 'rating' and 'name' keys

while ($m = get_next_movie ()) {

  $ratings[$m['rating']][] = $m['movie'];

  $temp_ratings = $ratings;
  $top5 = array ();
  $rating = 5;
  while (1) {
    if (count ($temp_ratings[$rating])) {
      $top5[] = array_shift ($temp_ratings[$rating]);
    } elseif ($rating > 0) {
      --$rating;
    } else {
      break;
    }
  }

  // $top5 has current top 5 :-)

}

$ рейтинг массива выглядит следующим образом, каждый рейтинг имеет массив фильмов внутри: 

Array
    (
    [5] => Array
        (
            [0] => Five!
        )

    [3] => Array
        (
            [0] => Three
            [1] => Threeeeee
            [2] => Thr-eee-eee
        )

    [4] => Array
        (
            [0] => FOR
        )
    )
0 голосов
/ 21 марта 2009
  1. нет необходимости в двух ключах в массиве. массив с именем в качестве ключа и рейтингом в качестве значения. Сортировать с помощью arsort () ;
  2. алгоритм не идеален, вы можете сделать это оптимально с помощью связанного списка. Хотя я думаю, что связанный список, реализованный в PHP, будет на самом деле медленнее, чем вызов функции asort () для 6 элементов. Для большой оценки O можно предположить, что сортировка 6 элементов имеет постоянное время.
  3. Вы будете сортировать только тогда, когда вы встретите фильм, оцененный выше, чем фактический, поэтому в среднем случае вы будете делать это реже, а прогрессировать. Сортировать по каждому фильму можно только в худшем случае, если исходный список отсортирован по самым низким рейтингам.
0 голосов
/ 21 марта 2009

Насколько велик список? Я предполагаю, что это не вариант сохранить весь список в памяти и отсортировать его в конце?

...