Find longest lines from a file

Question

This is a challenge question from codeeval.com:

Write a program which reads a file and prints to stdout the specified number of the longest lines that are sorted based on their length in descending order. Input sample:

Your program should accept a path to a file as its first argument. The file contains multiple lines. The first line indicates the number of lines you should output, the other lines are of different length and are presented randomly. You may assume that the input file is formatted correctly and the number in the first line is a valid positive integer.

For Example:

2 
Hello World
CodeEval 
Quick Fox
A
San Francisco

Output sample:

Print out the longest lines limited by specified number and sorted by their length in descending order.

For example:

San Francisco 
Hello World

Please let me know how I can improve this implementation.

#include<iostream>
#include<map>
#include<fstream>
#include<string>
#include<chrono>

class fixed_hash{
public:
        fixed_hash( int pSize )
        {
            size = pSize;
        }
        void push( std::string & record )
        {

            if( hash_table.size() < size )
            {
                hash_table.emplace( std::make_pair( record.size(), record ) );
            }
            else if( record.size() > hash_table.rbegin()->second.size() )
            {
                hash_table.erase( hash_table.begin() );
                hash_table.emplace( std::make_pair( record.size(), record ) );
            }
        }
        void print()
        {
            auto end = std::rend(hash_table);
            for( auto it = std::rbegin( hash_table ); it != end ; ++it )
            {
                std::cout << it->second << "\n";
            }
        }

 private:
        std::map<int,std::string> hash_table;
        int size;
};

void readInputFile( std::string fileName )
{
    std::ifstream infile( fileName );
    std::string record;
    int output_nbr = 0;
    infile >> output_nbr;
    fixed_hash output_string_list( output_nbr );
    while( std::getline( infile, record ) )
    {
        output_string_list.push( record );
    }

    output_string_list.print();
    infile.close();
}

int main( int argc, char* argv[] )
{
    auto start = std::chrono::steady_clock::now();
    if( argc < 2 )
    {
        std::cout << "Error: input file is missing " << "\n";
        exit( 0 );
    }

    std::ios_base::sync_with_stdio( false );
    readInputFile( argv[ 1 ]);

    auto end      = std::chrono::steady_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end-start);
    std::cout<< duration.count() << "\n";
    return 0;
}

Answer 1

This is a bug:

else if( record.size() > hash_table.rbegin()->second.size() )

As implemented, insertion stops once your program encounters the longest line in the file.

For example, suppose the input contains:

2
abcdefghijklmop
a
ab
abc
abcd

Your program will output:

abcdefghijklmop
a

The fix is simple: Change rbegin to begin.

---

Another potential issue is your use of a std::map as opposed to some other container. Your concept is fine, but not necessarily for "I'm the best hacker!" type sites that place strong emphasis on execution time. A vector-based solution could be faster. With the red-black tree-based hash, search, insertion, and delete are \$O(log n)\$ (but with large constants). With a vector-based solution, search would be \$O(log n)\$ (but potentially much faster than a red-black search), deleting the tail is \$O(1)\$ (which is a big win), but insertion is \$O(n)\$ (which is of course a big loss). However, for small enough values of n, a fast \$O(n)\$ algorithm can and will beat a slow \$O(log n)\$ algorithm.

One last remark: Rather than your void print() member, a stream insertion operator would be more C++-like:

class fixed_hash
{
    ...
    friend std::ostream& operator<<(std::ostream& os, const fixed_hash& hash);
    ...
};

std::ostream& operator<<(std::ostream& os, const fixed_hash& hash)
{
    auto end = std::rend(hash.hash_table);
    for( auto it = std::rbegin(hash.hash_table); it != end ; ++it )
    {
        os << it->second << "\n";
    }
    return os;
}

Answer 2

Here are some things that may help you improve your code, but with the caveat that "improve" could mean one of several things. In this review, I'm mostly going to comment on things that will make the code more readable, and not necessarily yield performance improvements.

Use better naming

The name readInputFile is a bit misleading, since it does much more than simply reading -- all of the processing, including output, is done there. Also, I tend to prefer CamelCase for class names, so I'd be inclined to name the class something else, perhaps FixedHash, although I'm not very fond of that name either.

Use std::size_t instead of int

A more appropriate type for your size in fixed_hash would be std::size_t instead of int.

Consider using a multiset instead

One could easily argue it either way, but I'd be inclined to use a std::multiset instead of a std::map. Your current code is more efficient in that it uses less memory and is probably faster, but an alternative would be to use a more-or-less plain multiset:

template <class T>
struct longer {
    bool operator()(const T &left, const T &right) const {
        return right.size() < left.size();
    }
};
std::multiset<std::string, longer<std::string>> lines;

Printing would then be:

for (auto line = lines.cbegin(); count && line != lines.cend(); ++line, --count) {
    std::cout << *line << std::endl;
}

If needed, you could adapt the multiset as you have for the map. It seems to me that the code might be slightly simpler.

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main.

Answer 3

You may consider using std::multimap since there may be strings of equal length in the input. For example (C++11), change your input stream accordingly or use freopen with this code.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    multimap <size_t, string, greater<size_t>> map;
    string line;
    while (getline(cin, line)) 
        map.emplace(line.length(), line);
    for (auto i = map.begin(); i != map.end() && n--; ++i)
        cout << i->second << endl;
    return 0;
}

See it working here.

---

C++11 is not present on codeeval.com. A C++03 compatible version would look like this:

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char * argv[]) {
    int n;
    cin >> n;
    multimap <size_t, string, greater<size_t> > map;
    string line;
    while (getline(cin, line)) 
        map.insert(make_pair(line.length(), line));
    for (multimap<size_t, string>::iterator i = map.begin(); i != map.end() && n--; ++i)
        cout << i->second << endl;
    return 0;
}

Answer 4

In addition to all above answers, here are a few things that may improve your existing code:

In the push member function, it's not necessary to do the comparing and deleting and its algorithm there; it seems odd. It's better to make it for inserting a new elements that's quite regular, especially when std::map has template parameter comparators made for that purpose and the compare expression by default is std::less<T>. You can create your compare expression or use std::greater<T> which is defined in the <functional> header file.

std::map<std::size_t ,std::string, std::greater<int>> hash_table;

and push member function will be like this

    void push( std::string & record )
    {
        hash_table.emplace( std::make_pair( record.size(), record ) );
    }

In the print member function, try not use std::begin() std::end(). That would be really unnecessary for STL containers. It already has its own begin() and end().

    void print()
    {
        for( auto it = hash_table.begin(); it != hash_table.end() && size; ++it , --size )
        {
            std::cout << it->second <<"\n";
        }
    }

My suggestion is to pick the right container for this question. It's known that std::vector is a better choice for small data sizes and best for iterating data, but it has limitations in lookup, unlike std::map. This example really is a perfect reason to go with std::vector over std::map, especially because it asked for longer lines in a text file only.

My opinion is to create std::vector<std::string> and once all data is stored in the vector, it can be sorted and printed easily by using what STL offers to us as shown below:

#include <iostream>
#include <string>
#include <fstream>
#include <algorithm>
#include <vector>

int main(int argc, char* argv[])
{
    std::ifstream in(argv[1]);
    std::vector<std::string> vec;
    std::string line;
    while (std::getline(in, line))
    {       
        vec.push_back(line);
    }
    std::size_t n = atoi(vec.begin()->c_str());
    std::sort(vec.begin(), vec.end(), [](const std::string &left, const std::string &right){ return right.size() < left.size(); });
    std::copy(vec.begin(), vec.begin() + n, std::ostream_iterator<std::string>(std::cout, "\n"));
}

Answer 5

Following corrections are implemented:

1. Reported bug is fixed

2. Instead of std::map<> using std::multi_map<>

3. Using size_t instead of wrong use of int as a type

//

#include<iostream>
#include<map>
#include<fstream>
#include<string>
#include<chrono>

class fixed_hash{
public:
        fixed_hash( std::size_t pSize )
        {
            size = pSize;
        }
        void push( std::string & record )
        {

            if( hash_table.size() < size )
            {
                hash_table.emplace( std::make_pair( record.size(), record ) );
            }
            else if( record.size() > hash_table.begin()->second.size() )
            {
                hash_table.erase( hash_table.begin() );
                hash_table.emplace( std::make_pair( record.size(), record ) );
            }
        }
        void print()
        {
            auto end = std::rend(hash_table);            
            for( auto it = std::rbegin( hash_table ); it != end ; ++it )            
            {
                std::cout << it->second << "\n";
            }
        }

 private:
        std::multimap<int,std::string> hash_table;
        std::size_t size;
};

void readInputFile( std::string fileName )
{
    std::ifstream infile( fileName );
    std::string record;
    int output_nbr = 0;
    infile >> output_nbr;
    fixed_hash output_string_list( output_nbr );
    while( std::getline( infile, record ) )
    {
        output_string_list.push( record );
    }

    output_string_list.print();
    infile.close();
}

int main( int argc, char* argv[] )
{
    auto start = std::chrono::steady_clock::now();
    if( argc < 2 )
    {
        std::cout << "Error: input file is missing " << "\n";
        exit( 0 );
    }

    std::ios_base::sync_with_stdio( false );
    readInputFile( argv[ 1 ]);

    auto end      = std::chrono::steady_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end-start);
    std::cout<< duration.count() << "\n";
    return 0;
}