Я пытаюсь реализовать алгоритм поиска нескольких файлов XML для определенной записи. известно, что записи не сортируются (у меня нет индексированного идентификатора). Какой самый быстрый алгоритм для поиска этой записи?
пожалуйста, дайте мне знать, если что-то неясно,
заранее спасибобыстрый алгоритм поиска
galambalazs правильно: Unsorted данных означает, что вы должны пройти через все это, чтобы искать то, что вам нужно. Но это касается лишь небольшой части вопроса.
При обработке нескольких файлов, вероятно, большая часть вашего времени обработки будет занята файлами ввода-вывода. Чтобы найти файл в каталоге и открыть его, компьютерным стандартам требуется много времени. Но это стоимость, которую вы понесете в основном независимо от того, какую программу вы в конечном итоге используете.
Другая часть уравнения производительности - это тот парсер, который вы используете. В зависимости от структуры вашего XML, у вас есть выбор, используя рукописный парсер, парсер DOM XML или парсер Sax.
Если метки, связанные с вашими запрошенными данными, всегда встречаются на той же строке, что и эти данные, и нет никакой двусмысленности, то чтение строки по строке и поиск по строковому запросу или регулярному выражению являются допустимой возможностью. Многие люди на SO протестуют против того, что соответствие регулярному выражению является ужасным способом обработки XML, и это, как правило, правильно; это быстрый и грязный способ выполнять поиск в очень специфическом и ограниченном наборе случаев и очень хрупкий по отношению к структуре XML, с которой вы в конечном итоге работаете.
DOM-парсер «вдыхает» весь ваш XML-документ в структуру памяти, которую ваше приложение затем может искать последовательно, независимо от того, что это такое. DOM отлично подходят, если вы хотите выполнить ряд сложных операций над деревом XML; для последовательного поиска это ужасная идея, потому что
Поэтому самым рекомендуемым подходом было бы использовать синтаксический анализатор SAX. Googling найдет вас одним для вашего любимого языка. Анализатор SAX сканирует ваш входной файл один раз, создавая события в каждом элементе, который вы можете (и должен!) Обрабатывать соответствующим образом.Данные обрабатываются последовательно, и нет другого хранилища, кроме того, что вы решите делать с данными, которые вы находите. Анализаторы SAX обычно значительно быстрее, чем DOM-парсеры, но для планирования событий требуется небольшое планирование.
Также можно использовать XPath. Хотя важны детали реализации. Например. по умолчанию реализация Java XPath основана на DOM-парсере, насколько я помню, таким образом, наследуя все ее последствия для производительности. Но XPath настолько выразителен, что в случае избыточного веса в случаях =) – Rorick
Теперь, когда вы упомянули об этом, разумным и очень «XML-y» способом сделать это может быть использование XSLT для преобразования входного документа XML в произвольный выходной документ, содержащий просто строки поиска. Апелляция здесь заключается в том, что вполне возможно подключить трансформатор к источнику SAX, таким образом, гарантируя (возможно?), Что вход будет обрабатываться последовательно. Это позволило бы объединить выразительность выражений XPath для определения поиска со скоростью анализа SAX. –
Без сортировки линейного поиска является лучшим выбором. Думаю об этом.
И как я уже сказал в комментариях: имеет значение, если вы хотите искать один или несколько раз. Потому что тогда вам может понадобиться создать индекс. Но если вы будете искать только один раз, это будет бесполезно.
Последовательный поэтапный поиск приходит в голову. Используйте несколько потоков для одновременного приема нескольких файлов.
Если все они находятся на одном и том же дисководе, то поиск будет, скорее всего, связан с I/O-привязкой, и многопоточность потоков не принесет особых результатов. –
Очень верно, но вы не будете знать, откуда они взялись или насколько они велики. Кроме того, это зависит от того, как вы передаете файл по очереди или сначала загрузите его в память, а затем проанализируйте. –
Это действительно зависит от того, как часто вы хотите выполнять задачу над этими файлами. Если записи не отсортированы, вы можете выполнять поиск по ним только линейно. Но если вам нужно делать это чаще всего в одном наборе записей, вы можете создать индекс или отсортировать его во время первого запуска.
Все, что вам нужно решить здесь Sorting Algorithms
Естественно звучит так, что вы должны предварительно обрабатывать XML-файлы и создавать индекс для облегчения быстрого поиска. – polygenelubricants
Да, это важно, если вы хотите искать один или несколько раз. Потому что тогда вам может понадобиться создать индекс. Но если вы будете искать только один раз, это будет бесполезно. – galambalazs
Интересный вопрос. Интересно, когда мы увидим некоторые отзывы от Moayyad, особенно в отношении вопроса о разном или множественном доступе? –