достаточно забавно, это, вероятно, проблема переполнения стека

Question

Следующая процедура (пояснение приведено ниже) отлично работает для действительно небольших списков, но когда список содержит большее количество элементов (1/2 миллиона), приложение переходит в состояние «не отвечает», и для его завершения требуется около 2,5 минут (очень плохое время). Я мог бы добавить, что приложение должно обрабатывать списки из 100 миллионов элементов по крайней мере (в конце концов).

вот код для проблемной процедуры:

    public void removeItems(List<long> L, SortedList<long, List<long>> _subLists)
    {
        foreach (KeyValuePair<long, List<long>> kvp in _subLists)
        {
            foreach (long duplicate in kvp.Value)
            {
                int j = L.IndexOf(duplicate);
                L.RemoveRange(j,(int)kvp.Key); 

            }
        }
    }

L - список длинных значений. _subLists представляет собой отсортированный список, где каждое значение представляет собой список значения от L, начиная ряд арифметической прогрессии некоторой разницы (не имеет значения). ключ, связанный с этим значением, является длиной ряда, который содержат значения.

Пример:

L = {1,2,3,5,6,7,18,20,21} _subLists = {2, <20>} {3, <1,5>}

Процедура просто удаляет ряд арифметической прогрессии из L.

Answer 1

Время выполнения этой процедуры в больших обозначениях O будет равно n ^ 2, что довольно медленно, и вы можете ожидать медленного времени выполнения, если в одном из списков есть 100 миллионов записей. Здесь нет проблемы переполнения стека, просто слишком медленно перебирать столько данных. Я не вижу здесь вопроса, вы хотите сделать это быстрее? Если это так, то вложенный цикл определенно является проблемой.

Answer 2

Ваша проблема в том, что вы удаляете много элементов из L, что является очень дорогостоящей операцией. Каждый раз, когда элемент удаляется, память копируется, чтобы переместить все элементы над удаленными элементами вниз. Чем больше элементов будет удалено и чем больше элементов будет перетасовано, тем больше времени потребуется. Память является узким местом для производительности, ОЗУ работает медленнее, чем ЦП, и если вы выполняете подкачку на диск, то это действительно медленно.

Как вы можете улучшить это.

Самый простой вариант - использовать контейнер для L, который имеет лучшую производительность при удалении элементов - например, LinkedList. LinkedLists не нужно перемещать элементы в памяти, когда элементы удалены, но им требуется больше памяти для хранения данных (два указателя на значение). Если это слишком много служебной информации, тогда, возможно, вместо LinkedList <List <long>>, где каждый List <long> содержит максимальное количество значений.

Либо измените алгоритм удаления, чтобы выполнить итерацию по списку L и создать новый список, содержащий значения, отсутствующие в _subLists. Вы можете изменить способ хранения данных в _subLists, чтобы ускорить поиск элементов в диапазонах.

Answer 3

Если возможно:

A) Конвертировать L в отсортированный связанный список. O: n * log (n)

B) Преобразовать подсписки в пары отсортированных списков, где первый элемент - это # ​​в последовательности в L (дублируется в фрагменте размещенного кода), а второй элемент - это длина последовательности. O: n * log (n)

C) Выполните один проход через L, используя подсписки, чтобы определить, сколько элементов нужно удалить в данном месте в L. Воспользуйтесь преимуществом того факта, что оба списка отсортированы так, что они не возвращаются ни в один из списков. O: n

Должно быть в состоянии получить сложность O: n * log (n), если это возможно. Конечно, я не уверен на 100% во всех деталях проблемы. Например - может ли L иметь дубликаты? Если да, имеет ли значение порядок подсписков? Вы можете быть вынуждены отказаться от такого алгоритма или изменить его в зависимости от ответов на эти вопросы. Кроме того, это, очевидно, будет использовать больше памяти.