文字列のシーケンスのギャップを見つける

Question

私は文字列のシーケンスを持っています - 0000001, 0000002, 0000003....まで2百万。彼らは連続していません。隙間があることを意味する。 0000003の後に次の文字列が0000006であるかもしれません。私はこれらのすべてのギャップを見つける必要があります。上記の場合（0000004、0000005）。

これは私がこれまでにやっていることである -

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 

をしかし、あなたは推測しているだろうと私はlistを使用しておりますので、これは遅いです。 dictを使用すると、curr_idsをあらかじめ入力すると処理が高速になります。しかし、ハッシュテーブルにデータを入れることにはどんな複雑さがありますか？これを行う最速の方法は何ですか？

Answer 1

あなたはIDのリストをソートしてから一度だけ、それをステップ実行できます。

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'] 

を入力リストが順番にすでにある場合、あなたは避けることができsorted（それは少し害をしても：リストがすでにソートされている場合、Pythonのadaptive mergesortはO（n）です。

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

2百万の整数のシーケンスを格納する場合はbitarrayを使用できます。ここで、各ビットは1つの整数（ビット配列内のそのインデックスの整数）を意味します。コード例：

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

私はそれを取るint型ではなく、処理のための文字列と、出力にもう一度文字列

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