Fastest way of examining vector

This is a discussion on Fastest way of examining vector within the C++ Programming forums, part of the General Programming Boards category; Hi I am reading a text file containing values like below (file may be 16.000 to 100.000 lines) Value1-Value2 A-B ...

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

    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
    22,271
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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
    269
    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
    22,271
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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
    269
    Thanks for reply..

    Any ideas about Sql solution?

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,271
    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?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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
    269
    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, 04: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21