Problème avec une HashMap (STL/SGI)

**nphilippe1684** · 15/02/2011, 19h09

Je te mets le code avec tes modifs :

-----> type.h

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
#ifndef TYPES_H
#define TYPES_H
 
#ifndef ullong
#define ullong unsigned long long
#endif
 
#ifndef uint
#define uint unsigned int
#endif
 
#endif

-----> StringFactor.h

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#ifndef STRING_FACTOR_H
#define STRING_FACTOR_H
#include "type.h"
#include <string>
 
using namespace std;
 
class StringFactor {
private:
  char *m_factor; 
public:
  StringFactor(const char *string, uint pos, uint kmer_length);
 
  ~StringFactor();
 
  char *c_str() const;
 
};
#endif

------> StringFactor.cpp

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include "StringFactor.h"
 
StringFactor::StringFactor(const char *string, uint pos, uint kmer_length) {
  char m_factor[kmer_length+1]; // +1 pour le 0 terminal
  strncpy(m_factor, string.c_str()+pos,kmer_length);
}
 
~StringFactor()::StringFactor(){
  // delete [] m_factor;
}
 
char *c_str() const {
  return m_factor;
}

------> buildSGIHash.cpp

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
#include <iostream>
#include <fstream>
#include <string>
#include <sys/time.h>
#include <ext/hash_map>
#include "type.h"
#include "StringFactor.h"
extern "C" {
#include <time.h>
}
 
using namespace std;
namespace std { using namespace __gnu_cxx; }
 
ullong getChrono() {
  struct timeval time;
  time_t sec;
  suseconds_t usec;
 
  if (gettimeofday(&time,NULL) != -1) {
    sec = time.tv_sec;
    usec = time.tv_usec;
    return (ullong)sec*1000000+usec;
  }
  return 0;
}
 
 
struct HashStringFactor : public hash<const char *>{
 
};
 
struct EqStringFactor{
  bool operator()(const StringFactor &s1, const StringFactor &s2) const {
    return strcmp(s1.c_str(),s2.c_str())==0;
  }
};
 
 
int main(int argc, char **argv)
{
  if (argc < 4){
    cerr << "Usage: " << argv[0] <<" read_file read_length threshold" << endl; 
    exit(1);
  }
  ullong start = getChrono();
 
  ifstream reads;
  reads.open(argv[1], ios::in);
  if (! reads.is_open()) {
    cerr << "Cannot open reads file: " << argv[1] << endl;
    exit(2);
  }
  reads.seekg (0, ios::end);
  ullong length = reads.tellg();
  uint read_length = atoi(argv[2]);
  char *line = new char[read_length+1];
  reads.seekg (0, ios::beg);
  ullong nb_reads = length/(read_length+1);
  uint threshold= atoi(argv[3]);
 
  //ullong nb_elements = (read_length-threshold)*nb_reads;
  hash_map<StringFactor, int, HashStringFactor, EqStringFactor > hash_kmer;
 
  ullong current = 0;
  //  cout << "nb_reads: " << nb_reads << endl; 
  //cout << sizeof(ullong) << endl;
  ullong state = 1;
  while (current < nb_reads) {
    if (current >= state*10000){
      cout << current << " reads is included in stl_hash in " << (getChrono()-start)/1000000. << " s" << endl;
      state++;
    }
    reads.getline(line, read_length+1);
    for (ullong i = 0 ; i < (read_length-threshold) ; i++){
      StringFactor factor = StringFactor(line,i,threshold);
      hash_kmer[factor] ++ ;
    }
    current++;
  }  
  cout << "nb_factors indexed in hash_kmer: " << hash_kmer.size() << endl;
  cerr << "Creation of stl_hash_map: " << (getChrono()-start)/1000000. << " s" << endl;
  return 0;
}

----> Makefile

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
CPP=g++
DBG=# -O0 
CPPFLAGS=-Wall -g $(DBG) -funroll-loops -O2
CFLAGS=-Wall -ansi
OBJ=StringFactor.o buildSGIHash.o
EXE=buildSGIHash
all: $(EXE)
 
buildSGIHash : % : %.o $(OBJ)
        $(CPP) -o $@ $^ 
 
%.o : %.cpp
        $(CPP) $(CPPFLAGS) -c $^
 
%.cpp : %.h
 
%.c : %.h
 
clean: 
        rm -f *.o

Je ne pense pas que ce soit la seule erreur, il en n'indique qu'une mais à mon avis une fois que celle-là sera corrigée, il y aura d'autres surprises.

En tout cas merci beaucoup pour ton soucis d'avoir une implémentation efficace !

screetch · 16/02/2011, 11h59

ah oui j'avais dit des betises avec mon hash, je reposte le code corrigé:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#ifndef STRING_FACTOR_H
#define STRING_FACTOR_H
#include "type.h"
#include <string>
 
using namespace std;
 
class StringFactor {
private:
  static const int max_kmer = 30;
  char m_factor[max_kmer];
public:
  StringFactor(const char *string, uint pos, uint kmer_length);
 
  ~StringFactor();
 
  const char *c_str() const;
 
};
#endif

je croyais que ton kmer etait statique donc connu a la compilation. C'est beaucoup plus facile dans ce cas puisque si tu connais la taille tu peux prévoir assez d'espace sans recourir a une allocation dynamique.
Mais comme c'était pas possible, j'ai ajouté une constante max_kmer qui me permet de réserver suffisemment d'espace (peut etre trop mais pas beaucoup)

le CPP:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include "StringFactor.h"
#include <cassert>
#include <cstring>
 
StringFactor::StringFactor(const char *string, uint pos, uint kmer_length) {
  assert(kmer_length < max_kmer);
  strncpy(m_factor, string+pos,kmer_length);
}
 
StringFactor::~StringFactor(){
}
 
const char *StringFactor::c_str() const {
  return m_factor;
}

j'ai juste corrigé quelques erreurs qui seraient apparues si tu avais pu lancer la compilation, pas de gros changement

le principal C++:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <sys/time.h>
#include <ext/hash_map>
#include "type.h"
#include "StringFactor.h"
#include <cstring>
extern "C" {
#include <time.h>
}
 
using namespace std;
namespace std { using namespace __gnu_cxx; }
 
ullong getChrono() {
  struct timeval time;
  time_t sec;
  long usec;
 
  if (gettimeofday(&time,NULL) != -1) {
    sec = time.tv_sec;
    usec = time.tv_usec;
    return (ullong)sec*1000000+usec;
  }
  return 0;
}
 
 
struct HashStringFactor : public hash<const char *>{
 size_t operator()(const StringFactor& s) const { return  hash<const char *>::operator()(s.c_str()); }
};
 
struct EqStringFactor{
  bool operator()(const StringFactor &s1, const StringFactor &s2) const {
    return strcmp(s1.c_str(),s2.c_str())==0;
  }
};
 
 
int main(int argc, char **argv)
{
  if (argc < 4){
    cerr << "Usage: " << argv[0] <<" read_file read_length threshold" << endl; 
    exit(1);
  }
  ullong start = getChrono();
 
  ifstream reads;
  reads.open(argv[1], ios::in);
  if (! reads.is_open()) {
    cerr << "Cannot open reads file: " << argv[1] << endl;
    exit(2);
  }
  reads.seekg (0, ios::end);
  ullong length = reads.tellg();
  uint read_length = atoi(argv[2]);
  char *line = new char[read_length+1];
  reads.seekg (0, ios::beg);
  ullong nb_reads = length/(read_length+1);
  uint threshold= atoi(argv[3]);
 
  //ullong nb_elements = (read_length-threshold)*nb_reads;
  hash_map<StringFactor, int, HashStringFactor, EqStringFactor > hash_kmer;
 
  ullong current = 0;
  //  cout << "nb_reads: " << nb_reads << endl; 
  //cout << sizeof(ullong) << endl;
  ullong state = 1;
  while (current < nb_reads) {
    if (current >= state*10000){
      cout << current << " reads is included in stl_hash in " << (getChrono()-start)/1000000. << " s" << endl;
      state++;
    }
    reads.getline(line, read_length+1);
    for (ullong i = 0 ; i < (read_length-threshold) ; i++){
      StringFactor factor = StringFactor(line,i,threshold);
      hash_kmer[factor] ++ ;
    }
    current++;
  }  
  cout << "nb_factors indexed in hash_kmer: " << hash_kmer.size() << endl;
  cerr << "Creation of stl_hash_map: " << (getChrono()-start)/1000000. << " s" << endl;
  return 0;
}

le seul gros changement c'est le hash. Comme je l'avais dit plus haut, tu as besoin d'une fonction de hash sur un StringFactor, donc une structure du type

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
struct hash
{
  size_t operator()(const StringFactor& factor) {... }
};

or tu sais déja comment avoir un hash de string, donc on peut le réutiliser et l'adapter, c'est pour ca qu'on hérite de hash<const char *>: pour mettre a disposition dans le hash la fonction de hash des string:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
struct HashStringFactor : public hash<const char *>{
 size_t operator()(const StringFactor& s) const { return  hash<const char *>::operator()(s.c_str()); }
};

donc maintenant on peut hasher des Stringfactor

je n'ai pas lancé le programme mais je suis curieux du résultat si tu as moins d'allocations mémoire

**nphilippe1684** · 16/02/2011, 16h06

Un grand merci à screetch pour avoir résolu mon problème !

Problème avec une HashMap (STL/SGI)

C++

Discussions similaires

Partager

Partager