Количество уникальных строк в большом файле

Question

Как посчитать приблизительное количество уникальных строк в файле, используя малое количество памяти (<< количества уникальных строк)? При этом погрешность ответа должна быть не больше нескольких процентов.

Строки приходят "онлайн", т.е. в любой момент требуется сказать текущее примерное количество уникальных. Длина строк может быть различной, но не превосходит маленького числа.

Answer 1

Почему бы просто не прокурутить std::hash по каждой стркое и посчитать их в std::map ?

Если кейс: a b b c d - 3 уникальных - то используем std::map

#include <cstdlib>

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

int main () {
  
  std::string inFile{"data"};
  std::ifstream input(inFile , std::ios::in);
  if (!input.is_open()) {
    std::cerr << "Error open file : " << inFile << std::endl;
    return EXIT_FAILURE;
  }
  
  std::map<std::size_t, std::size_t> m;
  std::hash<std::string> hf{};
  for(std::string line; std::getline(input, line ); ) {
    m[hf(line)] += 1;
  }

  std::size_t ret{0};
  auto fobj{[&ret](std::pair<std::size_t, std::size_t> v){if (v.second == 1) ++ret;}};
  std::for_each(std::begin(m), std::end(m), fobj);

  std::cout << "Uniq lines : " << ret << std::endl;

  return EXIT_SUCCESS;;
}

UPD : Если кейс: a b b c d - 4 уникальных - то используем std::set

#include <cstdlib>

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

int main () {
  
  std::string inFile{"data"};
  std::ifstream input(inFile , std::ios::in);
  if (!input.is_open()) {
    std::cerr << "Error open file : " << inFile << std::endl;
    return EXIT_FAILURE;
  }
  
  std::set<std::size_t> s;
  std::hash<std::string> hf{};
  for(std::string line; std::getline(input, line ); ) {
    s.insert(hf(line));
  }

  std::cout << "Uniq lines : " << s.size() << std::endl;

  return EXIT_SUCCESS;;
}

БЛОГ НА HUSL

Количество уникальных строк в большом файле

Ответы (1 шт):