1

我正在用 PHP 编写一个小算法，它遍历n部带有评级的电影，并将存储前 5 部。我不是从数据文件中读取，而是从流中读取，所以我不能简单地按评级对电影进行排序。

我的问题是，当我阅读流媒体时，跟踪排名前 5 的电影的最有效方法是什么？目前我执行以下操作：

  1. 读入 5 部电影（进入名为 movies[] 的数组），带有两个键 movies[][name] 和 movies[][rating]
  2. 使用 array_multisort() 按 movies[rating] 排序数组（最高评分现在位于 movies[4]）
  3. 在下一部电影中阅读
  4. 如果这个新电影评分 > movies[0][rating] 则用这个新电影替换 movies[0]
  5. 重新排序列表
  6. 重复 3-5 直到完成

我的方法有效，但每次阅读后都需要对列表进行排序。我相信这是一种昂贵的方法，主要是因为每次我使用 array_multisort() 时，我都必须对 5 部电影进行 for 循环，以构建要排序的索引。谁能提出一个更好的方法来解决这个问题？

4

8 回答 8

4

链接列表可以在这里工作。

建立一个以正确顺序链接前 5 部电影的链表。对于每部新电影，只需从链的末端开始，一直走到您的电影介于评分较高的电影和评分较低的电影之间。然后将您的链接插入到此处的列表中。如果这部电影比最差的电影好（因此您的列表现在长 6 个），只需删除链中的最后一个链接，您就会回到第 5 个。

没有排序，没有索引。

于 2009-03-21T12:12:59.520 回答
3

你的算法看起来不错。我不确定数组是如何在 PHP 中实现的。从算法的角度来看：使用堆而不是数组。

于 2009-03-21T12:02:56.270 回答
3

每次阅读后重新排序没有意义，因为您实际上只需要插入一个新条目。使用以下算法，它可能会为您提供最佳速度。它基本上是一个展开的循环，而不是最漂亮的代码。

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 部电影进行调整，则可以。最好的选择是再次卷起循环。然而，在某些时候，对它进行排序会比使用这种方法更有效。这种方法只适用于小数据集。

于 2009-03-21T12:34:47.317 回答
1

我的方法有效，但每次阅读后都需要对列表进行排序。

不，它没有，它只需要在你找到一部评级为 > movies[0][rating] 的新电影后进行排序。

这种方法对我来说似乎很有效。只有当前 5 名有新条目时，您才会偶尔进行排序，您处理的电影越多，这种情况发生的次数就越少。

于 2009-03-21T12:26:07.243 回答
0

名单有多大？我猜这不是将整个列表保存在内存中并在最后对其进行排序的选项吗？

于 2009-03-21T12:22:08.593 回答
0
  1. 数组中不需要两个键。以名称为键，以评级为值的数组就可以了。使用arsort()对其进行排序；
  2. 该算法并不完美，您可以使用链表优化。虽然我认为在 PHP 中实现的链表实际上会更慢，对 6 个元素的 asort() 函数调用。对于大 O 估计，您可以假设对 6 个元素进行排序具有恒定时间。
  3. 只有当您遇到比实际评分更高的电影时，您才会进行排序，因此在平均情况下，您会在进步的同时少做少做。只有在最坏的情况下，您才会对每部电影进行排序，即初始列表从最低评分开始排序。
于 2009-03-21T12:52:38.427 回答
0

这是我要做的：

// 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 :-)

}

$ratings 数组看起来像这样，每个评分里面都有电影数组：

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

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

    [4] => Array
        (
            [0] => FOR
        )
    )
于 2009-03-21T13:45:37.300 回答
0

也许这会有所帮助。

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());
于 2009-03-21T16:12:45.013 回答