무작위 재생목록 알고리즘
https://stackoverflow.com/questions/1816534
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
모든 순서가 동일한 확률을 갖도록 임의의 순서로 범위(예: 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.메모리 할당이 필요하지 않은 것을 찾고 있습니다.
감사해요.
해결책
조심하지 않으면 실제로 까다로울 수 있습니다 (즉, 순진한 셔플 링 알고리즘). 살펴보십시오 Fisher-Yates/Knuth 셔플 알고리즘 적절한 값 분포.
셔플 링 알고리즘이 있으면 나머지는 쉬워야합니다.
여기에 있습니다 자세한 세부 사항 Jeff Atwood에서.
마지막으로 여기 Jon Skeet이 있습니다 구현 및 설명.
편집하다
나는 당신의 두 가지 충돌 요구 사항을 충족시키는 솔루션이 있다고 생각하지 않습니다 (첫째, 반복없이 무작위로, 두 번째는 추가 메모리를 할당하지 않기 위해). 나는 당신이 내장되지 않는 한 메모리의 의미가 무시할 수 있기 때문에 솔루션을 조기에 최적화 할 수 있다고 생각합니다. 아니면 아마도 나는 대답을 내놓을만큼 똑똑하지 않을 것입니다.
이를 통해 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;
}
노트: 당신이 사용할 수있는 ushort 대신에 int 재생 목록에 65,535 개 이상의 항목이없는 한 메모리 크기의 절반까지. 항상 프로그래밍 방식으로 전환 할 수 있습니다 int 크기가 초과되는 경우 ushort.MaxValue. 개인적으로 65k 이상의 항목을 재생 목록에 추가 한 경우 메모리 활용도가 높아지지 않을 것입니다.
또한 이것은 관리되는 언어라는 것을 기억하십시오. VM은 OS에 더 많은 RAM을 요청하고 단편화를 제한하는 데 필요한 횟수를 제한하기 위해 사용하는 것보다 항상 더 많은 메모리를 예약합니다.
편집하다
좋아요, 마지막 시도 : 우리는 성능/메모리 거래를 조정할 수 있습니다. ~할 수 있었다 정수 목록을 작성한 다음 디스크에 작성하십시오. 그런 다음 파일의 오프셋에 대한 포인터를 유지하십시오. 그런 다음 새 번호가 필요할 때마다 다루는 디스크 I/O 만 있습니다. 아마도 여기서 균형을 찾을 수 있고 그냥 읽을 수 있습니다. N-메모리에 대한 크기의 데이터 블록 N 당신이 편한 숫자입니다.
셔플 알고리즘에 대한 많은 작업처럼 보이지만 메모리 보존을 막기 위해 데드 세트라면 적어도 옵션입니다.
다른 팁
개인적으로 음악 연주자의 경우 셔플리스트를 생성하지 않은 다음 재생 한 다음 다른 셔플 목록을 생성하지만 다음과 같은 작업을 수행합니다.
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 노래 중 하나를 다시들을 가능성.
최대 선형 피드백 시프트 레지스터를 사용하는 경우 O(1)의 메모리와 대략 O(1)의 시간을 사용하게 됩니다. 여기를 보아라 편리한 C 구현을 위해(두 줄!우후!) 및 사용할 피드백 용어 표.
해결책은 다음과 같습니다.
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);
}
}
}
}
이제 위 링크에서 피드백 용어를 (잘못) 무작위로 선택했습니다.여러 개의 최대 항이 있는 버전을 구현하고 그 중 하나를 무작위로 선택할 수도 있지만 그거 알아요?이것은 당신이 원하는 것에 매우 좋습니다.
테스트 코드는 다음과 같습니다.
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보다 빠릅니다.
원래 노래 목록(원하는 노래 목록)을 섞지 않는 한 원하는 작업을 수행하려면 추가 메모리를 할당해야 합니다.
노래 인덱스의 임의 순열을 미리 생성하는 경우(현재 수행 중인 것처럼) 이를 인코딩하거나 목록으로 저장하기 위해 적지 않은 양의 메모리를 할당해야 합니다.
사용자가 목록을 볼 필요가 없다면 즉시 임의의 노래 순서를 생성할 수 있습니다.각 노래가 끝나면 재생되지 않은 노래 풀에서 다른 임의의 노래를 선택하세요.이미 재생된 노래를 추적해야 하지만 이를 위해 비트필드를 사용할 수 있습니다.10000개의 노래가 있는 경우 10000비트(1250바이트)만 필요하며 각 비트는 해당 노래가 아직 재생되었는지 여부를 나타냅니다.
정확한 제한 사항은 모르지만 오디오 재생에 필요한 메모리 양에 비해 재생 목록을 저장하는 데 필요한 메모리가 상당한지 궁금합니다.
현재 솔루션 (편집 한 솔루션)을 고수해야한다고 생각합니다.
반복없이 재주문을하고 코드가 신뢰할 수 없게 만들지 않으려면 사용하지 않은 색인을 유지하거나 원래 목록에서 간접적으로 교체하여 이미 사용했던 것 / 좋아하는 것을 추적해야합니다.
작업 응용 프로그램의 맥락에서이를 확인하는 것이 좋습니다. 즉, 시스템의 다른 부분이 사용하는 메모리와 관련이있는 경우 즉.
메모리가 특정 수의 레코드 후에 실제로 우려되는 경우 메모리 경계에 도달하면 동일한 노래가 반복되지 않는 한 일부 반복이 있더라도 중요하지 않은 항목이 충분하다고 말하는 것이 안전합니다. 두 번, 나는 조합 방법을 사용합니다.
사례 1 : <max 메모리 제한 조건 카운트 인 경우, 재생 목록을 미리 생성하고 Knuth Shuffle을 사용하십시오 (다른 답변에서 언급 된 Jon Skeet의 구현 참조).
CASE 2 : COUNT> = MAX 메모리 제약 조건이라면, 재생되는 노래는 런타임에 결정됩니다 (노래가 재생되기 시작하자마자 다음 곡이 이미 생성 될 때 이미 생성됩니다). . 마지막 [최대 메모리 제약 조건 또는 일부 토큰 값] 곡을 재생하고 1과 송 카운트 사이에 무작위 숫자 (r)를 생성하고 x 마지막 곡 중 하나가 재생되면 새로운 r을 생성하지 않을 때까지 새 R을 생성합니다. 목록에서. 그 노래를 연주하십시오.
최대 메모리 제약 조건은 항상 유지되지만, 많은 노래를 연주하거나 우연히 자주 반복 숫자를 얻는 경우 사례 2에서는 성능이 어려울 수 있습니다.
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;
}
논리적 인 관점에서 볼 수 있습니다. 목록이 주어졌습니다 N 노래가 있습니다 N! 순열; 각 순열을 할당하면 1에서 1에서 N! (또는 0에서 n! -1 : -d) 그리고 그 숫자 중 하나를 무작위로 선택하면, 당신은 현재 사용중인 순열의 수와 원본 목록 및 순열 내의 현재 노래 색인을 저장할 수 있습니다.
예를 들어, 노래 목록 {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의 세 번째 (2, 제로 기반) 노래, 예를 들어 노래 1임을 알고 있습니다.
그러나이 방법은 효율적인 방법을 결정하는 데 의존합니다. 나TH의 노래 제이내가 생각할 기회가있을 때까지 (또는 내가 삽입 할 수있는 것보다 더 강한 수학적 배경을 가진 사람)가 "기적이 일어난다"는 것과 같습니다. 그러나 원칙이 있습니다.
상태를 저장하지 않고도 순열을 생성하는 방법에는 여러 가지가 있습니다. 보다 이 질문.
기억을 할당해야하지만 많이 할 필요는 없습니다. int 대신 bool 어레이를 사용하여 메모리 풋 프린트 (C#의 내장에 대해 많이 알지 못하기 때문에 확실하지 않은 정도)를 줄일 수 있습니다. 최상의 시나리오 이것은 메모리의 바이트 (count / 8) 만 사용합니다. 이는 너무 나쁘지 않습니다 (그러나 C#이 실제로 BOOL을 단일 비트로 나타냅니다).
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;
}
}
도움이되기를 바랍니다!
다른 많은 사람들이 말했듯이, 당신은 당신이 최적화하고 필요한 부품 만 최적화해야한다고 말했듯이 (프로파일 러로 확인). 나는 당신이 필요한 목록을 얻는 (희망적으로) 우아한 방법을 제공합니다.
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);
}
}
}
}
추가 메모리를 할당하지 않고 수행하는 것은 거의 불가능합니다. 할당 된 추가 메모리의 양이 걱정된다면 언제든지 임의의 하위 집합을 선택하고 그 사이의 셔플을 선택할 수 있습니다. 모든 노래가 재생되기 전에 반복을 얻을 수 있지만 충분히 큰 서브 세트로 몇 사람이 눈에 띄게 보증 할 것입니다.
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];
}
}
