Цитата romeo91:
В текущей версии парсера обнаружил несколько нюансов.
Парсер не корректно вносит данные по HWID, если в HWID есть переменные %%
А также в наименовании устройства если переменная это часть наименования.
|
Я в курсе этого. Я все откладывал это на потом, поскольку правильная обработка этих (довольно редких) случаев замедлила бы весь процесс индексации, что было бы неудобно для отладки парсера. В результате я это так и не доделал.
Меня этот парсер на регулярных выражениях больше не интересует. Это может быть самой оптимальным решением под VBScript/JavaScript, но на более полноценных языках программирования можно сделать гораздо лучше.
Цитата romeo91:
Также не до конца понятно. Насколько я понял работа с hash-таблицами возможна только на отсортированных массивах. Но сортировка в DRP по HWID мне не понятна. Он не сортирует реально по всем HWID? т.е. начало определенного HWID может встретится не в строках подряд, а в любом месте файла базы данных.
Из-за этого может получится что программа, может находить не все совпадения?
|
Я бы советовал сначала ознакомится с общим принципом работы hash-таблиц.
Вот технические детали моей реализации hash-таблиц:
1. В качестве ключа в хешах используется хеш код HWIDа.
2. Сортировка осуществляется по хеш кодам HWIDов.
3. Сортируется алгоритмом QuickSort. Это наиболее быстрый алгоритм, но он относится к нестабильным(равноценные элементы могут помнятся местами) и при наихудшем возможном случае у него средние показатели. Стабильность в нашем случае не важна, а наихудший случай редко происходит.
4. Расположение записей в индексах можно условно назвать случайным. Однако они расположены таким образом что записи с одинаковых хеш кодом всегда находятся подряд. Именно это свойство позволяет при поиске обойтись анализом только одной тысячной части от всех записей.
Цитата romeo91:
|
У себя в программе я сделал сортировку по HWID в алфавитном порядке, можете сравнить.
|
Ты это сделал чтобы искать HWIDы методом бинарного поиска? Этот метод в среднем имеет логарифмическую сложность(для 100 000 HWIDов нужно в среднем 17 проверок, для 100 000 000 в среднем 26). hash-таблицы в среднем находят в среднем с 3-4 проверок, независимо от размера индексов.
Также группировка HWIDов с одинаковых хеш рядом кодом позволяет загрузить блок с нужными HWIDами за одну операцию чтения. В случае с бинарным поиском рассматриваемые HWIDы могут находится в разных концах индексов.
При использовании хеш таблиц индексы даже не нужно полностью загружать в память. DPS достаточно было загрузить только 2.7МБ из 40МБ. Бинарный поиск пожалуй все-таки требует полной загрузки индексов, Windows и HDD не могут быстро выполнять запросы по чтению мелких кусков данных, которые расположены не подряд.
