ali01 · August 29, 2015 14:00
diff --git a/generate_test_file.py b/generate_test_file.py
 #!/usr/bin/env python

 import math
 import random

 # presently set so that the resulting file size is ~1GB on average
 NUM_LINES = int(math.pow(2, 21))
 MAX_LINE_LENGTH = int(math.pow(2, 10))


 def generate_test_file():
  random.seed()
  with open('./data.txt', 'a') as f:
    for i in range(0, NUM_LINES):
      line_length = random.randint(0, MAX_LINE_LENGTH)

      line = ''
      for j in range(0, line_length):
        line += str(unichr(random.randint(97, 122)))

      f.write("%s\n" % line)


 if __name__ == '__main__':
  generate_test_file()
  exit(0)
diff --git a/longest.cpp b/longest.cpp
 #include <cstring>
 #include <deque>
 #include <fcntl.h>
 #include <iostream>
 #include <string>
 #include <sys/stat.h>
 #include <sys/mman.h>
 #include <unistd.h>

 using namespace std;


 // Datastructure used to keep track of the N longest strings inserted.
 class LongestStrQueue {
 public:

  // Constructor:
  // uint32_t cap -- number of strings to keep track of
  LongestStrQueue(uint32_t cap) : cap_(cap), min_length_(0) {}


  // Inserts a string.
  // Runs in linear time with respect to `cap`, However, only strings that are
  // longer than min_length_, which is the length of the smallest string,
  // currently stored, need be inserted. If the being inserted come from a
  // pool of strings whose lengths are uniformly distributed [0, L), then the
  // fraction of strings that need to be inserted decreases with time as
  // min_length_ approaches L.
  void
  insert(string str) {
    if (str.length() > min_length_) {
      deque<string>::iterator it;
      for (it = strings_.begin(); it != strings_.end(); ++it) {
        if ((*it).length() < str.length())
          break;
      }

      strings_.insert(it, str);
      if (strings_.size() > cap_) {
        strings_.pop_back();
      }

    } else if (strings_.size() < cap_) {
      strings_.push_back(str);
      min_length_ = str.length();
    }
  }

  // Returns a const reference to the list of N.
  // longest strings in sorted order (decreasing length).
  const deque<string>&
  strings() {
    return strings_;
  }

 private:
  deque<string> strings_; // list of strings in sorted order (decreasing length)
  uint32_t min_length_;   //
  const uint32_t cap_;    // maximum number of strings to keep track of
 };


 int
 longest(const string& filepath, LongestStrQueue& longest_lines) {
  int fd = open(filepath.c_str(), O_RDONLY);

  // determine the size of the input file
  struct stat st;
  if (fstat(fd, &st) < 0) {
    perror("fstat");
    return -1;
  }

  // mmap input file
  void *data = mmap(NULL, st.st_size, PROT_READ, MAP_FILE|MAP_PRIVATE, fd, 0);
  if (data == MAP_FAILED) {
    perror("mmap");
    return -1;
  }

  // breakdown file into lines and insert them into LongestStrQueue
  const char *data_str = (const char *)data;
  while (true) {
    int index = strcspn(data_str, "\n");
    if (data_str[index] == '\0')
      break;

    string line(data_str, index + 1);
    longest_lines.insert(line);

    data_str += index + 1;
  }

  return 0;
 }


 void
 print_usage(const char *program_name) {
  printf("usage: %s %s %s\n\n", program_name, "<input_filename>", "<num_lines");
  printf("Options:\n");
  printf("  -h  show this help message and exit\n\n");
 }


 int
 main(int argc, char **argv) {
  // parse command line options
  int c_i;
  while ((c_i = getopt(argc, argv, "h")) != -1) {
    switch(c_i) {
      case 'h':
      case '?':
      default:
        print_usage(argv[0]);
        return 0;
    }
  }

  // parse non-option arguments
  // expect two non-option arguments
  if (optind + 2 != argc) {
    print_usage(argv[0]);
    return -1;
  }

  const string filepath = argv[optind];
  const uint32_t num_lines = stoi(argv[++optind]);

  // heavy lifting done by longest()
  LongestStrQueue longest_lines(num_lines);
  longest(filepath, longest_lines);

  // output result to stdout
  deque<string> strings = longest_lines.strings();
  for (deque<string>::iterator it = strings.begin(); it != strings.end(); ++it){
    cout << *it;
  }

  return 0;
 }
diff --git a/Makefile b/Makefile
 all:
 	g++ -O2 -std=c++11 longest.cpp -o longest

 run: longest
 	@./longest

 clean:
 	rm -rf longest
	#!/usr/bin/env python

	import math
	import random

	# presently set so that the resulting file size is ~1GB on average
	NUM_LINES = int(math.pow(2, 21))
	MAX_LINE_LENGTH = int(math.pow(2, 10))


	def generate_test_file():
	random.seed()
	with open('./data.txt', 'a') as f:
	for i in range(0, NUM_LINES):
	line_length = random.randint(0, MAX_LINE_LENGTH)

	line = ''
	for j in range(0, line_length):
	line += str(unichr(random.randint(97, 122)))

	f.write("%s\n" % line)


	if __name__ == '__main__':
	generate_test_file()
	exit(0)
	#include <cstring>
	#include <deque>
	#include <fcntl.h>
	#include <iostream>
	#include <string>
	#include <sys/stat.h>
	#include <sys/mman.h>
	#include <unistd.h>

	using namespace std;


	// Datastructure used to keep track of the N longest strings inserted.
	class LongestStrQueue {
	public:

	// Constructor:
	// uint32_t cap -- number of strings to keep track of
	LongestStrQueue(uint32_t cap) : cap_(cap), min_length_(0) {}


	// Inserts a string.
	// Runs in linear time with respect to `cap`, However, only strings that are
	// longer than min_length_, which is the length of the smallest string,
	// currently stored, need be inserted. If the being inserted come from a
	// pool of strings whose lengths are uniformly distributed [0, L), then the
	// fraction of strings that need to be inserted decreases with time as
	// min_length_ approaches L.
	void
	insert(string str) {
	if (str.length() > min_length_) {
	deque<string>::iterator it;
	for (it = strings_.begin(); it != strings_.end(); ++it) {
	if ((*it).length() < str.length())
	break;
	}

	strings_.insert(it, str);
	if (strings_.size() > cap_) {
	strings_.pop_back();
	}

	} else if (strings_.size() < cap_) {
	strings_.push_back(str);
	min_length_ = str.length();
	}
	}

	// Returns a const reference to the list of N.
	// longest strings in sorted order (decreasing length).
	const deque<string>&
	strings() {
	return strings_;
	}

	private:
	deque<string> strings_; // list of strings in sorted order (decreasing length)
	uint32_t min_length_; //
	const uint32_t cap_; // maximum number of strings to keep track of
	};


	int
	longest(const string& filepath, LongestStrQueue& longest_lines) {
	int fd = open(filepath.c_str(), O_RDONLY);

	// determine the size of the input file
	struct stat st;
	if (fstat(fd, &st) < 0) {
	perror("fstat");
	return -1;
	}

	// mmap input file
	void *data = mmap(NULL, st.st_size, PROT_READ, MAP_FILE\|MAP_PRIVATE, fd, 0);
	if (data == MAP_FAILED) {
	perror("mmap");
	return -1;
	}

	// breakdown file into lines and insert them into LongestStrQueue
	const char data_str = (const char )data;
	while (true) {
	int index = strcspn(data_str, "\n");
	if (data_str[index] == '\0')
	break;

	string line(data_str, index + 1);
	longest_lines.insert(line);

	data_str += index + 1;
	}

	return 0;
	}


	void
	print_usage(const char *program_name) {
	printf("usage: %s %s %s\n\n", program_name, "<input_filename>", "<num_lines");
	printf("Options:\n");
	printf(" -h show this help message and exit\n\n");
	}


	int
	main(int argc, char **argv) {
	// parse command line options
	int c_i;
	while ((c_i = getopt(argc, argv, "h")) != -1) {
	switch(c_i) {
	case 'h':
	case '?':
	default:
	print_usage(argv[0]);
	return 0;
	}
	}

	// parse non-option arguments
	// expect two non-option arguments
	if (optind + 2 != argc) {
	print_usage(argv[0]);
	return -1;
	}

	const string filepath = argv[optind];
	const uint32_t num_lines = stoi(argv[++optind]);

	// heavy lifting done by longest()
	LongestStrQueue longest_lines(num_lines);
	longest(filepath, longest_lines);

	// output result to stdout
	deque<string> strings = longest_lines.strings();
	for (deque<string>::iterator it = strings.begin(); it != strings.end(); ++it){
	cout << *it;
	}

	return 0;
	}
	all:
	g++ -O2 -std=c++11 longest.cpp -o longest

	run: longest
	@./longest

	clean:
	rm -rf longest