Trouver des trous de données avec masquage de bits

Question

Je suis confronté à un problème de recherche de discontinuités (intervalles) d'une longueur donnée dans une suite de nombres. Donc, par exemple, donné [1,2,3,7,8,9,10] et un écart de length=3, je vais trouver [4,5,6]. Si l'écart est length=4, je ne trouverai rien. La séquence réelle est, bien sûr, beaucoup plus longue. J'ai vu ce problème dans un bon nombre de messages, et il avait diverses applications et implémentations possibles. Un moyen que j'ai pensé pourrait fonctionner et devrait être relativement rapide est de représenter l'ensemble complet comme un tableau de bits contenant 1 pour le nombre disponible et 0 pour manquant - de sorte que ce qui précède ressemblera [1,1,1,0,0,0,1,1,1,1]. Ensuite, exécutez éventuellement une fonction de fenêtre qui va masquer un tableau de la longueur donnée avec l'ensemble complet jusqu'à ce que tous les emplacements aboutissent à 1. Cela nécessitera un seul passage sur toute la séquence dans approximativement ~ O (n), plus le coût de masquage dans chaque course.

Voici ce que je réussi à venir avec:

def find_gap(array, start=0, length=10): 
    """ 
    array: assumed to be of length MAX_NUMBER and contain 0 or 1 
      if the value is actually present 
    start: indicates what value to start looking from 
    length: what the length the gap should be 
    """ 

    # create the bitmask to check against 
    mask = ''.join([1] * length) 

    # convert the input 0/1 mapping to bit string 
    # e.g - [1,0,1,0] -> '1010' 
    bits =''.join([ str(val) for val in array ]) 

    for i in xrange(start, len(bits) - length): 

     # find where the next gap begins 
     if bits[i] != '0': continue 

     # gap was found, extract segment of size 'length', compare w/ mask 
     if (i + length < len(bits)): 
      segment = bits[i:i+length] 

      # use XOR between binary masks 
      result = bin(int(mask, 2)^int(segment, 2)) 

      # if mask == result in base 2, gap found 
      if result == ("0b%s" % mask): return i 

    # if we got here, no gap exists 
    return -1 

Ceci est assez rapide pour ~ 100k (< 1 sec). J'apprécierais des conseils sur la façon de rendre cela plus rapide/plus efficace pour les grands ensembles. Merci!

Answer 1

Recherchez les différences entre les nombres adjacents, puis recherchez une différence suffisamment grande. Nous trouvons les différences en construisant deux listes - tous les nombres mais le premier, et tous les nombres mais le dernier - et en les soustrayant par paires. Nous pouvons utiliser zip pour apparier les valeurs.

def find_gaps(numbers, gap_size): 
    adjacent_differences = [(y - x) for (x, y) in zip(numbers[:-1], numbers[1:])] 
    # If adjacent_differences[i] > gap_size, there is a gap of that size between 
    # numbers[i] and numbers[i+1]. We return all such indexes in a list - so if 
    # the result is [] (empty list), there are no gaps. 
    return [i for (i, x) in enumerate(adjacent_differences) if x > gap_size] 

(également, s'il vous plaît apprendre quelques expressions idiomatiques Python. Nous préférons l'itération directe, et nous avons un type réel booléenne.)

Answer 2

Si c'est vous l'efficacité après, je ferais quelque chose le long les lignes suivantes (où x la liste des numéros de séquence):

for i in range(1, len(x)): 
    if x[i] - x[i - 1] == length + 1: 
    print list(range(x[i - 1] + 1, x[i])) 

Answer 3

Quasiment ce aix a fait ... mais obtenir seulement les lacunes de la longueur désirée:

def findGaps(mylist, gap_length, start_idx=0): 
    gap_starts = [] 
    for idx in range(start_idx, len(mylist) - 1): 
     if mylist[idx+1] - mylist[idx] == gap_length + 1: 
      gap_starts.append(mylist[idx] + 1) 

    return gap_starts 

EDIT: Ajusté aux souhaits de l'OP.

Answer 4

Ils fournissent une seule marche de votre liste d'entrée.

Liste des valeurs d'écart de longueur donnée:

from itertools import tee, izip 
def gapsofsize(iterable, length): 
    a, b = tee(iterable) 
    next(b, None) 
    return (p for x, y in izip(a, b) if y-x == length+1 for p in xrange(x+1,y)) 

print list(gapsofsize([1,2,5,8,9], 2)) 

[3, 4, 6, 7] 

Toutes les valeurs de l'écart:

def gaps(iterable): 
    a, b = tee(iterable) 
    next(b, None) 
    return (p for x, y in izip(a, b) if y-x > 1 for p in xrange(x+1,y)) 

print list(gaps([1,2,4,5,8,9,14])) 

[3, 6, 7, 10, 11, 12, 13] 

Liste des lacunes en tant que vecteurs:

def gapsizes(iterable): 
    a, b = tee(iterable) 
    next(b, None) 
    return ((x+1, y-x-1) for x, y in izip(a, b) if y-x > 1) 

print list(gapsizes([1,2,4,5,8,9,14])) 

[(3, 1), (6, 2), (10, 4)] 

Notez que ce sont des générateurs et consomment très peu de mémoire. J'aimerais savoir comment cela fonctionne sur votre jeu de données de test.

Answer 5

Vous pouvez utiliser XOR et Shift et il fonctionne en temps approximatif O (n). Cependant, en pratique, la construction d'un index (liste de hachage de tous les intervalles supérieurs à une certaine longueur minimum) pourrait être une meilleure approche.En supposant que vous commenciez avec une séquence de ces nombres entiers (plutôt que d'un masque de bits), vous construisez un index en passant simplement par-dessus la séquence; Chaque fois que vous trouvez un écart supérieur à votre seuil, vous ajoutez cette taille à votre dictionnaire (instanciez-la en tant que liste vide si nécessaire, puis ajoutez le décalage dans la séquence.)

(une valeur supérieure à votre seuil souhaité) dans votre séquence

Une bonne chose à propos de cette approche est que vous devriez être en mesure de maintenir cet index lorsque vous modifiez la liste de base, donc le O (n * log (n)) temps initial passé la construction de l'indice est amorti par O (log (n)) pour les requêtes ultérieures coût et mises à jour des indices

est ici une fonction très grossière pour construire le gap_index().

def gap_idx(s, thresh=2): 
    ret = dict() 
    lw = s[0] # initial low val. 
    for z,i in enumerate(s[1:]): 
     if i - lw < thresh: 
      lw = i 
      continue 
     key = i - lw 
     if key not in ret: 
      ret[key] = list() 
     ret[key].append(z) 
     lw = i 
    return ret 

Une classe permettant de gérer à la fois un ensemble de données et l'index peut être mieux construite autour du module «bisect» intégré et de sa fonction insort().