Algorithmus für die Zählung Sortiert Strings (Homebrew "uniq -c")

Question

Ich habe folgende sortierten Daten:

AAA 
AAA 
TCG 
TTT 
TTT 
TTT 

ich die Vorkommen jedes String zählen möchten:

AAA 2 
TCG 1 
TTT 3 

Ich weiß, ich kann das mit uniq -c tun, aber hier muss ich zusätzliche Verarbeitung für den gesamten C++ - Code, den ich habe. (Nach 'pgras' Vorschlag modifiziert)

ich mit diesem Konstrukt stecke:

#include <iostream> 
#include <vector> 
#include <fstream> 
#include <sstream> 
using namespace std; 


int main (int arg_count, char *arg_vec[]) { 
    if (arg_count !=2) { 
     cerr << "expected one argument" << endl; 
     return EXIT_FAILURE; 
    } 

    string line; 
    ifstream myfile (arg_vec[1]); 


    if (myfile.is_open()) 
    { 
     int count; 
     string lastTag = ""; 

     while (getline(myfile,line)) 
     { 
      stringstream ss(line); 
      string Tag; 

      ss >> Tag; // read first column 
      //cout << Tag << endl; 

      if (Tag != lastTag) { 
       lastTag = Tag; 
       count = 0; 
      } 
      else { 
       count++; 
      } 

      cout << lastTag << " " << count << endl; 
     } 
     cout << lastTag << " " << count << endl; 
     myfile.close(); 

    } 
    else {cout << "Unable to open file";} 
    return 0; 
} 

Er druckt dieses falsche Ergebnis:

AAA 0 
AAA 1 
TCT 0 
TTT 0 
TTT 1 
TTT 2 
TTT 2 

Answer 1

Sie haben Zähler zurücksetzen, wenn Tag verschieden von lastTag ist, und Schritt, wenn es das gleiche ... Wenn der Tag unterscheidet Sie den vorherigen Tag verarbeiten kann damit Zählwert zugeordnet ist (bevor Sie Zählung zurückgesetzt) ...

Answer 2

Ihr Code syntaktisch leicht gebrochen sieht (die ifstream, ...), aber der Gesamtalgorithmus ist meiner Meinung nach solide. Lesen Sie Zeilen und erhöhen Sie einen Zähler jedes Mal, wenn die Zeile dieselbe wie die vorherige ist. Es kann einige Randbedingungen geben, die zu beachten sind (was ist, wenn die Eingabe nur eine Zeile ist?), Aber Sie werden diese während des Tests erfassen.

Answer 3

Die Verwendung des stringstream, nur um das Tag zu bekommen, scheint etwas übertrieben - ich würde wahrscheinlich string :: substr. Abgesehen davon, was denkst du ist falsch mit deinem Code? Was möchtest du verbessern?

Edit: Das nächste, was werden wir Downvoted Atmen erleichtert werden immer ...

Answer 4

Wenn Sie nur wollen, dass es auszudrucken, Ihr Algorithmus ist in Ordnung. Wenn Sie es an eine andere Funktion übergeben möchten, können Sie beispielsweise eine STL-Map verwenden.

map<string, int> dict; 

while(getline(myfile,line)) { 
      string Tag; 
      stringstream ss(line); 
      ss >> Tag; 
      if (dict.count(Tag) == 0) 
       dict[Tag] = 1; 
      else 
       dict[Tag]++; 
}  

Answer 5

Verwendung so etwas wie dieses:

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


std::ostream& operator << (std::ostream& out, const std::pair< std::string, size_t >& rhs) 
{ 
    out << rhs.first << ", " << rhs.second; 
    return out; 
} 

int main() 
{ 
    std::ifstream inp("mysorted_data.txt"); 
    std::string str; 
    std::map < std::string, size_t > words_count; 
    while (inp >> str) 
    { 
     words_count[str]++; 
    } 

    std::copy( 
     words_count.begin(), 
     words_count.end(), 
     std::ostream_iterator< std::pair< std::string, size_t > >(std::cout, "\n")); 

    return 0; 
} 

Answer 6

Vorausgesetzt, daß die Daten tatsächlich von DNA-Strings der Länge besteht 3 (oder allgemeiner Länge N wo N ist recht klein), können Sie dies sehr effizient, indem Sie eine q-Gramm-Tabelle verwendet, die mit einer Tischgröße von 4 ^N und die folgenden Hash-Funktion eine spezielle Hash-Tabelle ist:

// Disregard error codes. 
int char2dna_lookup[] = { 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x0 – 0xF 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x10 – 0x1F 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x20 – 0x2F 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x30 – 0x3F 
    0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, // A – P 
    0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // Q – 0x5F 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x60 – 0x6F 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x70 – 0x7F 
} 

unsigned int hash(string const& dna) { 
    unsigned int ret = 0; 

    for (unsigned int i = 0; i < dna.length(); ++i) 
     ret = ret * 4 + char2dna_lookup[dna[i]]; 

    return ret; 
} 

Sie können jetzt Indexieren Sie Ihr Array sehr effizient.

ifstream ifs("data.txt"); 
string line; 

if (not ifs >> line) 
    exit(1); 

unsigned* frequencies = new unsigned int[line.length()]; 

frequencies[hash(line)] = 1; 

while (ifs >> line) 
    ++frequencies[hash(line)]; 

// Print the frequencies … 

delete[] frequencies; 

Alternativ können Sie eine Bibliothek wie SeqAn für solche Aufgaben.

Answer 7

Ich denke, dass alles, was Sie tun müssen, um diese mit diesem

 if (Tag != lastTag) { 
      lastTag = Tag; 
      count = 0; 
     } 
     else { 
      count++; 
     } 

     cout << lastTag << " " << count << endl; 

wird ersetzen:

 if (Tag != lastTag) { 
      if (lastTag != "") { // don't print initial empty tag 
       cout << lastTag << " " << count << endl; 
      } 
      lastTag = Tag; 
      count = 1; // count current 
      } else { 
      count++; 
     } 

Answer 8

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

class Counter 
{ private: std::map<std::string,int>& m_count; 
    public: Counter(std::map<std::string,int>& data) :m_count(data){} 
     void operator()(std::string const& word) 
     { 
      m_count[word]++; 
     }}; 
class Printer 
{ private: std::ostream& m_out; 
    public: Printer(std::ostream& out) :m_out(out) {} 
     void operator()(std::map<std::string,int>::value_type const& data) 
     { 
      m_out << data.first << " = " << data.second << "\n"; 
     }}; 

int main() 
{ 
    std::map<std::string,int>  count; 

    for_each(std::istream_iterator<std::string>(std::cin), 
      std::istream_iterator<std::string>(), 
      Counter(count) 
      ); 

    for_each(count.begin(),count.end(), 
      Printer(std::cout) 
      ); 
}