¿Existe una cadena de verificación? Ve 20 veces

Question

Tengo un archivo de copia de seguridad de archivos XML de la biblioteca ITunes: unos 15 MB.

Tengo 20K archivos de música en mi unidad C y aproximadamente 25K en la unidad E con estructuras de carpetas exactamente similares.

Estoy recorriendo la primera ubicación y yendo archivo por archivo y comprobando si el archivo se extravió en la segunda ubicación. Esa parte funciona para mi

Ahora, para todos los archivos duplicados, si la ruta del archivo desde la unidad E existe en el XML, pero la ruta del disco C no existe en el XML, entonces quiero eliminar el archivo de la unidad C.

¿Cuál es la mejor manera de comprobar si existe una cadena en el archivo XML (tengo que hacer esto al menos 20K veces)?

Answer 1

Ordene alfabéticamente su lista de cadenas con las que hace coincidir, luego construya una matriz de índices que indique dónde comienza su lista para cada carácter que es un carácter inicial para una de las cadenas, tal vez indexando a la segundo personaje dependiendo de la amplitud de la variedad y si su coincidencia es sensible a mayúsculas o minúsculas.

Lea el archivo carácter por carácter con una secuencia para minimizar la huella de memoria, revise en la matriz de índice para ver dónde comienza y termina en la lista de cadenas para que pueda sacar esa página de caracteres, si hay algo que empiece por esas combinaciones de personajes. Luego continúe filtrando dentro de la página hasta que tenga una coincidencia restante y el siguiente carácter coincida 0.

Elimine esa cadena de la lista de cadenas para que coincida, colóquela en otra lista si lo desea. Luego comience a verificar su índice en el siguiente personaje y continúe haciéndolo cada vez que se encuentre sin coincidencias.

El índice le proporciona un agregado más eficiente para minimizar el número de elementos iterados.

Esto podría darle un índice de profundidad de dos caracteres:

Dictionary<string,int> stringIndex = new Dictionary<char,int>(); 
for(int i = 0; i < sortedSearchStrings.Length; i++;) 
{ 
    if (!stringIndex.Keys.Contains(sortedSearchStrings[i][0])) stringIndex[sortedSearchStrings[i][0]] = i; 
    if (!stringIndex.Keys.Contains(sortedSearchStrings[i][0] + sortedSearchStrings[i][1])) stringIndex[sortedSearchStrings[i][0] + sortedSearchStrings[i][1]] = i; 
} 

y para buscar el índice de partida en su lista que acaba de acceso:

int startOfCurrentCharPage = stringIndex[string.Format("{0}{1}", lastChar, currentChar)]; 

Answer 2

Dependiendo de si desea contar cuántas veces se produce una cadena, o si simplemente está comprobando la existencia de las cadenas, su enfoque será ligeramente diferente. Sin embargo, estas son las dos maneras que consideraría hacerlo:

Si quiere hacerlo con un mínimo de memoria:

carga el archivo línea por línea (o, si el código XML no está formateado como esto , nodo por nodo usando un analizador XML ... Creo que hay analizadores XML que pueden hacer esto). Haga una operación de búsqueda en la línea para cada cadena. No más de una línea/nodo estará en la memoria a la vez, si sobrescribe correctamente la última línea. La desventaja de esto es que tomará más tiempo y el archivo estará abierto por más tiempo.

Si quiere hacerlo rápido:

carga todo el archivo en la memoria, no se molestan en analizar, y sólo la búsqueda de cada cadena.

EDITAR

Sobre la base de sus aclaraciones, quisiera en primer lugar recoger todos los nombres de archivos duplicados en una matriz, y luego proceder a escanear cada línea del archivo XML usando mi primer método (arriba). Si ya está almacenando 20K nombres de archivo en la memoria, dudaría en cargar todo el XML de 15 MB al mismo tiempo.

Answer 3

Sugerencia: cargue como texto, use una expresión regular para extraer las cadenas deseadas (supongo que se incluyen con una etiqueta específica) y compile una lista hash con ellas. Puedes usar la lista para verificar la existencia.

Answer 4

leer cada cadena desde el XML y escribirlos en un HashSet<string>. Cuando desee buscar una cadena, búsquela en HashSet. El costo será O (n) para leer el XML y O (n) para realizar las búsquedas n desde el HashSet. No intente buscar repetidamente en el XML (en su lugar haga sus 20,000 búsquedas en el HashSet), porque el XML no está indexado/optimizado para la búsqueda.

Answer 5

¿Sería posible trabajar directamente desde el documento xml y omitir el primer paso?

Si es así, puede utilizar Xml.XmlDocument y, a partir de allí, Xml.XmlNode.SelectNodes (cadena), utilizando xpath para navegar por el documento. No sé qué tipo de información está presente en el documento, pero la forma en que se redacta la segunda etapa da la idea de que, a veces, tanto la ruta en C: \ como la ruta en E: \ están presentes. Si es así, sería tan simple como dos IO.File.Exists cheques y luego un IO.File.Delete().

Lo que quiero decir es que en lugar de buscar N en un documento XML para una cadena, realice su búsqueda a través del documento y elimine duplicados sobre la marcha para que solo ejecute el documento una vez.

No uso iTunes o tengo una de sus copias de seguridad de biblioteca a mano para decir si podría funcionar o no, sin embargo.

Answer 6

Aquí hay una solución simple usando Linq. Se ejecuta lo suficientemente rápido como para un solo uso:

using System; 
using System.IO; 
using System.Linq; 
using System.Xml.Linq; 

class ITunesChecker 
{ 
    static void Main(string[] args) 
    { 
     // retrieve file names 
     string baseFolder = @"E:\My Music\"; 
     string[] filesM4a = Directory.GetFiles(baseFolder, "*.m4a", SearchOption.AllDirectories); 
     string[] filesMp3 = Directory.GetFiles(baseFolder, "*.mp3", SearchOption.AllDirectories); 
     string[] files = new string[filesM4a.Length + filesMp3.Length]; 
     Array.Copy(filesM4a, 0, files, 0, filesM4a.Length); 
     Array.Copy(filesMp3, 0, files, filesM4a.Length, filesMp3.Length); 

     // convert to the format used by iTunes 
     for (int i = 0; i < files.Length; i++) 
     { 
      Uri uri = null; 
      if (Uri.TryCreate(files[i], UriKind.Absolute, out uri)) 
      { 
       files[i] = uri.AbsoluteUri.Replace("file:///", "file://localhost/"); 
      } 
     } 

     // read the files from iTunes library.xml 
     XDocument library = XDocument.Load(@"E:\My Music\iTunes\iTunes Music Library.xml"); 
     var q = from node in library.Document.Descendants("string") 
       where node.ElementsBeforeSelf("key").Where(n => n.Parent == node.Parent).Last().Value == "Location" 
       select node.Value; 

     // do the set operations you are interested in 
     var missingInLibrary = files.Except(q, StringComparer.InvariantCultureIgnoreCase); 
     var missingInFileSystem = q.Except(files, StringComparer.InvariantCultureIgnoreCase); 
     var presentInBoth = files.Intersect(q, StringComparer.InvariantCultureIgnoreCase); 
    } 
}