Thread: Fastest way of examining vector

  1. #1
    Just kidding.... fnoyan's Avatar
    Join Date
    Jun 2003
    Location
    Still in the egg
    Posts
    275

    Fastest way of examining vector

    Hi

    I am reading a text file containing values like below (file may be 16.000 to 100.000 lines)

    Value1-Value2
    A-B
    A-C
    A-D
    K-M
    K-F
    B-K
    B-A

    Each line is read and parsed with a parser. The values are pushed into a vector as "A-B" pairs. But at the same time, I also need to count the occurrence of any value in first column

    To do so;
    1 ) I can create two vectors, one to hold "A-B" pairs and the other to hold a STL Map container (key to be "A" and value is "3" for example). But, each time I read a new line, I have to trace the second vector, find relevant key and increase the related value by 1 and update the map vector. this is does not seem so efficient

    2 ) I can read file twice. At first round, I can create the map vector (that holds the name of element and number of its occurrence). In second tour, I create the "A-B" pairs. But reading file twice also seems a little bit "ad performance solution"

    3 ) I can use some sql engine, like Sqlite. Like reading file once and fill my sql table, and do the rest of the job with SQL. I really do not have an idea about the performance of this solution.

    Any other options are welcome.

    Thanks in advance....

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    If you need the data in the original order as stored in the file, then storing pairs in a vector is fine. If you need to count the occurrence of data in the first column, then storing a map to map the data values to their occurrences is fine. Since you need both, populate both, in the same loop with which you read from file.

    Incidentally, unless you also need the occurence map to be sorted by the data, consider if std::unordered_map would be suitable.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Just kidding.... fnoyan's Avatar
    Join Date
    Jun 2003
    Location
    Still in the egg
    Posts
    275
    So, you mean
    Code:
    while(not_end_of_file) {
    read_line();
    assign_vector();
    update_map_vector();
    }
    
    update_map_vector(){
     while(search_map())
        if(related_key_found)
                update_value();
    }
    But my concern is, doesn't it take too much time each time I read a line to perform update_map_vector(). The values in the file may not be in a sorted order.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by fnoyan
    But my concern is, doesn't it take too much time each time I read a line to perform update_map_vector().
    Finding the key in a std::map takes O(log n) time in the worst case; finding the key in a std::unordered_map takes constant time in the average case. With a mere 100000 entries max to search for a short string, I daresay even linear search would be acceptable (EDIT: okay, maybe not linear search since this will be called in a loop.)

    That said, note that your logic is slightly off: you need to insert into the map if the key is not found. Using the overloaded operator[] makes this simple, though very slightly inefficient.
    Last edited by laserlight; 03-06-2012 at 01:57 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Just kidding.... fnoyan's Avatar
    Join Date
    Jun 2003
    Location
    Still in the egg
    Posts
    275
    Thanks for reply..

    Any ideas about Sql solution?

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by fnoyan
    Any ideas about Sql solution?
    No point since you're already storing the data in a file. Granted, you can have an in-memory database with SQLite, but then you'll be performing queries in order to populate containers anyway, right?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Just kidding.... fnoyan's Avatar
    Join Date
    Jun 2003
    Location
    Still in the egg
    Posts
    275
    As you said, since the data in a TXT file, until reaching very large file sizes, it does not make too much sense.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Examining the Assembly Listing
    By quintenmater in forum C Programming
    Replies: 8
    Last Post: 12-11-2010, 08:15 AM
  2. Examining MBR and Printing Total Disk Size in Bytes
    By pantherman34 in forum C Programming
    Replies: 8
    Last Post: 04-30-2010, 03:27 PM
  3. I'm looking for the fastest!
    By Yarin in forum Windows Programming
    Replies: 4
    Last Post: 11-07-2007, 03:30 PM
  4. Examining flags when passed to a function?
    By DominicTrix in forum C++ Programming
    Replies: 5
    Last Post: 02-01-2003, 01:34 PM
  5. Examining the manifest
    By Troll_King in forum C# Programming
    Replies: 2
    Last Post: 01-07-2002, 07:43 AM