我正在寻找一个函数来使列表尽可能不排序。最好用Python。
背景故事:
我想检查 URL 状态并查看 URL 是否给出 404。我只是用asyncio
and requests
模块。没有什么花哨。
现在我不想让服务器超载,所以我想尽量减少同时检查同一域上的 URL。我的想法是对 URL 进行排序,使列表中彼此接近的项目(具有相同的排序键 = 域名)尽可能远离彼此。
带有数字的示例:
a=[1,1,2,3,3] # <== sorted list, sortness score = 2
0,1,2,3,4 # <== positions
可以未排序为:
b=[1,3,2,1,3] # <== unsorted list, sortness score = 6
0,1,2,3,4 # <== positions
我想说,我们可以通过对相等项(具有相同的键 = 域名)之间的距离求和来计算排序分数。较高的排序意味着更好的未排序。也许有更好的方法来测试不友善。
列表的排序得分a
是2。1的距离总和是(1-0)=1,2的距离总和是0,3的距离总和是(4-3)=1。
列表的排序得分b
是6。1的距离总和是(3-0)=3,2的距离总和是0,3的距离总和是(4-1)=3。
URL 列表看起来像(域,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'),
...
]
我正在开发一个原型,它工作得还不错,但不是最佳的,因为我可以找到一些更好地手动排序的变体。
有人想尝试一下吗?
这是我的代码 https://www.mycompiler.io/view/8XpFD9W,但这不是很好:):
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')
附言。我不只是在寻找随机函数,而且我知道有可以管理域负载的爬虫,但这是为了练习。