Faster indexing for batch find and project indexer
Faster indexing for batch find and project indexer
- Subject: Faster indexing for batch find and project indexer
- From: "Karan, Cem (Civ, ARL/CISD)" <email@hidden>
- Date: Wed, 15 Nov 2006 14:29:07 -0500
- Thread-topic: Faster indexing for batch find and project indexer
I've been making a lot of changes in some files (4-500+ at a time) in my
project to meet our new documentation requirements. This is relatively
easy to do via the batch find command, but I noticed that 1) it takes a
lot time to search all the files, and 2) every time I save, project
indexer gets kicked off, which also takes time. It occurred to me that
I spend a lot of time waiting, and, because I'm going to go through a
similar problem on my next project (indexing a lot of strings), I just
got curious as to what XCode's algorithm is doing precisely. Does
anyone know the precise algorithm in use for the batch find, and for the
project indexer?
I ask because in my new project, I have to index the suffixes in a large
set of files. In this case suffixes are defined like this: Treat the
data as one large string of bytes, and number the bytes from start to
finish, in order, e.g., 012345... The first suffix is the entire string,
the second suffix starts at byte 1, the third at byte 2, etc. If you
organize these properly into a suffix tree, you can search for and find
any string in the file with a run time that is on the order of the
length of the string you are searching for, NOT the length of the data
you are searching over.
The real reason I'm mentioning this? It turns out that it takes a
runtime of O(n) to build the tree, and, unless I figured it out wrong,
roughly O(m) to modify it, where n is the total number of bytes in all
the files, and m is the length of the string you are searching for. The
storage space for a real suffix tree is also O(n), but since this would
be an index, it would be larger than that (I have no idea how much, I
haven't calculated it). My thought is that XCode could spend the time
building and storing the trees for both the find command and for the
project indexer when you add in files, and then just use those trees
when searching. The search times would be extremely fast this way, the
storage space wouldn't be that much, it seems like a win/win
situation...
Looking forward to any comments,
Cem Karan
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Xcode-users mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden