私が取り組んでいる問題について質問があります。ビデオを繰り返さずに順番にランダムにビデオを再生する必要があります。各動画は、プレイリストごとに 1 回だけ再生できます。各ビデオには、0 から max_video_count までの一意の ID があり、これは実行時に決定されます (サーバーによって異なります)。
私が今やっていることは、再生された各ビデオの一意の ID を追加するリンク リストを作成したことです。0 と max_video_count の間の乱数をランダムに作成するよりも、数値がリンク リストに既にある場合は線形検索を実行し、そうであれば新しい数値を計算します..そして再び線形検索..などなど!!
明らかに、これはあまり実用的ではなく、要素を見つけるのに時間がかかる場合があります。特に、すでに多くの動画が再生されている場合。
だから私は考えました、私は線形検索の代わりに二分検索を実装しますが、それは私が最初にリストをソートしなければならないという問題に私をもたらします。したがって、私の次のステップは、新しいunique_idを挿入しながらリストをソートし、バイナリ検索を行うことだと考えることでした。
二分探索は O(n) 線形探索と比較して O(log n) であることを知っています。これは大きな進歩です。しかし、リストのソートもO(n)です。なぜなら、正しい場所を見つけるには、線形検索を再度実行する必要があるからです.... O(n) 線形検索 -> 線形検索高速。そうですか？たぶん私のアプローチ全体が間違っている..しかし、私はまだ何か良いものを思い付くことができませんでした...
私はアルゴリズムにまったく慣れていないので、誰かがここで私を啓発してくれるとうれしいです:-)
こんにちはマルクス