Algoritmo de búsqueda de matriz para secuencias idénticas y distancias de caracteres -- python campo con array campo con search camp codereview Relacionados El problema

Array-search algorithm for identical sequences and character distances


3
vote

problema

Español

Aquí está el código de Python escrito para realizar las siguientes operaciones:

  1. Encuentre cada ocurrencia de una secuencia de tres letras en una matriz de caracteres (por ejemplo, una secuencia como ('a','b','c') ), incluidas las secuencias superpuestas de hasta 2 caracteres compartidos.
  2. cuenta los caracteres entre el inicio de cada secuencia y el inicio de todas las secuencias idénticas siguiéndolo.
  3. Cada vez que el mismo número de caracteres resulta del # 2, incrementa un contador para ese número específico de caracteres (independientemente de qué secuencia de caracteres lo causó).
  4. devuelve un diccionario que contiene todos los contadores acumulados para distancias de carácter.

  counts = {} # repeating groups of three identical chars in a row for i in range(len(array)-2):     for j in range(i+1,len(array)-2):         if ((array[i] == array[j]) & (array[i+1] == array[j+1]) & (array[i+2] == array[j+2])):             if counts.has_key(j-i) == False:                 counts[j-i] = 1             else:                 counts[j-i] += 1   

Este código se escribió originalmente en otro idioma de programación, pero me gustaría aplicar cualquier optimización o mejoras disponibles en Python.

Original en ingles

Here is Python code written to perform the following operations:

  1. Find each occurrence of a three-letter sequence in a character array (e.g. a sequence such as ('a','b','c')), including overlapping sequences of up to 2 shared characters.
  2. Count the characters between the start of each sequence and the start of all identical sequences following it.
  3. Every time the same number of characters results from #2, increment a counter for that specific number of characters (regardless of which character sequence caused it).
  4. Return a dictionary containing all accumulated counters for character distances.

counts = {} # repeating groups of three identical chars in a row for i in range(len(array)-2):     for j in range(i+1,len(array)-2):         if ((array[i] == array[j]) & (array[i+1] == array[j+1]) & (array[i+2] == array[j+2])):             if counts.has_key(j-i) == False:                 counts[j-i] = 1             else:                 counts[j-i] += 1 

This code was originally written in another programming language, but I would like to apply any optimizations or improvements available in Python.

        

Lista de respuestas

4
 
vote
vote
La mejor respuesta
 

1. Mejora del código

Aquí hay algunas formas en las que podría mejorar su código, al dejar el algoritmo sin cambios:

  1. Puede evitar la necesidad de verificar if3 si usa if4 .

  2. Usted está en bucle sobre Todos los pares de distintos índices entre if5 if6 . La función if7 proporciona una manera Para expresar limpiamente su intención.

  3. En lugar de comparar tres pares de elementos de matriz, puede comparar un par de arreglos de matrices .

  4. Organice el código en una función con una Docstring .

  5. generalizarlo de 3 a $ k $.

  6. Python no tiene un tipo de "matriz", pero sí tiene secuencias . Por lo que sus variables podrían ser mejor nombradas.

Aquí está el código revisado después de hacer las mejoras anteriores:

  if8  

Es posible reescribir el cuerpo de esta función como una sola expresión:

  if9  

Algunas personas prefieren este estilo de codificación, y otros prefieren la explícita de la primera versión. No hace mucha diferencia en el rendimiento, así que se reduce al gusto personal.

2. Mejora del algoritmo

Aquí hay un enfoque alternativo (que podría usar si las subsiguiones sean sequibles). Su algoritmo original es $ O (n ^ 2) $, donde $ n $ es la longitud de la secuencia. El algoritmo a continuación es $ O (N + M) $, donde $ M $ es el número de triples repetidos. Esto no hará diferente en el peor de los casos, donde $ m = θ (n ^ 2) $, pero en los casos en que $ m = ο (n ^ 2) $ debe ser una mejora.

              $("#m5-" + i).removeClass("off"); 0  
 

1. Improving the code

Here are some ways in which you could improve your code, while leaving the algorithm unchanged:

  1. You can avoid the need to check counts.has_key(j-i) if you use collections.Counter.

  2. You are looping over all pairs of distinct indexes between 0 and len(array)-2. The function itertools.combinations provides a way to cleanly express your intention.

  3. Instead of comparing three pairs of array elements, you can compare one pair of array slices.

  4. Organize the code into a function with a docstring.

  5. Generalize it from 3 to \$k\$.

  6. Python doesn't have an "array" type, but it does have sequences. So your variables could be better named.

Here's the revised code after making the above improvements:

from collections import Counter from itertools import combinations  def subseq_distance_counts(seq, k=3):     """Return a dictionary whose keys are distances and whose values     are the number of identical pairs of `k`-length subsequences     of `seq` separated by that distance. `k` defaults to 3.      """     counts = Counter()     for i, j in combinations(range(len(seq) - k + 1), 2):         if seq[i:i + k] == seq[j:j + k]:             counts[j - i] += 1     return counts 

It's possible to rewrite the body of this function as a single expression:

    return Counter(j - i                    for i, j in combinations(range(len(seq) - k + 1), 2)                    if seq[i:i + k] == seq[j:j + k]) 

Some people prefer this style of coding, and others prefer the explicitness of the first version. It doesn't make much difference to the performance, so comes down to personal taste.

2. Improving the algorithm

Here's an alternative approach (that you could use if the subsequences are hashable). Your original algorithm is \$ O(n^2) \$, where \$n\$ is the length of the sequence. The algorithm below is \$O(n + m)\$, where \$m\$ is the number of repeated triples. This won't make any different in the worst case, where \$m = xcex98(n^2)\$, but in cases where \$m = xcexbf(n^2)\$ it should be an improvement.

def subseq_distance_counts(seq, k=3):     """Return a dictionary whose keys are distances and whose values     are the number of identical pairs of `k`-length subsequences     of `seq` separated by that distance. `k` defaults to 3.      >>> subseq_distance_counts('abcabcabc')     Counter({3: 4, 6: 1})     >>> subseq_distance_counts('aaaaaa', 1)     Counter({1: 5, 2: 4, 3: 3, 4: 2, 5: 1})      """     positions = defaultdict(list) # List of positions where each subsequence appears.     for i in range(len(seq) - k + 1):         positions[seq[i:i + k]].append(i)     return Counter(j - i                    for p in positions.itervalues()                    for i, j in combinations(p, 2)) 
 
 
0
 
vote

La primera forma de mejorar el código que puedo ver es: Hazlo más legible, más expresivo. En una palabra: refactorización.

Trate de evitar tantas variables de una letra y largas líneas a medida que obstruyan el significado del código. Además, está usando dos bucles anidados y dos afirmaciones anidadas con una condición bastante larga.

Intenta asignar aquellos a variables más significativas.

La muestra de código también está incompleta, sin mostrar lo que realmente es la "matriz". Python no tiene "matrices", así que supongo que está utilizando un tipo de lista estándar. Algo que puede acelerar este tipo de búsqueda podría ser "programación dinámica", es decir, en caché de algunos cálculos reorientados. Pero esto requeriría refactor en bloques más legibles primero.

 

The first way to improve the code that I can see is: make it more readable, more expressive. In one word: refactoring.

Try to avoid so many one-letter variables and long lines as they obstruct the meaning of the code. Also, you're using two nested loops and two nested if statements with a pretty long condition.

Try assigning those to more meaningful variables.

Your code sample is also incomplete, not showing what the "array" really is. Python doesn't have "arrays" so I guess you're using a standard list type. Something that can speed up this kind of lookup could be "dynamic programming", i.e. caching of some re-occuring computations. But this would require to refactor into more readable blocks first.

 
 
   
   
0
 
vote

En lugar de tomar tres elementos a la vez y comparándolos con todos los demás tres elementos, que lleva comparaciones O (N 2 ), puede usar lo siguiente, lo que solo requiere atravesar la matriz una vez:

  from collections import defaultdict  counts = defaultdict(int) for i in xrange(len(string) - 2):     counts[tuple(string[i:i+3])] += 1   

usando esta respuesta sobre un equivalente en Python a Ruby's cada_cons , puedes hacer esto aún mejor, aunque no No sé sobre el rendimiento.

A medida que la matriz contiene caracteres, puede llamarlo una cadena.

 

Instead of taking three elements at a time and comparing them to every other three elements, which takes O(n2) comparisons, you can use the following, which only requires traversing the array once:

from collections import defaultdict  counts = defaultdict(int) for i in xrange(len(string) - 2):     counts[tuple(string[i:i+3])] += 1 

Using this answer about a Python equivalent to Ruby's each_cons, you can make this even nicer, though I don't know about the performance.

As the array contains characters, you may as well call it a string.

 
 
 
 
0
 
vote

Puede usar el diccionario simple de Python y completar las comprensiones para lograr su objetivo:

  import re string = "test test test test test" aTuplePositions = {string[y:y+3]:[m.start() for m in re.finditer(''.join([string[y],'(?=',string[y+1:y+3],')']), string)] for y in range(len(string)-2) } aTupleDistances = [t-u for z in aTuplePositions for a,u in enumerate(aTuplePositions[z]) for t in aTuplePositions[z][a+1:]] counts = {y:aTupleDistances.count(y) for y in aTupleDistances if y >= 0} counts # returns {10: 12, 20: 2, 5: 17, 15: 7}   
 

You can use simple python dictionary and list comprehensions to achieve your goal:

import re string = "test test test test test" aTuplePositions = {string[y:y+3]:[m.start() for m in re.finditer(''.join([string[y],'(?=',string[y+1:y+3],')']), string)] for y in range(len(string)-2) } aTupleDistances = [t-u for z in aTuplePositions for a,u in enumerate(aTuplePositions[z]) for t in aTuplePositions[z][a+1:]] counts = {y:aTupleDistances.count(y) for y in aTupleDistances if y >= 0} counts # returns {10: 12, 20: 2, 5: 17, 15: 7} 
 
 
       
       

Relacionados problema

3  Encuentra una cadena en una matriz  ( Find a string in an array ) 
Este programa se utiliza para obtener nombres y números de N Person, imprima los números de una persona. Por favor, ayúdame a mejorar este código. Pregunta ...

2  Pequeño marco de búsqueda de ruta genérica en Java  ( Small generic path search framework in java ) 
Tengo esta pequeña biblioteca de búsqueda de ruta genérica. No es perfecto en absoluto, así que necesito algunos comentarios para tener la oportunidad de mejo...

5  Búsqueda binaria eficiente  ( Efficient binary search ) 
Mi implementación: 157 Implementación normal: 158 La diferencia de ser mi implementación hace una conjetura en el índice del valor en función de l...

3  Nede.js JSON Búsqueda y actualización  ( Node js json searching updating ) 
Estoy trabajando en un controlador de encendido / apagado basado en la web para múltiples interruptores. Estoy buscando una buena manera de administrar el est...

31  Un algoritmo de búsqueda  ( A search algorithm ) 
NodeData8 almacena toda la información del nodo que necesita el AStar algoritmo. Esta información incluye el valor de _cache0 , _cache1 y 998877665...

14  ¿Encontrar la subtupla en una colección más grande?  ( Finding subtuple in larger collection ) 
Tengo una matriz plana de & lt; 1000 artículos y necesito encontrar los índices de una tupla / matriz más pequeña dentro de la matriz. La tupla para encontrar...

4  HackerRank Grid Search Challenge  ( Hackerrank grid search challenge ) 
He escrito una respuesta para la búsqueda de la cuadrícula desafío en Hackerrank . Por favor, hágamelo saber de cualquier mejora que se pueda hacer en mi im...

3  Búsqueda a través de archivos .xml para texto que existe en cualquier lugar del archivo  ( Search through xml files for text that exists anywhere in the file ) 
Tengo alrededor de 1000 archivos .xml en diferentes directorios bajo una carpeta raíz. Mi directorio raíz contiene la estructura de abajo: RootDir1720a...

4  Búsqueda a través de una lista de contactos para los criterios dados  ( Searching through a contact list for given criteria ) 
He estado mirando a este código por un tiempo ahora y estoy pensando que hay una manera de optimizarlo (a saber, el if - 9988777665544337 Declaración con ...

1  Buscando y reemplazando el texto  ( Searching and replacing text ) 
Modificador de listas de reproducción simple Este programa es un programa de búsqueda y reemplazo para archivos basados ​​en texto. El objetivo principal ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos