Что плохого в производительности с этим кодом? List.Contains, случайное использование, многопоточность?

Question

У меня есть локальный класс с методом, используемым для построения списка строк, и я обнаружил, что когда я нажимаю этот метод (в цикле for 1000 раз), он часто не возвращает сумму, которую я запрашиваю.

У меня есть глобальная переменная:

string[] cachedKeys

Параметр, переданный методу:

int requestedNumberToGet

Метод выглядит примерно так:

List<string> keysToReturn = new List<string>();
int numberPossibleToGet = (cachedKeys.Length <= requestedNumberToGet) ? 
cachedKeys.Length : requestedNumberToGet;
Random rand = new Random();

DateTime breakoutTime = DateTime.Now.AddMilliseconds(5);

//Do we have enough to fill the request within the time? otherwise give 
//however many we currently have
while (DateTime.Now < breakoutTime
    && keysToReturn.Count < numberPossibleToGet
    && cachedKeys.Length >= numberPossibleToGet)
{
    string randomKey = cachedKeys[rand.Next(0, cachedKeys.Length)];
    if (!keysToReturn.Contains(randomKey))
        keysToReturn.Add(randomKey);
}

if (keysToReturn.Count != numberPossibleToGet)
    Debugger.Break();

У меня есть приблизительно 40 строк в cachedKeys, длина которых не превышает 15 символов.

Я не эксперт по многопоточности, поэтому буквально просто вызываю этот метод 1000 раз в цикле и последовательно выполняю там отладку.

Машина, на которой он работает, является довольно мощным рабочим столом, поэтому я ожидаю, что время прорыва будет реалистичным, фактически оно случайным образом прерывается в любой точке цикла (я видел 20, 100, 200, 300).

У кого-нибудь есть идеи, где я ошибаюсь?

Редактировать: ограничено .NET 2.0

Редактировать: цель прорыва заключается в том, что если выполнение метода занимает слишком много времени, клиенту (несколько веб-серверов, использующих данные для каналов XML) не придется ждать, пока другие зависимости проекта инициализировать, им просто дадут 0 результатов.

Редактировать: думал, что я опубликую характеристики производительности

Оригинал

• 0,0042477465711424217323710136 '- 10
• '0,0479597267250446634977350473' - 100
• '0,4721072091564710039963179678' - 1000

Скит

• '0,0007076318358897569383818334' - 10
• 0,007256508857969378789762386 '- 100
• 0.0749829936486341141122684587 '- 1000

Фредди Риос

• 0.0003765841748043396576939248 '- 10
• 0,0046003053460705201359390649 '- 100
• '0,0417058592642360970458535931' - 1000

Answer 1

Почему бы просто не взять копию списка - O (n) - перемешать ее, также O (n) - и затем вернуть количество ключей, которые были запрошены. Фактически, для перемешивания нужно только O (nRequested). Поменяйте местами случайный элемент не перетасованного бита списка с самого начала не перетасованного бита, затем увеличьте перетасованный бит на 1 (просто условный счетчик).

РЕДАКТИРОВАТЬ: Вот код, который выдает результаты в виде IEnumerable<T>. Обратите внимание, что он использует отложенное выполнение, поэтому, если вы измените источник, который был передан до того, как вы начнете перебирать результаты, вы увидите эти изменения. После получения первого результата элементы будут кэшированы.

static IEnumerable<T> TakeRandom<T>(IEnumerable<T> source,
                                    int sizeRequired,
                                    Random rng)
{
    List<T> list = new List<T>(source);

    sizeRequired = Math.Min(sizeRequired, list.Count);

    for (int i=0; i < sizeRequired; i++)
    {
        int index = rng.Next(list.Count-i);            
        T selected = list[i + index];
        list[i + index] = list[i];
        list[i] = selected;
        yield return selected;
    }
}

Идея состоит в том, что в любой момент после того, как вы извлекли n элементы, первыми n элементами списка будут эти элементы - поэтому мы уверены, что не выберем их снова. Когда затем выберите случайный элемент из «остальных», поменяйте его в правильную позицию и получите его.

Надеюсь, это поможет. Если вы используете C # 3, вы можете захотеть сделать это методом расширения, поставив «this» перед первым параметром.

Answer 2

Основной проблемой является использование повторов в случайном сценарии, чтобы обеспечить получение уникальных значений. Это быстро выходит из-под контроля, особенно если количество запрашиваемых предметов близко к количеству предметов, которые необходимо получить, т. Е. Если вы увеличите количество ключей, вы увидите проблему реже, но этого можно избежать.

Следующий метод делает это, сохраняя список оставшихся ключей.

List<string> GetSomeKeys(string[] cachedKeys, int requestedNumberToGet)
{
    int numberPossibleToGet = Math.Min(cachedKeys.Length, requestedNumberToGet);
    List<string> keysRemaining = new List<string>(cachedKeys);
    List<string> keysToReturn = new List<string>(numberPossibleToGet);
    Random rand = new Random();
    for (int i = 0; i < numberPossibleToGet; i++)
    {
        int randomIndex = rand.Next(keysRemaining.Count);
        keysToReturn.Add(keysRemaining[randomIndex]);
        keysRemaining.RemoveAt(randomIndex);
    }
    return keysToReturn;
}

Тайм-аут был необходим для вашей версии, так как вы могли бы продолжать попытки получить значение в течение длительного времени. Особенно, когда вы хотите получить весь список, и в этом случае вы почти наверняка получите ошибку с версией, основанной на повторных попытках.

Обновление: Выше работает лучше, чем эти варианты:

List<string> GetSomeKeysSwapping(string[] cachedKeys, int requestedNumberToGet)
{
    int numberPossibleToGet = Math.Min(cachedKeys.Length, requestedNumberToGet);
    List<string> keys = new List<string>(cachedKeys);
    List<string> keysToReturn = new List<string>(numberPossibleToGet);
    Random rand = new Random();
    for (int i = 0; i < numberPossibleToGet; i++)
    {
        int index = rand.Next(numberPossibleToGet - i) + i;
        keysToReturn.Add(keys[index]);
        keys[index] = keys[i];
    }
    return keysToReturn;
}
List<string> GetSomeKeysEnumerable(string[] cachedKeys, int requestedNumberToGet)
{
    Random rand = new Random();
    return TakeRandom(cachedKeys, requestedNumberToGet, rand).ToList();
}

Некоторые числа с 10.000 итераций:

Function Name    Elapsed Inclusive Time Number of Calls
GetSomeKeys              6,190.66       10,000
GetSomeKeysEnumerable     15,617.04       10,000
GetSomeKeysSwapping        8,293.64       10,000

Answer 3

Несколько мыслей.

Во-первых, ваш список keysToReturn потенциально добавляется в каждый раз через цикл, верно? Вы создаете пустой список, а затем добавляете каждый новый ключ в список. Поскольку список не был предварительно настроен, каждое добавление становится операцией O (n) ( см. Документацию MSDN ). Чтобы это исправить, попробуйте предварительно изменить размер списка следующим образом.

int numberPossibleToGet = (cachedKeys.Length <= requestedNumberToGet) ? cachedKeys.Length : requestedNumberToGet;
List<string> keysToReturn = new List<string>(numberPossibleToGet);

Во-вторых, ваше время прорыва нереально (хорошо, хорошо, невозможно) в Windows. Вся информация, которую я когда-либо читал о времени Windows, предполагает, что лучшее, на что вы можете надеяться, это разрешение 10 миллисекунд, но на практике это больше похоже на 15-18 миллисекунд. На самом деле, попробуйте этот код:

for (int iv = 0; iv < 10000; iv++) {
    Console.WriteLine( DateTime.Now.Millisecond.ToString() );
}

То, что вы увидите на выходе, это дискретные прыжки. Вот пример вывода, который я только что запустил на своей машине.

13
...
13
28
...
28
44
...
44
59
...
59
75
...

Значение миллисекунды изменяется с 13 до 28 до 44 до 59 до 75. Это примерно 15-16 миллисекундное разрешение в функции DateTime.Now для моей машины. Это поведение согласуется с тем, что вы увидите в вызове C времени выполнения ftime (). Другими словами, это системная черта механизма синхронизации Windows. Дело в том, что вы не должны полагаться на постоянное время прорыва 5 миллисекунд, потому что вы его не получите.

В-третьих, я прав, предполагая, что время прорыва препятствует блокировке основного потока? Если это так, то было бы довольно легко создать свою функцию в потоке ThreadPool и позволить ей запускаться до конца независимо от того, сколько времени это займет. Ваш основной поток может затем работать с данными.

Answer 4

Вместо этого используйте HashSet, HashSet намного быстрее для поиска, чем List

HashSet<string> keysToReturn = new HashSet<string>();
int numberPossibleToGet = (cachedKeys.Length <= requestedNumberToGet) ? cachedKeys.Length : requestedNumberToGet;
Random rand = new Random();

DateTime breakoutTime = DateTime.Now.AddMilliseconds(5);
int length = cachedKeys.Length;

while (DateTime.Now < breakoutTime && keysToReturn.Count < numberPossibleToGet) {
    int i = rand.Next(0, length);
    while (!keysToReturn.Add(cachedKeys[i])) {
        i++;
        if (i == length)
            i = 0;
    }
}

Answer 5

Попробуйте использовать Stopwatch вместо DateTime.Now. Это может быть просто из-за неточности DateTime.Now, когда вы говорите о миллисекундах.

Answer 6

Проблема вполне может быть здесь:

if (!keysToReturn.Contains(randomKey))
    keysToReturn.Add(randomKey);

Для этого потребуется выполнить итерацию по списку, чтобы определить, находится ли ключ в списке возврата. Однако, чтобы быть уверенным, вы должны попытаться профилировать это с помощью инструмента. Кроме того, 5 мс - это довольно быстрое время за 0,005 секунды, вы можете увеличить его.