vacíos en una secuencia de cadenas

Question

Tengo una secuencia de cadenas - 0000001, 0000002, 0000003.... hasta 2 millones. Ellos no son contiguos. Lo que significa que hay lagunas. Digamos después de 0000003 que la próxima cadena podría ser 0000006. Necesito averiguar todos estos huecos. En el caso anterior (0000004, 0000005).

Esto es lo que he hecho hasta ahora -

gaps = list() 
total = len(curr_ids) 

for i in range(total): 
    tmp_id = '%s' %(str(i).zfill(7)) 
    if tmp_id in curr_ids: 
     continue 
    else: 
     gaps.append(tmp_id) 
return gaps 

Pero como es de suponer, esto es lento ya que estoy usando list. Si uso un dict, a curr_ids rellenar previamente que va a ser más rápido. ¿Pero cuál es la complejidad de poblar una tabla hash? ¿Cuál es la forma más rápida de hacer esto?

Answer 1

Se puede ordenar la lista de los identificadores y luego paso a través de él una sola vez:

def find_gaps(ids): 
    """Generate the gaps in the list of ids.""" 
    j = 1 
    for id_i in sorted(ids): 
     while True: 
      id_j = '%07d' % j 
      j += 1 
      if id_j >= id_i: 
       break 
      yield id_j 

>>> list(find_gaps(["0000001", "0000003", "0000006"])) 
['0000002', '0000004', '0000005'] 

Si la lista de entrada ya está en orden, entonces puede evitar el sorted (a pesar de que hace poco daño : de Python adaptive mergesort es O (n ) si la lista ya está ordenada).

Answer 2

seq = *the sequence of strings* 
n = 2000000 

gaps = set(str(i).zfill(7) for i in range(1,n+1)) - set(seq) 

Answer 3

Para almacenar la secuencia de 2 millones de ints, puede usar bitarray. Aquí cada bit significa un entero (el entero de ese índice en bitarray). Código de ejemplo:

gaps = [] 
# bitarray is 0 based 
a = bitarray.bitarray(total + 1) 
a.setall(False) 
for sid in curr_ids: 
    a[int(sid)] = True 
for i in range(1, total): 
    if not a[i]: 
     gaps.append('%07d' %(i)) 
return gaps 

Answer 4

Yo sugeriría que tomar int en lugar de la secuencia para el procesamiento y luego lo que es una cadena de nuevo en la salida

j=0 
n=2000000 
#create a list of int number from your string 
foo = [i for i in range(n)] 
#creating gaps 
foo.remove(1) 
foo.remove(50) 
while j<n: 
    for i in foo: 
     if i>j: 
      print '%07d'%j 
      j+=1 
     j+=1