c# - ランダムプレイリストアルゴリズム

Question

すべての順序が同じ確率になるように、ランダムな順序で範囲（たとえば、xからy）の数値のリストを作成する必要があります。

ランダムな順序でプレイリストを作成するために、C＃で作成する音楽プレーヤーにこれが必要です。

何か案は？

ありがとう。

編集：元のリストを変更することに興味はありません。すべての順序が同じチャンスになるように、ランダムな順序で範囲からランダムなインデックスを取得するだけです。

これが私がこれまでに書いたものです：

    public static IEnumerable<int> RandomIndexes(int count)
    {
        if (count > 0)
        {
            int[] indexes = new int[count];
            int indexesCountMinus1 = count - 1;

            for (int i = 0; i < count; i++)
            {
                indexes[i] = i;
            }

            Random random = new Random();

            while (indexesCountMinus1 > 0)
            {
                int currIndex = random.Next(0, indexesCountMinus1 + 1);
                yield return indexes[currIndex];

                indexes[currIndex] = indexes[indexesCountMinus1];
                indexesCountMinus1--;
            }

            yield return indexes[0];
        }
    }

動作していますが、これの唯一の問題は、メモリに。のサイズの配列を割り当てる必要があることですcount。メモリ割り当てを必要としないものを探しています。

ありがとう。

score 31 · Accepted Answer

注意しないと（つまり、ナイーブなシャッフルアルゴリズムを使用する場合）、これは実際には注意が必要です。値の適切な分布については、Fisher-Yates/Knuthシャッフルアルゴリズムを参照してください。

シャッフルアルゴリズムを使用したら、残りは簡単です。

ジェフ・アトウッドの詳細です。

最後に、JonSkeetの実装と説明を示します。

編集

私はあなたの2つの相反する要件を満たす解決策があるとは思いません（最初は繰り返しなしでランダムであり、2番目は追加のメモリを割り当てないことです）。埋め込まれていない限り、メモリへの影響はごくわずかであるため、ソリューションを時期尚早に最適化している可能性があると思います。または、おそらく私は答えを思い付くのに十分賢くないだけです。

これで、Knuth-Fisher-Yatesアルゴリズムを使用して（わずかな変更を加えて）均等に分散されたランダムインデックスの配列を作成するコードを次に示します。結果の配列をキャッシュするか、実装の残りの部分に応じて任意の数の最適化を実行できます。

  private static int[] BuildShuffledIndexArray( int size ) {

     int[] array = new int[size];
     Random rand = new Random();
     for ( int currentIndex = array.Length - 1; currentIndex > 0; currentIndex-- ) {
        int nextIndex = rand.Next( currentIndex + 1 );
        Swap( array, currentIndex, nextIndex );
     }
     return array;
  }

  private static void Swap( IList<int> array, int firstIndex, int secondIndex ) {

     if ( array[firstIndex] == 0 ) {
        array[firstIndex] = firstIndex;
     }
     if ( array[secondIndex] == 0 ) {
        array[secondIndex] = secondIndex;
     }
     int temp = array[secondIndex];
     array[secondIndex] = array[firstIndex];
     array[firstIndex] = temp;
  }

注：プレイリストに65,535を超えるアイテムがない限り、メモリのサイズを半分にするushort代わりに使用できます。サイズがを超える場合は、intいつでもプログラムで切り替えることができます。個人的に、プレイリストに65Kを超えるアイテムを追加した場合、メモリ使用率の増加にショックを受けることはありません。intushort.MaxValue

これは管理された言語であることも忘れないでください。VMは、OSにRAMの追加を要求する回数を制限し、断片化を制限するために、使用しているよりも多くのメモリを常に予約します。

編集

さて、最後の試み：パフォーマンスとメモリのトレードオフを微調整することができます。整数のリストを作成して、それをディスクに書き込むことができます。次に、ファイル内のオフセットへのポインタを保持します。そうすれば、新しい番号が必要になるたびに、ディスクI/Oを処理するだけで済みます。おそらく、ここである程度のバランスを見つけることができ、Nサイズのデータブロックをメモリに読み込むだけです。ここで、 Nは快適な数値です。

シャッフルアルゴリズムには多くの作業が必要なようですが、メモリの節約に行き詰まっている場合は、少なくともそれはオプションです。

score 8 · Accepted Answer

最大線形フィードバックシフトレジスタを使用する場合は、メモリのO（1）とおおよそO（1）時間を使用します。便利なC実装（2行！woo-hoo！）と使用するフィードバック用語の表については、こちらを参照してください。

そしてここに解決策があります：

public class MaximalLFSR
{
    private int GetFeedbackSize(uint v)
    {
        uint r = 0;

        while ((v >>= 1) != 0)
        {
          r++;
        }
        if (r < 4)
            r = 4;
        return (int)r;
    }

    static uint[] _feedback = new uint[] {
        0x9, 0x17, 0x30, 0x44, 0x8e,
        0x108, 0x20d, 0x402, 0x829, 0x1013, 0x203d, 0x4001, 0x801f,
        0x1002a, 0x2018b, 0x400e3, 0x801e1, 0x10011e, 0x2002cc, 0x400079, 0x80035e,
        0x1000160, 0x20001e4, 0x4000203, 0x8000100, 0x10000235, 0x2000027d, 0x4000016f, 0x80000478
    };

    private uint GetFeedbackTerm(int bits)
    {
        if (bits < 4 || bits >= 28)
            throw new ArgumentOutOfRangeException("bits");
        return _feedback[bits];
    }

    public IEnumerable<int> RandomIndexes(int count)
    {
        if (count < 0)
            throw new ArgumentOutOfRangeException("count");

        int bitsForFeedback = GetFeedbackSize((uint)count);

        Random r = new Random();
        uint i = (uint)(r.Next(1, count - 1));

        uint feedback = GetFeedbackTerm(bitsForFeedback);
        int valuesReturned = 0;
        while (valuesReturned < count)
        {
            if ((i & 1) != 0)
            {
                i = (i >> 1) ^ feedback;
            }
            else {
                i = (i >> 1);
            }
            if (i <= count)
            {
                valuesReturned++;
                yield return (int)(i-1);
            }
        }
    }
}

ここで、上記のリンクからフィードバック用語を（ひどく）ランダムに選択しました。複数の最大項を持つバージョンを実装して、そのうちの1つをランダムに選択することもできますが、何を知っていますか？これはあなたが望むものにかなり良いです。

テストコードは次のとおりです。

    static void Main(string[] args)
    {
        while (true)
        {
            Console.Write("Enter a count: ");
            string s = Console.ReadLine();
            int count;
            if (Int32.TryParse(s, out count))
            {
                MaximalLFSR lfsr = new MaximalLFSR();
                foreach (int i in lfsr.RandomIndexes(count))
                {
                    Console.Write(i + ", ");
                }
            }
            Console.WriteLine("Done.");
        }
    }

最大のLFSRが0を生成することは決してないことに注意してください。私はi項-1を返すことによってこれをハックしました。これは十分に機能します。また、一意性を保証したいので、範囲外のものはすべて無視します。LFSRは2の累乗までのシーケンスしか生成しないため、高範囲では、2x-1の値が多すぎる場合に生成されます。これらはスキップされます-それでもFYKよりも高速です。

score 6 · Accepted Answer

個人的には、音楽プレーヤーの場合、シャッフルされたリストを生成してからそれを再生し、それがなくなったときに別のシャッフルされたリストを生成しますが、次のようなことを行います。

IEnumerable<Song> GetSongOrder(List<Song> allSongs)
{
    var playOrder = new List<Song>();
    while (true)
    {
        // this step assigns an integer weight to each song,
        // corresponding to how likely it is to be played next.
        // in a better implementation, this would look at the total number of
        // songs as well, and provide a smoother ramp up/down.
        var weights = allSongs.Select(x => playOrder.LastIndexOf(x) > playOrder.Length - 10 ? 50 : 1);

        int position = random.Next(weights.Sum());
        foreach (int i in Enumerable.Range(allSongs.Length))
        {
            position -= weights[i];
            if (position < 0)
            {
                var song = allSongs[i];
                playOrder.Add(song);
                yield return song;
                break;
            }
        }

        // trim playOrder to prevent infinite memory here as well.
        if (playOrder.Length > allSongs.Length * 10)
            playOrder = playOrder.Skip(allSongs.Length * 8).ToList();
    }    
}

これにより、最近再生されていない限り、曲が順番に選択されます。これにより、あるシャッフルの終わりから次のシャッフルへの「スムーズな」遷移が提供されます。これは、次のシャッフルの最初の曲が最後のシャッフルと1 /（合計曲）の確率で同じ曲になる可能性があるためです。構成可能）最後のx曲の1つをもう一度聞く可能性。

score 3 · Accepted Answer

元の曲のリストをシャッフルしない限り（やりたくないと言った）、目的を達成するために追加のメモリを割り当てる必要があります。

曲のインデックスのランダム順列を事前に生成する場合（実行しているように）、エンコードまたはリストとして保存するために、明らかに重要な量のメモリを割り当てる必要があります。

ユーザーがリストを表示する必要がない場合は、ランダムな曲の順序をその場で生成できます。各曲の後に、未再生の曲のプールから別のランダムな曲を選択します。どの曲がすでに再生されているかを追跡する必要がありますが、そのためにビットフィールドを使用できます。10000曲ある場合は、10000ビット（1250バイト）が必要です。各ビットは、曲がまだ再生されているかどうかを表します。

正確な制限はわかりませんが、プレイリストを保存するために必要なメモリは、オーディオの再生に必要な量と比較して重要かどうか疑問に思います。

score 2 · Accepted Answer

状態を保存せずに順列を生成する方法はいくつかあります。この質問を参照してください。

score 1 · Accepted Answer

私はあなたがあなたの現在の解決策（あなたの編集の解決策）に固執するべきだと思います。

繰り返しなしで並べ替えを行い、コードの動作を信頼できないものにしないためには、未使用のインデックスを保持するか、元のリストからスワップすることで間接的に、すでに使用したものを追跡する必要があります。

動作中のアプリケーションのコンテキストで確認することをお勧めします。つまり、システムの他の部分で使用されているメモリと比較して、重要性があるかどうかを確認します。

score 1 · Accepted Answer

論理的な観点から、それは可能です。n曲のリストを考えると、 nがあります！順列; 各順列に1からnまでの番号を割り当てると！（または0からn！-1 :-D）そしてそれらの番号の1つをランダムに選択すると、現在使用している順列の番号を、元のリストと現在の曲のインデックスとともに、順列。

たとえば、曲のリスト{1、2、3}がある場合、順列は次のようになります。

0: {1, 2, 3}
1: {1, 3, 2}
2: {2, 1, 3}
3: {2, 3, 1}
4: {3, 1, 2}
5: {3, 2, 1}

したがって、追跡する必要があるデータは、元のリスト（{1、2、3}）、現在の曲のインデックス（たとえば、1）、および順列のインデックス（たとえば、3）だけです。次に、再生する次の曲を見つけたい場合は、それが順列3の3番目（2、ただしゼロベース）の曲、たとえば曲1であることがわかります。

ただし、この方法は、 j番目の順列のi番目の曲を効率的に決定する手段を持っていることに依存しています。奇跡が起こる」。しかし、原則はそこにあります。

score 1 · Accepted Answer

一定数のレコードの後でメモリが本当に問題であり、そのメモリ境界に達した場合、同じ曲が繰り返されない限り、リピートがいくつかあるかどうかに関係なく、リストに十分なアイテムがあると言っても過言ではありません。 2回、私は組み合わせ方法を使用します。

ケース1：カウント<最大メモリ制約の場合、事前にプレイリストを生成し、クヌースシャッフルを使用します（他の回答で言及されているJon Skeetの実装を参照）。

ケース2：カウント> =最大メモリ制約の場合、再生される曲は実行時に決定されます（曲の再生が開始されるとすぐに実行されるため、現在の曲が終了するまでに次の曲がすでに生成されています）。最後に再生された[最大メモリ制約またはトークン値]の曲数を保存し、1から曲数までの乱数（R）を生成し、R =最後に再生されたX曲の1つである場合は、それがなくなるまで新しいRを生成しますリストにあります。その曲を再生します。

最大メモリの制約は常に維持されますが、ケース2では、多くの曲を再生したり、偶然に乱数を頻繁に繰り返したりすると、パフォーマンスが低下する可能性があります。

score 0 · Accepted Answer

他の多くの人が言っているように、次に最適化を実装し、それを必要とする部分のみを最適化する必要があります（プロファイラーで確認します）。私はあなたが必要とするリストを取得するための（うまくいけば）エレガントな方法を提供しますが、それはパフォーマンスについてはあまり気にしません：

using System;
using System.Collections.Generic;
using System.Linq;

namespace Test
{
    class Program
    {
        static void Main(string[] a)
        {
            Random random = new Random();
            List<int> list1 = new List<int>(); //source list
            List<int> list2 = new List<int>();
            list2 = random.SequenceWhile((i) =>
                 {
                     if (list2.Contains(i))
                     {
                         return false;
                     }
                     list2.Add(i);
                     return true;
                 },
                 () => list2.Count == list1.Count,
                 list1.Count).ToList();

        }
    }
    public static class RandomExtensions
    {
        public static IEnumerable<int> SequenceWhile(
            this Random random, 
            Func<int, bool> shouldSkip, 
            Func<bool> continuationCondition,
            int maxValue)
        {
            int current = random.Next(maxValue);
            while (continuationCondition())
            {
                if (!shouldSkip(current))
                {
                    yield return current;
                }
                current = random.Next(maxValue);
            }
        }
    }
}

score 0 · Accepted Answer

SQL Serverで行うトリックを使用して、guidを使用してこのようにランダムにセットを並べ替えることができます。値は常に均等にランダムに分散されます。

private IEnumerable<int> RandomIndexes(int startIndexInclusive, int endIndexInclusive)
{
    if (endIndexInclusive < startIndexInclusive)
        throw new Exception("endIndex must be equal or higher than startIndex");

    List<int> originalList = new List<int>(endIndexInclusive - startIndexInclusive);
    for (int i = startIndexInclusive; i <= endIndexInclusive; i++)
        originalList.Add(i);

    return from i in originalList
           orderby Guid.NewGuid()
           select i;
}

score 0 · Accepted Answer

ある程度のメモリを割り当てる必要がありますが、多くのメモリを割り当てる必要はありません。intの代わりにbool配列を使用することで、メモリフットプリント（C＃の本質についてはあまり知らないので、私にはわからない程度）を減らすことができます。最良のシナリオでは、これは（count / 8）バイトのメモリのみを使用しますが、それほど悪くはありません（ただし、C＃が実際にboolを1ビットとして表すとは思えません）。

    public static IEnumerable<int> RandomIndexes(int count) {
        Random rand = new Random();
        bool[] used = new bool[count];

        int i;
        for (int counter = 0; counter < count; counter++) {
            while (used[i = rand.Next(count)]); //i = some random unused value
            used[i] = true;
            yield return i;
        }
    }

お役に立てば幸いです。

score 0 · Accepted Answer

余分なメモリを割り当てずにそれを行うことはほとんど不可能です。割り当てられる余分なメモリの量が心配な場合は、いつでもランダムなサブセットを選択して、それらの間でシャッフルすることができます。すべての曲が再生される前にリピートが発生しますが、サブセットが十分に大きい場合は、ほとんどの人が気付かないことを保証します。

const int MaxItemsToShuffle = 20;
public static IEnumerable<int> RandomIndexes(int count)
{
    Random random = new Random();

    int indexCount = Math.Min(count, MaxItemsToShuffle);
    int[] indexes = new int[indexCount];

    if (count > MaxItemsToShuffle)
    {
        int cur = 0, subsetCount = MaxItemsToShuffle;
        for (int i = 0; i < count; i += 1)
        {
            if (random.NextDouble() <= ((float)subsetCount / (float)(count - i + 1)))
            {
                indexes[cur] = i;
                cur += 1;
                subsetCount -= 1;
            }
        }
    }
    else
    {
        for (int i = 0; i < count; i += 1)
        {
            indexes[i] = i;
        }
    }

    for (int i = indexCount; i > 0; i -= 1)
    {
        int curIndex = random.Next(0, i);
        yield return indexes[curIndex];

        indexes[curIndex] = indexes[i - 1];
    }
}

c# - ランダムプレイリストアルゴリズム

12 に答える 12

Related

Reference