|
Hi people
I have an idea for an algorithm, but am gonna need some help in actually implementing it.
What I need to do is read file paths from right to left, comparing all of them, finding the right-most unvarying element of the path.
An example of how I want this algorithm to work is below
C:\Root Dir\Const Sub Dir1\Sub Dir1
C:\Root Dir\Const Sub Dir1\Sub Dir2
C:\Root Dir\Const Sub Dir1
Path scanned was C:\Root Dir\Const Sub Dir1
Any ideas would be greatly appreciated
Cheers
Give me strength, give me caffeine
|
|
|
|
|
How about something like this: split the string into pieces separated by the \ character. You can do this using theString.Split('\\')
Once you've split the string up into an array, you can check the last elements of the array for the differences.
|
|
|
|
|
It will actually be faster to just go left to right, comparing each char as you go. When one of the chars varies, return the current string (as follows):
List<string> paths = new List<string>();
int shortestPathLength;
// Populate paths and shortestPathLength
if (paths.Count == 0) return string.Empty;
string result = string.Empty;
string tempResult = string.Empty;
for (int charIdx = 0; charIdx < shortestPathLength; ++charIdx) {
char c = paths[0][charIdx];
for (int pathIdx = 1; pathIdx < paths.Length; ++pathIdx) {
if (paths[pathIdx][charIdx] != c)
return result;
}
// Not sure if "DirectorySeparator" is the property, but you get the idea
if (c == Path.DirectorySeparator)
result = tempResult;
tempResult += c.ToString();
}
return tempResult;
Hope this helps!
Jeff
|
|
|
|
|
Cheers Jeff
Yeah this helped, am now working on translating your example into my source code, gonna be a long old scan, considering am talking about 3500+ paths here
Sam
Give me strength, give me caffeine
|
|
|
|
|
If you are dealing with that many paths, you could skip the first three characters if you know for sure they all start on the C drive. If not, you could skip only the second and third characters since you know they will be ":\" for all paths. Other than this optimization, there is no way to improve the efficiency of this algorithm since every character will need to be compared to check for equality.
Jeff
|
|
|
|
|
Tip:
Instead of creating a lot of intermediate strings by adding one character at a time, make result an int, put the length of tempResult in result, and use tempResult.Substring(0, result) to get the string.
---
single minded; short sighted; long gone;
|
|
|
|
|
Good call! In fact, you could change the code to be the following for max optimization using the previous suggestions:
int result = 0;
for (int charIdx = 0; charIdx < shortestPathLength; ++charIdx) {
if (charIdx == 1) {
++charIdx;
result = 2;
continue; // Skip the :\ from the path
}
char c = paths[0][charIdx];
for (int pathIdx = 1; pathIdx < paths.Length; ++pathIdx) {
if (paths[pathIdx][charIdx] != c)
return paths[0].Substring(0, result);
}
// Not sure if "DirectorySeparator" is the property, but you get the idea
if (c == Path.DirectorySeparator)
result = charIdx;
}
return paths[0].Substring(0, shortestPathLength);
|
|
|
|
|
Hi,
there is a lot of opportunity for optimizations here;
I assume you are not interested in partial folder names (i.e. C:\A\B1 and C:\A\B2 have
C:\A in common, not C:\A\B).
The candidate result initially equals the first string.
The only thing that can happen to it is you must drop everything from the last backslash
up to the end (possibly performed iteratively).
Something like:
public string findCommonPath(string[] strings) {
string common=strings[strings.Length-1];
foreach(string str in strings) {
while (!str.StartsWith(common)) {
int i=common.LastIndefOf(@"\");
if (i<=0) return null;
common=common.SubString(0,i);
}
}
return common;
}
remarks:
- you may want to do everything in case-insensitive way;
- if your strings happen to be sorted alphabetically, you should only compare the first
and last one !
- I started with the last string hoping it differs most from the first one, resulting
in a sooner shortening of common, hence less CPU cycles for StartsWith.
- if you happen to know what the shortest string is, you may want to handle that one first.
- the number of objects created is very low (in the order of the number of backslashes
in the first string)
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
I don't think that this algorithm will be faster in most cases. Here is why I think so:
1. The StartsWith will compare at most the length of common, but at least as much as the length of the match
2. LastIndexOf will compare the difference between the current guess at the common string and the next guess at the common string
3. Taking the substring will require the length of common to copy.
So the only time that I can think of where this algorithm would save time would be if you have two non-matching directories that start identically, such as "Food for thought" and "Food for thomas", and those are the ONLY directories you are comparing. Assuming that this is not the case (typical, since there are thousands of entries), the other way cuts out the expenses from parts 2 and 3. The other issue that I see with this is that if you have 3500 paths, and the first 200 fall into a directory that is NOT going to end up as the common directory, you spend a lot of extra time being told that these directories in fact do match a directory that doesn't matter. I also think that directory names in windows are case-sensitive, so the suggestion on making the comparison case-insensitive is unnecessary and takes more time (since you have to then convert the chars to lowercase). One thing that I do like is the suggestion to compare the first and last if they are already sorted (doubtful since you don't already know the common directory). The assumption made as to the efficiency of this algorithm also depends on the collection being "roughly" sorted, that is that the first and last directories differ significantly, which will reduce the amount of time wasted on using "StartsWith". Anyway, those are the reasons that I would stick with the other algorithm myself.
Jeff
|
|
|
|
|
There are many reasons why the character-based approach will not perform as well as one
would hope, including character indexing cost, cache inefficiency, etc. My approach makes
use of StartsWith which I assume is highly optimized, traverses the string collection only
once and for each string uses all the characters at once, drastically increasing the
level 1 cache efficiency.
If you really want to know, implement both and run some relevant tests.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Cache efficiency almost certainly gets better with this method. I am interested in the result of timing the two algorithms if c#_keithy takes the time to do it. If so, let us know which performs better on your data and maybe any noticable tendencies in the dataset you used.
Jeff
|
|
|
|
|
Cheers everyone, your input was greatly appreciated, the algorithm was needed to find the path that was recursively scanned to populate the database with file content information.
Am still working on an implementation of the algorithm using alphabetic sorting and comparing the top and bottom records, using a for loop
For now I am just storing meta data on the database so that I can automatically tell what path was scanned
Give me strength, give me caffeine
|
|
|
|
|
I would like to display a password in a DataGridViewTextBoxColumn. I want the password to be shown as characters ie. *. How can I achieve this?
|
|
|
|
|
there are more technics to solve ur problem:
and this is on of them:
u can add the temprory field to your gridview and then on it add a textbox with special name such as pass then put your favorite info from your db (for example...).
now you must to write below code in the rowcommand event of your gridview:
object obj=gridview.rows[index rows].findcontroll("pass");
textbox txt=(textbox)obj;
and in this step you must to write your favorite character instead of the real password.
txt is a object that contain information of the pass word for each rows that seperate by index rows.
good luck
nobody help you...
you have to help you yourself
and this is success way.
|
|
|
|
|
Hi all
I have created a window service which just starts a thread on its start method.it was working fine.Now when i stopped the service and just restart the service without any changes i am getting an error
"could not restart the service
The service didnot respond to the start or control request in a timely fashion"
Why is it so.Can any one pls help me
Thanks in advance
Regards
DilipRam
|
|
|
|
|
Hi
I an only guess that something bad happen in your OnStart method After you stop the service and restart it.
Use try catch block in order to process any exception thrown,
And log the error message to the event log in order to track down the bug.
|
|
|
|
|
Thanks for the reply
Regards
DilipRam
|
|
|
|
|
I want to do a math calculation for time
Like 12:31:01 - 05:12:12 and so on...
anyone wanna give me a little help .. i'll really appreciate it
|
|
|
|
|
Use a DateTime object and perform the calculation with that. The result will be a TimeSpan object.
|
|
|
|
|
thank you very much .. i managed to get it to work
|
|
|
|
|
hi
I have a XML like"row BLDG_CDE="01 100" BLDG_AMENITY_TYPE_CDE="DFA" BLDG_AMENITY_AVG_SAVINGS_AMT="6666.00" BLDG_AMENITY_RMRK=""/
|
|
|
|
|
Have a look at the XmlTextReader class.
Use MoveToFirstAttribute, MoveToNextAttribute and ReadAttributeValue methods to read the value for each attribute.
http://msdn2.microsoft.com/en-us/library/system.xml.xmltextreader.aspx
Paul
|
|
|
|
|
Hi,
i want to make chat programm for wan,not for lan ,any PC connected with internet.Like yahoo messanger.please help me
|
|
|
|
|
You would need a publicly available (on the internet) server for that. other than that. search CP for "chat server" there are alot of great articles on both UDP and TCP servers and clients
If it' stuck, DO NOT pull harder!
|
|
|
|
|
Greetings,
I am having C# project that make the Executable also. The system use over 20 users' machines. Currently I installed the exe indidual machines coping the source and it is tedious task to do! When i have to do any modification in existing, then again i have to make the setup.exe and installed individual machine.
Are their any way to do this task simple? like one VB.exe(in share folder in LAN), create shortcut and running ncely noh! like that!!!
Any learning resources, plz send me!!! U r Welcome!
Thanks in advance!
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
