1

私はPHPで小さなアルゴリズムを書いています.n個の映画をレーティングで通過し、上位5つを保存します.

私の質問は、ストリームを読んでいるときに、評価の高い上位 5 つの映画を追跡する最も効率的な方法は何ですか? 現在、私は次のことを行っています。

  1. 5 つの映画を (movies[] という配列に) 読み込み、movies[][name] と movies[][rating] の 2 つのキーを使用します。
  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

実際には新しいエントリを挿入するだけでよいため、読み取りごとに再ソートしても意味がありません。次のアルゴリズムを使用すると、最高の速度が得られる可能性があります。これは基本的に展開されたループであり、最も美しいコードではありません。

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 になるため、無効であることがわかります。これは、実際の映画の評価が 0 以上であることを前提としていますが、そうでない場合は値を調整できます。

5 つ以上の映画に合わせて調整する必要がある場合は、調整できます。最善の策は、ループを再度ロールアップすることです。ただし、ある時点で、この方法を使用するよりも並べ替えた方が効率的になります。この方法は、小さなデータ セットに対してのみ有効です。

于 2009-03-21T12:34:47.317 に答える
3

あなたのアルゴリズムは問題ないようです。PHPで配列がどのように実装されているかわかりません。アルゴリズムの観点から: 配列の代わりにヒープを使用します。

于 2009-03-21T12:02:56.270 に答える
1

私の方法は機能しますが、読み取りのたびにリストをソートする必要があります。

いいえ、そうではありません。並べ替えが必要なのは、評価が > movies[0][rating] の新しい映画を見つけた後でのみです。

この方法は私には効率的だと思われます。トップ 5 に新しいエントリがある場合にのみ並べ替えを行いますが、これは、処理する映画が多いほど発生しなくなります。

于 2009-03-21T12:26:07.243 に答える
0

リストの大きさは？リスト全体をメモリに保持し、最後に並べ替えるというオプションはないと思いますか?

于 2009-03-21T12:22:08.593 に答える
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 に答える
0
  1. 配列に 2 つのキーは必要ありません。名前をキー、評価を値とする配列で十分です。arsort()でソートします。
  2. アルゴリズムは完全ではありません。リンクされたリストで最適に実行できます。PHPで実装されたリンクリストは、実際には6要素のasort()関数呼び出しよりも遅くなると思いますが。Big 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 に答える