Увеличение и уменьшение списка <int>по сравнению с массивом bool большого размера с использованием индекса в качестве значения - PullRequest
Новая
       14

Увеличение и уменьшение списка <int>по сравнению с массивом bool большого размера с использованием индекса в качестве значения

0 голосов
/ 20 декабря 2018

Я не могу определить, будет ли более эффективным использование в моем приложении растущего и уменьшающегося Списка по сравнению с использованием массива Big Bool.

Чтобы подробнее остановиться на этом сравнении и реальной ситуации, вот примерыкаждый вариант, который, как я считаю, у меня есть:

Вариант 1 (список): 

public List<int> list = new List<int>();
while (true) { // game loop
    list.Add(Random.Range(0-300));
    list.Add(Random.Range(0-300));
    ...  // maximum of 10 of these can happen

    if (list.Contains(42)) { // roughly 10 - 50 of these checks can be true
        list.Remove(42);
    }
}

Вариант 2 (массив): 

bool[] arr = new bool[300];
while (true) { // game loop
    arr[Random.Range(0-300)] = true;
    arr[Random.Range(0-300)] = true;
    ... // maximum of 10 of these can happen

    for (int i = 0; i < 300; i++) {
        if (arr[i]) { // roughly 10 - 50 of these checks can be true
            arr[i] = false;
        }
    }
}

По сути, мой вопрос таков:

В какой момент слишком большое количество проверок .Contains становится дороже, чем цикл for для каждого возможного элемента (в зависимости от моих диапазонов)?

ВАЖНО

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

Ответы [ 2 ]

0 голосов
/ 20 декабря 2018

Я бы сказал, что реализация массива будет намного быстрее.В дополнение к стоимости изменения размера массива при вызове List.Add(T) или List.Remove(T), если вы проверите код реализации List .Вы заметите, что List.Contains(T) и List.Remove(T) оба используют IndexOf(T), в котором, я полагаю, есть цикл / итерация внутри списка.В вашем примере вы хотите звонить List.Contains(T) и List.Remove(T) примерно в 10-50 раз.Это означает, что в лучшем случае это будет стоить вам 20 (содержит + удалить), но в худшем случае это будет стоить (N * 50) + N, где N - количество элементов в вашем списке.

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

Если вы больше ориентируетесь на производительность, возможно, стоит взглянуть на HashSet структуру данных.Он имеет лучшую производительность в look up и remove операциях, чем List.

0 голосов
/ 20 декабря 2018

Вот интересная запись для массива vs List для обоих, foreach, EnumerableForEach и Sum от Jon Skeet:

https://codeblog.jonskeet.uk/2009/01/29/for-vs-foreach-on-arrays-and-lists/

В соответствии со статьей производительность выглядит следующим образом:

============ int[] ============
For                 1.00
ForHoistLength      2.03
ForEach             1.36
IEnumerableForEach 15.22
Enumerable.Sum     15.73

============ List<int> ============
For                 2.82
ForHoistLength      3.49
ForEach             4.78
IEnumerableForEach 25.71
Enumerable.Sum     26.03

Результаты можно количественно оценить, например, как массив int для цикла for в 2,8 раза быстрее.Если вы знаете размер массива и его фиксированный размер, используйте Array, иначе List.

Вот еще одна ссылка: Производительность массивов и списков

, а такжедержитесь подальше от Linq для больших данных и используйте циклы for / foreach.

...