Ayez le code suivant:

import sys


ints = [1,2,3,4,5,6,8,9,10,11,14,34,14,35,16,18,39,10,29,30,14,26,64,27,48,65]
ints.sort()
ints = list(set(ints))

c = {}

for i,v in enumerate(ints):

    if i+1 >= len(ints):
        continue

    if ints[i+1] == v + 1 or ints[i-1] == v - 1:

        if len(c) == 0:
            c[v] = [v]
            c[v].append(ints[i+1])
        else:
            added=False
            for x,e in c.items():
                last = e[-1]
                if v in e:
                    added=True
                    break

                if v - last == 1:
                    c[x].append(v)
                    added=True

            if added==False:
                c[v] = [v]
    else:
        if v not in c:
            c[v] = [v]



print('input ', ints)
print('output ', c))

L'objectif:

Étant donné une liste d'entiers, créez un dictionnaire qui contient des entiers consécutifs regroupés pour réduire la longueur totale de la liste.

Voici la sortie de ma solution actuelle:

input  [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 14, 16, 18, 26, 27, 29, 30, 34, 35, 39, 48, 64, 65]
output  {1: [1, 2, 3, 4, 5, 6], 8: [8, 9, 10, 11], 14: [14], 16: [16], 18: [18], 26: [26, 27], 29: [29, 30], 34: [34, 35], 39: [39], 48: [48], 64: [64]}

Conditions / contraintes:

  • Si l'entier actuel est soit a) dans une liste existante ou b) est le dernier élément d'une liste existante, nous ne voulons pas créer une autre liste pour cet élément. c'est-à-dire dans la plage 1 à 5 incluse, lorsque nous arrivons à 3, ne créez pas de liste 3,4, ajoutez plutôt 3 à la liste existante [1,2]

Mon itération actuelle fonctionne bien, mais elle devient exponentiellement plus lente si la liste est grande en raison de la vérification de la liste existante for x,e in c.items().

Comment puis-je accélérer cela tout en obtenant le même résultat?

Nouvelle solution (de 13 secondes à 0,03 secondes avec une liste d'entrée de 19 000 entiers):

c = {}

i = 0

last_list = None

while i < len(ints):
    cur = ints[i]

    if last_list is None:
        c[cur] = [cur]
        last_list = c[cur]

    else:

        if last_list[-1] == cur-1:
            last_list.append(cur)
        else:
            c[cur] = [cur]
            last_list = c[cur]

    i += 1
3
sk099 12 avril 2018 à 07:09

6 réponses

Meilleure réponse

Comme vous avez des listes de nombres consécutifs, je vous suggère d'utiliser des range objets au lieu de list:

d, head = {}, None
for x in l:
    if head is None or x != d[head].stop:
        head = x
    d[head] = range(head, x+1)
3
skovorodkin 12 avril 2018 à 06:26

Il existe une grande bibliothèque appelée more_itertools qui a une méthode appelée: {{X1 }}:

import more_itertools as mit
x = [1,2,3,4,5,6,8,9,10,11,14,34,14,35,16,18,39,10,29,30,14,26,64,27,48,65]
x = [list(j) for j in mit.consecutive_groups(sorted(list(set(x))))]
# [[1, 2, 3, 4, 5, 6], [8, 9, 10, 11], [14], [16], [18], [26, 27], [29, 30], [34, 35], [39], [48], [64, 65]]
dct_x = {i[0]: i for i in x}
print(dct_x)

Production:

{1: [1, 2, 3, 4, 5, 6], 8: [8, 9, 10, 11], 14: [14], 16: [16], 18: [18], 26: [26, 27], 29: [29, 30], 34: [34, 35], 39: [39], 48: [48], 64: [64, 65]}

Un autre commentaire, vous souhaitez trier après la conversion vers et depuis un ensemble, car les ensembles ne sont pas ordonnés.

1
user3483203 12 avril 2018 à 04:23

Vous pouvez essayer avec itertools, mais je voudrais essayer la récursivité:

input_dta=[1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 14, 16, 18, 26, 27, 29, 30, 34, 35, 39, 48, 64, 65]

final_=[]

def consecutives(data):
    sub_final=[]

    if not data:
        return 0
    else:
        for i,j in enumerate(data):
            try:

                if abs(data[i]-data[i+1])==1:
                    sub_final.extend([data[i],data[i+1]])



                else:
                    if sub_final:
                        final_.append(set(sub_final))




                    return consecutives(data[i+1:])
            except IndexError:
                pass

    final_.append(set(sub_final))


consecutives(input_dta)



print(final_)

Production:

[{1, 2, 3, 4, 5, 6}, {8, 9, 10, 11}, {26, 27}, {29, 30}, {34, 35}, {64, 65}]
0
Aaditya Ura 12 avril 2018 à 05:50

Voici une implémentation simple qui atteint ce que vous recherchez, en utilisant le découpage de liste:

integers = [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 14, 16, 18, 26, 27, 29, 30, 34, 35, 39, 48, 64, 65]
for i, integer in enumerate(integers):
    if i == 0:
        out_dict = {}
        start = 0
    else:
        if integer != prev_integer + 1:
            out_dict[integers[start]] = integers[start:i]
            start = i
        if i == len(integers) - 1:
            out_dict[integers[start]] = integers[start:]
    prev_integer = integer

>>>out_dict =  {1: [1, 2, 3, 4, 5, 6], 8: [8, 9, 10, 11], 14: [14], 16: [16], 18: [18], 26: [26, 27], 29: [29, 30], 34: [34, 35], 39: [39], 48: [48], 64: [64]}

Remarque: Le dictionnaire ne sera probablement pas trié par touches ascendantes, car les types dict ne sont pas classés.

0
Campbell McDiarmid 12 avril 2018 à 04:56

On peut résoudre cette tâche dans une complexité O(n) (linéaire). Restez simple:

integers = [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 14, 16, 18, 26, 27, 29, 30, 34, 35, 39, 48, 64, 65]

helper = []
counter = 0
while counter < len(integers):
  if not helper or helper[-1] + 1 != integers[counter]:
    print('gap found', integers[counter])  # do your logic
  helper.append(integers[counter])
  counter += 1

L'algorithme ci-dessus suppose que la liste d'entrée est déjà triée. Cela nous donne un énorme avantage. En même temps, on peut trier explicitement la liste des entiers avant d'exécuter cet algorithme. La complexité totale de la solution sera alors: O(n * log n) + O(n) qui est efficacement O(n * log n). Et O(n * log n) est la complexité de la procédure de tri.

Je vous suggère de vous souvenir de cette astuce extrêmement utile d'utiliser le tri avant d'aborder une tâche pour les utilisations futures.

0
Ivan Velichko 12 avril 2018 à 04:38

La solution est simple si vous utilisez une boucle for et suivez simplement votre liste actuelle. N'oubliez pas de faire une nouvelle liste lorsque vous trouvez un écart:

result = {}
cl = None
for i in ints:
    if cl is None or i - 1 != cl[-1]:
        cl = result.setdefault(i, [])
    cl.append(i)
2
Mad Physicist 12 avril 2018 à 04:59