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?

DevOps Toolchain Recommendations

Read this Gartner Research Note and discover how your IT organization can automate and optimize DevOps processes using a toolchain architecture.

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

Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
System.Security 2 27
send messages to whatsapp programatically 2 49
Google Directions API to Map URL -C#? 3 28
going to wrong jsp page 2 22
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
This article aims to explain the working of CircularLogArchiver. This tool was designed to solve the buildup of log file in cases where systems do not support circular logging or where circular logging is not enabled
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
This tutorial covers a practical example of lazy loading technique and early loading technique in a Singleton Design Pattern.

832 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