0

I'm faced with the following problem:

I have an array which is produced by the parsing of a yaml file which contains patterns in the following structure.

"Programming books"
    Title:
          a list of titles
    Author:
"Art Books"
    Title:
          foo
          bar
    Author:
          Mrs. Foo
          Mr. Bar
    Year:

the program is supposed to be given random input and find if there is a book with that particular Title,Author and Year.

So far I'm using the following

 foreach book_type,values from config{
       tag_match = 0
       foreach tag from values{
            tag_no = values.length()
            foreach value from tag{
                 if value in input
                      tag_match++
            }
      }
      if tag_match == values.length()
           /* tag the book matched continue matching*/
 }

The program is not supposed to receive many matching lines bu it is supposed to receive a huge amount of data. So far it has to do book_type.length() * tag.length() * value.length() iterations for each line of input, is there a better way to do this?

  • 1
    Look up the concept of indexing. Start with the properties that are most distinctive and most frequently asked. – Kilian Foth Jan 8 '14 at 8:33
  • there is no upvote in programmers (as opposed to overflow) anyway,thanks for the answer :) – ndp Jan 8 '14 at 10:10
1

Use a dictionary or collection, which has a Key-value pair, if the size of the data allows, if not a database - as stated above.

There are lots of different collections, dictionary, hash table etc implementations, and the right/fastest one to use will depend on the nature of its indented use, so you will have to look around to find the most suitable one. For example some will load faster, but take longer to read, some load slower, but have faster access times, and so on.

On other thing, might be, currently you are O(3n), by which I mean type X tag X value so if that's loops it might be 10 + 10 + 10 = 30 worst case. You could combine Type and Tag, and Value, which would be 10 worst case - just a thought.

Heres a link to an articular I found useful, but is .Net specific. IDictionary Options - Performance Test - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable

0

Hashing/indexing is the way to go. Up to a few million items or so, create a single or multilevel hashtable/hashmap/whatever it's called in your language. In C# it could be Dictionary<string, Dictionary<string, List<Book>>> books_by_title_and_author. The first key is the title, the second is the author, and the value is a list of matching books, supposed to hold only a few items. If you have too much data, you should do what a database would do, build a B-tree index. Again, this can be single or multi column. An index takes a bit longer to build, but can be more efficient with many items. Also an on-disk structure is the only way if your data is too big to fit in memory.

  • my data is fed to the script by an external application, the pattern file for the moment is not that big(a dozen mb) so it fits in memory. thanks a lot for the answer :) – ndp Jan 8 '14 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.