Shuffle метод

Тема в разделе ".NET", создана пользователем NikSoft, 14 янв 2007.

Статус темы:
Закрыта.
  1. NikSoft

    NikSoft Гость

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

    Код (Text):
    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 приводится ниже.

    Код (Text):
    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 определяется так

    Код (Text):
    namespace ShuffleNik
    {
    class Customer
    {
    string _name;

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

    public string Name
    {
    get{ return _name; }
    }
    }
    }
     
  2. 62316e

    62316e Гость

    А где суть?
     
  3. NikSoft

    NikSoft Гость

  4. Pasha

    Pasha Гость

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

    Изменяем немного шаффлер.
    Код (Text):
    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;
    }
    }
    и, соответственно, тестовый код
    Код (Text):
    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

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

    62316e Гость

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

    NikSoft Гость

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

    Pasha Гость

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

    NikSoft Гость

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

    Pasha Гость

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

    NikSoft Гость

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

    Pasha Гость

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

    Pasha Гость

  13. NikSoft

    NikSoft Гость

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

    Приведи пример
     
  14. Pasha

    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]
    текст совпадает с тестом для первого варианта, строчка
    Код (Text):
    shuffle.Next();
    заменяется на
    Код (Text):
    Shuffle<int>.ShuffleCollection(largeArray);
    результаты изменений - среднее время шаффлинга для timesToShuffle попыток.
    для особо ленивых:
    Код (Text):
            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;
    }
     
  15. Pasha

    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]
    смотри в старом топике.
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей