C# посоветуйте структуру для хранения данных
Сколько связей в среднем у файла? Почему положительные ответы не кешируешь?
поправлюсь. кэширую и положительные связи. в среднем около 6-8 связей, однако есть около 20 файлов с 80-90.
до этого был адский затык с множественным обращением к содержимому файлов (вычленить из строки M символы с N до N+100 сделал кэширующее чтение, с построением индекса по строкам, убрал проверки по нахождению индексов в диапазонах, оставив вместо этого исключения - помогло, ускорив программу с 1 часа до 10 минут. 10 минут тоже можно убрать до 1-2х, но как - пока не понятно.
до этого был адский затык с множественным обращением к содержимому файлов (вычленить из строки M символы с N до N+100 сделал кэширующее чтение, с построением индекса по строкам, убрал проверки по нахождению индексов в диапазонах, оставив вместо этого исключения - помогло, ускорив программу с 1 часа до 10 минут. 10 минут тоже можно убрать до 1-2х, но как - пока не понятно.
Ты не указал некоторые существенные вещи. Например:
- Должна ли структура поддерживать модификации? Или она строится один раз для набора файлов / связей, и потом для этого фиксированного графа многократно делаются запросы?
- Циклические зависимости возможны?
- Должна ли структура поддерживать модификации? Или она строится один раз для набора файлов / связей, и потом для этого фиксированного графа многократно делаются запросы?
- Циклические зависимости возможны?
структура строится 1 раз. отдельно кешируются новые найденные связи, иначе все распухает, как пирог, и все становится еще медленнее.
циклических зависимостей не должно быть, но все может быть, ибо работаю с плохим, полумертвым кодом.
циклических зависимостей не должно быть, но все может быть, ибо работаю с плохим, полумертвым кодом.
я не знаю (или не помню) как решается твоя задача, но могу помочь тем, что знаю как она называется
один раз при старте:
зависимости сортируются топологической сортировкой, и заполняется двухмерная таблица file[n]*file[n], значением массива является да, можно попасть;, нет, нельзя попасть.
если памяти под такую таблицу жалко, то заполняется Array<Set<int>>, и хранятся только возможные переходы
дальше все запросы обрабатываются за O(1)
ps
каноническая топологическая сортировка считает, что отношения строго меньше, и циклы невозможно, но ее несложно доработать до варианта, когда отношения рассматриваются как меньше или равно, тогда если цикл встречается, то все вершины внутри цикла считаются равными (стягиваются в одну точку и сортировка продолжается
зависимости сортируются топологической сортировкой, и заполняется двухмерная таблица file[n]*file[n], значением массива является да, можно попасть;, нет, нельзя попасть.
если памяти под такую таблицу жалко, то заполняется Array<Set<int>>, и хранятся только возможные переходы
дальше все запросы обрабатываются за O(1)
ps
каноническая топологическая сортировка считает, что отношения строго меньше, и циклы невозможно, но ее несложно доработать до варианта, когда отношения рассматриваются как меньше или равно, тогда если цикл встречается, то все вершины внутри цикла считаются равными (стягиваются в одну точку и сортировка продолжается
Оставить комментарий
AE169
Есть зависимости по включению между файлами в виде:файл -> файл1
файл -> файл2
файл -> файл3
файл2-> файлN
файл2-> файлN+1
Запрос - можно ли из файлаN попасть в файлM путем последовательности переходов.
Пока решается очень гандовым алгоритмом - а именно, рекурсивный проход от файлаN вглубь с запоминанием узлов, которые уже посетил. Одновременно, при ответе "НЕТ" на запрос - данный результат кэшируется системой.
Пока все зависимости хранятся в виде Dictionary<int,List<int>>, где инты - уникальные идентификаторы файлов. Можно придумать какую-то более "быструю" структуру(или все же необходимо заменить рекурсивный обход в глубь на что-то другое так как анализ показывает, что большинство времени здесь проводится на Dictionary.ContainsKey - все это довольно долго работает при 10000 записях вида "файл -> файл1", когда обрабатывается запрос о несколько миллионах связей.