Оптимизировать разбор строк
У меня есть требование для анализа файлов данных в формате "TXF". Файлы могут содержать более 1000 записей. Поскольку формат хорошо определен, как JSON, я хотел создать универсальный синтаксический анализатор, такой как JSON, который может сериализовать и десериализовывать файлы txf.
В отличие от JSON, разметка не может идентифицировать объект или массив. Если происходит запись с таким же тегом, мы должны рассматривать его как массив.
#Отмечает начало объекта.$Отмечает членов объекта/Отмечает конец объекта
Ниже приведен пример файла "TXF"
#Employees
$LastUpdated=2015-02-01 14:01:00
#Employee
$Id=1
$Name=Employee 01
#Departments
$LastUpdated=2015-02-01 14:01:00
#Department
$Id=1
$Name=Department Name
/Department
/Departments
/Employee
#Employee
/Employee
/Employees
Мне удалось создать универсальный анализатор TXF с помощью NSScanner. Но с большим количеством записей производительность нуждается в большем количестве настроек.
Я написал фундаментальный объект, полученный как plist и снова сравнил его производительность с парсером, который я написал. Мой парсер примерно в 10 раз медленнее, чем plist синтаксический анализатор.
В то время как plist размер файла в 5 раз больше txf и имеет больше символов разметки, я чувствую, что есть много места для оптимизации.
Любая помощь в этом направлении высоко ценится.
РЕДАКТИРОВАТЬ: Включая код синтаксического анализа
static NSString *const kArray = @"TXFArray";
static NSString *const kBodyText = @"TXFText";
@interface TXFParser ()
/*Temporary variable to hold values of an object*/
@property (nonatomic, strong) NSMutableDictionary *dict;
/*An array to hold the hierarchial data of all nodes encountered while parsing*/
@property (nonatomic, strong) NSMutableArray *stack;
@end
@implementation TXFParser
#pragma mark - Getters
- (NSMutableArray *)stack{
if (!_stack) {
_stack = [NSMutableArray new];
}return _stack;
}
#pragma mark -
- (id)objectFromString:(NSString *)txfString{
[txfString enumerateLinesUsingBlock:^(NSString *string, BOOL *stop) {
if ([string hasPrefix:@"#"]) {
[self didStartParsingTag:[string substringFromIndex:1]];
}else if([string hasPrefix:@"$"]){
[self didFindKeyValuePair:[string substringFromIndex:1]];
}else if([string hasPrefix:@"/"]){
[self didEndParsingTag:[string substringFromIndex:1]];
}else{
//[self didFindBodyValue:string];
}
}]; return self.dict;
}
#pragma mark -
- (void)didStartParsingTag:(NSString *)tag{
[self parserFoundObjectStartForKey:tag];
}
- (void)didFindKeyValuePair:(NSString *)tag{
NSArray *components = [tag componentsSeparatedByString:@"="];
NSString *key = [components firstObject];
NSString *value = [components lastObject];
if (key.length) {
self.dict[key] = value?:@"";
}
}
- (void)didFindBodyValue:(NSString *)bodyString{
if (!bodyString.length) return;
bodyString = [bodyString stringByTrimmingCharactersInSet:[NSCharacterSet illegalCharacterSet]];
if (!bodyString.length) return;
self.dict[kBodyText] = bodyString;
}
- (void)didEndParsingTag:(NSString *)tag{
[self parserFoundObjectEndForKey:tag];
}
#pragma mark -
- (void)parserFoundObjectStartForKey:(NSString *)key{
self.dict = [NSMutableDictionary new];
[self.stack addObject:self.dict];
}
- (void)parserFoundObjectEndForKey:(NSString *)key{
NSDictionary *dict = self.dict;
//Remove the last value of stack
[self.stack removeLastObject];
//Load the previous object as dict
self.dict = [self.stack lastObject];
//The stack has contents, then we need to append objects
if ([self.stack count]) {
[self addObject:dict forKey:key];
}else{
//This is root object,wrap with key and assign output
self.dict = (NSMutableDictionary *)[self wrapObject:dict withKey:key];
}
}
#pragma mark - Add Objects after finding end tag
- (void)addObject:(id)dict forKey:(NSString *)key{
//If there is no value, bailout
if (!dict) return;
//Check if the dict already has a value for key array.
NSMutableArray *array = self.dict[kArray];
//If array key is not found look for another object with same key
if (array) {
//Array found add current object after wrapping with key
NSDictionary *currentDict = [self wrapObject:dict withKey:key];
[array addObject:currentDict];
}else{
id prevObj = self.dict[key];
if (prevObj) {
/*
There is a prev value for the same key. That means we need to wrap that object in a collection.
1. Remove the object from dictionary,
2. Wrap it with its key
3. Add the prev and current value to array
4. Save the array back to dict
*/
[self.dict removeObjectForKey:key];
NSDictionary *prevDict = [self wrapObject:prevObj withKey:key];
NSDictionary *currentDict = [self wrapObject:dict withKey:key];
self.dict[kArray] = [@[prevDict,currentDict] mutableCopy];
}else{
//Simply add object to dict
self.dict[key] = dict;
}
}
}
/*Wraps Object with a key for the serializer to generate txf tag*/
- (NSDictionary *)wrapObject:(id)obj withKey:(NSString *)key{
if (!key ||!obj) {
return @{};
}
return @{key:obj};
}
РЕДАКТИРОВАТЬ 2:
Пример файла TXF с более чем 1000 записей.
2 ответа
Рассматривали ли вы использование чтения и рекурсивной обработки в стиле pull? Это исключило бы чтение всего файла в память, а также исключило бы управление собственным стеком для отслеживания глубины анализа.
Ниже приведен пример в Swift. Пример работает с вашим примером "txf", но не с версией dropbox; некоторые из ваших "членов" занимают несколько строк. Если это требование, оно может быть легко реализовано в switch/case "$" раздел. Однако я не вижу, чтобы ваш собственный код обрабатывал это. Кроме того, пример пока не соответствует правильной обработке ошибок Swift (parse метод потребует дополнительного NSError параметр)
import Foundation
extension String
{
public func indexOfCharacter(char: Character) -> Int? {
if let idx = find(self, char) {
return distance(self.startIndex, idx)
}
return nil
}
func substringToIndex(index:Int) -> String {
return self.substringToIndex(advance(self.startIndex, index))
}
func substringFromIndex(index:Int) -> String {
return self.substringFromIndex(advance(self.startIndex, index))
}
}
func parse(aStreamReader:StreamReader, parentTagName:String) -> Dictionary<String,AnyObject> {
var dict = Dictionary<String,AnyObject>()
while let line = aStreamReader.nextLine() {
let firstChar = first(line)
let theRest = dropFirst(line)
switch firstChar! {
case "$":
if let idx = theRest.indexOfCharacter("=") {
let key = theRest.substringToIndex(idx)
let value = theRest.substringFromIndex(idx+1)
dict[key] = value
} else {
println("no = sign")
}
case "#":
let subDict = parse(aStreamReader,theRest)
var list = dict[theRest] as? [Dictionary<String,AnyObject>]
if list == nil {
dict[theRest] = [subDict]
} else {
list!.append(subDict)
}
case "/":
if theRest != parentTagName {
println("mismatch... [\(theRest)] != [\(parentTagName)]")
} else {
return dict
}
default:
println("mismatch... [\(line)]")
}
}
println("shouldn't be here...")
return dict
}
var data : Dictionary<String,AnyObject>?
if let aStreamReader = StreamReader(path: "/Users/taoufik/Desktop/QuickParser/QuickParser/file.txf") {
if var line = aStreamReader.nextLine() {
let tagName = line.substringFromIndex(advance(line.startIndex, 1))
data = parse(aStreamReader, tagName)
}
aStreamReader.close()
}
println(JSON(data!))
И StreamReader был заимствован из /questions/25965830/chitat-fajl-url-postrochno-v-swift/25965846#25965846
редактировать
- см полный код https://github.com/tofi9/QuickParser
- построчное чтение в стиле pull-in в target -c: Как читать данные из NSFileHandle построчно?
Редактировать 2
Я переписал вышеупомянутое в C++11 и заставил его работать менее чем за 0,05 секунды (режим выпуска) на MBA I5 2012 года, используя обновленный файл в Dropbox. Я подозреваю NSDictionary а также NSArray должен иметь некоторое наказание. Приведенный ниже код может быть скомпилирован в проект target-c (для файла требуется расширение.mm):
#include <iostream>
#include <sstream>
#include <string>
#include <fstream>
#include <map>
#include <vector>
using namespace std;
class benchmark {
private:
typedef std::chrono::high_resolution_clock clock;
typedef std::chrono::milliseconds milliseconds;
clock::time_point start;
public:
benchmark(bool startCounting = true) {
if(startCounting)
start = clock::now();
}
void reset() {
start = clock::now();
}
double elapsed() {
milliseconds ms = std::chrono::duration_cast<milliseconds>(clock::now() - start);
double elapsed_secs = ms.count() / 1000.0;
return elapsed_secs;
}
};
struct obj {
map<string,string> properties;
map<string,vector<obj>> subObjects;
};
obj parse(ifstream& stream, string& parentTagName) {
obj obj;
string line;
while (getline(stream, line))
{
auto firstChar = line[0];
auto rest = line.substr(1);
switch (firstChar) {
case '$': {
auto idx = rest.find_first_of('=');
if (idx == -1) {
ostringstream o;
o << "no = sign: " << line;
throw o.str();
}
auto key = rest.substr(0,idx);
auto value = rest.substr(idx+1);
obj.properties[key] = value;
break;
}
case '#': {
auto subObj = parse(stream, rest);
obj.subObjects[rest].push_back(subObj);
break;
}
case '/':
if(rest != parentTagName) {
ostringstream o;
o << "mismatch end of object " << rest << " != " << parentTagName;
throw o.str();
} else {
return obj;
}
break;
default:
ostringstream o;
o << "mismatch line " << line;
throw o.str();
break;
}
}
throw "I don't know why I'm here. Probably because the file is missing an end of object marker";
}
void visualise(obj& obj, int indent = 0) {
for(auto& property : obj.properties) {
cout << string(indent, '\t') << property.first << " = " << property.second << endl;
}
for(auto& subObjects : obj.subObjects) {
for(auto& subObject : subObjects.second) {
cout << string(indent, '\t') << subObjects.first << ": " << endl;
visualise(subObject, indent + 1);
}
}
}
int main(int argc, const char * argv[]) {
try {
obj result;
benchmark b;
ifstream stream("/Users/taoufik/Desktop/QuickParser/QuickParser/Members.txf");
string line;
if (getline(stream, line))
{
string tagName = line.substr(1);
result = parse(stream, tagName);
}
cout << "elapsed " << b.elapsed() << " ms" << endl;
visualise(result);
}catch(string s) {
cout << "error " << s;
}
return 0;
}
Редактировать 3
Смотрите ссылку для полного кода C++: https://github.com/tofi9/TxfParser
Я немного поработал над вашим исходным кодом на github - после двух изменений я получил общее улучшение на 30%, хотя основное улучшение произошло в результате "Оптимизации 1"
Оптимизация 1 - на основе ваших данных пришла следующая работа.
+ (int)locate:(NSString*)inString check:(unichar) identifier
{
int ret = -1;
for (int i = 0 ; i < inString.length; i++){
if (identifier == [inString characterAtIndex:i]) {
ret = i;
break;
}
}
return ret;
}
- (void)didFindKeyValuePair:(NSString *)tag{
#if 0
NSArray *components = [tag componentsSeparatedByString:@"="];
NSString *key = [components firstObject];
NSString *value = [components lastObject];
#else
int locate = [TXFParser locate:tag check:'='];
NSString *key = [tag substringToIndex:locate];
NSString *value = [tag substringFromIndex:locate+1];
#endif
if (key.length) {
self.dict[key] = value?:@"";
}
}
Оптимизация 2:
- (id)objectFromString:(NSString *)txfString{
[txfString enumerateLinesUsingBlock:^(NSString *string, BOOL *stop) {
#if 0
if ([string hasPrefix:@"#"]) {
[self didStartParsingTag:[string substringFromIndex:1]];
}else if([string hasPrefix:@"$"]){
[self didFindKeyValuePair:[string substringFromIndex:1]];
}else if([string hasPrefix:@"/"]){
[self didEndParsingTag:[string substringFromIndex:1]];
}else{
//[self didFindBodyValue:string];
}
#else
unichar identifier = ([string length]>0)?[string characterAtIndex:0]:0;
if (identifier == '#') {
[self didStartParsingTag:[string substringFromIndex:1]];
}else if(identifier == '$'){
[self didFindKeyValuePair:[string substringFromIndex:1]];
}else if(identifier == '/'){
[self didEndParsingTag:[string substringFromIndex:1]];
}else{
//[self didFindBodyValue:string];
}
#endif
}]; return self.dict;
}
Надеюсь, это поможет вам.