Shuffle метод

[NikSoft]

Ниже приводится класс Shuffle, размещающий элементы в псевдо-случайной последовательности и реализующий одно из возможных решений

using System;
using System.Collections.Generic;

namespace ShuffleNik
{
sealed class Shuffle<T>
{
List<T> _list = new List<T>();

public Shuffle(T[] list)
{
_list.AddRange(list);
}

public List<T> Next()
{
List<T> result = new List<T>(_list.Capacity);
Random random = new Random();

while (_list.Count > 0)
{
int i = random.Next(0, _list.Count);
result.Add(_list[i]);
_list.RemoveAt(i);
}

return (_list = result);
}
}
}

Пример использования класса Shuffle приводится ниже.

using System;

namespace ShuffleNik
{
class Program
{
static void Main(string[] args)
{
////////////////////////////////////////////////////////////////////////////////
Shuffle<int> shuffleInt = 
new Shuffle<int>(new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15});
for (int i = 0; i < 100; i++ )
{
Console.Write("shuffle[{0}] = ", i + 1);
foreach (int j in shuffleInt.Next())
{
Console.Write("{0} ", j);
}
Console.WriteLine("");
}
Console.Write("=================================================");
Console.ReadLine();

////////////////////////////////////////////////////////////////////////////////
Shuffle<double> shuffleFloat = 
new Shuffle<double>(new double[] { 1.56, 2.86, 3.57, 4.56, 5.98, 6.35, 7.87, 8.69, 9.38, 10.57, 11.57, 12.74, 13.03, 14.46, 15.92 });
for (int i = 0; i < 100; i++)
{
Console.Write("shuffle[{0}] = ", i + 1);
foreach (double j in shuffleFloat.Next())
{
Console.Write("{0} ", j);
}
Console.WriteLine("");
}
Console.Write("=================================================");
Console.ReadLine();

////////////////////////////////////////////////////////////////////////////////
Shuffle<Customer> shuffleCustomer =
new Shuffle<Customer>(new Customer[] { new Customer("Sidorov"), 
new Customer("Petrov"),
new Customer("Ivanov"),
new Customer("Strunov"),
new Customer("Klinkin"),
new Customer("Mironov"),
new Customer("Smirnov")
});
for (int i = 0; i < 100; i++)
{
Console.Write("shuffle[{0}] = ", i + 1);
foreach (Customer customer in shuffleCustomer.Next())
{
Console.Write("{0} ", customer.Name);
}
Console.WriteLine("");
}
Console.Write("=================================================");
Console.ReadLine();
}
}
}

Класс Customer определяется так

namespace ShuffleNik
{
class Customer
{
string _name;

public Customer(string name){ _name = name; }

public string Name
{
get{ return _name; }
}
}
}

 

[62316e]

А где суть?

 

[NikSoft]

Для: 62316e
Посмотри сюда

https://codeby.net/threads/11643.html

 

[Pasha]

Что, и ни у кого не возникло подозрений? Тогда я немного покритикую Во время работы шаффлера n раз вызывается метод RemoveAt(i).
<!--QuoteBegin-MSDN+-->
<span class="vbquote">(MSDN)</span><!--QuoteEBegin-->public void RemoveAt (
int index
)
...
This method is an O operation, where n is (Count - index).[/quote]
Т.е. сложность использованного алгоритма шаффлинга O(n^2) (Время его работы пропорционально квадрату количества элементов). Для шаффлинга маленьких массивов (до 1000 элементов) это незаметно. Но что будет, если взять массив побольше:

using System;
using System.Collections.Generic;
using System.Text;

namespace Shuffler
{
class Program
{
static double MeasureShuffleTime(int[] largeArray, int timesToShuffle)
{
Shuffle<int> shuffle = new Shuffle<int>(largeArray);

int startTickCount = Environment.TickCount;

for (int i = 0; i < timesToShuffle; i++)
{
shuffle.Next();
}

return (Environment.TickCount - startTickCount) / (double)timesToShuffle;
}

static void Main(string[] args)
{
int n = 50000;
/// create a large array to shuffle
int[] largeArray = new int[n];

double measureResult = MeasureShuffleTime(largeArray, 10);

Console.WriteLine(measureResult / 1000);
}
}
}

Результаты тестов:
количество элементов - время шаффла (в секундах):
10000 - 0.02
20000 - 0.1
40000 - 0.6
50000 - 1.1
100000 - 6.5

Массив из 1M будет шаффлиться примерно 10 минут.

Изменяем немного шаффлер.

sealed class Shuffle<T>
{
public static List<T> ShuffleCollection(IEnumerable<T> originalCollection)
{
List<T> list = new List<T>(originalCollection);
Random random = new Random();
for (int i = 0; i < list.Count; i++)
{
int swapIndex = random.Next(i, list.Count);
T temp = list[swapIndex];
list[swapIndex] = list[i];
list[i] = temp;
}

return list;
}
}

и, соответственно, тестовый код

static double MeasureShuffleTime(int[] largeArray, int timesToShuffle)
{
// snip
Shuffle<int>.ShuffleCollection(largeArray);
// snip
}

Меряем еще раз:
10000 - 0.0015
20000 - 0.003
50000 - 0.0075
60000 - 0.008
100000 - 0.017

Вот теперь время выполнения линейно зависит от размера массива.

 

[62316e]

Для: NikSoft
Я видел этот топик поэтому и спросил) Вижу ты просто рожден для того что бы писать статьи)

 

[NikSoft]

Для: 62316e
Да мне нравиться программирование, вообще, и копаться в новых вещах, в частности

 

[Pasha]

Для: NikSoft
Писать статьи - это хорошо. Но нужно еще и реагировать на критику

 

[NikSoft]

Для: Pasha
Да, хорошо.
Как выдаться свободная минутка я посмотрю твои изменения.

 

[Pasha]

Для: NikSoft
заодно посмотри комменты к статье про web-контроллеры

 

[NikSoft]

Для: Pasha
Я пытался передать ClientID web-контроллеру в гриде(тогда не надо парсить клиенские идентификаторы), но компилятор ругается.
Может быть ты что - нибудь найдешь?

 

[Pasha]

Для: NikSoft
Нормального способа, насколько я знаю, нет. Предлагаю привязватся к ItemCreated/DataBound у грида, там искать в ячейках соответствующие друг другу контролы и проставлять TargetControlID для чекбокса.

 

[Pasha]

Для: sax_ol
начало темы про ClientID: https://codeby.net/threads/11623.html

 

[NikSoft]

Для: Pasha
Чтобы разобраться в твоих изменениях приведи полный текст функции MeasureShuffleTime(int[] largeArray, int timesToShuffle)
Не видно, где ты используешь параметр timesToShuffle в функции MeasureShuffleTime

Для: NikSoft
Нормального способа, насколько я знаю, нет. Предлагаю привязватся к ItemCreated/DataBound у грида, там искать в ячейках соответствующие друг другу контролы и проставлять TargetControlID для чекбокса.

Приведи пример

 

[Pasha]

<!--QuoteBegin-NikSoft+17:01:2007, 06:44 -->
<span class="vbquote">(NikSoft @ 17:01:2007, 06:44 )</span><!--QuoteEBegin-->Чтобы разобраться в твоих изменениях приведи полный текст функции MeasureShuffleTime(int[] largeArray, int timesToShuffle)
Не видно, где ты используешь параметр timesToShuffle в функции MeasureShuffleTime

[snapback]53459" rel="nofollow" target="_blank[/snapback]​

[/quote]
текст совпадает с тестом для первого варианта, строчка

shuffle.Next();

заменяется на

Shuffle<int>.ShuffleCollection(largeArray);

результаты изменений - среднее время шаффлинга для timesToShuffle попыток.
для особо ленивых:

		static double MeasureShuffleTime(int[] largeArray, int timesToShuffle)
{
int startTickCount = Environment.TickCount;

for (int i = 0; i < timesToShuffle; i++)
{
Shuffle<int>.ShuffleCollection(largeArray);
}

return (Environment.TickCount - startTickCount) / (double)timesToShuffle;
}

 

[Pasha]

<!--QuoteBegin-NikSoft+17:01:2007, 06:44 -->
<span class="vbquote">(NikSoft @ 17:01:2007, 06:44 )</span><!--QuoteEBegin-->Приведи пример

[snapback]53459" rel="nofollow" target="_blank[/snapback]​

[/quote]
смотри в старом топике.