file content search, most algorithm-wise, performance-wise approach.

Posted on 2013-01-22
Last Modified: 2013-02-11
Hi there;

I have a "sample" file which has several records in it. The actual file is meant to have hundreds and thousands of records.

The sample file content is as follows:

Company A:
1  0.6
44 0.13
46       0.17
4620       0.0
468       0.15
4631       0.15
4673       0.9
46732     3.6
Company B:
1       0.92
44       0.5
46       0.2
467       1.0
48       1.2

The blocks in the content are tab seperated.

Now, the aim is to search and find the longest matching input which is for example 4673212.
In company A, we will end up it 46732 and the program should output the corresponding item which is 3.6 with comapny letter and in company B, 467 and the output is 1.0 with comapny letter. If no match, simply output no match for that company.

This is fundamentally is to implement but I have to do it most efficient way.
I am using C# and Java.

Now, for the file search the culprit is this:
For each line read, I am checking whether it starts with "Company" literal or not, and i think this is really slowing. Then, I simply exploit try-catch block in which the program fells into catch and if "Company" literal is caught and I start populating a dictionary of values for that company values and finally, I add company dictionaries into a list.

Since, the minimalizing and fast algorithm is what I need, how can I do the check for each line most feasible way? Is it always an if-check?

Note that the content of the files are just to output, no calculation is expected. I assumed the values as int and float but should I go for a list having chars only in it?

Thanks for the help.

Question by:jazzIIIlove
  • 4
  • 2
  • 2
LVL 84

Assisted Solution

ozo earned 334 total points
ID: 38804576
If you are only going to search the file once, a linear scan over the entire file is the best you can do.
If you are going to do many searches over the same file for different inputs,
then you can sort the lines or build a trie.
LVL 16

Assisted Solution

krakatoa earned 166 total points
ID: 38804617
My comment would be the same as ozo's. Depends how many times you are going to do this, and how often the data will change or be updated. The only other key that seems apparent from the sample data is that the "." could be used as a length offset, giving you a way in to the longest record, but again the data would need to be sorted or sortable.
LVL 12

Author Comment

ID: 38804929
There will be many different inputs, but the inputs are coming from console and the question remains the same, I feel that I have to read file once and I am reading the file only once, and storing the values, but with if-check.

I have to search for the file completely for each individual input that comes from user via console. So, do I still need an if-check? I am trying to get rid of the if check concept in the reading of the file.

Also, which tree are we talking about? Should I convert every number block into a character list and search in that list? or should I store each numerical looking character as char in a tree? And which tree? Should I sort the values? The sample content is just as that.

As you can see,

46       0.17
4620       0.0
468       0.15
4631       0.15

It's not vertically sorted. So, should I sort? and which kind of sort for this input?

Networking for the Cloud Era

Join Microsoft and Riverbed for a discussion and demonstration of enhancements to SteelConnect:
-One-click orchestration and cloud connectivity in Azure environments
-Tight integration of SD-WAN and WAN optimization capabilities
-Scalability and resiliency equal to a data center

LVL 16

Expert Comment

ID: 38804954
I have a "sample" file which has

Time to make your mind up if the data is live from a console. Or file. Or not . . .
LVL 12

Author Comment

ID: 38804978
Sorry for misunderstanding.

The data is the file and this data should be checked against for user input coming from console, and if the user input matches it will give the float looking value with the Company in it as output, if not just indicates that Company has no corresponding key, so no float looking value.

LVL 84

Accepted Solution

ozo earned 334 total points
ID: 38805070
depending on the size of the file, and the number of searches you want to do on it
(and perhaps how much memory you have available), you can have different trade offs between pre-processing time, and search time.
One extreme may be to build an Aho–Corasick  finite state machine to scan the file,
Another extreme may be to build a trie or prefix tree
But in any case you should be able to keep the total time proportional to the length of the file + the length of the input to be found.
LVL 12

Author Comment

ID: 38806061

I am able to use Aho-Corasick algorithm. In order to use it efficiently, I also read the file content as bytes, but somehow, I couldn't construct a working algorithm on this:

What I am trying to do is:
I first read the file, to mappedbytebuffer, then, while there is anything left in buffer, I get the content to bytebuffer, then transfer it to a byte array. Then, the construction of my algorithm is as:
in the loop, if there is a blank, then the coming byte can be either a character between A and Z, like:
Company A:
A can be coming after blank.

else a value like 0.17 can come. If so, then i try to find the last carriage return and go for +1 of that to reach 4. So, I can take the bytes until the coming blank and reach 46.

46       0.17

But the problem is that I couldn't construct the algorithm as debugging bytes is futile. Can you help me on this?

Below is the code:

			FileInputStream f = new FileInputStream("List.txt");
			FileChannel fileChannel = f.getChannel();
			MappedByteBuffer mbb = FileChannel.MapMode.READ_ONLY,
					0L, fileChannel.size( ) );
			byte [] buffer1 = new byte[24];	        
			int i = 0;
			AhoCorasick tree = new AhoCorasick();
			TreeMap tm = new TreeMap();
			String output = "4620";
			List <Byte> byteList = new ArrayList<Byte> ();
			while ( mbb.hasRemaining( ) ) {	                
				ByteBuffer bb = mbb.get(buffer1, 0, 24);
				byte[] bytearr = new byte[bb.remaining()];
				//if(bytearr[i++] != 13 || bytearr[i++] != 10)
				//bytearr = bb.array();
				if(bytearr[i] == (byte)' ')
					if(bytearr[i] >= (byte)'A' || bytearr[i] <= (byte)'Z')
					char letter = (char)bytearr[i];
						if(bytearr[i] == (byte)'\n')
							int k = i;
									while(bytearr[k] != (byte)' ')
									Byte o []  = (Byte[])byteList.toArray();									 
									tree.add(o, output);
				else i++;				
		catch(Exception ex){}

Open in new window

LVL 12

Author Comment

ID: 38847523
Hi there;

Any update for my last comment with the code?


Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:

839 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question