Comprobar si hay duplicados en gran vector de cadenas

Question

Estoy intentando encontrar casos duplicados de cadenas en las que tengo un vector de ~ 2,5 millones de cuerdas ~

En el momento en que usar algo como:

std::vector<string> concatVec; // Holds all of the concatenated strings containing columns C,D,E,J and U. 
std::vector<string> dupecheckVec; // Holds all of the unique instances of concatenated columns 
std::vector<unsigned int> linenoVec; // Holds the line numbers of the unique instances only 

// Copy first element across, it cannot be a duplicate yet 
dupecheckVec.push_back(concatVec[0]); 
linenoVec.push_back(0); 

// Copy across and do the dupecheck 
for (unsigned int i = 1; i < concatVec.size(); i++) 
{ 
    bool exists = false; 

    for (unsigned int x = 0; x < dupecheckVec.size(); x++) 
    { 
     if (concatVec[i] == dupecheckVec[x]) 
     { 
      exists = true; 
     } 
    } 

    if (exists == false) 
    { 
     dupecheckVec.push_back(concatVec[i]); 
     linenoVec.push_back(i); 
    } 
    else 
    { 
     exists = false; 
    } 
} 

Lo que está bien para archivos pequeños, pero obviamente termina tomando un tiempo extremadamente largo a medida que crece el tamaño del archivo debido al ciclo anidado y el número creciente de cadenas contenidas en dupecheckVec.

¿Cuál podría ser una forma menos horrible de hacer esto en un archivo grande?

Answer 1

Si no te importa la reordenación del vector, entonces esto debe hacerlo en O(n*log(n)) tiempo:

std::sort(vector.begin(), vector.end()); 
vector.erase(std::unique(vector.begin(), vector.end()), vector.end()); 

Para preservar el orden, en su lugar podría usar un vector de (número de línea, cadena *) pares: ordenar por cadena, uniquify utilizando un comparador que compara contenido de la cadena, y finalmente ordenar por número de línea, a lo largo de las líneas de:

struct pair {int line, std::string const * string}; 

struct OrderByLine { 
    bool operator()(pair const & x, pair const & y) { 
     return x.line < y.line; 
    } 
}; 

struct OrderByString { 
    bool operator()(pair const & x, pair const & y) { 
     return *x.string < *y.string; 
    } 
}; 

struct StringEquals { 
    bool operator()(pair const & x, pair const & y) { 
     return *x.string == *y.string; 
    } 
}; 

std::sort(vector.begin(), vector.end(), OrderByString()); 
vector.erase(std::unique(vector.begin(), vector.end(), StringEquals()), vector.end()); 
std::sort(vector.begin(), vector.end(), OrderByLine()); 

Answer 2

Puede ordenar cuál es O (n logn), y luego cualquier elemento igual debe ser consecutivo, de modo que puede simplemente compararlo con el siguiente elemento, que es solamente O (n). Mientras que su solución ingenua es O (n^2).

Answer 3

Uso std::unique ver this

Answer 4

se puede utilizar una tabla hash que utiliza cadenas como claves y números enteros como valores (el conteo). A continuación, sólo iterar sobre la lista de cadenas y de incrementar el valor para cada cadena en 1. Finalmente iterar sobre la tabla hash y guardan las cuerdas con un recuento de 1

[ACTUALIZACIÓN] Otra solución:

• Utilice una tabla hash con cadena como clave y el índice de posición de la cadena en el vector/matriz
• Para cada cadena en el vector:
  • Si cadena está contenido en tabla hash [opcional: eliminar la entrada y] continuar
  • De lo contrario poner el índice de la posición de la cadena actual en la tabla hash usando la cadena como clave y continuar
• Cuando hace iterar sobre los índices de tabla hash y utilizar para recuperar cadenas únicas

Esta solución le da los índices de todas las cadenas, filtrando duplicados. Si solo quiere esas cadenas, que no tienen duplicados, debe eliminar la entrada de la tabla hash si la cadena ya se utiliza en la capa hastable.