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

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 будет п^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% обо всех деталях проблемы. Например, может ли у вас дублировать? Если да, то имеет значение порядок подсписей? В зависимости от ответов на них вы можете быть вынуждены перекочевать или модифицировать такой алгоритм. Кроме того, это, очевидно, будет использовать больше памяти.