Estoy buscando una función para hacer que la lista esté lo más desordenada posible. Preferiblemente en Python.
Trasfondo:
Quiero verificar los estados de las URL y ver si las URL dan un 404 o no. Solo uso asyncio
y módulos de requests
. Nada sofisticado.
Ahora no quiero sobrecargar los servidores, así que quiero minimizar la verificación de las URL que están en el mismo dominio al mismo tiempo. Tengo la idea de ordenar las URL de manera que los elementos que están cerca uno del otro (que tienen la misma clave de clasificación = nombre de dominio) se coloquen lo más separados posible en la lista.
Un ejemplo con números:
a=[1,1,2,3,3] # <== sorted list, sortness score = 2 0,1,2,3,4 # <== positions
podría desclasificarse como:
b=[1,3,2,1,3] # <== unsorted list, sortness score = 6 0,1,2,3,4 # <== positions
Diría que podemos calcular una puntuación de clasificación sumando las distancias entre elementos iguales (que tienen la misma clave = nombre de dominio). Mayor clasificación significa mejor sin clasificar. Tal vez haya una mejor manera de probar la falta de orden.
El puntaje de clasificación para la lista a
es 2. La suma de las distancias para 1 es (1-0)=1, para 2 es 0, para 3 es (4-3)=1.
El puntaje de clasificación para la lista b
es 6. La suma de las distancias para 1 es (3-0)=3, para 2 es 0, para 3 es (4-1)=3.
La lista de URL se parecería a una lista de tuplas (dominio, URL):
[ ('example.com', 'http://example.com/404'), ('test.com', 'http://test.com/404'), ('test.com', 'http://test.com/405'), ('example.com', 'http://example.com/405'), ... ]
Estoy trabajando en un prototipo que funciona bien, pero no de manera óptima, ya que puedo encontrar algunas variantes que es mejor ordenarlas a mano.
¿Alguien quiere darle una oportunidad?
Este es mi código , pero no es genial :):
from collections import Counter from collections import defaultdict import math def test_unsortness(lst:list) -> float: pos = defaultdict(list) score = 0 # Store positions for each key # input = [1,3,2,3,1] => {1: [0, 4], 3: [1, 3], 2: [2]} for c,l in enumerate(lst): pos[l].append(c) for k,poslst in pos.items(): for i in range(len(poslst)-1): score += math.sqrt(poslst[i+1] - poslst[i]) return score def unsort(lst:list) -> list: free_positions = list(range(0,len(lst))) output_list = [None] * len(free_positions) for val, count in Counter(lst).most_common(): pos = 0 step = len(free_positions) / count for i in range(count): output_list[free_positions[int(pos)]] = val free_positions[int(pos)] = None # Remove position later pos = pos + step free_positions = [p for p in free_positions if p] return output_list lsts = list() lsts.append( [1,1,2,3,3] ) lsts.append( [1,3,2,3,1] ) # This has the worst score after unsort() lsts.append( [1,2,3,0,1,2,3] ) # This has the worst score after unsort() lsts.append( [3,2,1,0,1,2,3] ) # This has the worst score after unsort() lsts.append( [3,2,1,3,1,2,3] ) # This has the worst score after unsort() lsts.append( [1,2,3,4,5] ) for lst in lsts: ulst = unsort(lst) print( ( lst, '%.2f'%test_unsortness(lst), '====>', ulst, '%.2f'%test_unsortness(ulst), ) ) # Original score Unsorted score # ------- ----- -------- ----- # ([1, 1, 2, 3, 3], '2.00', '====>', [1, 3, 1, 3, 2], '2.83') # ([1, 3, 2, 3, 1], '3.41', '====>', [1, 3, 1, 3, 2], '2.83') # ([1, 2, 3, 0, 1, 2, 3], '6.00', '====>', [1, 2, 3, 1, 2, 3, 0], '5.20') # ([3, 2, 1, 0, 1, 2, 3], '5.86', '====>', [3, 2, 1, 3, 2, 1, 0], '5.20') # ([3, 2, 1, 3, 1, 2, 3], '6.88', '====>', [3, 2, 3, 1, 3, 2, 1], '6.56') # ([1, 2, 3, 4, 5], '0.00', '====>', [1, 2, 3, 4, 5], '0.00')
PD. No estoy buscando solo una función aleatoria y sé que hay rastreadores que pueden administrar cargas de dominio, pero esto es solo por ejercicio.
En lugar de desordenar su lista de URL, ¿por qué no agruparlas por dominio, cada una en una cola, y luego procesarlas de forma asíncrona con un retraso (¿aleatorio?) en el medio?
Me parece menos complejo que lo que está tratando de hacer para lograr lo mismo y si tiene mucho dominio, siempre puede acelerar el número para ejecutarlo simultáneamente en ese punto.
Usé Google OR Tools para resolver este problema. Lo enmarqué como un problema de optimización de restricciones y lo modelé de esa manera.
from collections import defaultdict from itertools import chain, combinations from ortools.sat.python import cp_model model = cp_model.CpModel() data = [ ('example.com', 'http://example.com/404'), ('test.com', 'http://test.com/404'), ('test.com', 'http://test.com/405'), ('example.com', 'http://example.com/405'), ('google.com', 'http://google.com/404'), ('example.com', 'http://example.com/406'), ('stackoverflow.com', 'http://stackoverflow.com/404'), ('test.com', 'http://test.com/406'), ('example.com', 'http://example.com/407') ] tmp = defaultdict(list) for (domain, url) in sorted(data): var = model.NewIntVar(0, len(data) - 1, url) tmp[domain].append(var) # store URLs as model variables where the key is the domain vals = list(chain.from_iterable(tmp.values())) # create a single list of all variables model.AddAllDifferent(vals) # all variables must occupy a unique spot in the output constraint = [] for urls in tmp.values(): if len(urls) == 1: # a single domain does not need a specific constraint constraint.append(urls[0]) continue combos = combinations(urls, 2) for (x, y) in combos: # create combinations between each URL of a specific domain constraint.append((x - y)) model.Maximize(sum(constraint)) # maximize the distance between similar URLs from our constraint list solver = cp_model.CpSolver() status = solver.Solve(model) output = [None for _ in range(len(data))] if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: for val in vals: idx = solver.Value(val) output[idx] = val.Name() print(output) ['http://example.com/407', 'http://test.com/406', 'http://example.com/406', 'http://test.com/405', 'http://example.com/405', 'http://stackoverflow.com/404', 'http://google.com/404', 'http://test.com/404', 'http://example.com/404']
No existe una definición obvia de desorden que funcione mejor para usted, pero aquí hay algo que al menos funciona bien:
En orden ordenado, los índices de los elementos que están juntos suelen diferir solo en los bits más pequeños. Al invertir el orden de los bits, los nuevos índices para los elementos que están muy juntos difieren en los bits más grandes , por lo que terminarán muy separados.
def bitreverse(x, bits): # reverse the lower 32 bits x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1) x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2) x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4) x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8) x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16) # take only the appropriate length return (x>>(32-bits)) & ((1<<bits)-1) def antisort(inlist): if len(inlist) < 3: return inlist inlist = sorted(inlist) #get the next power of 2 list length p2len = 2 bits = 1 while p2len < len(inlist): p2len *= 2 bits += 1 templist = [None] * p2len for i in range(len(inlist)): newi = i * p2len // len(inlist) newi = bitreverse(newi, bits) templist[newi] = inlist[i] return [item for item in templist if item != None] print(antisort(["a","b","c","d","e","f","g", "h","i","j","k","l","m","n","o","p","q","r", "s","t","u","v","w","x","y","z"]))
Producción:
['a', 'n', 'h', 'u', 'e', 'r', 'k', 'x', 'c', 'p', 'f', 's', 'm', 'z', 'b', 'o', 'i', 'v', 'l', 'y', 'd', 'q', 'j', 'w', 'g', 't']